什么诡异的题目都有

[pongba]

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

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

[莫华枫]

1:
挨个异或，结果就是那个数。
2:
考虑中...

在07-11-15，pongba <pon...@gmail.com> 写道：

--
反者道之动，弱者道之用
m...@seaskysh.com
longsh...@gmail.com
http://blog.csdn.net/longshanks/

[SpitFire]

比较老的题了。。

在07-11-15，莫华枫 <longsh...@gmail.com> 写道：

--
SpitFire

[pongba]

其实我关心的是，有几个人在不知道答案的情况下想到呢？
出题目的人是通过异或操作的性质推导出这个题目的，这是正向思考。但解题的人就不同了，是去思考充分条件，是逆向思考，搜索空间大得多了，跟猜谜差不多。。
更重要的问题是：像这类问题，有系统化的思考方法么？没有的话，所谓直觉，也实在不靠谱。因为我一直相信直觉也是训练出来的，也是有迹可循的，进一步说，直觉是可以系统化的。

[SpitFire]

唉，开始扯点哲学也不错，hoho

在07-11-15，pongba <pon...@gmail.com> 写道：

--
SpitFire

[莫华枫]

系统化的思考方法的确是训练出来的。也就是通过问题-解的不断输入，在头脑中形成快速神经回路。解题实际上就是模式匹配，长期训练获得的结果和方法存放在脑子里，多数在潜意识中。当外界的一个问题进来之后，便会激活相关的记忆。脑子会自动匹配与问题"同构"的记忆。记忆越强，匹配越快。所以说，技能是训练出来的。就像程序员只能训练出来，是"教"不出来的。
但是，一些更本质的理论和方法可以帮助我们更快地获得系统化分析能力。比如，物理学中计算物体运行轨迹，比如卫星或者天体，可以采用基本的力学微分方程，加上初始条件、边界条件、约束条件等等，然后解方程。另一种方法则是计算能量，利用物体运行总是寻求能量最小的轨迹这个特点，运用变分（泛函分析），可以直接获得解。后者更加系统，直接，而且具有普遍性，甚至可以被用于神经计算。
所有的事物都有其更本质的特性，掌握这类本质，则有助于更快地获得系统分析能力。我想kmp也不会是方案穷举，或者凭空猜出来的吧。:)

在07-11-15，pongba <pon...@gmail.com> 写道：

[hayate]

嗯
这些数学素养也是训练出来的。懂数学的人不过是工具箱比别人多一些好用的工具罢了。
当然，真正的数学家，开创者不在此列。

[dom]

先异或得到 a^b
再去 a^b^x=c （x不为全1，0的情况下）
a^b同或x＝d （x不为全1，0的情况下）
如果 c＝＝～d就算得出一个值

有其他更好的方法吗？

On Nov 15, 5:01 pm, "莫华枫" <longshank...@gmail.com> wrote:
> 1:
> 挨个异或，结果就是那个数。
> 2:
> 考虑中...
>
> 在07-11-15，pongba <pon...@gmail.com> 写道：
>
>
>
> > 1. 一个数组，其中只有一个数只出现一次，其余数皆出现偶数次。设计Time: O(n) Space: O(1)的算法得出那个只出现一次的数。
> > 2. 如果只有两个数只出现一次呢？
>
> > --
> > 刘未鹏(pongba)|C++的罗浮宫
> >http://blog.csdn.net/pongba
> > TopLanguage
> >http://groups.google.com/group/pongba
>
> --
> 反者道之动，弱者道之用
> m...@seaskysh.com

> longshank...@gmail.comhttp://blog.csdn.net/longshanks/

[Googol Lee]

我们写个程序来穷举这个算法吧。

比如随机生成一定长度的二进制数据。跑起一个test程序，对每个生成的二进制，然后给一个数组做输入，返回一个int，看是不是符合要求。如果不符合
要求就重新生成。

要是随机出个format c来咋办？

On Nov 16, 8:34 am, "莫华枫" <longshank...@gmail.com> wrote:
> 系统化的思考方法的确是训练出来的。也就是通过问题-解的不断输入，在头脑中形成快速神经回路。解题实际上就是模式匹配，长期训练获得的结果和方法存放在脑子里，多数在潜意识中。当外界的一个问题进来之后，便会激活相关的记忆。脑子会自动匹配与问题"同构"的记忆。记忆越强，匹配越快。所以说，技能是训练出来的。就像程序员只能训练出来，是"教"不出来的。
> 但是，一些更本质的理论和方法可以帮助我们更快地获得系统化分析能力。比如，物理学中计算物体运行轨迹，比如卫星或者天体，可以采用基本的力学微分方程，加上初始条件、边界条件、约束条件等等，然后解方程。另一种方法则是计算能量，利用物体运行总是寻求能量最小的轨迹这个特点，运用变分（泛函分析），可以直接获得解。后者更加系统，直接，而且具有普遍性，甚至可以被用于神经计算。
> 所有的事物都有其更本质的特性，掌握这类本质，则有助于更快地获得系统分析能力。我想kmp也不会是方案穷举，或者凭空猜出来的吧。:)
>
> 在07-11-15，pongba <pon...@gmail.com> 写道：
>
>
>
>
>
> > 其实我关心的是，有几个人在不知道答案的情况下想到呢？
> > 出题目的人是通过异或操作的性质推导出这个题目的，这是正向思考。但解题的人就不同了，是去思考充分条件，是逆向思考，搜索空间大得多了，跟猜谜差不多。。
>
> > 更重要的问题是：像这类问题，有系统化的思考方法么？没有的话，所谓直觉，也实在不靠谱。因为我一直相信直觉也是训练出来的，也是有迹可循的，进一步说，直觉是可以系统化的。
>

> > On Nov 15, 2007 5:17 PM, SpitFire <spitfi...@gmail.com> wrote:
>
> > > 比较老的题了。。
>
> > > 在07-11-15，莫华枫 <longshank...@gmail.com> 写道：

>
> > > > 1:
> > > > 挨个异或，结果就是那个数。
> > > > 2:
> > > > 考虑中...
>
> > > > 在07-11-15，pongba < pon...@gmail.com> 写道：
>
> > > > > 1. 一个数组，其中只有一个数只出现一次，其余数皆出现偶数次。设计Time: O(n) Space:
> > > > > O(1)的算法得出那个只出现一次的数。
> > > > > 2. 如果只有两个数只出现一次呢？
>
> > > > > --
> > > > > 刘未鹏(pongba)|C++的罗浮宫
> > > > >http://blog.csdn.net/pongba
> > > > > TopLanguage
> > > > >http://groups.google.com/group/pongba
>
> > > > --
> > > > 反者道之动，弱者道之用
> > > > m...@seaskysh.com

> > > > longshank...@gmail.com

> > > >http://blog.csdn.net/longshanks/
>
> > > --
> > > SpitFire
>
> > --
> > 刘未鹏(pongba)|C++的罗浮宫
> >http://blog.csdn.net/pongba
> > TopLanguage
> >http://groups.google.com/group/pongba
>
> --
> 反者道之动，弱者道之用
> m...@seaskysh.com

> longshank...@gmail.comhttp://blog.csdn.net/longshanks/

[pongba]

On Nov 16, 2007 11:12 AM, dom <liji...@gmail.com> wrote:

先异或得到  a^b
再去 a^b^x=c  （x不为全1，0的情况下）
       a^b同或x＝d  （x不为全1，0的情况下）
如果 c＝＝～d就算得出一个值

有其他更好的方法吗？

有。

2个元素的情况也要求时间复杂度O(n)。

[hayate]

公布答案吧
2个数的想不出来

[codediscuss.com]

x^y=a
x+y=b

能否解出x和y？

[hayate]

如何求出a+b

On Nov 19, 2007 4:55 PM, codediscuss.com <flyi...@gmail.com> wrote:
> x^y=a
> x+y=b
>
> 能否解出x和y？
>
> >
>

[pongba]

好吧，既然这么久无人回帖。
公布解答：

前面根据第一道问题，已经知道在第二道问题中我们可以通过异或所有的元素得到a^b。
再因为a和b不等，那么a^b必然不为0。
那么a^b这个数上面必然能够找到一个二进制位是1，在这个二进制位上，a和b不等。
根据这个二进制位，将各元素中在这位上为1的分派到左边，为0的分派到右边，形成两个子数组。可以证明，1）这两个数组分别包含a和b。2）每个数组中除了a或b之外的所有元素都是成对出现的。

自此，问题归约为第一个问题。

[莫华枫]

奇妙的数，奇妙的自然。
呵呵，奇妙的和谐

--

[钙瓷]

看算法导论以前要搞定 离散数学 和 概率 吗？

[hayate]

妙！别的不说了

On Nov 26, 2007 8:15 PM, pongba <pon...@gmail.com> wrote:

[pongba]

On Nov 26, 2007 10:08 PM, hayate <haya...@gmail.com> wrote:

妙！别的不说了

而我最想知道的是，这个问题有没有系统化的思考方法。因为告诉我这个方法的老兄觉得这个解就是"直觉"的。直觉我不相信，我相信直觉后面一定隐藏着系统化的方法。只不过那些被锻炼出来的人，不需要在表层意识运用系统化方法，底层意识就直接代劳了。（不过似乎"类比"过程是没法系统化的，我也很怀疑真正的直觉其实就是源于类比。而这个类比的能力则是可以训练出来的（训练不也是一种系统化方法么？:)）

所以，我在看《How to Solve It: Modern Heuristics》。

[hayate]

嗯 我知道你在看这个 fanfou上看到了 这个问题我也不知道
但是对于肯定有答案的问题 至少还可以大胆尝试 要是碰上有没有答案都不知道的问题 事情就棘手了

这让我想起了数论。数论可以算是最没有系统化方法的一门数学分支，数论的发展几乎都存在着各种各样的灵感和创造。往往是在别的分支发现了某个方程，既而发现把它应用在数论上可以得到很好的结果。

根据歌德尔不完备性原理，要证明公理体系以外的结论，光靠逻辑和推理是不能完成的，总有某处依靠所谓的灵感——在这一点上你可能怎么找不出想到它的理由。所以我觉得所谓系统化的方法不一定导致解答的产生，但是或许能增大发现解答的概率：大量的知识积累至少让你可以站得更高，也许离解答很近的时候你就能先看见；一个好用的脑子可以作为数据库帮助你管理这些知识，搜索起来又快又准。

[Googol Lee]

再发散一下，如果有三个不同的数呢？

如果有n个不同的数呢？

ps 记得以前有个关于数学家的笑话。说是有个大牛数学家，带博士的毕业论文就是证明某个定理在特定维度下的正确性。第一个博士生证明1维情况，第二个证明2维情况，等等。

之后有个博士生，一高兴把n维普遍情况给证明了。结果引得这位大牛大怒，因为他把后面所有人的博士课题都证完了……

在 07-11-26，pongba<pon...@gmail.com> 写道：

--
新的理论从少数人的主张到一统天下，并不是因为这个理论说服了别人抛弃旧观点，而是因为一代人的逝去。

My blog: http://googollee.blog.163.com

[hayate]

应该可以分两次分别求出a和b^c 以及b和a^c

[R.C Wu]

最近在看机器学习……看着看着就乱了……人也是这样学习的么？真的所有学习过程都能抽象出代码描述？

[王宁]

看机器学习还是少发散些比较好。遗传算法与生物进化如天壤之别，神经网络和人脑构造远不是一回事。相似，但是截然不同的两个领域。

[pongba]

On Nov 27, 2007 11:17 AM, 王宁 <nwan...@gmail.com> wrote:

看机器学习还是少发散些比较好。遗传算法与生物进化如天壤之别，神经网络和人脑构造远不是一回事。相似，但是截然不同的两个领域。

果然如此么？能否解释一下遗传算法跟生物进化的本质区别？神经网络跟人脑构造的本质区别呢？

[莫华枫]

人工神经网络和生物神经网络之间的差异主要在于形式和规模，以及复杂度上。他们的实现手法不同，但原理一致。人工神经网络正在努力接近生物神经网络的特性。
举个例子：神经胶质细胞在十年前被认为不参与神经活动，只是起到支撑和营养供应的作用。但最近的研究表明，神经胶质细胞非但参加神经活动，而且起到了重要的长时程调控作用。当研究人员将胶质细胞引入人工神经网络模型后，系统的性能大幅提高，更加接近生物神经系统的特征。

On Nov 27, 2007 11:17 AM, 王宁 <nwan...@gmail.com> wrote:

[pongba]

On Nov 27, 2007 12:58 PM, 莫华枫 <longsh...@gmail.com> wrote:

人工神经网络和生物神经网络之间的差异主要在于形式和规模，以及复杂度上。他们的实现手法不同，但原理一致。人工神经网络正在努力接近生物神经网络的特性。
举个例子：神经胶质细胞在十年前被认为不参与神经活动，只是起到支撑和营养供应的作用。但最近的研究表明，神经胶质细胞非但参加神经活动，而且起到了重要的长时程调控作用。当研究人员将胶质细胞引入人工神经网络模型后，系统的性能大幅提高，更加接近生物神经系统的特征。

 

莫兄连这个也研究啊～PFPF！推荐一些资料啊..:)

[莫华枫]

呵呵，大学里的的爱好了。好长时间不关注了。
这个故事是从《新发现》杂志上学来的。现在也就看个杂志了解一下，当故事看罗。:)

[李一楠]

 

如果 a^b^c == 0 就不行了

[hayate]

Re! 3个就不能用这个办法了 我开始想错了

[Tauren Jerin]

(关于4、6楼：）联想到【涌现】。。。。

[kusk]

想了好久没有想出来（第2问），发邮件到公司的列表向同事们询问，得出了如下答案：

（设未知数为x0, x1，异或符号为^）

1. 异或全体数，得到结果x0 ^ x1. Time: O(n)
2. 由于x0 != x1，故x0, x1至少有一位不相同，亦即至少可以从x0 ^ x1中找出某一位为"1"，记为该位第k位，且不妨设x0第k
位为"0"，x1第k位为"1". Time: O(1)
3. 异或全体第k位为"1"（或"0"）的数，结果即为x1（或x0）. Time: O(n)
4. 再将其与第1步结果异或，即得到另一个数. Time: O(1)

[kusk]

Oops...看漏眼，原来已经有人帖出答案了~ : P

再帖一个关于3个数的讨论吧。直接从邮件中copy出来了，没翻译......供大家探讨。

Let x1, x2 and x3 are the numbers of answer. First, do XOR on all
numbers, say it A: A = x1 ^ x2 ^ x3.

Do at most k times' scan on n numbers(k is number of bits of these
numbers, constant), for the ith time:

1) If ith bit of A is 0:
Obvious {x1, x2, x3} = {0, 0, 0} or {1, 1, 0}.
Do XOR on all numbers except ones with its ith bit 0, assuming the
result is Ri. If Ri == A, it means this "bit row" of x1, x2 and x3 is
case {0, 0, 0}, and we need to find next row. OTHERWISE, if Ri does
not equal to the XOR result, it must be {1, 1, 0} case and Ri = x1 xor
x2 (suppose they are the '1' ones). Here we could work out three
numbers easily, in the same time and space complexity.

2) Similar way when ith bit of A == 1.


Because there is at least one time's {1, 1, 0} (or {1, 0, 0}), so the
"OTHERWISE" case in 1 (or 2 when x == 1) at least occurs once and we
must be able to get the answer. Because k is a constant, the time
complexity is O(n).

> > TopLanguagehttp://groups.google.com/group/pongba- Hide quoted text -
>
> - Show quoted text -

[lbaby]

使用O(n)的排序也可以吧？

[wave]

离散数学应该是要的。
概率当然很重要，但似乎，和算法导论这本书关系不那么密切。
各位觉得呢？

[hayate]

在算法导论里至少 quicksort 证明平均情况下的时间复杂度需要初等的概率知识
TAOCP第二卷 半数值算法也有很多随机数的内容