1204.水题 SDNUOJ 1204

递推与递归：
适应问题：规律题，大数由小数推导
解决方案：找一个点切开…不过这个点怎么定…是规律题的问题所在（如何建立大与小、前与后的联系）

原文出处：https://blog.csdn.net/clamercoder/article/details/24363817

Description
一个整数总可以拆分为2的幂的和，例如：
7=1+2+4
7=1+2+2+2
7=1+1+1+4
7=1+1+1+2+2
7=1+1+1+1+1+2
7=1+1+1+1+1+1+1
总共有六种不同的拆分方式。
再比如：4可以拆分成：4 = 4，4 = 1 + 1 + 1 + 1，4 = 2 + 2，4=1+1+2。
用f(n)表示n的不同拆分的种数，例如f(7)=6.
要求编写程序，读入n(不超过1000000)，输出f(n)%1000000000。
Input
每组输入包括一个整数：N(1<=N<=1000000)。
Output
对于每组数据，输出f(n)%1000000000。
Sample Input
7
Sample Output
6

对于奇数n=2k+1：它的拆分的第一项一定是1，考虑去掉这个1，其实就对应于 2k的拆分，因此f(2k+1)=f(2k).
对于偶数n=2k：考虑有1和没有1的拆分：
有1的拆分，与(2k-1)的拆分一一对应，与上面奇数的情况 理由相同；
没有1的拆分，将每项除以2，正好一一对应于k的所有拆分。
因此f(2k) = f(2k-1) + f(k).

#include <cstdio>
#include <iostream>
using namespace std;

int f[1000005];

int main ()
{
    int n;
    while(~scanf("%d",&n))
    {
        f[0] = f[1] = 1;
        for(int i=2; i<=n; ++i)
        {
            if(i & 1)
                f [i] = f[i-1];
            else
                f [i] = (f[i-1] + f[i/2]) % 1000000000;
        }
        cout << f[n] << '\n';
    }
    return 0;
}