內容
東東有個嗜好，爬階梯不是一次走一階，就是一次走兩階。
換句話說，假設階梯有三階，那他有三種走法
一：第一步走一階，第二步走二階。
二：第一步走二階，第二步走一階。
三：全程都走一階。
這題要問你，假設階梯有 n 階，那東東有幾種走法?
輸入
第一行有一個正整數 n，0<n<100，表示階梯有 n 階。
1
2
5
輸出
請輸出 n 個階梯有幾種走法。
1
2
8
解題思路
和 c547 同一題，本題沒有使用 MOD 運算，因此最後幾項即使使用 unsigned long long 存也會溢位，這邊可以用萬進制的想法開另一個陣列去存進位的值，輸出時判斷是否有進位到新陣列來選擇不同的格式輸出即可。
完整程式碼
AC (1ms, 60KB)
#include <stdio.h>
#define SIZE 100
#define MAX 10000000000000000000ULL
unsigned long long list[SIZE] = { 1, 1 };
int list2[SIZE];
int main()
{
int n;
for (int i = 2; i < SIZE; i++)
{
list[i] = list[i - 1] + list[i - 2];
list2[i] = list2[i - 1] + list2[i - 2];
if (list[i] >= MAX)
list[i] -= MAX, list2[i]++;
}
while (scanf(" %d", &n) == 1)
{
if (list2[n]) printf("%d%012llu\n", list2[n], list[n]);
else printf("%llu\n", list[n]);
}
return 0;
}
|
