Board logo

标题: [数值计算] [出题挑战]数字的四则运算组合 [打印本页]
作者: hongrk    时间: 2019-4-14 16:04     标题: [出题挑战]数字的四则运算组合

因为等级不够不能在[出题挑战]区发。

要求：输入一串数字，输出在此串数字中 插入四则运算 允许括号 所能得到的 自然数结果（可后跟对应的1个算式），结果按从小到大排列。

例：输入333，输出：
  1. 0=(3-3)*3

  2. 2=(3+3)/3

  3. 3=3+3-3

  4. 4=3/3+3

  5. 6=3*3-3

  6. 9=3+3+3

  7. 11=33/3

  8. 12=3*3+3

  9. 18=(3+3)*3

  10. 27=3*3*3

  11. 30=33-3

  12. 36=33+3

  13. 99=33*3

  14. 333=333
复制代码
若觉得比较麻烦，可以自行简化要求。比如只输出结果不带算式、运算数都只1位之类的。
另外，如5155算出24的情况……其实也算符合要求的吧。
作者: 老刘1号    时间: 2019-4-14 20:01

本帖最后由 老刘1号 于 2019-4-14 20:02 编辑

先占个楼，感觉lz的要求（前10行）用逆波兰表达式比较好搞
作者: 523066680    时间: 2019-4-14 20:35

回复 2# 老刘1号

    枚举全部结果还好，要是对每个值枚举不重复的全部公式就比较麻烦。比如 (1+2)*3 和 3*(1+2)，3*(2+1) 是完全一样的性质
10897 如何不重复地枚举 24 点算式？（上）
10897 如何不重复地枚举 24 点算式？（中）
10897 如何不重复地枚举 24 点算式？（下）

我们直接跳到最后一章

三、总结

　　本文解决了减法和除法中由「去括号」和「反转减号」造成的重复，修改主要体现在 actions 函数中。为了排除由「反转减号」造成的重复，我们定义了算式的极性。极性在运算中的传递规律非常复杂，造成 actions 函数冗长而不优雅，我也很无奈。
　　用最终版程序可以算出，由 n 个变量经四则运算可以组成的算式个数为：
[attach]11922[/attach]

这个数列也被 The Online Encyclopedia of Integer Sequences 收录


也就是二三四五六都可以用现成的模板套，这样可以省去大量冗余的试算过程。（这还没考虑数字相同的情况，数字相同的话减法和除法就不必要调换了，看需求严格程度吧）

两个参与数
  1. a + b

  2. a - b

  3. b - a

  4. a * b

  5. a / b

  6. b / a
复制代码
三个参与数
  1. c - (a + b)

  2. a + b - c

  3. c * (a + b)

  4. c / (a + b)

  5. (a + b) / c

  6. c * (a - b)

  7. c / (a - b)

  8. (a - b) / c

  9. c * (b - a)

  10. c / (b - a)

  11. (b - a) / c

  12. c + a * b

  13. c - a * b

  14. a * b - c

  15. c / (a * b)

  16. a * b / c

  17. c + a / b

  18. c - a / b

  19. a / b - c

  20. c + b / a

  21. c - b / a

  22. b / a - c

  23. b - (a + c)

  24. a + c - b

  25. b * (a + c)

  26. b / (a + c)

  27. (a + c) / b

  28. b * (a - c)

  29. b / (a - c)

  30. (a - c) / b

  31. b * (c - a)

  32. b / (c - a)

  33. (c - a) / b

  34. b + a * c

  35. b - a * c

  36. a * c - b

  37. b / (a * c)

  38. a * c / b

  39. b + a / c

  40. b - a / c

  41. a / c - b

  42. b + c / a

  43. b - c / a

  44. c / a - b

  45. a + b + c

  46. a - (b + c)

  47. b + c - a

  48. a * (b + c)

  49. a / (b + c)

  50. (b + c) / a

  51. a * (b - c)

  52. a / (b - c)

  53. (b - c) / a

  54. a * (c - b)

  55. a / (c - b)

  56. (c - b) / a

  57. a + b * c

  58. a - b * c

  59. b * c - a

  60. a * b * c

  61. a / (b * c)

  62. b * c / a

  63. a + b / c

  64. a - b / c

  65. b / c - a

  66. a + c / b

  67. a - c / b

  68. c / b - a
复制代码
4个和5个


至于5 5 5 1, 3 3 8 8, 3 3 7 7 之类求24的精度问题。转分数（有理化）处理。
作者: 523066680    时间: 2019-4-15 13:14

本帖最后由 523066680 于 2019-4-15 16:25 编辑

5551，取非负整数部分
  1. 0=(((5-5)*5)*1)

  2. 1=(((5+5)/5)-1)

  3. 2=(((5+5)/5)*1)

  4. 3=(((5+5)/5)+1)

  5. 4=(((5+5)-5)-1)

  6. 5=(((5+5)-5)*1)

  7. 6=(((5+5)-5)+1)

  8. 7=(((5/5)+5)+1)

  9. 10=(((5/5)+1)*5)

  10. 11=(1/(5/55))

  11. 12=((55/5)+1)

  12. 14=(((5+5)+5)-1)

  13. 15=(((5+5)+5)*1)

  14. 16=(((5+5)+5)+1)

  15. 19=(((5*5)-5)-1)

  16. 20=(((5*5)-5)*1)

  17. 21=(((5*5)-5)+1)

  18. 24=((5-(1/5))*5)

  19. 25=(((5+1)*5)-5)

  20. 26=(((1/5)+5)*5)

  21. 29=(((5*5)+5)-1)

  22. 30=(((5*5)+5)*1)

  23. 31=(((5*5)+5)+1)

  24. 35=(((5+1)*5)+5)

  25. 40=((5-1)*(5+5))

  26. 41=(51-(5+5))

  27. 45=(((5+5)-1)*5)

  28. 49=(((5+5)*5)-1)

  29. 50=(((5+5)*5)*1)

  30. 51=(((5+5)*5)+1)

  31. 52=((5/5)+51)

  32. 55=(((5+5)+1)*5)

  33. 59=((5+55)-1)

  34. 60=((5+1)*(5+5))

  35. 61=((5+5)+51)

  36. 76=((5*5)+51)

  37. 100=((5-1)*(5*5))

  38. 106=(55+51)

  39. 120=(((5*5)-1)*5)

  40. 124=(((5*5)*5)-1)

  41. 125=(((5*5)*5)*1)

  42. 126=(((5*5)*5)+1)

  43. 130=(((5*5)+1)*5)

  44. 150=((5+1)*(5*5))

  45. 220=((5-1)*55)

  46. 230=((51-5)*5)

  47. 250=((5*51)-5)

  48. 260=((5*51)+5)

  49. 270=((55-1)*5)

  50. 274=((5*55)-1)

  51. 275=((5*55)*1)

  52. 276=((5*55)+1)

  53. 280=((5+51)*5)

  54. 330=((5+1)*55)

  55. 510=((5+5)*51)

  56. 546=(551-5)

  57. 554=(555-1)

  58. 555=(555*1)

  59. 556=(5+551)

  60. 1275=((5*5)*51)

  61. 2755=(5*551)

  62. 2805=(55*51)

  63. 5551=5551
复制代码
作者: 523066680    时间: 2019-4-15 13:21

本帖最后由 523066680 于 2019-4-15 21:20 编辑 
  1. use Math::BigRat;

  2. STDOUT->autoflush(1);

  3. our %hash;

  4. our @op = qw/+ - * \//;

  5. my $num = "5551";

  6. my @nums= split("", $num);

  7. my @arr = split("", join(" ", @nums));

  8. my @comb;

  9. spliter(\@arr, $#nums, 0, 0, \@comb);

  10. grep { gen_exp( $_, $#$_, 0 ) } @comb;

  11. 

  12. for my $k (sort {$a <=> $b} keys %hash) {

  13.     printf "%s\n", $hash{$k};

  14. }

  15. 

  16. sub gen_exp

  17. {

  18.     our @op, our %hash;

  19.     my ($nums, $limit,  $lv ) = @_;

  20. 

  21.     if ($lv >= $limit) {

  22.         my $res;

  23.         my $exp = $nums->[0];

  24.         $exp=~s/\d+/Math::BigRat->new(\"$&\/1\")/g;

  25.         $exp=~s/\*/ * /g;

  26.         eval("\$res = $exp");

  27.         return if $res == inf or $res == -inf or $res eq NaN;

  28.         my $val = $res->as_float();

  29.         return unless int($val) == $val and $val >= 0;

  30.         $hash{$val} = $res ."=". $nums->[0] unless ( exists $hash{$res} );

  31.         return;

  32.     }

  33. 

  34.     my $pick = enum($nums);

  35.     for my $e ( @$pick ) {

  36.         for my $op ( @op ) {

  37.             my @tf = ($e->[0], $op, $e->[1]);

  38.             gen_exp(["(". join("", @tf) .")", @{$e->[2]} ], $limit, $lv+1 );

  39.         }

  40.     }

  41. }

  42. 

  43. sub enum

  44. {

  45.     my ( $nums ) = @_;

  46.     my $last = $#$nums;

  47.     my $res = [];

  48.     for my $a ( 0 .. $last ) {

  49.         for my $b ( 0 .. $last-1 ) {

  50.             my @tmpr = @$nums;

  51.             push @$res, [splice(@tmpr,$a,1), splice(@tmpr,$b,1), [@tmpr] ];

  52.         }

  53.     }

  54.     return $res;

  55. }

  56. 

  57. sub spliter

  58. {

  59.     my ($nums, $limit, $pos, $lv, $comb) = @_;

  60.     if ( $lv >= $limit ) {

  61.         push @$comb, [ split(" ", join("", @$nums)) ];

  62.         return;

  63.     }

  64. 

  65.     for my $id ( $pos+1 .. $#$nums  ) {

  66.         if ( $nums->[$id] eq " " ) {

  67.             spliter( [@$nums], $limit, $id, $lv+1, $comb );

  68.             $nums->[$id] = "";

  69.             spliter( [@$nums], $limit, $id, $lv+1, $comb );

  70.         }

  71.     }

  72. }
复制代码




欢迎光临 批处理之家 (http://www.bathome.net/) Powered by Discuz! 7.2