m******3
发帖数: 346 | |
a********5
发帖数: 1631 | 2 其实挺有意思的一个问题。
直觉上来说，只有同样的数字拼在一块，可以产生更大的数字：22会变成22本身，33会
变成23,333（如果存在）会变成33再变成23，所以可以从直觉上知道3是数列里数字的
上限。
下面给一个不太严格的证明，严格证明可以用类似的归纳法来做。
假设数列中出现4 则4必定是由连续4个相同的数字，如1111,2222,3333等产生。以N指
代这一数字，则前一项数列中必定出现NNNN。
假设NNNN开始于偶数位上，则其含义是：N个N，N个N。这与数列的定义不符，因为如果
前一项数列出现了N个N，N个N，则应该是产生连续2N个N，因此应该生成的数列为（2N)
N 而非NNNN。假设不成立。
假设NNNN开始于奇数位上，则完整的偶数个字符片段应该形如：PNNNNQ。其含义为：P
个N，N个N，N个Q。这也与数列的定义不符，因为这样的数列应该生成（P+N)NNQ 而非
PNNNNQ。因此假设不成立。
所以数列中不可能出现连续4个相同数字，因此不可能出现4.
当然，这个证明不严谨。正确的证明方法是去证明不存在任何大于等于4的数字。可以
用反证加归纳，证明假设存在这样的数字N>=4，需要开始数字无穷大以及无限步数才可
以构造出这样的N出现在数列的某一项中。 |
b**********5
发帖数: 7881 | 3 谢谢。。 我也是直觉， 但说不出所以然。。。
2N)
【在 a********5 的大作中提到】
: 其实挺有意思的一个问题。
: 直觉上来说，只有同样的数字拼在一块，可以产生更大的数字：22会变成22本身，33会
: 变成23,333（如果存在）会变成33再变成23，所以可以从直觉上知道3是数列里数字的
: 上限。
: 下面给一个不太严格的证明，严格证明可以用类似的归纳法来做。
: 假设数列中出现4 则4必定是由连续4个相同的数字，如1111,2222,3333等产生。以N指
: 代这一数字，则前一项数列中必定出现NNNN。
: 假设NNNN开始于偶数位上，则其含义是：N个N，N个N。这与数列的定义不符，因为如果
: 前一项数列出现了N个N，N个N，则应该是产生连续2N个N，因此应该生成的数列为（2N)
: N 而非NNNN。假设不成立。
|
y*****e
发帖数: 712 | 4 我昨天也在看这道题，找到了一个related theorem，就是说从第8个数开始，每一个都
是由92个base sequence组成的，第八个数是1113213211， 11132是92个base的一个，
13211也是一个，11132会evolve成311312， 13211会变成11131221， 然后后面这两个
也会变成92个base里的其他。总之这个数列所有的数都是由这些base不同的组合成的，
有循环和规律。既然92个base里没有4，那么sequence也不会出现123之外的数。
这是那个theorem
http://www.njohnston.ca/2010/10/a-derivation-of-conways-degree-
我个人感觉不会让写证明，所有这应该不是面试官期待的答案，应该还是intuitive的
说说就可以，比如base之间的关系。希望发面经的大牛能说说当时怎么答的。。 |
b********a
发帖数: 70 | 5 因为假设有4个连续一样的数 假设是1111那这种情况就违反了规则因为第二位和第四位
的数字是一样的 这四位应该一起读 结果应该是两位不是四位 |
b******i
发帖数: 914 | 6 second this
2N)
【在 a********5 的大作中提到】
: 其实挺有意思的一个问题。
: 直觉上来说，只有同样的数字拼在一块，可以产生更大的数字：22会变成22本身，33会
: 变成23,333（如果存在）会变成33再变成23，所以可以从直觉上知道3是数列里数字的
: 上限。
: 下面给一个不太严格的证明，严格证明可以用类似的归纳法来做。
: 假设数列中出现4 则4必定是由连续4个相同的数字，如1111,2222,3333等产生。以N指
: 代这一数字，则前一项数列中必定出现NNNN。
: 假设NNNN开始于偶数位上，则其含义是：N个N，N个N。这与数列的定义不符，因为如果
: 前一项数列出现了N个N，N个N，则应该是产生连续2N个N，因此应该生成的数列为（2N)
: N 而非NNNN。假设不成立。
|
