当前时区为 UTC + 8 小时



发表新帖 回复这个主题  [ 8 篇帖子 ] 
作者 内容
1 楼 
 文章标题 : [问题]问一个数的拆分的算法问题
帖子发表于 : 2007-09-23 23:01 

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


页首
 用户资料  
 
2 楼 
 文章标题 :
帖子发表于 : 2007-09-24 1:33 

注册: 2006-01-18 15:01
帖子: 1074
送出感谢: 0 次
接收感谢: 1
引用:
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 }


页首
 用户资料  
 
3 楼 
 文章标题 :
帖子发表于 : 2007-09-25 22:22 

注册: 2007-05-11 22:52
帖子: 50
地址: 四川大学
送出感谢: 0 次
接收感谢: 0 次
2楼的大哥啊
给一点点解释啊
再谢了 ^_^


页首
 用户资料  
 
4 楼 
 文章标题 :
帖子发表于 : 2007-09-25 22:54 
头像

注册: 2007-04-10 18:36
帖子: 76
地址: 西安
送出感谢: 0 次
接收感谢: 0 次
为什么不用递归呢?
代码:
#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 次

页首
 用户资料  
 
5 楼 
 文章标题 :
帖子发表于 : 2007-09-25 23:06 
头像

注册: 2007-04-10 18:36
帖子: 76
地址: 西安
送出感谢: 0 次
接收感谢: 0 次
原来要数目啊,用
代码:
echo 数字|./程序名|wc -l

就好了


页首
 用户资料  
 
6 楼 
 文章标题 :
帖子发表于 : 2007-09-26 0:00 

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


页首
 用户资料  
 
7 楼 
 文章标题 :
帖子发表于 : 2007-09-26 12:13 

注册: 2007-05-11 22:52
帖子: 50
地址: 四川大学
送出感谢: 0 次
接收感谢: 0 次
谢谢大家啊!!


页首
 用户资料  
 
8 楼 
 文章标题 : Re: [问题]问一个数的拆分的算法问题
帖子发表于 : 2007-09-28 17:53 
头像

注册: 2006-05-03 0:39
帖子: 8273
地址: المريخ
送出感谢: 0 次
接收感谢: 1
scu_guzo 写道:
有没有什么直接一点数学公式可以用啊,

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


_________________
PHP是最好的语言!不服来战!


页首
 用户资料  
 
显示帖子 :  排序  
发表新帖 回复这个主题  [ 8 篇帖子 ] 

当前时区为 UTC + 8 小时


在线用户

正在浏览此版面的用户:没有注册用户 和 1 位游客


不能 在这个版面发表主题
不能 在这个版面回复主题
不能 在这个版面编辑帖子
不能 在这个版面删除帖子
不能 在这个版面提交附件

前往 :  
本站点为公益性站点,用于推广开源自由软件,由 DiaHosting VPSBudgetVM VPS 提供服务。
我们认为:软件应可免费取得,软件工具在各种语言环境下皆可使用,且不会有任何功能上的差异;
人们应有定制和修改软件的自由,且方式不受限制,只要他们自认为合适。

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
简体中文语系由 王笑宇 翻译