題目連結 http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b024。
分析爬樓梯問題後,會得到
3 階是 fib(4)
4 階是 fib(5)
5 階是 fib(6)
... etc
這樣的結果其實是 Fibonacci number。
程式碼:
- #include <iostream>
- using namespace std;
- long long int combi(int n, int k)
- {
- long long int C[n + 1][k + 1];
- int i, j;
- for (i = 0; i <= n; i++)
- {
- for (j = 0; j <= min(i, k); j++)
- {
- if (j == 0 || j == i) // C(n, 0) = C(n, n) = 1
- C[i][j] = 1;
- else // C(n, k) = C(n-1, k-1) + C(n-1, k)
- C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
- }
- }
- return C[n][k];
- }
- int main()
- {
- int x, y;
- cin >> x >> y;
- cout << combi(x+y, x) << endl;
- return 0;
- }
沒有留言:
張貼留言