pairs of number，python算法求助

Vincent_lee_ll · 发表于 2020-4-1 15:55:44

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

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

Vincent_lee_ll · 发表于 2020-4-1 15:58:17

最开始，想着用斐波拉切数列，但是有个严重的问题，比如这个数列，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 · 发表于 2020-4-1 16:08:59

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

sunrise085 · 发表于 2020-4-1 16:15:31

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

Vincent_lee_ll · 发表于 2020-4-1 16:41:33

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

是的，两对数字

Vincent_lee_ll · 发表于 2020-4-1 16:43:54

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 · 发表于 2020-4-1 16:45:38

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 · 发表于 2020-4-2 20:09:35

自己顶一下吧

账号		自动登录	找回密码
密码			立即注册