6

有两行数字，第1行是从0开始的连续数字，现在请您填写第2行，以确保第2行的数字是第1行的对应数字出现在第2行的次数。

例如：

0 1 2 3 4 5 6 7 8 9

_ _ _ _ _ _ _ _ _ _

更具体地说，我们使用row1第 1 行和row2第 2 行，我们填写row2以确保它满足：row2[i] = count(row2, row1[i])。表示其中count(row2, row1[i])的频率计数。row1[i]row2

4

3 回答 3

3

在 1000 次运行中，此解决方案必须平均运行循环 3.608 次

import random

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

fast = list(range(10))

while f(fast) != fast:
    fast = []
    slow = []
    for i in range(10):
        r = random.randint(0,9)
        fast.append(r)
        slow.append(r)
    while True:
        fast = f(f(fast))
        slow = f(slow)
        if fast == slow:
            break

print(fast)

f(x) 进行猜测 x 并返回计数。我们本质上是在寻找一个满足 f(x) = x 的解决方案。

我们首先从 0-9 中选择 10 个随机整数并列一个列表。我们的目标是重复将此列表设置为等于自身，直到我们找到解决方案或陷入循环。为了检查循环，我们使用 Tortoise 和 Hair 算法，它们以 2 种速度移动。快的速度是慢速度的两倍。如果它们相等，我们就会进入一个循环并从一个新的随机场景开始。

我跑了几次，找到了 n>6 的一般解决方案（在这种情况下 n = 10）。它的形式为 [n-4,2,1,0...,0,1,0,0,0]

于 2013-07-24T03:55:43.020 回答
3

我们可以用数学方法解决这个问题。

让我们称我们的解决方案s和p的子集s，其中s[i] > 0，即表示数字的集合（任何零都是未表示的数字或索引）。

我们可以这么说n = sum of all frequencies = sum p

现在让我们调用withoutp'的子集，它们只是大于零的数字的频率。ps[0]

显然sum p' = sum p - s[0] = length p，这只是计算有多少数字s大于零。

记住这一点length p = length p' + 1。现在如果length p > 4，我们知道了，sum p' > 4剩下的m长度分区 ( p') 必须总和为m+1，其中m > 3。可以做到这一点的唯一方法是使用(m-1)1 和一个 2，例如，[1,1,1,2]在m=4（根据定义，在 中没有零p'）的情况下。这样的分区作为我们问题的解决方案是没有意义的，因此我们看到p，或者我们的解决方案中大于零的数字子集，必须少于 5 个元素。

现在我们可以解决特定情况：

每个解决方案都必须有s[0] > 0，因为零列中的零将使解决方案无效。

length p = 1s[0]只有在同时为零和大于零的情况下才有可能。

length p = 2暗示p' = [2]，所以有两个零和两个 2，s=[2,0,2,0]

length p = 3暗示p' = [1,2]。因为我们知道只有一个s[i]，即s[0] > 02 inp'必须要么引用它自己，在这种情况下我们有s=[2,1,2,0,0]; 或两个 1，因此s=[1,2,1,0]

length p = 4, p' = [2,1,1]. 在这种情况下，2 只能指两个 1，我们必须假设s[0] > 2，这也意味着sum p >= (3+2+1+1 = 7)。这是 user1125600 发现的最终/一般情况：s[1]=2, s[2]=1。最后一个 1 指代s[0]，因此它的索引等于s[0]。记住sum p - s[0] = length p，我们得到 ，s[0] = n - 4和解，对于 p = 4，n > 6：s=[n - 4,2,1...1,0,0,0]

于 2013-07-25T01:36:00.163 回答
1

解决方法：蛮力。10 的整数分区只有 42个。尝试所有这些，看看哪一个有效。

于 2013-07-24T03:32:51.980 回答