[征集]算24点全解无重复程序

头像
523066680
Administrator
Administrator
帖子: 340
注册时间: 2016年07月19日 12:14
拥有现金: 锁定
储蓄: 锁定
Has thanked: 30 times
Been thanked: 27 times
联系:

[征集]算24点全解无重复程序

帖子 #1 523066680 » 2016年08月31日 18:10

语言不限,先满足基本要求,然后考虑扩展情况。(期待遇到直接搞定的大牛 ;)

基本要求:
  1. 接收4个(或更多)整数参数,枚举能够算出24点的组合公式
  2. 参与的算术符号 + - * /
扩展:
  1. 考虑 1/3 = 0.333333333 在某些环境下可能丢失精度的情况,建议把这些数按分数处理,而不要出现浮点数。
  2. 在列出的所有公式类型中,尽可能地避免重复的公式,比如 a+b 和 b+a 是一样的;a+b+(c/d) 和 a+b+c/d 是一样的
    当有 a/b 和 a/c ,而 b 和 c 是同一个数时,也视为重复

扩展1,在使用C语言 逐步计算某个公式的时候尤其明显:

代码: 全选

#include <stdio.h>

int main(int argc, char *argv[] )
{
    float x, y, z;
    x = 8.0/3.0;
    y = 3.0 - x;
    z = 8.0 / y;
    printf("%f", z );
    return 0;
}
输出24.000006

但如果是在一个式子内求结果

代码: 全选

printf("%f", 8.0/(3.0-8.0/3.0));
则输出24.000000


扩展1.的一些例子
8 8 3 3
6 5 4 1
3 3 7 7
4 4 7 7

头像
523066680
Administrator
Administrator
帖子: 340
注册时间: 2016年07月19日 12:14
拥有现金: 锁定
储蓄: 锁定
Has thanked: 30 times
Been thanked: 27 times
联系:

Re: [征集]算24点全解无重复程序

帖子 #2 523066680 » 2016年08月31日 20:33

#占楼

Perl 版,因为是枚举所有公式类型并整个Eval,所以好像没有扩展1的情况。
还未对重复意义的公式进行筛选和排除

Code: [全选] [展开/收缩] [Download] (Untitled.pl)
  1. =info
  2.     Code-By: 523066680
  3.        Date: 2016-09-01
  4. =cut
  5.  
  6. my @nums = qw/3 3 7 7/;
  7. our @ops = ("+", "-", "*", "/");
  8. our %hash;
  9.  
  10. arrange(\@nums, [], 0, $#nums);
  11.  
  12. #排列组合
  13. sub arrange
  14. {
  15.     my ($ref, $ref2, $lv, $top) = @_;
  16.  
  17.     my @tr;
  18.     my @collect;
  19.  
  20.     if ($lv <= $top)
  21.     {        
  22.         for my $o ( 0 .. $#$ref )
  23.         {
  24.             @collect = (@$ref2, $ref->[$o]);
  25.             @tr = @$ref[ 0..$o-1, $o+1..$#$ref ];
  26.             arrange(\@tr, \@collect, $lv+1, $top);
  27.         }
  28.     }
  29.     else
  30.     {
  31.         prior($ref2, 0, $#$ref2);
  32.     }
  33. }
  34.  
  35. #递归设置优先级
  36. sub prior
  37. {
  38.     our $hash;
  39.  
  40.     my ($ref, $lv, $top) = @_;
  41.     my @arr;
  42.  
  43.     if ( $lv < $top )
  44.     {
  45.         for my $i (0 .. $#$ref-1)
  46.         {
  47.             for my $o (@ops)
  48.             {
  49.                 @arr = bracket( $ref, $i, $o );
  50.                 prior(\@arr, $lv+1, $top);
  51.             }
  52.         }
  53.     }
  54.     else
  55.     {
  56.         my $exp = join("", @$ref );
  57.         my $x;
  58.         eval("\$x = $exp") or $x = 0;  #如果遇到除数为0或者返回0错误,则赋值为0
  59.  
  60.         if ( $x == 24 and (not exists $hash{$exp}) )
  61.         {
  62.             print "$exp = $x \n";
  63.             $hash{$exp} = 1;
  64.         }
  65.     }
  66. }
  67.  
  68. #加括号处理
  69. sub bracket
  70. {
  71.     my ($aref, $idx, $o) = @_;
  72.     my @arr;
  73.  
  74.     for my $i ( 0 .. $#{$aref})
  75.     {
  76.         if ( $i == $idx )
  77.         {
  78.             push @arr, "(". $aref->[$i] . $o . $aref->[$i+1] .")" ;
  79.         }
  80.         elsif ( $i == ($idx+1) )
  81.         {
  82.         }
  83.         else
  84.         {
  85.             push @arr, $aref->[$i];
  86.         }
  87.     }
  88.  
  89.     return @arr;
  90. }


输出结果
((3+(3/7))*7) = 24
(((3/7)+3)*7) = 24
(7*(3+(3/7))) = 24
(7*((3/7)+3)) = 24

头像
灵台方寸山
出类拔萃
出类拔萃
帖子: 79
注册时间: 2016年08月06日 16:40
拥有现金: 锁定
储蓄: 锁定
来自: [color=red]斜月三星洞[/color]
Has thanked: 24 times
Been thanked: 17 times

Re: [征集]算24点全解无重复程序

帖子 #3 灵台方寸山 » 2016年08月31日 20:37

:holyhigh

进行难度分级。

从低难度开始做。
:crazylaugh3 :oh_no
少发点科普,对中医产业,骗子产业不好。

头像
523066680
Administrator
Administrator
帖子: 340
注册时间: 2016年07月19日 12:14
拥有现金: 锁定
储蓄: 锁定
Has thanked: 30 times
Been thanked: 27 times
联系:

Re: [征集]算24点全解无重复程序

帖子 #4 523066680 » 2016年08月31日 20:41

灵台方寸山 写了::holyhigh

进行难度分级。

从低难度开始做。

是的,先满足基本要求,贴代码。然后考虑扩展。

=======================================================================
2016-09-03
方案一、
    大致思路,用字符a b c d代表数字,+ - * / 作为参与的运算符
    遍历所有运算符排列方式、代数组合,存为模板(4位数、5位数、6位数的模板)。在实际计算时导入模板代入数值进行计算。

  • 枚举不同的优先级
    四个数字参与的公式,有3个运算符,可以有5种优先类型。
    Code: [全选] [展开/收缩] [Download] (Untitled.txt)
    1. ((a / b) / c) / d  -> 1 2 3
    2. (a / b) / (c / d)  -> 1 3 2 *
    3. (a / (b / c)) / d  -> 2 1 3
    4. a / ((b / c) / d)  -> 2 3 1
    5. (a / b) / (c / d)  -> 3 1 2 *
    6. a / (b / (c / d))  -> 3 2 1

    第二种和第五种,顺序不同,但结果明显一致。所以是重复项。

    生成不同优先级公式的Perl代码,不限制于数字的个数。
    1. my @nums = ('a'..'e');
    2.  
    3. func(\@nums, 0, $#nums);
    4.  
    5. sub func
    6. {
    7.     my ($ref, $lv, $top) = @_;
    8.     my @arr;
    9.  
    10.     if ( $lv < $top )
    11.     {
    12.         for my $i (0 .. $#$ref-1)
    13.         {
    14.             @arr = prior( $ref, $i );
    15.             func(\@arr, $lv+1, $top);
    16.         }
    17.     }
    18.     else
    19.     {
    20.         print join(" ", @$ref ), "\n";
    21.     }
    22. }
    23.  
    24. sub prior
    25. {
    26.     my ($aref, $idx) = (shift, shift);
    27.     my @arr;
    28.  
    29.     for my $i ( 0 .. $#{$aref})
    30.     {
    31.         if ( $i == $idx )
    32.         {
    33.             push @arr, "(". $aref->[$i] . " / " . $aref->[$i+1] .")" ;
    34.         }
    35.         elsif ( $i == ($idx+1) )
    36.         {
    37.         }
    38.         else
    39.         {
    40.             push @arr, $aref->[$i];
    41.         }
    42.     }
    43.  
    44.     return @arr;
    45. }

    代码: 全选

    ((((a / b) / c) / d) / e)
    (((a / b) / c) / (d / e))
    (((a / b) / (c / d)) / e)
    ((a / b) / ((c / d) / e))
    (((a / b) / c) / (d / e))
    ((a / b) / (c / (d / e)))
    (((a / (b / c)) / d) / e)
    ((a / (b / c)) / (d / e))
    ((a / ((b / c) / d)) / e)
    (a / (((b / c) / d) / e))
    ((a / (b / c)) / (d / e))
    (a / ((b / c) / (d / e)))
    (((a / b) / (c / d)) / e)
    ((a / b) / ((c / d) / e))
    ((a / (b / (c / d))) / e)
    (a / ((b / (c / d)) / e))
    ((a / b) / ((c / d) / e))
    (a / (b / ((c / d) / e)))
    (((a / b) / c) / (d / e))
    ((a / b) / (c / (d / e)))
    ((a / (b / c)) / (d / e))
    (a / ((b / c) / (d / e)))
    ((a / b) / (c / (d / e)))
    (a / (b / (c / (d / e))))
  • 将abcd、运算符所有排列情况下的公式生成,针对 +运算符和 * 运算符,去除类似a*b <=> b*a, (a op b) * c <=> c * (a op b) 这样的重复项


方案二、在递归生成公式的时候,就对 * 和 + 情况下的置换做判断处理

24game
渐入佳境
渐入佳境
帖子: 42
注册时间: 2016年09月02日 22:09
拥有现金: 锁定
Has thanked: 3 times
Been thanked: 15 times
联系:

Re: [征集]算24点全解无重复程序

帖子 #5 24game » 2016年09月02日 22:17

我不管重复的了

输出形式为 逆波兰形式, 为简化编码, 将减法和除法都各拆成了两种运算

如: 5 3 - 即是 5-3=2, 而 3 5 <- 也是一样的 <- 表示反向减法, 即, a b <- 等同于 b a -
另同样的: a b </ 等同于 b a / 例如: 3 12 </ 就是 12 3 / 也就是 12/3=4

以下 C 代码仅适用于解出 表达式二叉树形如下图(任何其他形态, 如能通过若干次调换 同一结点下的左右分支, 最后变为此形态, 都作此归并):
逆波兰表达式形式为: # # O # O # O 其中 # 表示任意数, O 表示任意运算符
Code: [全选] [展开/收缩] [Download] (Untitled.txt)
  1. /*
  2. //       O
  3. //      / \
  4. //     O   O
  5. //    / \
  6. //   O   O
  7. //  / \
  8. // O   O
  9. */


Code: [全选] [展开/收缩] [Download] (Untitled.c)
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. typedef struct rational_number
  5. {
  6.     int numerator, denominator;
  7. } Rational;
  8.  
  9. Rational new_Rational(int n, int d)
  10. {
  11.     Rational r;
  12.     r.numerator = n;
  13.     r.denominator = d;
  14.     return r;
  15. }
  16.  
  17. enum oper
  18. {
  19.     add = 1, rev_subtract, subtract, multiply, rev_division, division
  20. };
  21.  
  22. Rational calc(Rational a, Rational b, int t)
  23. {
  24.  
  25.     if (!a.denominator || !b.denominator) return new_Rational(0, 0);
  26.  
  27.     if (t == division && b.numerator == 0) return new_Rational(0, 0);
  28.  
  29.     switch (t)
  30.     {
  31.     case add:
  32.         return new_Rational(a.numerator * b.denominator + b.numerator * a.denominator, a.denominator * b.denominator);
  33.         break;
  34.  
  35.     case rev_subtract:
  36.         return calc(b, a, subtract);
  37.         break;
  38.  
  39.     case subtract:
  40.         return new_Rational(a.numerator * b.denominator - b.numerator * a.denominator, a.denominator * b.denominator);
  41.         break;
  42.  
  43.     case multiply:
  44.         return new_Rational(a.numerator * b.numerator, a.denominator * b.denominator);
  45.         break;
  46.  
  47.     case rev_division:
  48.         return calc(b, a, division);
  49.         break;
  50.  
  51.     case division:
  52.         return new_Rational(a.numerator * b.denominator, a.denominator * b.numerator);
  53.         break;
  54.     }
  55.  
  56.     return new_Rational(0, 0);
  57. }
  58.  
  59. void writeExp(int exp[], int len)
  60. {
  61.     int i;
  62.     for (i = 0; i < len; i++)
  63.     {
  64.         if (i > 0 && ~i & 1)
  65.         {
  66.             switch (exp[i])
  67.             {
  68.             case add:
  69.                 printf("+");
  70.                 break;
  71.             case rev_subtract:
  72.                 printf("<-");
  73.                 break;
  74.             case subtract:
  75.                 printf("-");
  76.                 break;
  77.             case multiply:
  78.                 printf("*");
  79.                 break;
  80.             case rev_division:
  81.                 printf("</");
  82.                 break;
  83.             case division:
  84.                 printf("/");
  85.                 break;
  86.             }
  87.         }
  88.         else
  89.         {
  90.             printf("%d", exp[i]);
  91.         }
  92.  
  93.         if (i < len - 1) printf(" ");
  94.     }
  95.     printf("\n");
  96. }
  97.  
  98. int main()
  99. {
  100.     int datas[] = {4,7,8,8};
  101.  
  102.     int cnt = sizeof (datas) / sizeof (datas[0]);
  103.     int len = cnt * 2 - 1;
  104.     int pMAX = cnt * 2 - 2;
  105.  
  106.     int used[cnt], exp[len], pds[len], opr[len], p, i;
  107.     Rational result[len];
  108.  
  109.     for (i = 0; i < cnt; i++)
  110.     {
  111.         for (p = 0; p < cnt; p++) used[p] = 0;
  112.  
  113.         p = 0;
  114.         pds[p] = i;
  115.         used[pds[p]] = 1;
  116.         exp[p] = datas[pds[p]];
  117.  
  118.         result[p] = new_Rational(exp[p], 1);
  119.  
  120.         opr[p] = 0;
  121.  
  122.         do
  123.         {
  124.             if (~p & 1)
  125.             {
  126.  
  127.                 if (opr[p] > division)
  128.                 {
  129.                     p--;
  130.  
  131.                     used[pds[p]] = 0; // 释放当前操作数
  132.  
  133.                     // 搜索直到第一个可用数或出界
  134.                     pds[p]++;
  135.                     while (pds[p] < cnt)
  136.                     {
  137.                         if (used[pds[p]]) pds[p]++;
  138.                         else break;
  139.                     }
  140.                 }
  141.                 else
  142.                 {
  143.  
  144.                     if (p > 0)
  145.                     {
  146.                         exp[p] = opr[p];
  147.  
  148.                         result[p] = calc(result[p - 2], new_Rational(exp[p - 1], 1), exp[p]);
  149.                     }
  150.  
  151.                     if (p >= pMAX)
  152.                     {
  153.                         // 检测并输出
  154.                         if (/* 1 || */ (result[p].denominator != 0 && result[p].denominator * 24 == result[p].numerator))
  155.                             writeExp(exp, sizeof (exp) / sizeof (exp[0]));
  156.  
  157.                         opr[p]++;
  158.                     }
  159.                     else
  160.                     {
  161.                         p++;
  162.                         pds[p] = 0;
  163.                         do
  164.                         {
  165.                             if (used[pds[p]]) pds[p]++;
  166.                             else break;
  167.                         }
  168.                         while (pds[p] < cnt);
  169.                     }
  170.                 }
  171.  
  172.             }
  173.             else
  174.             {
  175.  
  176.                 if (pds[p] >= cnt)
  177.                 {
  178.                     p--;
  179.                     opr[p]++;
  180.                 }
  181.                 else
  182.                 {
  183.                     used[pds[p]] = 1;
  184.                     exp[p] = datas[pds[p]];
  185.  
  186.                     p++;
  187.                     opr[p] = add;
  188.                 }
  189.             }
  190.  
  191.         }
  192.         while (p > 0);
  193.     }
  194.  
  195.     printf("Hello world!\n");
  196.     return 0;
  197. }
上次由 24game 在 2016年09月03日 16:42,总共编辑 1 次。

头像
523066680
Administrator
Administrator
帖子: 340
注册时间: 2016年07月19日 12:14
拥有现金: 锁定
储蓄: 锁定
Has thanked: 30 times
Been thanked: 27 times
联系:

Re: [征集]算24点全解无重复程序

帖子 #6 523066680 » 2016年09月02日 22:27

24game 写了:

学习了,原来有这种表达方式(逆波兰)。
我还在考虑能不能先生成所有公式的模板,然后用正则表达式筛选剔除重复项。

24game
渐入佳境
渐入佳境
帖子: 42
注册时间: 2016年09月02日 22:09
拥有现金: 锁定
Has thanked: 3 times
Been thanked: 15 times
联系:

Re: [征集]算24点全解无重复程序

帖子 #7 24game » 2016年09月02日 23:34

523066680 写了:
24game 写了:
523..


我的算法有漏洞, 例如:
不可能 解出 2*6+2*6, 这个的逆波兰式为: 2 6 * 2 6 * +

因为我的算法只能生成: # # O # O # O # O ... 这样的逆波兰式, 其中 # 表示任意操作数, O 表示任意二元运算符 , 所以只能生成部分解, 而不是完全解

24game
渐入佳境
渐入佳境
帖子: 42
注册时间: 2016年09月02日 22:09
拥有现金: 锁定
Has thanked: 3 times
Been thanked: 15 times
联系:

Re: [征集]算24点全解无重复程序

帖子 #8 24game » 2016年09月03日 13:16

数的总数: S
所有运算符都是二元运算符, 全表达式是一个 叶结点总数为 S, 度为 2 的总数为 S - 1 的二叉树,
如果不考虑结果=24, 那么, 当 S = 4 时, 这个二叉树至少会表现成两种形态(左右对称形态归并成一种了):
Code: [全选] [展开/收缩] [Download] (Untitled.txt)
  1. A
  2.       O
  3.      / \
  4.     O   O
  5.    / \
  6.   O   O
  7.  / \
  8. O   O
  9.  
  10. B
  11.        O
  12.       / \
  13.      /   \
  14.     O     O
  15.    / \   / \
  16.   O   O O   O

我上面的C代码, 仅有A形态

所有 参与运算的整数任意排列组合到所有的叶结点上, 而所有度为 2 的结点上是任意的二元运算符

当 S > 4 时, 全表达式仍是一个 叶结点总数为 S, 度为 2 的总数为 S - 1 的二叉树, 但可能的形态将更多, 而不止两个, 算法需要能表达出任何可能的形态, 并在其上把所有数字任意排列组合到所有叶结点上, 所有运算符任意放到度为 2 的结点上

有些组合没有 A 形态的解, 例:
1 5 5 9
有 B 形态的解
(1+5)*(9-5)
逆波兰表达式为
1 5 + 9 5 - *

以下 C 代码可解出 两种 形态的解, 参与计算的整数总数仅限 4 个, 不适于其他个数

附几个参考链接:
https://zh.wikipedia.org/wiki/24%E7%82% ... 0.E7.AE.97
http://www.puzzlesland.com/games/24/
https://en.wikipedia.org/wiki/Maths24#Rules
http://www.mathplayground.com/make_24.html
http://www.4nums.com/game/


Code: [全选] [展开/收缩] [Download] (Untitled.c)
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. typedef struct rational_number
  5. {
  6.     int numerator, denominator;
  7. } Rational;
  8.  
  9. Rational new_Rational(int n, int d)
  10. {
  11.     Rational r;
  12.     r.numerator = n;
  13.     r.denominator = d;
  14.     return r;
  15. }
  16.  
  17. enum oper
  18. {
  19.     add = 1, rev_subtract, subtract, multiply, rev_division, division
  20. };
  21.  
  22. Rational calc(Rational a, Rational b, int t)
  23. {
  24.  
  25.     if (!a.denominator || !b.denominator) return new_Rational(0, 0);
  26.  
  27.     if (t == division && b.numerator == 0) return new_Rational(0, 0);
  28.  
  29.     switch (t)
  30.     {
  31.     case add:
  32.         return new_Rational(a.numerator * b.denominator + b.numerator * a.denominator, a.denominator * b.denominator);
  33.         break;
  34.  
  35.     case rev_subtract:
  36.         return calc(b, a, subtract);
  37.         break;
  38.  
  39.     case subtract:
  40.         return new_Rational(a.numerator * b.denominator - b.numerator * a.denominator, a.denominator * b.denominator);
  41.         break;
  42.  
  43.     case multiply:
  44.         return new_Rational(a.numerator * b.numerator, a.denominator * b.denominator);
  45.         break;
  46.  
  47.     case rev_division:
  48.         return calc(b, a, division);
  49.         break;
  50.  
  51.     case division:
  52.         return new_Rational(a.numerator * b.denominator, a.denominator * b.numerator);
  53.         break;
  54.     }
  55.  
  56.     return new_Rational(0, 0);
  57. }
  58.  
  59. void writeExp(int exp[], int len, char t)
  60. {
  61.     int i;
  62.     for (i = 0; i < len; i++)
  63.     {
  64.         if (i > 0 && ((t=='A' && ~i & 1) || (t=='B' && (i==2 || i==5 || i==6  ))))
  65.         {
  66.             switch (exp[i])
  67.             {
  68.             case add:
  69.                 printf("+");
  70.                 break;
  71.             case rev_subtract:
  72.                 printf("<-");
  73.                 break;
  74.             case subtract:
  75.                 printf("-");
  76.                 break;
  77.             case multiply:
  78.                 printf("*");
  79.                 break;
  80.             case rev_division:
  81.                 printf("</");
  82.                 break;
  83.             case division:
  84.                 printf("/");
  85.                 break;
  86.             }
  87.         }
  88.         else
  89.         {
  90.             printf("%d", exp[i]);
  91.         }
  92.  
  93.         if (i < len - 1) printf(" ");
  94.     }
  95.     printf("\n");
  96. }
  97.  
  98. int main()
  99. {
  100.     int datas[] = {1,5,6,12};
  101.  
  102.     int cnt = sizeof (datas) / sizeof (datas[0]);
  103.     int len = cnt * 2 - 1;
  104.     int pMAX = cnt * 2 - 2;
  105.  
  106.     int used[cnt], exp[len], pds[len], opr[len], p, i, sumA, sumB;
  107.     Rational result[len];
  108.  
  109.  
  110.     while (1)
  111.     {
  112.         printf("input 4 numbers, separate by space\n");
  113.         scanf("%d%d%d%d", &datas[0], &datas[1], &datas[2], &datas[3]);
  114.  
  115.         sumA = sumB = 0;
  116.  
  117.         for (i = 0; i < cnt; i++)
  118.         {
  119.  
  120.  
  121.  
  122. // A 形态
  123.  
  124. /*
  125. //       O
  126. //      / \
  127. //     O   O
  128. //    / \
  129. //   O   O
  130. //  / \
  131. // O   O
  132. */
  133.  
  134.  
  135.             for (p = 0; p < cnt; p++) used[p] = 0;
  136.  
  137.             p = 0;
  138.             pds[p] = i;
  139.             used[pds[p]] = 1;
  140.             exp[p] = datas[pds[p]];
  141.  
  142.             result[p] = new_Rational(exp[p], 1);
  143.  
  144.             opr[p] = 0;
  145.  
  146.             do
  147.             {
  148.                 if (~p & 1)
  149.                 {
  150.  
  151.                     if (opr[p] > division)
  152.                     {
  153.                         p--;
  154.  
  155.                         used[pds[p]] = 0; // 释放当前操作数
  156.  
  157.                         // 搜索直到第一个可用数或出界
  158.                         pds[p]++;
  159.                         while (pds[p] < cnt)
  160.                         {
  161.                             if (used[pds[p]]) pds[p]++;
  162.                             else break;
  163.                         }
  164.                     }
  165.                     else
  166.                     {
  167.  
  168.                         if (p > 0)
  169.                         {
  170.                             exp[p] = opr[p];
  171.  
  172.                             result[p] = calc(result[p - 2], new_Rational(exp[p - 1], 1), exp[p]);
  173.                         }
  174.  
  175.                         if (p >= pMAX)
  176.                         {
  177.                             // 检测并输出
  178.                             if ((result[p].denominator != 0 && result[p].denominator * 24 == result[p].numerator)) {
  179.                                 writeExp(exp, sizeof (exp) / sizeof (exp[0]), 'A');
  180.                                 sumA++;
  181.                             }
  182.  
  183.                             opr[p]++;
  184.                         }
  185.                         else
  186.                         {
  187.                             p++;
  188.                             pds[p] = 0;
  189.                             do
  190.                             {
  191.                                 if (used[pds[p]]) pds[p]++;
  192.                                 else break;
  193.                             }
  194.                             while (pds[p] < cnt);
  195.                         }
  196.                     }
  197.  
  198.                 }
  199.                 else
  200.                 {
  201.  
  202.                     if (pds[p] >= cnt)
  203.                     {
  204.                         p--;
  205.                         opr[p]++;
  206.                     }
  207.                     else
  208.                     {
  209.                         used[pds[p]] = 1;
  210.                         exp[p] = datas[pds[p]];
  211.  
  212.                         p++;
  213.                         opr[p] = add;
  214.                     }
  215.                 }
  216.  
  217.             }
  218.             while (p > 0);
  219.  
  220.  
  221. //  B 形态
  222. //
  223. //   a  b   +-* /   c   d   +-* /    +-* /
  224. //      c           d
  225. //      d
  226. //
  227. //   0  1   2       3   4    5       6
  228.  
  229.  
  230.             for (p = 0; p < cnt; p++) used[p] = 0;
  231.  
  232.             p = 0;
  233.             pds[p] = i;
  234.             used[pds[p]] = 1;
  235.             exp[p] = datas[pds[p]];
  236.  
  237.             result[p] = new_Rational(exp[p], 1);
  238.  
  239.             opr[p] = 0;
  240.  
  241.             do
  242.             {
  243.                 if (p==2 || p==5 || p==6)
  244.                 {
  245.                     if (opr[p] > division)
  246.                     {
  247.                         p--;
  248.  
  249.                         if (p==1 || p==4) {
  250.  
  251.                             used[pds[p]] = 0; // 释放当前操作数
  252.  
  253.                             // 搜索直到第一个可用数或出界
  254.                             pds[p]++;
  255.                             while (pds[p] < cnt)
  256.                             {
  257.                                 if (used[pds[p]]) pds[p]++;
  258.                                 else break;
  259.                             }
  260.                         } else {
  261.  
  262.                             opr[p]++;
  263.  
  264.                         }
  265.                     }
  266.                     else
  267.                     {
  268.  
  269.                         if (p > 0)
  270.                         {
  271.                             exp[p] = opr[p];
  272.  
  273.                             if (p==2 || p==5) {
  274.                                 result[p] = calc(new_Rational(exp[p - 2], 1), new_Rational(exp[p - 1], 1), exp[p]);
  275.                             } else {
  276.                                 result[p] = calc(result[2], result[5], exp[p]);
  277.                             }
  278.                         }
  279.  
  280.                         if (p >= pMAX)
  281.                         {
  282.                             // 检测并输出
  283.                             if (/* 1 || */ (result[p].denominator != 0 && result[p].denominator * 24 == result[p].numerator)) {
  284.                                 writeExp(exp, sizeof (exp) / sizeof (exp[0]), 'B');
  285.                                 sumB++;
  286.                             }
  287.  
  288.                             opr[p]++;
  289.                         }
  290.                         else
  291.                         {
  292.                             if (p==2){
  293.                                 p++;
  294.                                 pds[p] = 0;
  295.                                 do
  296.                                 {
  297.                                     if (used[pds[p]]) pds[p]++;
  298.                                     else break;
  299.                                 }
  300.                                 while (pds[p] < cnt);
  301.                             } else {
  302.                                 p++;
  303.                                 opr[p] = add;
  304.                             }
  305.                         }
  306.                     }
  307.  
  308.                 }
  309.                 else
  310.                 {
  311.                     if (pds[p] >= cnt)
  312.                     {
  313.                         if (p==3){
  314.                             p--;
  315.                             opr[p]++;
  316.                         } else if (p==4) {
  317.  
  318.                             p--;
  319.                             used[pds[p]] = 0; // 释放当前操作数
  320.  
  321.                             // 搜索直到第一个可用数或出界
  322.                             pds[p]++;
  323.                             while (pds[p] < cnt)
  324.                             {
  325.                                 if (used[pds[p]]) pds[p]++;
  326.                                 else break;
  327.                             }
  328.  
  329.                         } else { // p==1
  330.                             p--;  // p <== 0 will exit while (p > 0);
  331.                         }
  332.                     }
  333.                     else
  334.                     {
  335.                         used[pds[p]] = 1;
  336.                         exp[p] = datas[pds[p]];
  337.  
  338.                         if (p==1 || p==4) {
  339.                             p++;
  340.                             opr[p] = add;
  341.                         } else {  // p==0 || p==3
  342.                             p++;
  343.                             pds[p] = 0;
  344.                             do
  345.                             {
  346.                                 if (used[pds[p]]) pds[p]++;
  347.                                 else break;
  348.                             }
  349.                             while (pds[p] < cnt);
  350.                         }
  351.  
  352.                     }
  353.                 }
  354.  
  355.             }
  356.             while (p > 0);
  357.  
  358.         }
  359.  
  360.         if (sumA + sumB == 0) {
  361.             printf("NOT found any solution\n\n");
  362.         } else {
  363.             printf("A form: %d  B form: %d\n\n", sumA, sumB);
  364.         }
  365.  
  366.     }
  367.     return 0;
  368. }

24game
渐入佳境
渐入佳境
帖子: 42
注册时间: 2016年09月02日 22:09
拥有现金: 锁定
Has thanked: 3 times
Been thanked: 15 times
联系:

Re: [征集]算24点全解无重复程序

帖子 #9 24game » 2016年09月03日 18:05

4 到 6 叶的 二叉树 形态:

(任何能通过若干次调换同一结点上的两个分支(即左右互换)而变成同一形态的归并成一种)
4 叶的有 2 种
5 叶的有 3 种
6 叶的有 6 种

Code: [全选] [展开/收缩] [Download] (Untitled.txt)
  1. 4 叶 4 层
  2.       O
  3.      / \
  4.     O   O
  5.    / \
  6.   O   O
  7.  / \
  8. O   O
  9.  
  10. 4 叶 3 层
  11.      O
  12.     / \
  13.    /   \
  14.   O     O
  15.  / \   / \
  16. O   O O   O
  17.  
  18. 5 叶 5 层
  19.         O
  20.        / \
  21.       O   O
  22.      / \
  23.     O   O
  24.    / \
  25.   O   O
  26.  / \
  27. O   O
  28.  
  29. 5 叶 4 层 A
  30.        O
  31.       / \
  32.      /   \
  33.     O     O
  34.    / \   / \
  35.   O   O O   O
  36.  / \
  37. O   O
  38.  
  39. 5 叶 4 层 B
  40.         O
  41.        / \
  42.       /   \
  43.      O     O
  44.     / \
  45.    /   \
  46.   O     O
  47.  / \   / \
  48. O   O O   O
  49.  
  50. 6 叶 6 层
  51.           O
  52.          / \
  53.         O   O
  54.        / \
  55.       O   O
  56.      / \
  57.     O   O
  58.    / \
  59.   O   O
  60.  / \
  61. O   O
  62.  
  63. 6 叶 5 层 A
  64.          O
  65.         / \
  66.        /   \
  67.       O     O
  68.      / \   / \
  69.     O   O O   O
  70.    / \
  71.   O   O
  72.  / \
  73. O   O
  74.  
  75. 6 叶 5 层 B
  76.          O
  77.         / \
  78.        O   O
  79.       / \
  80.      /   \
  81.     O     O
  82.    / \   / \
  83.   O   O O   O
  84.  / \
  85. O   O
  86.  
  87. 6 叶 5 层 C
  88.          O
  89.         / \
  90.        O   O
  91.       / \
  92.      O   O
  93.     / \
  94.    /   \
  95.   O     O
  96.  / \   / \
  97. O   O O   O
  98.  
  99. 6 叶 4 层 A
  100.           O
  101.          / \
  102.         /   \
  103.        /     \
  104.       O       O
  105.      / \      /\
  106.     /   \    /  \
  107.    O     O  O    O
  108.   /\     /\
  109.  /  \   /  \
  110. O    O O    O
  111.  
  112. 6 叶 4 层 B
  113.           O
  114.          / \
  115.         /   \
  116.        /     \
  117.       O       O
  118.      / \      /\
  119.     /   \    /  \
  120.    O     O  O    O
  121.   /\       /\
  122.  /  \     /  \
  123. O    O   O    O
上次由 24game 在 2016年09月04日 10:23,总共编辑 1 次。

24game
渐入佳境
渐入佳境
帖子: 42
注册时间: 2016年09月02日 22:09
拥有现金: 锁定
Has thanked: 3 times
Been thanked: 15 times
联系:

Re: [征集]算24点全解无重复程序

帖子 #10 24game » 2016年09月04日 00:52

加法, 乘法具有交换律, 对这两种运算的表达式 全部进行 左 右式 可能必要的置换, 可以将许多不同的中缀表达式统一化

经过统一处理后的所有中缀表达式, 作相同与否的比较即可去重, 已不困难

本楼 C 代码, 输出 逆波兰, 中缀, 统一处理后的中缀 三种形式 的 表达式


输入
Code: [全选] [展开/收缩] [Download] (Untitled.txt)
  1. 1  5  5  9


输出
Code: [全选] [展开/收缩] [Download] (Untitled.txt)
  1. 1 5 + 5 9 <- *          (1 + 5) * (9 - 5)               (1 + 5) * (9 - 5)
  2. 1 5 + 9 5 - *           (1 + 5) * (9 - 5)               (1 + 5) * (9 - 5)
  3. 1 5 + 5 9 <- *          (1 + 5) * (9 - 5)               (1 + 5) * (9 - 5)
  4. 1 5 + 9 5 - *           (1 + 5) * (9 - 5)               (1 + 5) * (9 - 5)
  5. 5 1 + 5 9 <- *          (5 + 1) * (9 - 5)               (1 + 5) * (9 - 5)
  6. 5 1 + 9 5 - *           (5 + 1) * (9 - 5)               (1 + 5) * (9 - 5)
  7. 5 9 <- 1 5 + *          (9 - 5) * (1 + 5)               (1 + 5) * (9 - 5)
  8. 5 9 <- 5 1 + *          (9 - 5) * (5 + 1)               (1 + 5) * (9 - 5)
  9. 5 1 + 5 9 <- *          (5 + 1) * (9 - 5)               (1 + 5) * (9 - 5)
  10. 5 1 + 9 5 - *           (5 + 1) * (9 - 5)               (1 + 5) * (9 - 5)
  11. 5 9 <- 1 5 + *          (9 - 5) * (1 + 5)               (1 + 5) * (9 - 5)
  12. 5 9 <- 5 1 + *          (9 - 5) * (5 + 1)               (1 + 5) * (9 - 5)
  13. 9 5 - 1 5 + *           (9 - 5) * (1 + 5)               (1 + 5) * (9 - 5)
  14. 9 5 - 5 1 + *           (9 - 5) * (5 + 1)               (1 + 5) * (9 - 5)
  15. 9 5 - 1 5 + *           (9 - 5) * (1 + 5)               (1 + 5) * (9 - 5)
  16. 9 5 - 5 1 + *           (9 - 5) * (5 + 1)               (1 + 5) * (9 - 5)
  17. A form: 0  B form: 16




本楼代码在输入
Code: [全选] [展开/收缩] [Download] (Untitled.txt)
  1. 3  3  3  8


得输出

Code: [全选] [展开/收缩] [Download] (Untitled.txt)
  1. (3 + 3 - 3) * 8
  2. (3 - (3 - 3)) * 8
  3. (3 - 3 + 8) * 3
  4. (8 - (3 - 3)) * 3
  5. 8 / (3 / (3 * 3))
  6. 3 * 3 / 3 * 8
  7. 3 * 3 * 8 / 3
  8. 3 / (3 / 3) * 8
  9. 8 / (3 / 3 / 3)
  10. 3 * 8 / (3 / 3)
  11. 3 / (3 / 3 / 8)
  12. (3 + 8 - 3) * 3
  13. (3 - (3 - 8)) * 3
  14. 3 + 3 * 8 - 3
  15. 3 - (3 - 3 * 8)
  16. 3 / (3 / (3 * 8))
  17. 3 * 3 / (3 / 8)
  18. 3 / (3 / 8 / 3)
  19. 3 * 8 + 3 - 3
  20. 3 * 8 - (3 - 3)
  21. 3 * 8 * 3 / 3


如果做 去括号(括号内的减法, 除法反向), 同优先级运算串联时次序置换, 可以将上面结果归为 4 类(同一类中都认为是同一形式)

(3 + 3 - 3) * 8
Code: [全选] [展开/收缩] [Download] (Untitled.txt)
  1. (3 + 3 - 3) * 8
  2. (3 - (3 - 3)) * 8


(3 - 3 + 8) * 3
Code: [全选] [展开/收缩] [Download] (Untitled.txt)
  1. (3 - 3 + 8) * 3
  2. (8 - (3 - 3)) * 3
  3. (3 + 8 - 3) * 3
  4. (3 - (3 - 8)) * 3


3 * 8 * 3 / 3
Code: [全选] [展开/收缩] [Download] (Untitled.txt)
  1. 8 / (3 / (3 * 3))
  2. 3 * 3 / 3 * 8
  3. 3 * 3 * 8 / 3
  4. 3 / (3 / 3) * 8
  5. 8 / (3 / 3 / 3)
  6. 3 * 8 / (3 / 3)
  7. 3 / (3 / 3 / 8)
  8. 3 / (3 / (3 * 8))
  9. 3 * 3 / (3 / 8)
  10. 3 / (3 / 8 / 3)
  11. 3 * 8 * 3 / 3


3 * 8 + 3 - 3
Code: [全选] [展开/收缩] [Download] (Untitled.txt)
  1. 3 + 3 * 8 - 3
  2. 3 - (3 - 3 * 8)
  3. 3 * 8 + 3 - 3
  4. 3 * 8 - (3 - 3)



Code: [全选] [展开/收缩] [Download] (Untitled.c)
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #define LEN (7)
  5. #define LEN1 (6*6*6*4*3*2*2)
  6.  
  7. // const int LEN1 = (6*6*6*4*3*2*2);
  8.  
  9. typedef struct rational_number
  10. {
  11.     int numerator, denominator;
  12. } Rational;
  13.  
  14. typedef struct binary_expression
  15. {
  16.     int val, op_type;
  17.     char *Infix, *stdInfix;
  18.     struct binary_expression *left, * right;
  19. } B_exp;
  20.  
  21. char *stdInfixs[LEN1];
  22. int cnt_stdInfixs;
  23.  
  24. Rational new_Rational(int n, int d)
  25. {
  26.     Rational r;
  27.     r.numerator = n;
  28.     r.denominator = d;
  29.     return r;
  30. }
  31.  
  32. enum oper
  33. {
  34.     none = 0, add, rev_subtract, subtract, multiply, rev_division, division
  35. };
  36.  
  37. char *operators[] =
  38. {
  39.     "", " + ", " <- ", " - ", " * ", " </ ", " / "
  40. };
  41.  
  42. char *oprs[] =
  43. {
  44.     "","+","<-","-","*","</","/"
  45. };
  46.  
  47. enum exp_type
  48. {
  49.     number = 0, operator
  50. };
  51.  
  52. Rational calc(Rational a, Rational b, int t)
  53. {
  54.  
  55.     if (!a.denominator || !b.denominator) return new_Rational(0, 0);
  56.  
  57.     if (t == division && b.numerator == 0) return new_Rational(0, 0);
  58.  
  59.     switch (t)
  60.     {
  61.     case add:
  62.         return new_Rational(a.numerator * b.denominator + b.numerator * a.denominator, a.denominator * b.denominator);
  63.         break;
  64.  
  65.     case rev_subtract:
  66.         return calc(b, a, subtract);
  67.         break;
  68.  
  69.     case subtract:
  70.         return new_Rational(a.numerator * b.denominator - b.numerator * a.denominator, a.denominator * b.denominator);
  71.         break;
  72.  
  73.     case multiply:
  74.         return new_Rational(a.numerator * b.numerator, a.denominator * b.denominator);
  75.         break;
  76.  
  77.     case rev_division:
  78.         return calc(b, a, division);
  79.         break;
  80.  
  81.     case division:
  82.         return new_Rational(a.numerator * b.denominator, a.denominator * b.numerator);
  83.         break;
  84.     }
  85.  
  86.     return new_Rational(0, 0);
  87. }
  88.  
  89. int opr_level(int opr)
  90. {
  91.     if (opr < add) return 0;
  92.     else if (opr >= multiply) return 2;
  93.     else return 1;
  94. }
  95.  
  96. int opr_dir_sensitive(int opr)
  97. {
  98.     if (opr == none || opr == add || opr == multiply) return 0;
  99.     else return 1;
  100. }
  101.  
  102. char * add_parentheses(char * str)
  103. {
  104.     char temp[100] = "";
  105.     return strcat(strcpy(str, strcat(strcpy(temp, "("), str)), ")");
  106. }
  107.  
  108. void writeExp(int exp[], int exp_t[], int len)
  109. {
  110.  
  111.     // code for 中缀表达式 begin
  112.     B_exp bin_expS[LEN], *bin_expStk[LEN];
  113.     int ps = 0;
  114.     // code for 中缀表达式 end
  115.  
  116.     int i;
  117.     for (i = 0; i < len; i++)
  118.     {
  119.  
  120.         // code for 中缀表达式 begin
  121.         // init bin_expS[i];
  122.  
  123.         // 中缀式标准式: 每一个有交换律运算的 左式 和 右式 比较, 小的做左式
  124.  
  125.         bin_expS[i].Infix = (char *) malloc(sizeof (char) * 100);
  126.         bin_expS[i].stdInfix = (char *) malloc(sizeof (char) * 100); // 标准式
  127.  
  128.  
  129.         *(bin_expS[i].Infix) = '\0';
  130.         *(bin_expS[i].stdInfix) = '\0';
  131.  
  132.         bin_expS[i].val = 0;
  133.         bin_expS[i].op_type = none;
  134.         bin_expS[i].left = NULL;
  135.         bin_expS[i].right = NULL;
  136.  
  137.         // code for 中缀表达式 end
  138.  
  139.  
  140.  
  141.         // if (i > 0 && ((t=='A' && ~i & 1) || (t=='B' && (i==2 || i==5 || i==6  ))))
  142.         if (exp_t[i] == operator)
  143.         {
  144.             printf("%s", oprs[exp[i]]);
  145.  
  146.             // code for 中缀表达式 begin
  147.             if (exp[i] == rev_division || exp[i] == rev_subtract)
  148.             {
  149.                 bin_expS[i].op_type = exp[i] + 1;
  150.                 bin_expS[i].left = bin_expStk[ps - 1];
  151.                 bin_expS[i].right = bin_expStk[ps - 2];
  152.             }
  153.             else
  154.             {
  155.                 bin_expS[i].op_type = exp[i];
  156.                 bin_expS[i].right = bin_expStk[ps - 1];
  157.                 bin_expS[i].left = bin_expStk[ps - 2];
  158.             }
  159.             ps -= 2;
  160.             bin_expStk[ps++] = &(bin_expS[i]);
  161.  
  162.  
  163.             /*  加括号原则
  164.             1
  165.  
  166.             子运算的运算优先级 低于 当前运算
  167.             + - 低于 * /
  168.  
  169.             2
  170.  
  171.             子运算的运算优先级 同于 当前运算
  172.             子运算 是 当前运算 - 或者 / 的右项( <-  </ 的左项), 且当前运算是有向运算(无交换律的运算)
  173.  
  174.             即, 当前运算 是 - 或者 /  或者 <- 或者 </
  175.  
  176.             而子运算 是 - 的 减数, 或者是 / 的除数
  177.  
  178.              */
  179.  
  180.             if (bin_expS[i].left -> op_type != none)
  181.                 if (opr_level(bin_expS[i].left -> op_type) < opr_level(bin_expS[i].op_type))
  182.                 {
  183.                     add_parentheses(bin_expS[i].left ->Infix);
  184.                     add_parentheses(bin_expS[i].left ->stdInfix);
  185.                 }
  186.  
  187.             if (bin_expS[i].right -> op_type != none)
  188.                 if ((opr_level(bin_expS[i].right -> op_type) < opr_level(bin_expS[i].op_type))
  189.                         ||
  190.                         (
  191.                             (opr_level(bin_expS[i].right -> op_type) == opr_level(bin_expS[i].op_type))
  192.                             &&
  193.                             opr_dir_sensitive(bin_expS[i].op_type)
  194.                         )
  195.                    )
  196.                 {
  197.                     add_parentheses(bin_expS[i].right ->Infix);
  198.                     add_parentheses(bin_expS[i].right ->stdInfix);
  199.  
  200.                 }
  201.  
  202.             strcat(strcat(strcpy(bin_expS[i].Infix, bin_expS[i].left ->Infix), operators[bin_expS[i].op_type]),
  203.                    bin_expS[i].right->Infix);
  204.  
  205.             if (opr_dir_sensitive(bin_expS[i].op_type))
  206.             {
  207.                 strcat(strcat(strcpy(bin_expS[i].stdInfix, bin_expS[i].left ->stdInfix), operators[bin_expS[i].op_type]),
  208.                        bin_expS[i].right->stdInfix);
  209.             }
  210.             else
  211.             {
  212.  
  213.                 if (strcmp(bin_expS[i].right ->stdInfix, bin_expS[i].left ->stdInfix) < 0)
  214.                 {
  215.                     strcat(strcat(strcpy(bin_expS[i].stdInfix, bin_expS[i].right ->stdInfix), operators[bin_expS[i].op_type]),
  216.                            bin_expS[i].left->stdInfix);
  217.                 }
  218.                 else
  219.                 {
  220.                     strcat(strcat(strcpy(bin_expS[i].stdInfix, bin_expS[i].left ->stdInfix), operators[bin_expS[i].op_type]),
  221.                            bin_expS[i].right->stdInfix);
  222.                 }
  223.             }
  224.  
  225.             // code for 中缀表达式 end
  226.  
  227.  
  228.         }
  229.         else
  230.         {
  231.             printf("%d", exp[i]);
  232.  
  233.  
  234.             // code for 中缀表达式 begin
  235.  
  236.             bin_expS[i].val = exp[i];
  237.             bin_expS[i].op_type = none;
  238.  
  239.             sprintf(bin_expS[i].Infix, "%d", bin_expS[i].val);
  240.             sprintf(bin_expS[i].stdInfix, "%d", bin_expS[i].val);
  241.  
  242.             // 数压栈
  243.             bin_expStk[ps++] = &(bin_expS[i]);
  244.  
  245.             // code for 中缀表达式 end
  246.         }
  247.  
  248.         if (i < len - 1) printf(" ");
  249.  
  250.  
  251.     }
  252.     printf("\t\t%s\t\t%s", bin_expStk[ps - 1]->Infix, bin_expStk[ps - 1]->stdInfix); // 中缀表达式
  253.     printf("\n");
  254.  
  255.     int existing;
  256.     existing = 0;
  257.     for (i=0; i<cnt_stdInfixs; i++)
  258.     {
  259.         if (strcmp(stdInfixs[i], bin_expStk[ps - 1]->stdInfix) == 0)
  260.         {
  261.             existing = 1;
  262.             break;
  263.         }
  264.     }
  265.     if (!existing)
  266.     {
  267.         if (stdInfixs[cnt_stdInfixs] == NULL)
  268.         {
  269.             stdInfixs[cnt_stdInfixs] = (char *) malloc(sizeof (char) * 100);
  270.             *(stdInfixs[cnt_stdInfixs]) = '\0';
  271.         }
  272.  
  273.         strcpy(stdInfixs[cnt_stdInfixs++], bin_expStk[ps - 1]->stdInfix);
  274.     }
  275. }
  276.  
  277. int main()
  278. {
  279.  
  280.     int datas[] = {1, 5, 5, 9};
  281.  
  282.     int cnt = sizeof (datas) / sizeof (datas[0]);
  283.     int len = cnt * 2 - 1;
  284.     int pMAX = cnt * 2 - 2;
  285.  
  286.     int used[cnt], exp[len], exp_t[len], pds[len], opr[len], p, i, sumA, sumB, L1;
  287.     Rational result[len];
  288.  
  289.  
  290.     for (i=0, L1 = LEN1; i< L1; i++) stdInfixs[i] = NULL;
  291.  
  292.  
  293.     while (1)
  294.     {
  295.         for (i=0, L1 = LEN1; i< L1; i++)
  296.             if (stdInfixs[i] != NULL)
  297.             {
  298.                 free(stdInfixs[i]);
  299.                 stdInfixs[i] = NULL;
  300.             }
  301.  
  302.         cnt_stdInfixs =0;
  303.  
  304.         printf("input 4 numbers, separate by space\n");
  305.         scanf("%d%d%d%d", &datas[0], &datas[1], &datas[2], &datas[3]);
  306.  
  307.         sumA = sumB = 0;
  308.  
  309.         for (i = 0; i < cnt; i++)
  310.         {
  311.  
  312.  
  313.  
  314.             // A 形态
  315.  
  316.             /*
  317.             //       O
  318.             //      / \
  319.             //     O   O
  320.             //    / \
  321.             //   O   O
  322.             //  / \
  323.             // O   O
  324.              */
  325.  
  326.  
  327.             for (p = 0; p < cnt; p++) used[p] = 0;
  328.  
  329.             p = 0;
  330.             pds[p] = i;
  331.             used[pds[p]] = 1;
  332.             exp[p] = datas[pds[p]];
  333.             exp_t[p] = number;
  334.  
  335.             result[p] = new_Rational(exp[p], 1);
  336.  
  337.             opr[p] = 0;
  338.  
  339.             do
  340.             {
  341.                 if (~p & 1)
  342.                 {
  343.  
  344.                     if (opr[p] > division)
  345.                     {
  346.                         p--;
  347.  
  348.                         used[pds[p]] = 0; // 释放当前操作数
  349.  
  350.                         // 搜索直到第一个可用数或出界
  351.                         pds[p]++;
  352.                         while (pds[p] < cnt)
  353.                         {
  354.                             if (used[pds[p]]) pds[p]++;
  355.                             else break;
  356.                         }
  357.                     }
  358.                     else
  359.                     {
  360.  
  361.                         if (p > 0)
  362.                         {
  363.                             exp[p] = opr[p];
  364.                             exp_t[p] = operator;
  365.  
  366.                             result[p] = calc(result[p - 2], new_Rational(exp[p - 1], 1), exp[p]);
  367.                         }
  368.  
  369.                         if (p >= pMAX)
  370.                         {
  371.                             // 检测并输出
  372.                             if ((result[p].denominator != 0 && result[p].denominator * 24 == result[p].numerator))
  373.                             {
  374.                                 writeExp(exp, exp_t, sizeof (exp) / sizeof (exp[0]));
  375.                                 sumA++;
  376.                             }
  377.  
  378.                             opr[p]++;
  379.                         }
  380.                         else
  381.                         {
  382.                             p++;
  383.                             pds[p] = 0;
  384.                             do
  385.                             {
  386.                                 if (used[pds[p]]) pds[p]++;
  387.                                 else break;
  388.                             }
  389.                             while (pds[p] < cnt);
  390.                         }
  391.                     }
  392.  
  393.                 }
  394.                 else
  395.                 {
  396.  
  397.                     if (pds[p] >= cnt)
  398.                     {
  399.                         p--;
  400.                         opr[p]++;
  401.                     }
  402.                     else
  403.                     {
  404.                         used[pds[p]] = 1;
  405.                         exp[p] = datas[pds[p]];
  406.                         exp_t[p] = number;
  407.  
  408.                         p++;
  409.                         opr[p] = add;
  410.                     }
  411.                 }
  412.  
  413.             }
  414.             while (p > 0);
  415.  
  416.  
  417.             /*  B 形态
  418.  
  419.             //       O
  420.             //      / \
  421.             //     /   \
  422.             //    O     O
  423.             //   / \   / \
  424.             //  O   O O   O
  425.             //
  426.             //   a  b   +-* /   c   d   +-* /    +-* /
  427.             //      c           d
  428.             //      d
  429.             //
  430.             //   0  1   2       3   4    5       6
  431.             */
  432.  
  433.  
  434.             for (p = 0; p < cnt; p++) used[p] = 0;
  435.  
  436.             p = 0;
  437.             pds[p] = i;
  438.             used[pds[p]] = 1;
  439.             exp[p] = datas[pds[p]];
  440.             exp_t[p] = number;
  441.  
  442.             result[p] = new_Rational(exp[p], 1);
  443.  
  444.             opr[p] = 0;
  445.  
  446.             do
  447.             {
  448.                 if (p == 2 || p == 5 || p == 6)
  449.                 {
  450.                     if (opr[p] > division)
  451.                     {
  452.                         p--;
  453.  
  454.                         if (p == 1 || p == 4)
  455.                         {
  456.  
  457.                             used[pds[p]] = 0; // 释放当前操作数
  458.  
  459.                             // 搜索直到第一个可用数或出界
  460.                             pds[p]++;
  461.                             while (pds[p] < cnt)
  462.                             {
  463.                                 if (used[pds[p]]) pds[p]++;
  464.                                 else break;
  465.                             }
  466.                         }
  467.                         else
  468.                         {
  469.  
  470.                             opr[p]++;
  471.  
  472.                         }
  473.                     }
  474.                     else
  475.                     {
  476.  
  477.                         if (p > 0)
  478.                         {
  479.                             exp[p] = opr[p];
  480.                             exp_t[p] = operator;
  481.  
  482.                             if (p == 2 || p == 5)
  483.                             {
  484.                                 result[p] = calc(new_Rational(exp[p - 2], 1), new_Rational(exp[p - 1], 1), exp[p]);
  485.                             }
  486.                             else
  487.                             {
  488.                                 result[p] = calc(result[2], result[5], exp[p]);
  489.                             }
  490.                         }
  491.  
  492.                         if (p >= pMAX)
  493.                         {
  494.                             // 检测并输出
  495.                             if (/* 1 || */ (result[p].denominator != 0 && result[p].denominator * 24 == result[p].numerator))
  496.                             {
  497.                                 writeExp(exp, exp_t, sizeof (exp) / sizeof (exp[0]));
  498.                                 sumB++;
  499.                             }
  500.  
  501.                             opr[p]++;
  502.                         }
  503.                         else
  504.                         {
  505.                             if (p == 2)
  506.                             {
  507.                                 p++;
  508.                                 pds[p] = 0;
  509.                                 do
  510.                                 {
  511.                                     if (used[pds[p]]) pds[p]++;
  512.                                     else break;
  513.                                 }
  514.                                 while (pds[p] < cnt);
  515.                             }
  516.                             else
  517.                             {
  518.                                 p++;
  519.                                 opr[p] = add;
  520.                             }
  521.                         }
  522.                     }
  523.  
  524.                 }
  525.                 else
  526.                 {
  527.                     if (pds[p] >= cnt)
  528.                     {
  529.                         if (p == 3)
  530.                         {
  531.                             p--;
  532.                             opr[p]++;
  533.                         }
  534.                         else if (p == 4)
  535.                         {
  536.  
  537.                             p--;
  538.                             used[pds[p]] = 0; // 释放当前操作数
  539.  
  540.                             // 搜索直到第一个可用数或出界
  541.                             pds[p]++;
  542.                             while (pds[p] < cnt)
  543.                             {
  544.                                 if (used[pds[p]]) pds[p]++;
  545.                                 else break;
  546.                             }
  547.  
  548.                         }
  549.                         else   // p==1
  550.                         {
  551.                             p--; // p <== 0 will exit while (p > 0);
  552.                         }
  553.                     }
  554.                     else
  555.                     {
  556.                         used[pds[p]] = 1;
  557.                         exp[p] = datas[pds[p]];
  558.                         exp_t[p] = number;
  559.  
  560.                         if (p == 1 || p == 4)
  561.                         {
  562.                             p++;
  563.                             opr[p] = add;
  564.                         }
  565.                         else   // p==0 || p==3
  566.                         {
  567.                             p++;
  568.                             pds[p] = 0;
  569.                             do
  570.                             {
  571.                                 if (used[pds[p]]) pds[p]++;
  572.                                 else break;
  573.                             }
  574.                             while (pds[p] < cnt);
  575.                         }
  576.  
  577.                     }
  578.                 }
  579.  
  580.             }
  581.             while (p > 0);
  582.  
  583.         }
  584.  
  585.         if (sumA + sumB == 0)
  586.         {
  587.             printf("NOT found any solution\n\n");
  588.         }
  589.         else
  590.         {
  591.             printf("A form: %d  B form: %d\n\n", sumA, sumB);
  592.  
  593.             printf("merged infix expression : %d\n\n", cnt_stdInfixs);
  594.  
  595.             for (i=0; i<cnt_stdInfixs; i++) puts(stdInfixs[i]);
  596.  
  597.             printf("\n\n");
  598.         }
  599.  
  600.     }
  601.     return 0;
  602. }


回到 “算法和编码”

在线用户

用户浏览此论坛: 没有注册用户 和 0 访客