[今天我们思考18]马后炮的意义

[pongba]

应该有同学记得前些时候我发到讨论组上的一道题目：

1. 一个数组，其中只有一个数只出现一次，其余数皆出现偶数次。设计Time: O(n) Space: O(1)的算法得出那个只出现一次的数。

2. 如果只有两个数只出现一次呢？

SpitFire还说是道老题目了，不过再火星的题目总也有人不知道啦。当时silwile问我，我没想出来。虽然模糊的想到应该有某种手法把两两相同的元素even out掉，但并没有想到XOR操作。只想"要是一正一负"就好了。（现在想来，如果继续往下想，那么什么操作能够把同样的两个数运算得到0呢？也许有希望想到非加减乘除的其它运算上。而当时没想到合适的运算就放弃了这一思路，教训是一个大体的plan如果细节上还有缺口，不代表整个plan不对，也许应该细查缺口有没有补上的可能性）

但这道题目最关键的还不是这里，而是扩展版——如果有两个数只出现一次。

当时绝大多数人都能想到可以归约到第一个问题，即分裂成两个数组使得其中两个数各占一边。

但如何分割这个数组，没有人想到。也没有思路。后来我就把silwile的答案给贴出来了。

最近又想到这道题目，再次试图寻找其中可行的启发式思路，下面是各个一般性步骤（看起来有许多步，但实际上每一步都是很一般性的，跨问题的，而且自然lead到下一步），大家思考如果当时并不知道答案，在以下一般性的启发式思路之下有没有可能想到答案呢？

第一步——题中之题：现在的子问题是，有一堆数，里面有两个不一样的值a1, a2，我们不知道他们在什么位置，我们要用某种分割数组的手法，能保证将它们分到不同的堆。
第二步——用特例启发法思考第一步的题中之题：不妨建设a1=1，a2=2，我们该怎么分割才能确保它们被分在不同的堆呢？答案：用1.5之类的位于1和2之间的数来划分。
第三步——第二步每个人都能想到这样一个抽象的结论：我们是基于a1和a2的某种不同点进行划分的，比如a1< 1.5 <a2。而这个不同点肯定蕴含在题目中关于a1和a2的知识里面，譬如这里a1=1和a2=2这个知识我们就能得到它蕴含的不同点：它们一个小于，一个大于1.5。
第四步——将从特例中获得的启发运用到原问题，我们如何寻找原问题中a1和a2的不同点呢？刚才知道，这个不同点肯定蕴含在题目中关于a1和a2的知识中，而a1和a2的知识有什么？只有一条——a1 != a2。我们要用的知识肯定是从它推导出来的，即a1 != a2 => __。
第五步——一般来说，当要填这样一个空"p => __"的时候，不妨考虑四种方向：p => __；~p => __；__=>p；__=>~p。这里当考虑~p=>__这个填空。即如果a1和a2相等的话我们有什么结论呢？全等，每个位置上的值都相等，对不对？（这一步也许不是trivial的，因为从a1=a2推导到a1和a2的二进制位全等还是有一定的跳跃性的，但是如果考虑到我们已经知道XOR这个运算要被用到这个上下文背景的话也许可能性就大些了）。因此a1 != a2 => 至少有一位不等。后者就是我们所要的用来指导划分的"不同点"。

再一次，这个思路看起来很复杂，但实际上熟练的在大脑里运算也就是一分钟的事。每一步都是跨问题的，启发式的。虽然我认为silwile当时肯定是顺着a1 xor a2这个结论蕴含的性质解出来的（正推）。虽然这样来总结是有点马后炮，但所有知道答案后的总结都是马后炮的，如果能够马后炮出一般性的东西，就能得到更多，不是吗？

--
刘未鹏(pongba)|C++的罗浮宫
http://blog.csdn.net/pongba
TopLanguage
http://groups.google.com/group/pongba

[pongba]

2008/5/9 pongba <pon...@gmail.com>:

应该有同学记得前些时候我发到讨论组上的一道题目：

1. 一个数组，其中只有一个数只出现一次，其余数皆出现偶数次。设计Time: O(n) Space: O(1)的算法得出那个只出现一次的数。

2. 如果只有两个数只出现一次呢？

SpitFire还说是道老题目了，不过再火星的题目总也有人不知道啦。当时silwile问我，我没想出来。虽然模糊的想到应该有某种手法把两两相同的元素even out掉，但并没有想到XOR操作。只想"要是一正一负"就好了。（现在想来，如果继续往下想，那么什么操作能够把同样的两个数运算得到0呢？也许有希望想到非加减乘除的其它运算上。而当时没想到合适的运算就放弃了这一思路，教训是一个大体的plan如果细节上还有缺口，不代表整个plan不对，也许应该细查缺口有没有补上的可能性）

但这道题目最关键的还不是这里，而是扩展版——如果有两个数只出现一次。

当时绝大多数人都能想到可以归约到第一个问题，即分裂成两个数组使得其中两个数各占一边。

但如何分割这个数组，没有人想到。也没有思路。后来我就把silwile的答案给贴出来了。

最近又想到这道题目，再次试图寻找其中可行的启发式思路，下面是各个一般性步骤（看起来有许多步，但实际上每一步都是很一般性的，跨问题的，而且自然lead到下一步），大家思考如果当时并不知道答案，在以下一般性的启发式思路之下有没有可能想到答案呢？

第一步——题中之题：现在的子问题是，有一堆数，里面有两个不一样的值a1, a2，我们不知道他们在什么位置，我们要用某种分割数组的手法，能保证将它们分到不同的堆。
第二步——用特例启发法思考第一步的题中之题：不妨建设a1=1，a2=2，我们该怎么分割才能确保它们被分在不同的堆呢？答案：用1.5之类的位于1和2之间的数来划分。
第三步——第二步每个人都能想到这样一个抽象的结论：我们是基于a1和a2的某种不同点进行划分的，比如a1< 1.5 <a2。而这个不同点肯定蕴含在题目中关于a1和a2的知识里面，譬如这里a1=1和a2=2这个知识我们就能得到它蕴含的不同点：它们一个小于，一个大于1.5。
第四步——将从特例中获得的启发运用到原问题，我们如何寻找原问题中a1和a2的不同点呢？刚才知道，这个不同点肯定蕴含在题目中关于a1和a2的知识中，而a1和a2的知识有什么？只有一条——a1 != a2。我们要用的知识肯定是从它推导出来的，即a1 != a2 => __。
第五步——一般来说，当要填这样一个空"p => __"的时候，不妨考虑四种方向：p => __；~p => __；__=>p；__=>~p。这里当考虑~p=>__这个填空。即如果a1和a2相等的话我们有什么结论呢？全等，每个位置上的值都相等，对不对？（这一步也许不是trivial的，因为从a1=a2推导到a1和a2的二进制位全等还是有一定的跳跃性的，但是如果考虑到我们已经知道XOR这个运算要被用到这个上下文背景的话也许可能性就大些了）。因此a1 != a2 => 至少有一位不等。后者就是我们所要的用来指导划分的"不同点"。

再一次，这个思路看起来很复杂，但实际上熟练的在大脑里运算也就是一分钟的事。每一步都是跨问题的，启发式的。虽然我认为silwile当时肯定是顺着a1 xor a2这个结论蕴含的性质解出来的（正推）。

现在想来，silwile肯定是从a1 xor a2蕴含的性质正推出来的。在知道了答案之后，这个性质是如此的显然，显然得就像在鼻子底下一样。为什么当时就想不到呢？hayate？追寻一下你逝去的记忆～:P

[张鹏程]

现在是马后炮，也许以后就是告知式的想法 呢。

在08-5-9，pongba <pon...@gmail.com> 写道：

应该有同学记得前些时候我发到讨论组上的一道题目：

1. 一个数组，其中只有一个数只出现一次，其余数皆出现偶数次。设计Time: O(n) Space: O(1)的算法得出那个只出现一次的数。

2. 如果只有两个数只出现一次呢？

SpitFire还说是道老题目了，不过再火星的题目总也有人不知道啦。当时silwile问我，我没想出来。虽然模糊的想到应该有某种手法把两两相同的元素even out掉，但并没有想到XOR操作。只想"要是一正一负"就好了。（现在想来，如果继续往下想，那么什么操作能够把同样的两个数运算得到0呢？也许有希望想到非加减乘除的其它运算上。而当时没想到合适的运算就放弃了这一思路，教训是一个大体的plan如果细节上还有缺口，不代表整个plan不对，也许应该细查缺口有没有补上的可能性）

但这道题目最关键的还不是这里，而是扩展版----如果有两个数只出现一次。

当时绝大多数人都能想到可以归约到第一个问题，即分裂成两个数组使得其中两个数各占一边。

但如何分割这个数组，没有人想到。也没有思路。后来我就把silwile的答案给贴出来了。

最近又想到这道题目，再次试图寻找其中可行的启发式思路，下面是各个一般性步骤（看起来有许多步，但实际上每一步都是很一般性的，跨问题的，而且自然lead到下一步），大家思考如果当时并不知道答案，在以下一般性的启发式思路之下有没有可能想到答案呢？

第一步----题中之题：现在的子问题是，有一堆数，里面有两个不一样的值a1, a2，我们不知道他们在什么位置，我们要用某种分割数组的手法，能保证将它们分到不同的堆。
第二步----用特例启发法思考第一步的题中之题：不妨建设a1=1，a2=2，我们该怎么分割才能确保它们被分在不同的堆呢？答案：用1.5之类的位于1和2之间的数来划分。
第三步----第二步每个人都能想到这样一个抽象的结论：我们是基于a1和a2的某种不同点进行划分的，比如a1< 1.5 <a2。而这个不同点肯定蕴含在题目中关于a1和a2的知识里面，譬如这里a1=1和a2=2这个知识我们就能得到它蕴含的不同点：它们一个小于，一个大于1.5。
第四步----将从特例中获得的启发运用到原问题，我们如何寻找原问题中a1和a2的不同点呢？刚才知道，这个不同点肯定蕴含在题目中关于a1和a2的知识中，而a1和a2的知识有什么？只有一条----a1 != a2。我们要用的知识肯定是从它推导出来的，即a1 != a2 => __。
第五步----一般来说，当要填这样一个空"p => __"的时候，不妨考虑四种方向：p => __；~p => __；__=>p；__=>~p。这里当考虑~p=>__这个填空。即如果a1和a2相等的话我们有什么结论呢？全等，每个位置上的值都相等，对不对？（这一步也许不是trivial的，因为从a1=a2推导到a1和a2的二进制位全等还是有一定的跳跃性的，但是如果考虑到我们已经知道XOR这个运算要被用到这个上下文背景的话也许可能性就大些了）。因此a1 != a2 => 至少有一位不等。后者就是我们所要的用来指导划分的"不同点"。

[hayate]

:D 我也来分享一个马后炮，关于那个N个数的链表等概率取k个数的。

1.尝试特例k=1，自然地。

2.因为不知道N有多大，那么实际上这个算法应该是对于任意N都成立，继而可以得出子问题也是成立的----即进行到遍历到M(M<N)个元素时，就应该以1/M的概率取到1个元素。事实上，认识到这一点很重要，意味着结论不是最后一刻产生，而是随时更新的。可惜地，当时没有意识到这一点。

3.既然这样，马上就可以再尝试特例获取更多信息，N=1，显然我们需要100%的取得一个元素，这也是做的到的；N=2时，也是明显的；N=3时，我们已经以1/2的概率得到前两个中的一个，而第3个元素新加入的，要以1/3的概率取到第3个数，唯一的办法就是以1/3的概率取第3个数(听起来像废话)。那么还有2/3的概率是留给前两个数的结果的，至此结果已经明显了。

一个general的说法就是，我们已经从N个数中等概率的得到一个元素，这时新加入一个元素，我们需要从两个中选择一个，使得结果还是等概率的。

然后k>1也很容易想出来的

 

分析：从这个推理来说，逻辑上没有问题，但是为什么当时没有想出来的，我觉得原因可能有这么几点：

1.马后炮毕竟是马后炮，当我们回望来时路时，视野是清晰的，方向是明确的，但是从起点来看，也许充斥着很多无关的路径和不明确的方向，并且会怀有某种不安，这势必需要耗费精力，即使上逻辑上是必然，脑子未必清醒，容易否定一些本来是对的思路

2.时间。有时做不出一道题，是否真的做不出来？或者如何定义做不做的出来。也许睡一觉再来想，立马就有了思路，这种经历大家经常都会遇到。这或许和身体状态有关，也许思维的盲点和陷阱有关，比如这道题我就老是focus到如何得到一个任意的概率上去了，殊不知这完全就是不必操心的；另外等概率总是容易让人去想在N个元素中公平地选取，却不容易想到可以不平均的选取。换个时间想，或许可以丢掉上次的包袱，或许也可以想起新的未尝试的思路或者启发法。

3.思考方法确实还有待改进....比如有意识的进行抽象也是一种能力。

4.知识掌握的还不够，如果熟悉古典概率，熟悉各种抽签方法，那么这题就完全没有新意了。

2008/5/9 pongba <pon...@gmail.com>:

2008/5/9 pongba <pon...@gmail.com>:

应该有同学记得前些时候我发到讨论组上的一道题目：

1. 一个数组，其中只有一个数只出现一次，其余数皆出现偶数次。设计Time: O(n) Space: O(1)的算法得出那个只出现一次的数。

2. 如果只有两个数只出现一次呢？

SpitFire还说是道老题目了，不过再火星的题目总也有人不知道啦。当时silwile问我，我没想出来。虽然模糊的想到应该有某种手法把两两相同的元素even out掉，但并没有想到XOR操作。只想"要是一正一负"就好了。（现在想来，如果继续往下想，那么什么操作能够把同样的两个数运算得到0呢？也许有希望想到非加减乘除的其它运算上。而当时没想到合适的运算就放弃了这一思路，教训是一个大体的plan如果细节上还有缺口，不代表整个plan不对，也许应该细查缺口有没有补上的可能性）

但这道题目最关键的还不是这里，而是扩展版----如果有两个数只出现一次。

当时绝大多数人都能想到可以归约到第一个问题，即分裂成两个数组使得其中两个数各占一边。

但如何分割这个数组，没有人想到。也没有思路。后来我就把silwile的答案给贴出来了。

最近又想到这道题目，再次试图寻找其中可行的启发式思路，下面是各个一般性步骤（看起来有许多步，但实际上每一步都是很一般性的，跨问题的，而且自然lead到下一步），大家思考如果当时并不知道答案，在以下一般性的启发式思路之下有没有可能想到答案呢？

第一步----题中之题：现在的子问题是，有一堆数，里面有两个不一样的值a1, a2，我们不知道他们在什么位置，我们要用某种分割数组的手法，能保证将它们分到不同的堆。
第二步----用特例启发法思考第一步的题中之题：不妨建设a1=1，a2=2，我们该怎么分割才能确保它们被分在不同的堆呢？答案：用1.5之类的位于1和2之间的数来划分。
第三步----第二步每个人都能想到这样一个抽象的结论：我们是基于a1和a2的某种不同点进行划分的，比如a1< 1.5 <a2。而这个不同点肯定蕴含在题目中关于a1和a2的知识里面，譬如这里a1=1和a2=2这个知识我们就能得到它蕴含的不同点：它们一个小于，一个大于1.5。

第四步----将从特例中获得的启发运用到原问题，我们如何寻找原问题中a1和a2的不同点呢？刚才知道，这个不同点肯定蕴含在题目中关于a1和a2的知识中，而a1和a2的知识有什么？只有一条----a1 != a2。我们要用的知识肯定是从它推导出来的，即a1 != a2 => __。
第五步----一般来说，当要填这样一个空"p => __"的时候，不妨考虑四种方向：p => __；~p => __；__=>p；__=>~p。这里当考虑~p=>__这个填空。即如果a1和a2相等的话我们有什么结论呢？全等，每个位置上的值都相等，对不对？（这一步也许不是trivial的，因为从a1=a2推导到a1和a2的二进制位全等还是有一定的跳跃性的，但是如果考虑到我们已经知道XOR这个运算要被用到这个上下文背景的话也许可能性就大些了）。因此a1 != a2 => 至少有一位不等。后者就是我们所要的用来指导划分的"不同点"。

再一次，这个思路看起来很复杂，但实际上熟练的在大脑里运算也就是一分钟的事。每一步都是跨问题的，启发式的。虽然我认为silwile当时肯定是顺着a1 xor a2这个结论蕴含的性质解出来的（正推）。