數的計算

題目描述

我們要求找出具有下列性質數的個數(包含輸入的自然數nn):

先輸入一個自然數nn(n \le 1000n≤1000),然後對此自然數按照如下方法進行處理:

不作任何處理;

在它的左邊加上一個自然數,但該自然數不能超過原數的一半;

加上數後,繼續按此規則進行處理,直到不能再加自然數為止.

輸入輸出格式

輸入格式：

11個自然數nn(n \le 1000n≤1000)

輸出格式：

11個整數，表示具有該性質數的個數。

輸入輸出樣例

輸入樣例#1： 複制

6

輸出樣例#1： 複制

6

說明

滿足條件的數為

6，16，26，126，36，136

思路分析：

在打代碼之前，我們不妨手動模拟一下

n=0,n=1時，答案顯然是1

n=2, ans=2; n=3,ans=2

n=4,ans=4; n=5,ans=4

n=6,ans=6; n=7,ans=6

相信大家也發現了，2n與2n+1(n為非負整數)的答案是一樣的 這就是第一個規律

然後我們以n=8為例，手動模拟一下

一共有10組解

8 1 8 2 8 3 8 4 8

1 2 8 1 3 8 1 4 8 2 4 8

1 2 4 8

我打出的東西很像一棵搜尋樹。。。

當我們把8和8下面的左三棵子樹放在一起（即8和下面三列），并将所有的8都改成7，我們能發現，我們得到了n=7時的所有解；

我們再把最右端的子樹（即剩下的部分）中的所有8删去，我們得到了n=4時的所有解

就這樣，我們可以得到一個遞推式，

f(n)=f(n-1)                //7=8-1

    +f(n/2)                //4=8/2
           

再結合之前發現的規律

就能得到：

n%2==0時
    f(n)=f(n-1)+f(n/2)
n%2==1時
    f(n)=f(n-1)
           

然後問題就迎刃而解啦

參考代碼：

#include <iostream>
using namespace std;
int main()
{
	int n,cn=1,i,f[1001];
	f[0]=f[1]=1;
	cin>>n;
	for(i=2;i<=n;i++)
	{
		if(i%2==0)
			f[i]=f[i-1]+f[i/2];
		else
			f[i]=f[i-1];
	}
	cout<<f[n]<<endl;
	return 0;
}