題目鏈接：https://www.luogu.com.cn/problem/P1028

考點：找規律，遞推

題意：
給一個整數n(n≤1000），在n左邊添加一個不大于n/2的數構成一個新數，然后對添加的數也做相同處理。統計所有可能性。
以10舉例，可以有以下14種可能性：

110 210,1210, 310,1310, 410,1410,2410,12410, 510,1510,2510,12510, 10

解法一（遞歸）：
理解了題意之后，不難寫出遞歸的解法：

#include <bits/stdc++.h> using namespace std; int n,cnt=1; int A[1005]; void dfs(int x){for(int i=1;i<=x/2;i++){cnt++;dfs(i);} } int main(){cin >> n;dfs(n);cout << cnt; }

輸出：

14

這個解法可以得出正確答案，但是數據大了會超時。接下來主要有兩種做法，一種是用遞歸把1000種答案算出來，把答案寫在代碼里，根據輸入來輸出答案，時間復雜度是O(1)，這樣做的好處是不需要動腦，實在找不到規律就只能用這個笨辦法了，題目數據是1000，所以花個幾十分鐘還是可以算出來的；第二種辦法是小范圍的打印出前幾項答案，找規律，改用遞推公式解。
找規律的代碼：

#include <bits/stdc++.h> using namespace std; int n,cnt=1; int A[1005]; void dfs(int x){for(int i=1;i<=x/2;i++){cnt++;dfs(i);} } int main(){for (int i = 0; i <= 50; i++) {cnt = 1;dfs(i);printf("%d:%d\n", i, cnt);A[i] = cnt;} }

輸出：

0:1 1:1 2:2 3:2 4:4 5:4 6:6 7:6 8:10 9:10 10:14 11:14 12:20 13:20 14:26 15:26 16:36 17:36 18:46 19:46 20:60 ...

解法二（遞推）：
根據以上結果，可以找出兩條規律。
規律一：當n是奇數，A[i] = A[i-1]
規律二：當n是偶數，A[i] = A[i-1] + A[i/2]

因此答案如下：

#include <bits/stdc++.h> using namespace std; int A[1005]; // 記錄答案 /* 根據題意算出前幾項，以便找規律i 0 1 2 3 4 5 6 7 8 9 ...A[i] 1 1 2 2 4 4 6 6 10 10 ...規律一：當n是奇數，A[i] = A[i-1]規律二：當n是偶數，A[i] = A[i-1] + A[i/2] */ int main() {int n; cin >> n;A[0] = 1; A[1] = 1;for (int i = 2; i < 1000; i++) {if (i % 2 != 0) {A[i] = A[i-1];} else {A[i] = A[i-1] + A[i/2];}}cout << A[n];return 0; }

這個A[i] = A[i-1] + A[i/2]我實在是想不出來，不知道大佬們是怎么想到的，orz

總結

以上是生活随笔為你收集整理的【递推】P1028 数的计算的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。