2

这是一个派生问题，你可以参考原始问题，我的问题是：给定10个随机整数（从0到9，允许重复）和一个变换函数f，f这是（在python 3.3代码中）：

def f(a):
    l = []
    for i in range(10):
        l.append(a.count(i))
return l

假设a是十个随机整数，执行f并将结果赋值给a，重复这个过程，几次之后，你就会进入一个循环。也就是说：a,a1=f(a),a2=f(a1)...，这个序列中有一个循环。

测试代码如下（来自@user1125600的代码）：

import random
# [tortoise and hare algorithm][2] to detect cycle
a = []
for i in range(10):
    a.append(random.randint(0,9))
print('random:', a)
fast = a
slow = a
i = 0
while True:
    fast = f(f(fast))
    slow = f(slow)
    print('slow:', slow, 'fast:', fast)
    i +=1
    # in case of running into an infinite loop, we are limited to run no more than 10 times
    if(i > 10):
        print('more than 10 times, quit')
        break
    if fast == slow:
        print('you are running in a cycle:', fast, 'loop times:', i)
        break

如何证明为什么存在一个循环呢？另一个有趣的事情是：看看测试结果，你会发现fast和slow只会在三个点上相遇：[7, 1, 0, 1, 0, 0, 1, 0, 0, 0]和[6, 3, 0, 0, 0, 0, 0, 1, 0, 0][6, 2, 1, 0, 0, 0, 1, 0, 0, 0]

4

1 回答 1

4

必须有一个循环，因为f它是一个函数（它总是为给定的输入产生相同的输出），并且因为函数的范围（可能的输出集）是有限的。由于范围是有限的，如果您反复将范围映射到自身，您最终必须获得一些您已经看到的值。

于 2013-07-26T03:01:11.307 回答