不知道思密达

根据题意,用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)。

由于1为最小自然数,因此1无法扩展出其他自然数。自然数i(2<=i=n)按照规则扩展出的自然数包括自然数i;i左边加上1;i左边加上2按规则扩展出的h[2]个自然数…;由于i左邻的自然数不超过[i/2],因此直至i左边加上h[[i/2]]个自然数(这些自然数由[i/2]按规则扩展出)为止。由此得出递推的计数公式∶

h(1)=1; ...... h(i)=1＋h(1)＋h(2)＋…＋h(i/2)。(i>1) 从1出发,按照上述公式递推至自然数n,便可得出n按规则扩展出的自然数个数h[n]。

代码： #include <bits/stdc++.h> using namespace std; long long h[1010]; int main() { int i,j,n; cin>>n; //按照递增顺序计算扩展出的自然数的个数 for(i=1;i<=n;i++){ h[i]=1;//扩展出的自然数包括 i本身 //i左边分别加上 1…自然数[i/2]，按规则扩展出的自然数 for(j=1;j<=i/2;j++){ h[i]=h[i]+h[j]; } } cout<<h[n]-1;//减去自己本身 return 0; }