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

C、C++和Java语言
回复
scu_guzo
帖子: 50
注册时间: 2007-05-11 22:52
来自: 四川大学
送出感谢: 0
接收感谢: 0
联系:

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

#1

帖子 scu_guzo » 2007-09-23 23:01

比如4:
4=4;
4=3+1;
4=2+2;
4=2+1+1;
4=1+1+1+1;
总共5种不同的拆法,如果是任意一个数呢?
如:17,20,50,100..... 可以有多少中拆法?
有没有什么直接一点数学公式可以用啊,
或者哪位好新人贴下源代码
谢谢
xiechy
帖子: 1074
注册时间: 2006-01-18 15:01
送出感谢: 0
接收感谢: 1 次

#2

帖子 xiechy » 2007-09-24 1:33

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
帖子: 50
注册时间: 2007-05-11 22:52
来自: 四川大学
送出感谢: 0
接收感谢: 0
联系:

#3

帖子 scu_guzo » 2007-09-25 22:22

2楼的大哥啊
给一点点解释啊
再谢了 ^_^
头像
anod221
帖子: 76
注册时间: 2007-04-10 18:36
来自: 西安
送出感谢: 0
接收感谢: 0
联系:

#4

帖子 anod221 » 2007-09-25 22:54

为什么不用递归呢?

代码: 全选

#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 在 2007-09-27 22:40,总共编辑 1 次。
头像
anod221
帖子: 76
注册时间: 2007-04-10 18:36
来自: 西安
送出感谢: 0
接收感谢: 0
联系:

#5

帖子 anod221 » 2007-09-25 23:06

原来要数目啊,用

代码: 全选

echo 数字|./程序名|wc -l
就好了
xiechy
帖子: 1074
注册时间: 2006-01-18 15:01
送出感谢: 0
接收感谢: 1 次

#6

帖子 xiechy » 2007-09-26 0:00

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
计算方法很简单,和你差不多,但我不是一开始就观察到的,是从这个方阵元素的定义推导到的。
另外,一般能用递归的,用递推更好点吧。中间的多余计算省略了,如果能直接得到通项公式自然是最快的好办法。
不过我列出了递推公式就没有化通项了,反正计算很快。
scu_guzo
帖子: 50
注册时间: 2007-05-11 22:52
来自: 四川大学
送出感谢: 0
接收感谢: 0
联系:

#7

帖子 scu_guzo » 2007-09-26 12:13

谢谢大家啊!!
头像
stlxv
论坛版主
帖子: 8273
注册时间: 2006-05-03 0:39
来自: المريخ
送出感谢: 0
接收感谢: 1 次

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

#8

帖子 stlxv » 2007-09-28 17:53

scu_guzo 写了:有没有什么直接一点数学公式可以用啊,
有,这是个简单的组合问题,你在草稿纸上写写就出来了
PHP是最好的语言!不服来战!
回复

回到 “C/C++/Java”