Recursion To recurrence 递归变递推

[rɪ'kɝʃən] [rɪ'kɝəns]

精典例题 NOI 1.5 -17:菲波那契数列

描述

菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。
给出一个正整数k，要求菲波那契数列中第k个数是多少。

输入

输入一行，包含一个正整数k。（1 <= k <= 46）

输出

输出一行，包含一个正整数，表示菲波那契数列中第k个数的大小

样例输入

19

样例输出

4181

例题分析1-递归变递推

#include <iostream>//此方法可以算出，但效率偏低，需要计算很多次

int days( int k ) { //（递归）

    if (k == 1) return 1;//初始值给定为1时返回
    if (k == 2) return 1;//初始值给定为2时返回
    return days(k-1) + days(k-2);  //初始值给定为k时，与k-1和k-2的关系，递归可从k向1和2递归结果值
}

int main(){
    int n, i;
    scanf("%d", &n);
    for(i = 1; i<=n; i++){
    if (i==n) printf("%d\n", days(i));  //递推，由1到k根据递归结果递推K的结果
    }    
    return 0;
}

例题分析2-

#include <iostream>

int main(){
    int n1=1, n2=1, n, k, i;
    scanf("%d", &k);
    for ( i=1; i<=k; i++){
        if (i<=2) n = n1;
        else{
            n = n1+n2;
            n1 = n2;
            n2 = n3;
        }
    }
    printf("%d\n", n);
    return 0;
}