Algorithm 版 (精华区)

发信人: ssos (存在与虚无·戒酒戒网), 信区: Algorithm
标  题: [合集]大家讨论一下吧。
发信站: 哈工大紫丁香 (2001年09月18日21:08:40 星期二), 站内信件


────────────────────────────────────────
 oyster (沉默是金)                    于 2001年09月17日18:28:36 星期一 说道:

自己总是犯范眼高手低的毛病，编程很费劲的说，还是和大家讨论一下思路把。
非常希望参加竞赛的同学能指点
a:这道题好像比较简单，一个递推公式便解决问题了，
  S(n)=2*S(n-2)+S(n-1)+1;S(1)=1;S(2)=2。
b:这道题的难点好像就在于将普通的查询表达式变为逆波兰式，这个
  问题数据结构书上都有的。这样便可以通过简单的交集、并集操作来得到结果。
c:题目没有读懂,sigh,但是看示例结果好像又不难，似乎一个结构链表就可以解决
  问题，此结构含有一个索引值、一个指针链表和一个指向下一个结构的指针。
  索引用来放后n-1个字段的值，指针链表存放后后几个字段是索引值的行的第一个
  字段的值。结构链表按索引值的大小是有序的。每次都从结构链表头开始，将第一
  个字段的值插入到相应的结构中，如果没有相应的索引，则新建一个插入到结构链
  表中。
d:这道题最简单的思路就是利用回溯法搜索所有的解了，时间复杂性挺大，不过只有
  0和1两种情况，似乎可以接受。利用A*算法应该能够得到更好的解，不过参数不好
  定，特别是上界。
e:觉得这道题目好像没有什么难度，纯粹是考察思维严密性的。很复杂的说，说了也
  肯定不对，还是不说了，:-)。
f:这道题不会，:((。感觉应该是用动态规划法，可是实在不知道怎么建立递归关系，
  还望多多指教。

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年09月17日19:02:03 星期一 说道:

第一题的递推式子好像不对
第二提用不着这么作,可以用位图来做,很快的
第三题如果用链表做程序编写速度太慢了
第四题广度优先足够,用不着A*算法
第六题是典型的动态规划问题TSP问题
另外,思路好想,关键时把他们在有限的时间内编程程序并且通过测试

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年09月17日19:05:09 星期一 说道:

还是试一下,看能调试出来多少:)

────────────────────────────────────────
 deem (摩亚迪·沙丘男爵)              于 2001年09月17日19:43:10 星期一 说道:

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
非常赞成你的这一句话，个人感觉这就是acm/icpc最大的难点！

────────────────────────────────────────
 lizhenguo (夸父·追日)               于 2001年09月17日20:10:50 星期一 说道:

最后一题就是最小生成树。

────────────────────────────────────────
 oyster (沉默是金)                    于 2001年09月18日08:41:31 星期二 说道:

1能说一下第一个递推式子错在那里吗？此式子的意义是如果有n个环，先取出
前n-2个，再将第n个环取下，将前n-2个装上，最后取下n-1个环。
2能详细诉一下怎样用位图作第二题吗？不会的说。谢谢！
3第三题如果不用链表，似乎很难按顺序输出。有什么好方法，希望能告诉一下。
//首先要声明一点，我在这里讨论并不是想和参加竞赛的同学比什么，我见识过
参加acm的狠人，1、2百行的的程序一口气编下来，基本上不带出错的。
  我觉得对于我这样的普通的同学，并不需要花大量的时间将每个程序都编出来
进行验证。毕竟只是想用尽量少的时间来学习一些算法，而不是怎样编程实现，
（主要还是编程功底不扎实，总是要查书，编起来实在很慢）
何况编程关键还是思路，大家都是程序员，都明白只要能说清楚，就一定能编出
来的道理。

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年09月18日09:56:51 星期二 说道:

编程关键是实践,很多东西都能说清楚,但是未必能够编出来
对于算法的实现
需要很长时间的训练

────────────────────────────────────────
 oyster (沉默是金)                    于 2001年09月18日10:19:24 星期二 说道:

    等了半天还是没有得到希望的回答。我觉得解算法题还是思路重要，
我有了思路，可能暂时由于一些编程能力的原因编不出来，但是查些资料
问问牛人总会编出来的。
    版主说得很对，算法的实现式需要很长时间的训练的，可是当我们没有大
量的时间进行编程训练或者只是希望通过研究算法来训练自己的思维的话，讨论
思路——准确地说是算法解题步骤的描述才是最重要的。
   //可以回答我上篇中提出的问题吗？我到这里来不是想讨论算法思路和
算法实现的重要性的，我是想学习别人是怎样解决问题的，比如版主说的位
图法解第2道题。
谢谢。

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年09月18日10:34:02 星期二 说道:

位图是这样的用一位来表示一个数据源是否存在
这样每个关键字都对应一个位数组,通过位数组的与或来实现与或
要比单纯的实现容易的多

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年09月18日10:35:20 星期二 说道:

第三题我想用链表可能实现比较慢,题中也并没有要求按顺序输出

────────────────────────────────────────
 oyster (沉默是金)                    于 2001年09月18日10:46:36 星期二 说道:

多谢！
还有第一题的递推公式错在那里了？（版主说好像不对）

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年09月18日11:29:18 星期二 说道:

你能不能算几个数看看
我感觉上好像不对
我得递推式是两组,经过整理和你的不大一样

────────────────────────────────────────
 oyster (沉默是金)                    于 2001年09月18日12:12:59 星期二 说道:

我的从2到20的结果分别是:
2,5,10,21,42,85,170,341,682,1365,2730,5461,10922,21845
43690,87381,174762,349525,699050;
对吗？

────────────────────────────────────────
 jjyy (十二)                          于 2001年09月18日13:33:07 星期二 说道:

没有错，但我觉得你这样想好像不严密

────────────────────────────────────────
 lizhenguo (夸父·追日)               于 2001年09月18日18:24:21 星期二 说道:

                              ~~~~~~~~~~~装上的顺序你注意了吗？
                                          ~~~~~~~~~~~~只有这样才能快，准
                                     ~~~~~~~~~~~~~算法毕竟是要用的吧
                                  ~~~~我觉得是编程少的缘故
                                                              ~~~~~
                                                            hoho,未必哦

────────────────────────────────────────
 utah (尤他去吧·你快回来)            于 2001年09月18日20:02:56 星期二 说道:

oyster的说法有错误，不是将前n-2个装上，而是将第n-2个装上，这样那个公式就对了
另外，可能觉得不严密之处在于第n-2拿下来和第n-2拿上去的步数是否一样
我们可以这样想，第n-2拿下来的时候，反着做，
是不是也可以把第n-2拿上去。这样想很浅显，但不无道理

────────────────────────────────────────
 sino (一层秋雨一层凉)                于 2001年09月18日20:30:50 星期二 说道:

1。n=1。装上1和拆下1，都是一步
2。n=2. 空白套子装单2和单2拆成空白套子，都是3步
    满的2套子拆1..2和空白套子装1..2，都是2步
3。对于n>2, 空白套子装单n和单n拆成空白套子, 都等于装单n-1, 装（拆）n,拆单n-1。
   对于n>2, 满的n套子拆1..n,等于拆1..n-2, 拆n ,拆单n-1。
        空白套子装1..n，等于装单n-1,装n,装1..n-2。  相等。

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年09月18日20:41:07 星期二 说道:

你这么写看得人肯定faint

────────────────────────────────────────
 sino (一层秋雨一层凉)                于 2001年09月18日20:45:06 星期二 说道:

为什么？@_@

────────────────────────────────────────
 sino (一层秋雨一层凉)                于 2001年09月18日20:46:51 星期二 说道:

此人在工大吗？

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年09月18日20:50:06 星期二 说道:

绕口令:)

────────────────────────────────────────
 sino (一层秋雨一层凉)                于 2001年09月18日20:51:09 星期二 说道:

我先要faint了 ~~~~~~~~~
绕口令:)

────────────────────────────────────────