题解：P11042 [蓝桥杯 2024 省 Java B] 类斐波那契循环数

· · 题解

P11042 类斐波那契循环数题解

题目大意

对于一个有 n 位的十进制数 N = d_1d_2d_3\dots d_n，可以生成一个类斐波那契数列 S。

数列 S 的前 n 个数为 \{S_1=d_1,S_2=d_2,S_3=d_3,\dots,S_n=d_n\}，数列 S 的第 k(k>n) 个数为 \sum^{k−1}_{i=k−n} S_i。

如果这个数 N 会出现在对应的类斐波那契数列 S 中，那么 N 就是一个类斐波那契循环数。 求小于 10^7 的最大的类斐波那契循环数是多少。

题目思路

直接暴力搜索 n，每一次用一个函数 pd(i) 来判断 n 是否为类斐波那契循环数。

接下来详细说说 pd(i) 的写法。

首先定义数组 a，a_i=d_i。数组 b 的前 n 个数为对应下标的 a_i。也就是说，b_i=a_i (i \le n)。

对于后面的 b_i，b_i=\sum^{i-1}_{j=i-1-n}b_j。如果 b_i=n，那么 n 就是类斐波那契循环数。

判断代码：

def pd(x):
    s=str(x)
    n=len(s)
    a=[]
    for i in range(n):
        a.append(int(s[i]))
    b=a
    while 1==1:
        t=0
        for i in range(len(b)-n,len(b)):
            t+=b[i]
        if t>10000000 :
            return 0
        if t==x:
            return 1
        b.append(t)

正确代码

def pd(x):
    s=str(x)
    n=len(s)
    a=[]
    for i in range(n):
        a.append(int(s[i]))
    b=a
    while 1==1:
        t=0
        for i in range(len(b)-n,len(b)):
            t+=b[i]
        if t>10000000 :
            return 0
        if t==x:
            return 1
        b.append(t)

for i in range(10000000, 0, -1):
    if pd(i) == 1:
        print(i)
        break

结果输出 7913837，那么答案就是 7913837。

AC 代码

print(7913837)