关于c++:PAT甲级2020年冬季考试-71-The-Closest-Fibonacci-Number

7-1 The Closest Fibonacci Number (20 分)

The Fibonacci sequence Fn is defined by $$F_{n+2} =F_{n+1} +F​_n \;\;for \;\;n≥0, with \;\;F_​0 =0 \;\;and\;\; F_​1 =1.$$ The closest Fibonacci number is defined as the Fibonacci number with the smallest absolute difference with the given integer N.

Your job is to find the closest Fibonacci number for any given N.

Input Specification:

Each input file contains one test case, which gives a positive integer N (≤10^8).

Output Specification:

For each case, print the closest Fibonacci number. If the solution is not unique, output the smallest one.

Sample Input:

305

Sample Output:

233

Hint:

Since part of the sequence is {0, 1, 1, 2, 3, 5, 8, 12, 21, 34, 55, 89, 144, 233, 377, 610, …}, there are two solutions: 233 and 377, both have the smallest distance 72 to 305. The smaller one must be printed out.

题目要求

题目粗心

给定一个 N，要求输入斐波拉契数列中最靠近 N 的数字。

算法思路

须要一直生成斐波拉契数列的每一项，遇到第一次大于等于 N 的数字就进行，而后记录以后地位为 k，判断 k - 1 和 k 地位的那个数字和 N 更靠近就输入哪个。生成斐波那契数列的办法就是采纳递归加上记忆化搜寻 (应用 dp 数组作为一个缓存，遇到算过的值就间接返回，否则就递归计算，而后保留)

留神点

• 1、间接暴力递归会导致测试点 5 运行超时

提交后果

AC 代码

#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;

int dp[1000000];

int F(int n) {if (n == 0 || n == 1) {dp[n] = n;
        return n;
    }
    if(dp[n]!=-1){return dp[n];
    }else{dp[n] = F(n - 1) + F(n - 2);
    }
    return dp[n];
}

int main() {
    int N;
    scanf("%d", &N);
    memset(dp, -1, sizeof(dp));
    dp[0] = dp[1] = 1;
    int k;
    for (int i = 0;; ++i) {if (dp[i] == -1) {dp[i] = F(i);
        }
        if (dp[i] >= N) {
            k = i;
            break;
        }
    }
    int a = abs(dp[k] - N);
    int b = abs(dp[k - 1] - N);
    if (a < b) {printf("%d", dp[k]);
    } else {printf("%d", dp[k - 1]);
    }
    return 0;
}