|
| win_hate 回复于：2004-09-20 18:55:42
|
贴图可把我搞晕了。
|
| yangtou 回复于：2004-09-20 19:28:07
|
不需要考虑细节情况，就可以判断可能性
x=pn/(a-b) > m/b
只要改变p的值就可以找到合适的x，x>m/b所以只要ab不等就必定相遇
另外如果m较小比如0,由x=pn/(a-b)(不考虑m/b)
则x只决定于a-b(只要改变p就可以得到x的合适的最小值，而p是决定于a-b的)
T=(au+bu+av+w)x，在(a-b)一定的情况下，ab取值越小T越小
|
| win_hate 回复于：2004-09-20 20:31:45
|
yangtou 说得对。
我上面的推理中，有一处条件没有用尽，显然：
a = (xf - m) mod n
b = (xg-m ) mod n
a - b = x (f-g) mod n
从而可知道当 f - g != 0 时， (f-g, n) | (a - b) 总是成立的。所以只要 f,g 不等，即可检测出重合点。此外， yangtou 的推理也比我的简单，我应该在发贴前仔细看看各位的帖子的。 :em16:
以上是按我的记号，以下按 yangtou 的：
T=(au+bu+av+w)x 是什么东西？
|
| yangtou 回复于：2004-09-20 20:44:02
|
T是FH老大帖子里面的
|
| 思一克 回复于：2004-09-21 09:07:26
|
TO：flw as well as FH.
可以不碰数据。用指针中的无用区域做标记。
这是可以运行的和完成任务的。
但不符合数据结构，还用了Ｃ技巧。总之不是一个“好”程序。
|
| FH 回复于：2004-09-21 10:08:15
|
楼上老兄，我觉得从理论上就不存在什么“指针中的无用区域”，涉及到具体实现则有可能存在，但会影响原应用。
我觉得我们所探讨的方法是在应用之外以旁观者的角度去考察，应当不干涉或影响原有应用。
|
| flw 回复于：2004-09-21 20:21:20
|
[quote:93d23a2087="思一克"]TO：flw as well as FH.
可以不碰数据。用指针中的无用区域[color=red:93d23a2087]做标记[/color:93d23a2087][/quote:93d23a2087]
“做标记”本身就是对原始数据的一种修改。
如果你修改的是别人的数据，我不管；
如果你修改的是我的数据，
那我就告诉你：不许动！[color=red:93d23a2087]在我这里，每一个字节、每一个比特，都不允许你为了节省一个指针变量而给我乱动！[/color:93d23a2087]
|
| 思一克 回复于：2004-09-22 08:48:26
|
to flw:
这里是在探讨计算和C的方法和技巧。
问题就是那个问题，目的是做一个函数达到所有要求。
我是在说，用一个指针完全可以达到问题要求。当函数返回时，数据，链表当然都完好无损，保持原来不动。
我没有说我说的是一个好方法，而且说你给出的方法好。
即使是不好的方法，只要是可行的，我们就可以讨论它。本论坛不就是讨论C程序的各种可能的方法吗？
对吧
|
| FH 回复于：2004-09-22 08:58:49
|
to 思一克：
给你个结构链表，能给我们说说一个指针是怎么做的么？
[code:1:71d9ff85f8]struct {
void *next;
int number;
}[/code:1:71d9ff85f8]
|
| 思一克 回复于：2004-09-22 09:03:51
|
在linux i386下，指针里面就相当与一个整数，你看成是unsigned整数，而且它没有用完所有的位。
如果在考虑指针对齐，可以空出来的位就更多了。
原来一个DOS下的著名软件（好象叫sidekick吧）就充分利用了我说的技巧--利用指针的空闲位。
当然，利用后要恢复，不能破坏连表的任何内容。
|
| FH 回复于：2004-09-22 09:22:57
|
算法应当不涉及具体的系统，因此，不能说指针中有空余的位。
至于对齐，谁又能保证对齐是以字为单位呢？如果是字节对齐呢？
|
| 思一克 回复于：2004-09-22 09:31:23
|
to: FH, 你说的对。但这是C/C++论坛，不是专门研究算法的，所以我才会说出。如果在算法论坛上，我不会说。
还有，我是从实用角度来说的。如果为研究算法，全当这方法无效。
如果研究C技巧，可以研究。
|
| FH 回复于：2004-09-22 09:58:41
|
实际上，一个指针是可以解决问题的，自己管理一个堆栈就是了，可是复杂度要比用两个指针高得多，得不偿失。
|
| aero 回复于：2004-09-22 09:58:47
|
用的哪个指针中的空于位呢？这个如果是链表中的指针，那么这个“位”的所有权不还是链表的所有者吗？你怎么知道他没有利用这个“位”呢？而如果是另外用来移动的指针，那么……想不出怎么用这个位。
|
| 思一克 回复于：2004-09-22 10:35:06
|
如何发code帖子使格式不乱？ 我忘了
|
| aero 回复于：2004-09-22 11:24:48
|
用
“[co*de]”和“[/co*de]”把code括起来。
|
| yutian 回复于：2004-09-22 15:56:31
|
这个问题越讨论越明朗了
|
| star55 回复于：2004-09-23 19:22:26
|
用拓扑排序就行了
即去枝叶方法。一般的数据结构都会有介绍，看看就明白了，在这边我也将不清楚，还是书比较容易说明问题，呵呵
|
| mfmain 回复于：2004-09-23 20:00:02
|
大家把问题复杂化了，一般说来应该步长分别为1和2是最优算法，问题可以简化为时针和分针的相遇问题，假设时针和分针每步都走一格的整数倍，显然如果步长分别为1和2，则能保证在一圈之内肯定相遇，而其他情况除非瞎猫正好蹦到死耗子，否则...
|
| mfmain 回复于：2004-09-24 14:38:12
|
sorry, 刚才分析的不对，假设步长为a,b，进入圈之前长度为m，圈长n，实际上，不论步长为多少（只要不相同），圈内相遇的步数都不会超过n步，我们重新分析效率问题：
双方都进入圈需要：m/min{a,b}步
最差情况下圈内相遇的步数：n/最大公约数{a,b,n}
事实上，因为n是随机的，因此圈内相遇的步数也是随机的，不可控制，但上限是n步，所以应该尽量减小双方进入圈需要的步数，所以a,b越大越好，但又产生了另外一个问题，就是步长越长，走一步所花的时间就越长，所以是两难！
|
| YeLLoW 回复于：2004-09-24 15:16:13
|
学习中，非常感谢
|
| jiangchun_xn 回复于：2004-09-24 15:32:18
|
普通算法:时间复杂度O(n^2)
变步长算法时间复杂度接近O(n)
的确算法非常漂亮,
但是无论哪种数据结构本身就应该满足这种数据结构的逻辑意义,因此,对于出现中间环的链表本身就是发生了错误,说明链表的操作中发生了错误.(单向链表不应该提供尾指针随意指向的方法)
如果在实际中会发生这种情况,这就说明用单向链表这种数据结构就是不合适的.这种结构应该是多入单出,可以证明这样的环只会存在一个.(可以用数学归纳法),这样维护这个结构可以在链表之外维护一个bool变量circled,并且提供一个方法,就是设置尾指针制向,同时修改circled,这样,查找是否有环的时间复杂度为o(1).
其实我并不是说这个算法不好，相反,这个算法非常精妙,但是,我个人认为数据结构更重要的是如何选择合适的数据结构和严格的应用数据结构.
|
| aero 回复于：2004-09-24 15:42:50
|
你的意思是要用另一个变量来对应链表尾指针的NULL与否？当circled是false的时候，要记得去把尾指针置NULL，然后把circled置true？
如果这个程序员能记得去置circled为true，那他自然就会记得将尾指针置成NULL了。而他记得将尾指着置成NULL，却未必能记得将circled置成false。
觉得加的这个变量是蛇足，没有任何意义！链表自然是不应该出错的。但是一旦他里面有了环，怎么能保证和链表一同维护的circled是可信的呢？
|
| jiangchun_xn 回复于：2004-09-24 15:51:10
|
[quote:d30d38340f="aero"]你的意思是要用另一个变量来对应链表尾指针的NULL与否？当circled是false的时候，要记得去把尾指针置NULL，然后把circled置true？
如果这个程序员能记得去置circled为true，那他自然就会记得将尾指针置成NULL了。..........[/quote:d30d38340f]
的确circled有点多余( :cry: )
我的意思是链表不应该出现环(除了头尾相连的为了方便的链表),链表提供的所有方法均不应该产生环.产生环就说明发生了 意外 的错误.
|
