(算法问题)序列求解问题

石油工人干IT

让我们来假设这样一道题：
   
    有一条环型的山路，路边随机分布着一些苹果树，树上随机结着一些苹果。有个人，从某棵苹果树出发，遍历整个环型山路，一边走呢，一边摘苹果。他身上没任何食物，只能吃苹果充饥，你可以把他想象成鲁宾逊

条件如下：

1、该环型山路有n公里长。

2、为简化问题，我们假设鲁宾逊吃1个苹果可以走1公里路，假设他身上可以存无限数量的苹果，若是苹果吃完了，还没走到下一颗苹果树，就地倒毙。

3、要求编程求出：该环型山路中是否存在这样一颗苹果树，使鲁宾逊从该树出发，能够遍历完整个山路回到该树。

希望能考虑到山路的长度n和苹果树的数量m都非常大时，算法的效率问题。

任何讨论都是欢迎的。包括问题的程序化，数据结构，算法和优化。

Zelgadiss

友情顶贴
请勿跟风

起始有果子吗?
每棵树有多少个果子呢?

cjaizss

n<m的时候，一定是没有这样的路的；
n=m的时候，记得以前我们学校的算法版上有人证明过是是一定可以的。
n>m的时候，当然也是可以的（因为可以放低到m)

ArXoR

如果要构造出解的话
问题可以转化为求2m长的序列里任意长度为m的段的最小值
这个可以在O(m)做出来...

楼上的结论想了一下.
在上面的规约的思路基础上应该可以证明.

Zelgadiss

友情顶贴
请勿跟风

有没有人想过,起点那颗树上一个果子
然后最近的那颗树离他有2公里呢?

............

貌似偶然性很大.........

Edengundam

原帖由 Zelgadiss 于 2006-12-28 09:51 发表
友情顶贴
请勿跟风

有没有人想过,起点那颗树上一个果子
然后最近的那颗树离他有2公里呢?

............

貌似偶然性很大.........

这颗树显然不是起点. 我们找一颗满足的即可.

sevendays

能不能换个说法啊，一说吃苹果，烧绳子，走迷宫，我就索然无味了...来个实际的说话
比如果某个项目中要做到啥啥啥...
不是效率差就是空间不够使

原帖由 石油工人干IT 于 2006-12-27 16:36 发表
让我们来假设这样一道题：
   
    有一条环型的山路，路边随机分布着一些苹果树，树上随机结着一些苹果。有个人，从某棵苹果树出发，遍历整个环型山路，一边走呢，一边摘苹果。他身上没任何食物，只能吃苹果充 ...

boxpei

原帖由 cjaizss 于 2006-12-27 20:06 发表
n<m的时候，一定是没有这样的路的；
n=m的时候，记得以前我们学校的算法版上有人证明过是是一定可以的。
n>m的时候，当然也是可以的（因为可以放低到m)

折返跑怎么办？
比如
5公里路
2.5公里处有3个苹果，5公里处有2个苹果

boxpei

哦，没注意环形路

book11

考虑N=m的情况，逆时针方向环绕。
设共用k棵苹果树：T(1),T(2),.......T(k)
T(i)有N(i)个苹果，T(i)与T(i+1)间的距离L(i)
现在记X(i)=N(i)-L(i)
则X(1)+X(2)+.....+X(k)=0
问题转化为选择某个X(i)，
使得从X(i)开始，任意j个变量之和非负（1<j<k)。

X(i)中至少有一个数非负，不妨就记为X(i)
我们令X(i)＝X(i)＋X(i+1）
消去X(i+1),k--

重复上面的步骤，直到k==1

最后剩下的X(i)就是初始出发的地点。