java递规算法达人请进，帮小弟看一下关于递规算法的问题！！！！！！

Question

用递规计算下面问题：用不同的整数加出10000，共有多少种方法？如：10000=1+9999,2+9998,1+2+9997注：1+9999和9999+1算一种方法！ 

Answer 1

long sum(int x)
{
     for()
}

Answer 2

递归算法如此设计:
f(int sum,int maxAddened);//f(sum,maxAddened)为和为sum,最大加数为maxAddened,并且加数各不相同的方法数
//f(10000,9999)就是需要的结果.
利用f(m,n)=f(m-n,n-1)+f(m,n-1)递归算出结果即可

Answer 3

int s = 10000;
int num = 0;
for(int i=s-1;i>1;i--){
    num += i;
    i--;
}
这么算的结果不知道对不对，如果对，改成递归算法也容易
public int result(int s){
    if(s == 2)
         return 1;
    if(s == 3)
         return 2;
    return s-1+result(s-2);
}

Answer 4

經驗證，上述方法皆誤：得到如下算法：
//函數求出以min為最小加數，sum為和的方法種數。其中，round(x)是取整函數，即不大于x的最大整數
int f(min, sum){
  s = 0;
  if (min < sum / 2) {
    s++;
    for (i = min; i <= round((sum-1)/2); i++) {
      s += f(min + 1, sum - min);
    }
  }
  return s;
}可得到正确答案。哈哈，如需要分析，請樓主留言。

Answer 5

哈哈，上述函數的第3行：
  if (min < sum / 2) {
應改為：
  if (min < (sum + 1) / 2) {

Answer 6

你的算法肯定不对
2 = 1+1；
3 = 1+1+1；3 = 1+2；
4 = 1+1+1+1； 4 = 1+1+2； 4 = 1+3； 4 = 2+2；
5 = 1+1+1+1+1； 5 = 1+1+1+2； 5 = 1+1+3； 5 = 1+4； 5 = 1+2+2； 5 = 2+3；
.......
可以找出规律：a[n] = n-1+a[n-2];
只是不知道规律对不对

Answer 7

“不同的整数”啊！！！整理一下（java表現）：int f(int min, int sum) {
  int s = 0;
  if (min < (sum + 1) / 2) {
    s++;
    for (int i = min; i <= Math.round((sum-1)/2); i++) {
      s += f(min + 1, sum - min);
    }
  }
  return s;
}

Answer 8

public class Prime {
static long[] solve(int max) {
long[] sum = new long[max+1];
sum[1]=0;
sum[2]=0;
for(int i=3;i<max+1;i++){
sum[i]=i/2;
for(int j=0;j<i/2;j++){
sum[i]+=sum[j+1];
}
}
return sum;

}
public static void main(String[] args) {
long[] sum = solve(10000);
System.out.println(sum[10000]);
}}
ps:以上这个是递推而非递归，假如用递归的话，会死得很难看，呵呵
我的想法是
一个数n(n>2),总可以找到满足 a+b = n 的所有a
a属于[1,n/2]
也就是说一个数总可以找到两个数之和的形式，而其它如三个，四个数的和的形式总可以由这两个数再分解而得
              n/2
所以total(n)= ∑(total(a)+total(n-a))+n/2
              a=1
不知道对不对，请大家拍砖

Answer 9

上面的这个表达式变形了,n/2
∑(total(a)+total(n-a))+n/2
a=1

Answer 10

我找规律发现一个方法：
当只求两个数的和的可能情况数为f(int n,int sum)n为个数，sum为和
f(2,3)=1;f(2,4)=1;f(2,5)=2;f(2,6)=2.........规律很明显，值为(sum+1)/2-1;
当只求三个数的和的可能情况数时
当第一个数为1时（升序），
f(3,6)=1；f(3,7)=1;f(3,8)=2;f(3,9)=2;
当第一个数为2时，
f(3,9)=1;f(3,10)=1;f(3,11)=2;f(3,12)=2;
...............
以后的规律都是一样，最后求得
public static int f(int n, int sum) {
   int s = 0;
   int m = n*(n+1)/2;
   if(sum >= m){
     if(n == 2)
       return (sum+1)/2-1;
     for(int i=0;i<(sum - m + 1);i++){
       s += f(n-1,sum - n*(i+1));
     }
   }
   return s;
  }   原题的解还应该加上
    int sum = 6;
    int total = 0;
    for(int i = 2;i*(i+1)/2<=sum;i++){
      total += f(i,sum);
    }
    System.out.println(total);    要做个for循环，不知道这样对不对，感觉差不多了。

Answer 11

算到10000是不可能的，我们这样估计以下：
从1-1000里面随便挑9个数，可知他们的和小于9000,那么再加上一个大于1000的数，就是一种组合。这种情况下就有C(1000,9)种组合而C(1000,9)大约是2.6E21
同理
C(500,19) 大约是1.1E34
C(200,49) 大约是1.5E4110的41次方是什么数量级？所以大家就不要想用程序算了，除非直接给出公式。

Answer 12

int count(int min, int sum){
        int s = 0;
        if(min < (float)(sum) / 2){
            s += Math.round((sum + 1)/2) - min;
            for (int i = min; i < Math.round((sum-1)/2); i++){
                s += count(i + 1, sum - i);
            }
        }
        return s;
    }我的想法是对每一种有效的方法进行分类，对一个和n，先计算所有存在1的表达式，再计算存在2但不存在1的表达式，存在3但不存在2和1的表达式......直到存在n/2(取整)但不存在所有小于n/2的整数的表达式。