比如4:
4=4;
4=3+1;
4=2+2;
4=2+1+1;
4=1+1+1+1;
总共5种不同的拆法,如果是任意一个数呢?
如:17,20,50,100..... 可以有多少中拆法?
有没有什么直接一点数学公式可以用啊,
或者哪位好新人贴下源代码
谢谢
[问题]问一个数的拆分的算法问题
-
- 帖子: 52
- 注册时间: 2007-05-11 22:52
- 来自: 四川大学
-
- 帖子: 1074
- 注册时间: 2006-01-18 15:01
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 }
- anod221
- 帖子: 76
- 注册时间: 2007-04-10 18:36
- 来自: 西安
为什么不用递归呢?
就是一个数 n 可以分解成为 0+n , 1+(n-1) ......... n/2 + (n-n/2)
根据递归和栈的关系,一定也可以用栈的。
代码: 全选
#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;
}
根据递归和栈的关系,一定也可以用栈的。
上次由 anod221 在 2007-09-27 22:40,总共编辑 1 次。
-
- 帖子: 1074
- 注册时间: 2006-01-18 15:01
可能是思路不一样吧。我一开始就知道是算数目,所以就没想要知道怎么分,当作是个递推数列的问题。anod221 写了:原来要数目啊,用就好了代码: 全选
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
计算方法很简单,和你差不多,但我不是一开始就观察到的,是从这个方阵元素的定义推导到的。
另外,一般能用递归的,用递推更好点吧。中间的多余计算省略了,如果能直接得到通项公式自然是最快的好办法。
不过我列出了递推公式就没有化通项了,反正计算很快。
- stlxv
- 论坛版主
- 帖子: 8275
- 注册时间: 2006-05-03 0:39
- 来自: المريخ