題目描述

一只蜜蜂在圖5.1-2所示的數字蜂房上爬動，已知它只能從標號小的蜂房爬到標號大的相鄰蜂房，

現在問你：蜜蜂從蜂房M開始爬到蜂房N，l≤M

輸入

M，N的值。

輸出

一個數表示爬行路線種數。

樣例輸入

1 14

樣例輸出

377

代碼:

#include <stdio.h>
#include <string>
#include <algorithm>
using namespace std;
typedef string Number;Number Map[100000];
#define ONE string("1")
#define Rev(a) reverse(a.begin(), a.end())
#define Get(a) ((a) - '0')
int x, y;
Number add(Number a, Number b) // 計算a+b
{Rev(a), Rev(b);size_t Size1 = a.size(), Size2 = b.size();Number ans;int carry = 0;for (size_t i = 0; i < Size1 || i < Size2; i++){int addsum = carry;carry = 0;if (i < Size1) addsum += Get(a[i]);if (i < Size2) addsum += Get(b[i]);if (addsum >= 10) addsum -= 10, carry = 1;ans.push_back(addsum + '0');}if (carry) ans.push_back('1');Rev(ans);return ans;
}
int main()
{int m, n;scanf("%d%d", &m, &n);Map[m] = ONE;if (m + 1 <= n) Map[m + 1] = ONE;for (int i=m+2;i<=n;i++) Map[i] = add(Map[i - 1], Map[i - 2]);printf("%s",Map[n].c_str());return 0;
}