【題目鏈接】

OpenJudge NOI 2.6 1944:吃糖果
注：ybt 1193：吃糖果 頁面打不開，可以在OpenJudge做該題。

【題目考點(diǎn)】

1. 遞推/遞歸

2. 搜索

【解題思路】

解法1. 遞推

• 遞推狀態(tài)：a[i]:吃i個巧克力的方案數(shù)
• 初始狀態(tài)：
  • 要吃1塊巧克力，方案數(shù)為1：a[1] = 1。
  • 要吃2塊巧克力，方案數(shù)為2：a[2] = 2。
• 遞推關(guān)系：
  要想吃i個巧克力，先考慮第1天吃幾塊
  • 如果第1天吃1塊巧克力，接下來吃i-1塊巧克力的方案數(shù)為a[i-1]，因此這種情況下的方案數(shù)為：a[i-1]。
  • 如果第1天吃2塊巧克力，接下來吃i-1塊巧克力的方案數(shù)為a[i-2]，因此這種情況下的方案數(shù)為：a[i-2]。
  • 因此吃i個巧克力的方案數(shù)為a[i] = a[i-1] + a[i-2]

實(shí)際就是一個求斐波那契數(shù)列第n項(xiàng)的問題。

解法2：遞歸

n最大為20，使用普通遞歸或記憶化遞歸均可。

解法3：深搜

問題規(guī)模不大，用深搜也可以解該題

【題解代碼】

解法1：遞推

#include <bits/stdc++.h> using namespace std; int main() {int n, a[25];cin >> n;a[1] = 1, a[2] = 2;for(int i = 3; i <= n; ++i)a[i] = a[i-1] + a[i-2];cout << a[n];return 0; }

解法2：遞歸

• 一般遞歸

#include <bits/stdc++.h> using namespace std; int solve(int k)//返回吃k個巧克力的方案數(shù) {if(k <= 2)return k;return solve(k-1) + solve(k-2); } int main() {int n;cin >> n;cout << solve(n);return 0; }

• 記憶化遞歸

#include <bits/stdc++.h> using namespace std; int a[25];//a[i]:吃i個巧克力的方案數(shù) int solve(int k)//返回吃k個巧克力的方案數(shù) {if(a[k] > 0)return a[k];if(k <= 2)return k;return a[k] = solve(k-1) + solve(k-2); } int main() {int n;cin >> n;cout << solve(n);return 0; }

解法3：深搜

#include <bits/stdc++.h> using namespace std; int ans; void dfs(int a)//要吃a顆巧克力 統(tǒng)方案徑數(shù) {for(int i = 1; i <= 2; ++i)//這一次吃i個巧克力 {if(a-i == 0)ans++;//方案數(shù)加1 else if(a-i > 0)dfs(a-i);//看下一次吃幾個 } } int main() {int n;cin >> n;dfs(n);cout << ans;return 0; }

總結(jié)

以上是生活随笔為你收集整理的信息学奥赛一本通 1193：吃糖果 | OpenJudge NOI 2.6 1944:吃糖果的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。