1320 OJ 分苹果问题的找规律递推解法

分苹果

对数据进行评估与描述

题目描述

yyf获得了一定数量的苹果，他可以选择将不超过总数一半的苹果赠予一位好友，或者选择全部保留食用。而这位好友同样具备将所获苹果分给另一位朋友或自行保留的权利，此过程可不断延续，直至无法继续分配为止。现需计算所有可能的分配方式总数；例如，当yyf获得6个苹果时，其分配方式如下：

6；

6 3；

6 3 1；

6 2；

6 2 1；

6 1；
因此，总共有6种不同的分配方式

输入描述

n代表yyf获得的苹果数量为n个

输出描述

分类方法的总数量

样例输入

6

样例输出展示

6

思路：规律题，比如当我们有10个苹果，我们可分的情况就是有5个苹果时的情况+1（10个都给自己）

AC代码：

    #include<bits/stdc++.h>
    using namespace std;
    int a[100100]={0,1,2,2,4,4,6,6};
    // 将1-7列举好 
    int main()
    {
    	int n;
    	for(int i=8;i<=10010;i++)	//从8开始递推 
    	{
    		for(int j=i/