Chinaunix首页 | 论坛 | 博客
  • 博客访问: 65028
  • 博文数量: 115
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 10
  • 用 户 组: 普通用户
  • 注册时间: 2014-03-08 19:09
文章分类
文章存档

2015年(115)

我的朋友

分类: C/C++

2015-08-06 16:49:49

第21题 输入两个整数 n 和 m,从数列1,2,3.......n 中 随意取几个数,
使其和等于 m ,要求将其中所有的可能组合列出来.
这个动态规划应该能做,但是可能比较复杂,如果只是问有几种排列应该还好做,可要列出所有可能性就有点麻烦了。
暂时用回溯算法做了下。用perl实现,代码还比较简单。
大致就是枚举所有可能性。
枚举填入一位result[i] = x,然后在枚举填入下一位 result[i] = y. y的取值范围是(x+1 .. n).
以此类推。
第一个参数是n,第二个参数是m.

点击(此处)折叠或打开

  1. my $size = $ARGV[0];
  2. my $target = $ARGV[1];

  3. sub fill{
  4.     my $index = shift;
  5.     my $value = shift;    
  6.     my @tresult = @_;
  7.     $tresult[$index] = $value;
  8.     {
  9.         my $sum = 0;
  10.         for(@tresult){
  11.             $sum+=$_;
  12.         }
  13.         if($sum == $target){
  14.             print "@tresult \n";
  15.             return;
  16.         }
  17.         return if($sum> $target);
  18.     }
  19.     for( $value+1 .. $size){
  20.         fill($index+1, $_, @tresult);
  21.     }
  22. }

  23. my @result;
  24. for(1..$size){
  25.     fill(0, $_, @result);
  26. }

 
阅读(371) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~