##斐波那契数列的应用 — 题目斐波那契
题目：
如果数组 A = (a0, a1, · · · , an−1) 满足以下条件，就说它是一个斐波那契数组：
1. n ≥ 2；
2. a0= a1；
3. 对于所有的 i(i ≥ 2)，都满足 ai= ai−1+ ai−2。
现在，给出一个数组 A ，你可以执行任意次修改，每次修改将数组中的某个位置的元素修改为一个大于 0 的整数。请问最少修改几个元素之后，数组 A 会变成一个斐波那契数组。
输入格式
输入的第一行包含一个整数 n ，表示数组 A 中的元素个数。
第二行包含 n 个整数 a0, a1, · · · , an−1，相邻两个整数之间用一个空格分隔。
输出格式
输出一行包含一个整数表示最少需要修改数组 A 中的几个元素之后，数组 A 可以变为一个斐波那契数组。
样例输入
复制
51 2 2 4 8
样例输出
复制
3
提示
将原数组修改为 (1, 1, 2, 3, 5)，最少修改三个元素变成了一个斐波那契数组。
对于所有评测用例，2 ≤ n ≤ 105，1 ≤ ai≤ 106。
解题思路:我们枚举出前30个数的时候，发现第31个数已经超出了10的6次方，那么这后面的数全部都要修改，所以我们就不管30个以后的数了，我们的关注点就放在这30个。 然后我们发现，以下的式子都符合斐波那契数列的定义：
互相为倍数关系 1：1 1 2 3 5
2：2 2 4 6 10 3：3 3 6 9 15 则可以设计字典录入每层中有多少数，进行动态解题 循环每到一个数则对数取余看是否满足倍数关系，在对数取整存入 字典，最后利用数组长度减去倍数层最多的数，可得到需要修改的数。
注意事项: get函数的使用 — 用在字典处
dict.get(key, default=None)
解释：
key：字典中要查找的键
default：键不存在时要返回的默认值，若不提供，则返回None
import osimport sysn = int(input())# 接收数组长度a = list(map(int, input().split()))# 输入的要修改的数组nums = [1, 1]for i in range(1, 29):nums.append(nums[i - 1] + nums[i])# 枚举出前30个斐波那契数列r = []# 接收nums / a 的倍率for i in range(min(len(a), len(nums))):r.append(nums[i] / a[i])res = 0# 统计数目 符合的数di = {}# 建立一个字典，以分层不同的倍率层for j in r:di[j] = di.get(j, 0) + 1# 不断增加个数res = max(di[j], res)print(len(a) - res)# 减去倍率层中数目最多的那个 就是最小要修改的数感谢你的观看。