约定第一个报偶数的颜色难道不是共同约定?还得通过更复杂方法解码!

这道问题就是要囚犯通过共同约定(比较术语一些就是协议,PROTOCAL)来自救.

用山东话,湖南话,或者是通过拖长声音都是共同约定.只要有效,都是好算法.甚至于拖长声比间接回答更不着痕迹.

但是归结到数学模型上,他们都是一族的,有一个共同模型!T=F.其根本高明的地方在于通过一次有效通信传递两个信息,让两个信息接受方都满意.

具体到实用上,比如设计一个分布式算法,计算节点在网络的不同站点,算法的意义就明显了.

这种算法通过环状结构就能完成,计算复杂度最低O(N),节点计算量最小O(1).

奇偶算法必须通过N次星型通讯来广播单个节点计算结果O(N),同时还要进行一次环状(挨个回答颜色)和N(N-1)次点对点通讯(要POLL每个下级节点取得颜色状态).最后解码计算量也是O(N).

如果给这种情况让你选择,我想你也会明白.

即使是单个计算节点,两种算法都能达到空间复杂度O(1),但是前者时间复杂度O(N),后者O(N^2).

很多人不服气的地方就在于我利用一次机会传达了比他能想象的多的信息,使得他们看起来深的不的了的事情突然没了技术含量.

我要说的就是,只有想不到,没有做不到.况且,这只是一道高中生的题.

所有跟帖： 

• 只要你认为有protocal就有解就行。没人不服气，只要不说“正解”就好了。 -蓝莓馅饼- ♂ (77 bytes) () 12/13/2011 postreply 10:21:09

• 不说正解能把你吸引来看? -a7a8- ♀ (0 bytes) () 12/13/2011 postreply 10:33:20