OJ练习之Fibonacci数列

WY22 Fibonacci数列入门 通过率:36.94% 时间限制:1秒 空间限制:32M知识点数学 模拟描述Fibonacci数列是这样定义的F[0] 0F[1] 1for each i ≥ 2: F[i] F[i-1] F[i-2]因此Fibonacci数列就形如0, 1, 1, 2, 3, 5, 8, 13, …在Fibonacci数列中的数我们称为Fibonacci数。给你一个N你想让其变为一个Fibonacci数每一步你可以把当前数字X变为X-1或者X1现在给你一个数N求最少需要多少步可以变为Fibonacci数。输入描述输入为一个正整数N(1 ≤ N ≤ 1,000,000)输出描述输出一个最小的步数变为Fibonacci数示例1输入15输出2思路一#includeiostream#includevectorusingnamespacestd;// 从第2个斐波那契数开始与这个整数做比较当大于N的时候保存这个斐波那契数同时保存上一个斐波那契数让N分别于这两个数求差值哪个小就是哪个// 因为题目中已经说明了是N肯定大于等于1所以可以从第二个或第三个斐波那契数开始比较intmain(){intN0;vectorlonglongFib;// 存斐波那契数intleft-1;// 记录下标intright-1;// 记录下标inti1;// 下标从1开始从第二个斐波那契数开始比较intmin0;Fib.push_back(0);Fib.push_back(1);cinN;while(true){// 如果i 1,每次就要更新最新的斐波那契值if(i1){Fib.push_back(Fib[i-1]Fib[i-2]);}if(Fib[i]N){min0;break;}elseif(Fib[i]N){righti;lefti-1;minFib[right]-N;if(N-Fib[left]min){minN-Fib[left];}break;}else{i;}}coutmin;return0;}思路二#includeiostream#includevectorusingnamespacestd;// 只保留三个斐波那契数a,b,c因为初始第三个斐波那契数c也是1只需要让c与N其对比直到c大于等于N就说明N满足 bNc(数学表示)那么只需要获得b到N和N到c距离的最小值即可。intmain(){inta0,b1,c1;intN0;cinN;while(true){if(cN){ab;bc;cab;}else{coutmin(c-N,N-b);break;}}return0;}思路二代码简化#includeiostream#includevectorusingnamespacestd;// 只保留三个斐波那契数a,b,c因为初始第三个斐波那契数c也是1只需要让c与N其对比直到c大于等于N就说明N满足 bNc(数学表示)那么只需要获得b到N和N到c距离的最小值即可。intmain(){inta0,b1,c1;intN0;cinN;while(cN){ab;bc;cab;}// 走到这里就说明N满足 bNc(数学表示)coutmin(c-N,N-b);return0;}