題目描述?Description

我們要求找出具有下列性質數的個數(包含輸入的自然數n):
　　先輸入一個自然數n(n<=1000),然后對此自然數按照如下方法進行處理:
　　1.不作任何處理;
　　2.在它的左邊加上一個自然數,但該自然數不能超過原數的一半;
　　3.加上數后,繼續(xù)按此規(guī)則進行處理,直到不能再加自然數為止. ?輸入輸出格式?Input/output 輸入格式：
一個自然數n(n<=1000)
輸出格式：
一個整數，表示具有該性質數的個數。 ?輸入輸出樣例?Sample input/output 樣例測試點#1 輸入樣例： 6 輸出樣例： 6 思路： 方法一： 用遞歸，f(n)=1+f(1)+f(2)+…+f(div/2)，當n較大時會超時，時間應該為指數級。 方法二：用記憶化搜索，實際上是對方法一的改進。設h[i]表示自然數i滿足題意三個條件的數的個數。如果用遞歸求解，會重復來求一些子問題。例如在求h[4]時，需要再求h[1]和h[2]的值。現在我們用h數組記錄在記憶求解過程中得出的所有子問題的解，當遇到重疊子問題時，直接使用前面記憶的結果。

方法三：

用遞推，用h(n)表示自然數n所能擴展的數據個數，則h(1)=1, h(2)=2, h(3)=2, h(4)=4, h(5)=4, h(6)=6, h(7)=6, h(8)=10, h(9)=10.分析以上數據，可得遞推公式：h(i)=1+h(1)+h(2)+…+h(i/2)。此算法的時間度為O(n*n)。

設h[i]-i按照規(guī)則擴展出的自然數個數(1≤i≤n)。下表列出了h[i]值及其方案： 方法四： w是對方法三的改進，我們定義數組s，s(x)=h(1)+h(2)+…+h(x),h(x)=s(x)-s(x-1)，此算法的時間復雜度可降到O(n)。 方法五： w還是用遞推，只要作仔細分析，其實我們還可以得到以下的遞推公式: (1)當i為奇數時，h(i)=h(i-1); w???? (2)當i為偶數時,h(i)=h(i-1)+h(i/2). 代碼①如下（遞歸）： 1 #include<stdio.h> 2 int ans; 3 void dfs(int m) //統(tǒng)計m所擴展出的數據個數 4 { 5 int i; 6 ans++; //每出現一個原數，累加器加1； 7 for (i = 1; i <= m/2; i++) //左邊添加不超過原數一半的自然數，作為新原數 8 dfs(i); 9 } 10 int main() 11 { 12 int n; 13 scanf("%d",&n); 14 dfs(n); 15 printf("%d\n",ans); 16 return 0; 17 }

代碼②如下（非遞歸）：

1 #include <stdio.h> 2 int main() 3 { 4 int a[1001]={0}; 5 int n,p; 6 scanf("%d",&n); 7 a[1]=1; 8 a[2]=2; 9 for(p=3;p<=n;p++) 10 { 11 if(p%2==1) 12 { 13 a[p]=a[p-1]; 14 } 15 else 16 { 17 a[p]=a[p-1]+a[p/2]; 18 } 19 } 20 printf("%d\n",a[n]); 21 return 0; 22 }

?

轉載于:https://www.cnblogs.com/geek-007/p/4298760.html

總結

以上是生活随笔為你收集整理的NOIP2001-普及组复赛-第一题-数的计算的全部內容，希望文章能夠幫你解決所遇到的問題。

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