在列表中查找模式的周期

Question

我对编码还比较陌生，但我看到了一个很棒的 episode of Numberphile，他们使用斐波那契数列模数的特定重复模式来为结果数字分配音调。多么棒的小实验来检验我的知识！

所以我能够创建一个简单的循环来创建斐波那契数列的列表和另一个函数来计算生成的数列除以 n 后的余数。但是在该模数列表中找到模式的周期被证明是困难的。

这是我目前的情况：

#Fibonacci.py
#Basic terms
fiblist = list()
inp = "> "
n=None

#Calculates the FIbonacci sequence
def fib(n):
    a,b = 0,1
    while True:
        try:
            print "How many terms? "
            n = int(raw_input(inp))
            if n <= 0:
                print "Please enter a positive integer."
                continue
            else:
                for i in range(0,n):
                    a,b = b, a + b
                    fiblist.append(a)
                break
        except ValueError:
            print "Please enter a positive integer, not a letter or symbol"
            continue    
    return fiblist

#Calculates the modulo of each integer in fiblist
def modulo(n):  
    print """
Do you want to find the modulo?
1. Yes
2. No"""
    choice = raw_input(inp)
    if choice =="1":
        modlist = list()
        print "What modulo do you want to use?"
        modx = int(raw_input(inp))
        modlist = [x % modx for x in fiblist]
        print modlist
        print "The period of the pattern is ", principal_period(modlist)
        print "Goodbye!"
    else: 
        print "Goodbye!"

#Calculates the period of the modulo pattern of the Fibonacci sequence
def principal_period(modlist):
    a = str(modlist)
    i = (a+a).find(a, 1, -1)
    return None if i == -1 else n[:i]

print fib(n)
modulo(n)

让我失望的部分是

def principal_period(modlist):
    a = str(modlist)
    i = (a+a).find(a, 1, -1)
    return None if i == -1 else n[:i]

这总是 returns "None" 我从线程中得到了这个关于答案的信息。老实说，我不太理解这个答案，它没有给我想要的结果。

对于计算给定列表中重复模式的周期，您有什么建议吗？

Answer 1

它失败了，因为 modlist 是一个整数列表，而不是字符串。像这样更改 principal_period 中的第二行和第四行：

def principal_period(modlist):
    a = ''.join(str(m) for m in modlist)
    i = (a+a).find(a, 1, -1)
    return None if i == -1 else a[:i]

而不是 str(modlist) 你需要将数字连接成一个长字符串，你在最后一行有错字，n[:i] 而不是 a[:i].

运行该程序现在显示：

How many terms? 
> 9
[1, 1, 2, 3, 5, 8, 13, 21, 34]

Do you want to find the modulo?
1. Yes
2. No
> 1
What modulo do you want to use?
> 2
[1, 1, 0, 1, 1, 0, 1, 1, 0]
The period of the pattern is  110
Goodbye!

此输出的有趣之处在于，斐波那契数列遵循奇数、奇数、偶数序列。试用 99 个术语！

Answer 2

这里有一个简单的算法来计算离散函数的周期：

def findperiod(f, minlength=1, repetitions=2):
    """Find the period of a function f.

    Idea: assume length i = 1. Check that second copy is same as first (j
    iteration). If not, assume length 2. And so on. Once second copy matches
    first (no j breaks), return assumed length.

    The optional repetitions argument can be increased to check for more
    repetitions than the default 2 (two copies of the same sequence at the start
    of the list).

    Returns None if not enough repetitions are found in first billionish values.
    """
    for i in (range(minlength, 2**30)):
        for rep in range(1, repetitions):
            for j in range(i):
                if f(j) != f(i*rep+j): break
            else: return i

如果您的函数计算成本很高，那么记忆化是个好主意。我没有在这里这样做，因为如果没有必要，它会占用大量内存。

在列表中查找模式的周期

Finding the Period of a Pattern in a List

python

fibonacci

period

intervals