【題目鏈接】

ybt 1316：【例4.6】數(shù)的計(jì)數(shù)(Noip2001)
ybt 1914：【01NOIP普及組】數(shù)的計(jì)數(shù)
洛谷 P1028 [NOIP2001 普及組] 數(shù)的計(jì)算

【題目考點(diǎn)】

1.遞推

考慮：遞推狀態(tài)，初始狀態(tài)，遞推關(guān)系

2.記憶化遞歸

考慮：遞歸問題，遞歸關(guān)系，遞歸出口，狀態(tài)記錄

【解題思路】

解法1：

1)遞推：

• 遞推狀態(tài)：a[i]: 數(shù)字i經(jīng)過處理后可以生成的數(shù)字有多少個(gè)
• 遞推關(guān)系：思考過程：如果要想求a[n], 對(duì)于所有k(k<n)，a[k]是已知的。
  數(shù)字n左邊可以添加的數(shù)字可以有：0（不添加），1，2，…，n/2。而假設(shè)添加數(shù)字i（$0\le i\le n/2$)，那么由數(shù)字i可以生成a[i]種數(shù)字。
  共可以生成數(shù)字個(gè)數(shù)：a[n] = a[0]+a[1]+...+a[n/2]
• 初始狀態(tài)：a[0]左邊不添加數(shù)字，自己本身作為一個(gè)結(jié)果。a[0]的值為1。

2)記憶化遞歸：

• 遞歸問題：求數(shù)字n經(jīng)過處理后可以生成的數(shù)字有多少個(gè)，函數(shù)記為int getNum(int n)
• 遞歸關(guān)系：思考過程：如果要想求getNum(n)，可以先求getNum(k) (已知k<n)
  數(shù)字n左邊可以添加的數(shù)字可以有：0（不添加），1，2，…，n/2。而假設(shè)添加數(shù)字i（$0\le i\le n/2$)，那么由數(shù)字i可以生成getNum(i)種數(shù)字。
  總共可以生成數(shù)字的種類數(shù)為：getNum(0)+getNum(1)+...+getNum(n/2)
• 遞歸出口：getNum(0)表示左邊不添加數(shù)字，自己本身作為一個(gè)結(jié)果。getNum(0)的值應(yīng)該為1
• 狀態(tài)記錄：數(shù)字i能生成的數(shù)字?jǐn)?shù)量

解法2:

在解法1的基礎(chǔ)上繼續(xù)化簡(jiǎn)遞推公式
已知遞推關(guān)系：a[n] = a[0]+a[1]+...+a[n/2-1]+a[n/2]
那么：a[n-1] = a[0]+a[1]+...+a[(n-1)/2]

• 如果n為偶數(shù)，那么(n-1)/2 = n/2 - 1
  a[n-1] = a[0]+a[1]+...+a[n/2-1]
  a[n] = a[n-1] + a[n/2]
• 如果n為奇數(shù)，那么(n-1)/2 = n/2
  a[n-1] = a[0]+a[1]+...+a[n/2]
  a[n] = a[n-1]

（遞歸寫法略）

【題解代碼】

解法1：

• 遞推， 遞推關(guān)系：a[n] = a[0]+a[1]+...+a[n/2]

#include<bits/stdc++.h> using namespace std; int a[1005];//a[i]:數(shù)字i能生成的數(shù)字?jǐn)?shù)量 int main() {int n;cin >> n;a[0] = 1;for(int i = 1; i <= n; ++i){for(int j = 0; j <= i/2; ++j) a[i] += a[j];}cout << a[n];return 0; }

• 記憶化遞歸

#include<bits/stdc++.h> using namespace std; int num[1005];//num[i]:數(shù)字i能生成的數(shù)字?jǐn)?shù)量 int getNum(int k)//獲取數(shù)字k能生成的數(shù)字?jǐn)?shù)量 {if(k == 0)return 1;if(num[k] > 0)//記憶化遞歸 return num[k]; int s = 0;for(int i = 0; i <= k/2; ++i)//n坐標(biāo)的數(shù)字 s += getNum(i);return num[k] = s;//記憶狀態(tài) } int main() {int n;cin >> n;cout << getNum(n);return 0; }

解法2：

• 遞推 遞推關(guān)系：如果i是偶數(shù)a[i]=a[i-1]+a[i/2]，否則a[i]=a[i-1]

#include<bits/stdc++.h> using namespace std; int a[1005];//a[i]:數(shù)字i能生成的數(shù)字?jǐn)?shù)量 int main() {int n;cin >> n;a[0] = 1;for(int i = 1; i <= n; ++i){//或?qū)憺?#xff1a;a[i] = i%2 == 0 ? a[i-1]+a[i/2] : a[i-1];if(i % 2 == 0)a[i] = a[i-1] + a[i/2];elsea[i] = a[i-1];}cout << a[n];return 0; }

（遞歸寫法略）

總結(jié)

以上是生活随笔為你收集整理的信息学奥赛一本通 1316：【例4.6】数的计数(Noip2001) | 1914：【01NOIP普及组】数的计数 | 洛谷 P1028 [NOIP2001 普及组] 数的计算的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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