题目
【Fibonacci数列】Fibonacci数列是这样定义的：
F[0] = 0
F[1] = 1
for 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或者X+1，现在给你一个数N求最少需要多少步可以变为Fibonacci数。
输入描述：
输入为一个正整数N(1 ≤ N ≤ 1,000,000)
输出描述：
输出一个最小的步数变为Fibonacci数"
示例1：
输入:
15
输出:
2
答案
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<math.h> int main() { int n = 0; scanf("%d", &n); int f1 = 0; int f2 = 1; int f3 = f2 + f1; while (1) { if (n == f2) { printf("0\n"); //因为输入的n大于等于1，所以n也可能一开始等于f2，n=f2就只需要0步变换 } else if (n < f2) { if (abs(n - f2) < abs(n - f1)) //abs为求绝对值函数 { printf("%d\n", abs(n - f2)); } else { printf("%d\n", abs(n - f1)); } } f1 = f2; //n大于f2，循环会一直执行下去，直到n处于f1跟f2之间，随后做差求出最小的步数 f2 = f3; f3 = f1 + f2; } return 0; }
第一次接触的想法
#include<stdio.h> int main() { int n=0; int a=1; int i=0; int num=1; int arr[10000]={0}; int j=0; int y=0; scanf("%d",&n); for(i=0;num<=1000000;i=y) //Fibonacci数列一个一个找出来放入数组 { y=num; num+=i; arr[j]=num; j++; } int c=0; for(c=0;c<j-1;c++) //遍历数组对比 if((arr[c]<=n)&&(arr[c+1]>=n)) { printf("%d\n",((n-arr[c])>(arr[c+1]-n))?(arr[c+1]-n):(n-arr[c])); } return 0; }
先把Fibonacci数列一个一个找出来,然后遍历数组一个个对比,确实盲目麻烦.
