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. for my $k (sort {$a <=> $b} keys %hash) {
  12.     printf "%s\n", $hash{$k};
  13. }
  14. sub gen_exp
  15. {
  16.     our @op, our %hash;
  17.     my ($nums, $limit,  $lv ) = @_;
  18.     if ($lv >= $limit) {
  19.         my $res;
  20.         my $exp = $nums->[0];
  21.         $exp=~s/\d+/Math::BigRat->new(\"$&\/1\")/g;
  22.         $exp=~s/\*/ * /g;
  23.         eval("\$res = $exp");
  24.         return if $res == inf or $res == -inf or $res eq NaN;
  25.         my $val = $res->as_float();
  26.         return unless int($val) == $val and $val >= 0;
  27.         $hash{$val} = $res ."=". $nums->[0] unless ( exists $hash{$res} );
  28.         return;
  29.     }
  30.     my $pick = enum($nums);
  31.     for my $e ( @$pick ) {
  32.         for my $op ( @op ) {
  33.             my @tf = ($e->[0], $op, $e->[1]);
  34.             gen_exp(["(". join("", @tf) .")", @{$e->[2]} ], $limit, $lv+1 );
  35.         }
  36.     }
  37. }
  38. sub enum
  39. {
  40.     my ( $nums ) = @_;
  41.     my $last = $#$nums;
  42.     my $res = [];
  43.     for my $a ( 0 .. $last ) {
  44.         for my $b ( 0 .. $last-1 ) {
  45.             my @tmpr = @$nums;
  46.             push @$res, [splice(@tmpr,$a,1), splice(@tmpr,$b,1), [@tmpr] ];
  47.         }
  48.     }
  49.     return $res;
  50. }
  51. sub spliter
  52. {
  53.     my ($nums, $limit, $pos, $lv, $comb) = @_;
  54.     if ( $lv >= $limit ) {
  55.         push @$comb, [ split(" ", join("", @$nums)) ];
  56.         return;
  57.     }
  58.     for my $id ( $pos+1 .. $#$nums  ) {
  59.         if ( $nums->[$id] eq " " ) {
  60.             spliter( [@$nums], $limit, $id, $lv+1, $comb );
  61.             $nums->[$id] = "";
  62.             spliter( [@$nums], $limit, $id, $lv+1, $comb );
  63.         }
  64.     }
  65. }
复制代码





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