[问题]问一个数的拆分的算法问题

[scu_guzo]

比如4：
4=4；
4=3+1；
4=2+2；
4=2+1+1；
4=1+1+1+1；
总共5种不同的拆法，如果是任意一个数呢？
如：17，20，50，100..... 可以有多少中拆法？
有没有什么直接一点数学公式可以用啊，
或者哪位好新人贴下源代码
谢谢

[xiechy]

1 #include <vector>
2 #include <numeric>
3 #include <cstdio>
4 using namespace std;
5 int main()
6 {
7 vector <int> A;
8 A.push_back(1);
9 int ans;
10 scanf("%d",&ans);
11 for(int i=2;i<=ans;i++)
12 {
13 int tmp= ((i%2)==0) ?
14 2*accumulate(A.begin(),A.begin()+A.size()/2+1,0) -*(A.begin()+A.size() /2)+1 :
15 2*accumulate(A.begin(),A.begin()+A.size()/2,0) +1 ;
16 A.push_back(tmp);
17 }
18 printf("%d\n",*(--A.end()));
19 }

[scu_guzo]

2楼的大哥啊
给一点点解释啊
再谢了 ^_^

[anod221]

为什么不用递归呢？

代码： 全选

#include <stdio.h>
#include <stdio.h>
#include <string.h>

unsigned int *v;
unsigned int num;

void display()
{
  int i;
  printf("%d", v[0]);
  for(i=1;i<num;i++)//如果数组后面的数比前面的大，那么前面就会已经显示过了
    if(v[i] == 0) break;
    else if(v[i] < v[i-1]) {printf("\r");return;}
    else printf(" + %d", v[i]);
  printf("\n");
}

void so(unsigned int n, unsigned int *p)//递归的生成所需要的数组
{
  int i;
  for(i=0;p+i<v+1+num;i++)p[i]=0;//不清零后面的显示不出来
  p[0] = n;
  display();
  if(n == 1) return;

  for(i=1;i<=n/2;i++){
    p[0] = i;
    so(n-i, p+1);
  }
}

int main()
{
  scanf("%d", &num);
  v = (unsigned int*)malloc(num*sizeof(unsigned int));
  so(num, v);
  return 0;
}

就是一个数 n 可以分解成为 0+n , 1+(n-1) ......... n/2 + (n-n/2)
根据递归和栈的关系，一定也可以用栈的。

[anod221]

原来要数目啊，用

代码： 全选

echo 数字|./程序名|wc -l

就好了

[xiechy]

原来要数目啊，用

代码： 全选

echo 数字|./程序名|wc -l

就好了

可能是思路不一样吧。我一开始就知道是算数目，所以就没想要知道怎么分，当作是个递推数列的问题。
我定义了下面的方阵A_i_j,代表最大的数不大于j的对i的所有的组合的值，要求的数组就是
a_i_i(i=1...n)
其实这个方阵很整齐，是：
1 1 1 1 1 1 1 1
1 2 2 2 2 2 2 2
1 2 3 3 3 3 3 3
1 2 3 5 5 5 5 5
1 2 3 5
计算方法很简单，和你差不多，但我不是一开始就观察到的，是从这个方阵元素的定义推导到的。
另外，一般能用递归的，用递推更好点吧。中间的多余计算省略了，如果能直接得到通项公式自然是最快的好办法。
不过我列出了递推公式就没有化通项了，反正计算很快。

[scu_guzo]

谢谢大家啊!!

[stlxv]

有没有什么直接一点数学公式可以用啊，

有，这是个简单的组合问题，你在草稿纸上写写就出来了