pairs of number，python算法求助

Vincent_lee_ll

假设有一对数（a,b），每一步我们可以得到两个新的数字：（a,a+b）, (a+b,b)，以此类推
假设，初始的数为（1,1），然后输入一个数字N，0<N<1000000，
求最少需要多少步，能够得到这个数字，
重点来了，要求：时间限制：1000ms, 内存限制：64MB

Vincent_lee_ll

最开始，想着用斐波拉切数列，但是有个严重的问题，比如这个数列，1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269
给的这个数字N，987<N<1597,我以为只要在987的基础上再加一步，就肯定可以得到这个N，但事实不是这样，

BngThea

你先演示一下，初始为（1,1）时前四步能生成什么数字

sunrise085

没看明白题目啥意思
每一步得到的是两个数字，还是两对数字？
最后得到该数字N是什么意思，是这一对数字中有该数字N就算得到该数字了吗？

Vincent_lee_ll

sunrise085 发表于 2020-4-1 16:15
没看明白题目啥意思
每一步得到的是两个数字，还是两对数字？
最后得到该数字N是什么意思，是这一对数字 ...

是的，两对数字

Vincent_lee_ll

Vincent_lee_ll 发表于 2020-4-1 15:58
最开始，想着用斐波拉切数列，但是有个严重的问题，比如这个数列，1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,  ...

初始   （1,1）
第一步（2,1） （1,2）
第二步（3,1） （2,3） （3,2） （1,3）
以此类推，然后给一个数N，只要数N在这些数字里面，就行，但是要是最少步数

Vincent_lee_ll

sunrise085 发表于 2020-4-1 16:15
没看明白题目啥意思
每一步得到的是两个数字，还是两对数字？
最后得到该数字N是什么意思，是这一对数字 ...

初始   （1,1）
第一步（2,1） （1,2）
第二步（3,1） （2,3） （3,2） （1,3）
以此类推，然后给一个数N，只要数N在这些数字里面，就行，但是要是最少步数

Vincent_lee_ll

自己顶一下吧