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

头像
523066680
Administrator
Administrator
帖子: 573
注册时间: 2016年07月19日 12:14
联系:

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

帖子 523066680 »

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

基本要求:
  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
帖子: 573
注册时间: 2016年07月19日 12:14
联系:

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

帖子 523066680 »

#占楼

Perl 版,因为是枚举所有公式类型并整个Eval,所以好像没有扩展1的情况。
还未对重复意义的公式进行筛选和排除
=info
Code-By: 523066680
Date: 2016-09-01
=cut

my @nums = qw/3 3 7 7/;
our @ops = ("+", "-", "*", "/");
our %hash;

arrange(\@nums, [], 0, $#nums);

#排列组合
sub arrange
{
my ($ref, $ref2, $lv, $top) = @_;

my @tr;
my @collect;

if ($lv <= $top)
{
for my $o ( 0 .. $#$ref )
{
@collect = (@$ref2, $ref->[$o]);
@tr = @$ref[ 0..$o-1, $o+1..$#$ref ];
arrange(\@tr, \@collect, $lv+1, $top);
}
}
else
{
prior($ref2, 0, $#$ref2);
}
}

#递归设置优先级
sub prior
{
our $hash;

my ($ref, $lv, $top) = @_;
my @arr;

if ( $lv < $top )
{
for my $i (0 .. $#$ref-1)
{
for my $o (@ops)
{
@arr = bracket( $ref, $i, $o );
prior(\@arr, $lv+1, $top);
}
}
}
else
{
my $exp = join("", @$ref );
my $x;
eval("\$x = $exp") or $x = 0; #如果遇到除数为0或者返回0错误,则赋值为0

if ( $x == 24 and (not exists $hash{$exp}) )
{
print "$exp = $x \n";
$hash{$exp} = 1;
}
}
}

#加括号处理
sub bracket
{
my ($aref, $idx, $o) = @_;
my @arr;

for my $i ( 0 .. $#{$aref})
{
if ( $i == $idx )
{
push @arr, "(". $aref->[$i] . $o . $aref->[$i+1] .")" ;
}
elsif ( $i == ($idx+1) )
{
}
else
{
push @arr, $aref->[$i];
}
}

return @arr;
}
输出结果
((3+(3/7))*7) = 24
(((3/7)+3)*7) = 24
(7*(3+(3/7))) = 24
(7*((3/7)+3)) = 24
头像
灵台方寸山
出类拔萃
出类拔萃
帖子: 76
注册时间: 2016年08月06日 16:40
来自: [color=red]斜月三星洞[/color]

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

帖子 灵台方寸山 »

:holyhigh

进行难度分级。

从低难度开始做。
:crazylaugh3 :oh_no
少发点科普,对中医产业,骗子产业不好。
头像
523066680
Administrator
Administrator
帖子: 573
注册时间: 2016年07月19日 12:14
联系:

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

帖子 523066680 »

灵台方寸山 写了::holyhigh 进行难度分级。 从低难度开始做。
是的,先满足基本要求,贴代码。然后考虑扩展。
=======================================================================
2016-09-03
方案一、
  • 大致思路,用字符a b c d代表数字,+ - * / 作为参与的运算符
    遍历所有运算符排列方式、代数组合,存为模板(4位数、5位数、6位数的模板)。在实际计算时导入模板代入数值进行计算。
  • 枚举不同的优先级
    四个数字参与的公式,有3个运算符,可以有5种优先类型。
    ((a / b) / c) / d  -> 1 2 3
    (a / b) / (c / d) -> 1 3 2 *
    (a / (b / c)) / d -> 2 1 3
    a / ((b / c) / d) -> 2 3 1
    (a / b) / (c / d) -> 3 1 2 *
    a / (b / (c / d)) -> 3 2 1
    第二种和第五种,顺序不同,但结果明显一致。所以是重复项。

    生成不同优先级公式的Perl代码,不限制于数字的个数。
    my @nums = ('a'..'e');

    func(\@nums, 0, $#nums);

    sub func
    {
    my ($ref, $lv, $top) = @_;
    my @arr;

    if ( $lv < $top )
    {
    for my $i (0 .. $#$ref-1)
    {
    @arr = prior( $ref, $i );
    func(\@arr, $lv+1, $top);
    }
    }
    else
    {
    print join(" ", @$ref ), "\n";
    }
    }

    sub prior
    {
    my ($aref, $idx) = (shift, shift);
    my @arr;

    for my $i ( 0 .. $#{$aref})
    {
    if ( $i == $idx )
    {
    push @arr, "(". $aref->[$i] . " / " . $aref->[$i+1] .")" ;
    }
    elsif ( $i == ($idx+1) )
    {
    }
    else
    {
    push @arr, $aref->[$i];
    }
    }

    return @arr;
    }

    代码: 全选

    ((((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
渐入佳境
渐入佳境
帖子: 54
注册时间: 2016年09月02日 22:09
联系:

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

帖子 24game »

我不管重复的了

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

如: 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 表示任意运算符
/*
// O
// / \
// O O
// / \
// O O
// / \
// O O
*/
#include <stdio.h>
#include <stdlib.h>

typedef struct rational_number
{
int numerator, denominator;
} Rational;

Rational new_Rational(int n, int d)
{
Rational r;
r.numerator = n;
r.denominator = d;
return r;
}

enum oper
{
add = 1, rev_subtract, subtract, multiply, rev_division, division
};

Rational calc(Rational a, Rational b, int t)
{

if (!a.denominator || !b.denominator) return new_Rational(0, 0);

if (t == division && b.numerator == 0) return new_Rational(0, 0);

switch (t)
{
case add:
return new_Rational(a.numerator * b.denominator + b.numerator * a.denominator, a.denominator * b.denominator);
break;

case rev_subtract:
return calc(b, a, subtract);
break;

case subtract:
return new_Rational(a.numerator * b.denominator - b.numerator * a.denominator, a.denominator * b.denominator);
break;

case multiply:
return new_Rational(a.numerator * b.numerator, a.denominator * b.denominator);
break;

case rev_division:
return calc(b, a, division);
break;

case division:
return new_Rational(a.numerator * b.denominator, a.denominator * b.numerator);
break;
}

return new_Rational(0, 0);
}

void writeExp(int exp[], int len)
{
int i;
for (i = 0; i < len; i++)
{
if (i > 0 && ~i & 1)
{
switch (exp[i])
{
case add:
printf("+");
break;
case rev_subtract:
printf("<-");
break;
case subtract:
printf("-");
break;
case multiply:
printf("*");
break;
case rev_division:
printf("</");
break;
case division:
printf("/");
break;
}
}
else
{
printf("%d", exp[i]);
}

if (i < len - 1) printf(" ");
}
printf("\n");
}

int main()
{
int datas[] = {4,7,8,8};

int cnt = sizeof (datas) / sizeof (datas[0]);
int len = cnt * 2 - 1;
int pMAX = cnt * 2 - 2;

int used[cnt], exp[len], pds[len], opr[len], p, i;
Rational result[len];

for (i = 0; i < cnt; i++)
{
for (p = 0; p < cnt; p++) used[p] = 0;

p = 0;
pds[p] = i;
used[pds[p]] = 1;
exp[p] = datas[pds[p]];

result[p] = new_Rational(exp[p], 1);

opr[p] = 0;

do
{
if (~p & 1)
{

if (opr[p] > division)
{
p--;

used[pds[p]] = 0; // 释放当前操作数

// 搜索直到第一个可用数或出界
pds[p]++;
while (pds[p] < cnt)
{
if (used[pds[p]]) pds[p]++;
else break;
}
}
else
{

if (p > 0)
{
exp[p] = opr[p];

result[p] = calc(result[p - 2], new_Rational(exp[p - 1], 1), exp[p]);
}

if (p >= pMAX)
{
// 检测并输出
if (/* 1 || */ (result[p].denominator != 0 && result[p].denominator * 24 == result[p].numerator))
writeExp(exp, sizeof (exp) / sizeof (exp[0]));

opr[p]++;
}
else
{
p++;
pds[p] = 0;
do
{
if (used[pds[p]]) pds[p]++;
else break;
}
while (pds[p] < cnt);
}
}

}
else
{

if (pds[p] >= cnt)
{
p--;
opr[p]++;
}
else
{
used[pds[p]] = 1;
exp[p] = datas[pds[p]];

p++;
opr[p] = add;
}
}

}
while (p > 0);
}

printf("Hello world!\n");
return 0;
}
上次由 24game 在 2016年09月03日 16:42,总共编辑 1 次。
头像
523066680
Administrator
Administrator
帖子: 573
注册时间: 2016年07月19日 12:14
联系:

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

帖子 523066680 »

24game 写了:
学习了,原来有这种表达方式(逆波兰)。
我还在考虑能不能先生成所有公式的模板,然后用正则表达式筛选剔除重复项。
24game
渐入佳境
渐入佳境
帖子: 54
注册时间: 2016年09月02日 22:09
联系:

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

帖子 24game »

523066680 写了:
24game 写了:
523..
我的算法有漏洞, 例如:
不可能 解出 2*6+2*6, 这个的逆波兰式为: 2 6 * 2 6 * +

因为我的算法只能生成: # # O # O # O # O ... 这样的逆波兰式, 其中 # 表示任意操作数, O 表示任意二元运算符 , 所以只能生成部分解, 而不是完全解
24game
渐入佳境
渐入佳境
帖子: 54
注册时间: 2016年09月02日 22:09
联系:

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

帖子 24game »

数的总数: S
所有运算符都是二元运算符, 全表达式是一个 叶结点总数为 S, 度为 2 的总数为 S - 1 的二叉树,
如果不考虑结果=24, 那么, 当 S = 4 时, 这个二叉树至少会表现成两种形态(左右对称形态归并成一种了):
A
O
/ \
O O
/ \
O O
/ \
O O

B
O
/ \
/ \
O O
/ \ / \
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/

#include <stdio.h>
#include <stdlib.h>

typedef struct rational_number
{
int numerator, denominator;
} Rational;

Rational new_Rational(int n, int d)
{
Rational r;
r.numerator = n;
r.denominator = d;
return r;
}

enum oper
{
add = 1, rev_subtract, subtract, multiply, rev_division, division
};

Rational calc(Rational a, Rational b, int t)
{

if (!a.denominator || !b.denominator) return new_Rational(0, 0);

if (t == division && b.numerator == 0) return new_Rational(0, 0);

switch (t)
{
case add:
return new_Rational(a.numerator * b.denominator + b.numerator * a.denominator, a.denominator * b.denominator);
break;

case rev_subtract:
return calc(b, a, subtract);
break;

case subtract:
return new_Rational(a.numerator * b.denominator - b.numerator * a.denominator, a.denominator * b.denominator);
break;

case multiply:
return new_Rational(a.numerator * b.numerator, a.denominator * b.denominator);
break;

case rev_division:
return calc(b, a, division);
break;

case division:
return new_Rational(a.numerator * b.denominator, a.denominator * b.numerator);
break;
}

return new_Rational(0, 0);
}

void writeExp(int exp[], int len, char t)
{
int i;
for (i = 0; i < len; i++)
{
if (i > 0 && ((t=='A' && ~i & 1) || (t=='B' && (i==2 || i==5 || i==6 ))))
{
switch (exp[i])
{
case add:
printf("+");
break;
case rev_subtract:
printf("<-");
break;
case subtract:
printf("-");
break;
case multiply:
printf("*");
break;
case rev_division:
printf("</");
break;
case division:
printf("/");
break;
}
}
else
{
printf("%d", exp[i]);
}

if (i < len - 1) printf(" ");
}
printf("\n");
}

int main()
{
int datas[] = {1,5,6,12};

int cnt = sizeof (datas) / sizeof (datas[0]);
int len = cnt * 2 - 1;
int pMAX = cnt * 2 - 2;

int used[cnt], exp[len], pds[len], opr[len], p, i, sumA, sumB;
Rational result[len];


while (1)
{
printf("input 4 numbers, separate by space\n");
scanf("%d%d%d%d", &datas[0], &datas[1], &datas[2], &datas[3]);

sumA = sumB = 0;

for (i = 0; i < cnt; i++)
{



// A 形态

/*
// O
// / \
// O O
// / \
// O O
// / \
// O O
*/


for (p = 0; p < cnt; p++) used[p] = 0;

p = 0;
pds[p] = i;
used[pds[p]] = 1;
exp[p] = datas[pds[p]];

result[p] = new_Rational(exp[p], 1);

opr[p] = 0;

do
{
if (~p & 1)
{

if (opr[p] > division)
{
p--;

used[pds[p]] = 0; // 释放当前操作数

// 搜索直到第一个可用数或出界
pds[p]++;
while (pds[p] < cnt)
{
if (used[pds[p]]) pds[p]++;
else break;
}
}
else
{

if (p > 0)
{
exp[p] = opr[p];

result[p] = calc(result[p - 2], new_Rational(exp[p - 1], 1), exp[p]);
}

if (p >= pMAX)
{
// 检测并输出
if ((result[p].denominator != 0 && result[p].denominator * 24 == result[p].numerator)) {
writeExp(exp, sizeof (exp) / sizeof (exp[0]), 'A');
sumA++;
}

opr[p]++;
}
else
{
p++;
pds[p] = 0;
do
{
if (used[pds[p]]) pds[p]++;
else break;
}
while (pds[p] < cnt);
}
}

}
else
{

if (pds[p] >= cnt)
{
p--;
opr[p]++;
}
else
{
used[pds[p]] = 1;
exp[p] = datas[pds[p]];

p++;
opr[p] = add;
}
}

}
while (p > 0);


// B 形态
//
// a b +-* / c d +-* / +-* /
// c d
// d
//
// 0 1 2 3 4 5 6


for (p = 0; p < cnt; p++) used[p] = 0;

p = 0;
pds[p] = i;
used[pds[p]] = 1;
exp[p] = datas[pds[p]];

result[p] = new_Rational(exp[p], 1);

opr[p] = 0;

do
{
if (p==2 || p==5 || p==6)
{
if (opr[p] > division)
{
p--;

if (p==1 || p==4) {

used[pds[p]] = 0; // 释放当前操作数

// 搜索直到第一个可用数或出界
pds[p]++;
while (pds[p] < cnt)
{
if (used[pds[p]]) pds[p]++;
else break;
}
} else {

opr[p]++;

}
}
else
{

if (p > 0)
{
exp[p] = opr[p];

if (p==2 || p==5) {
result[p] = calc(new_Rational(exp[p - 2], 1), new_Rational(exp[p - 1], 1), exp[p]);
} else {
result[p] = calc(result[2], result[5], exp[p]);
}
}

if (p >= pMAX)
{
// 检测并输出
if (/* 1 || */ (result[p].denominator != 0 && result[p].denominator * 24 == result[p].numerator)) {
writeExp(exp, sizeof (exp) / sizeof (exp[0]), 'B');
sumB++;
}

opr[p]++;
}
else
{
if (p==2){
p++;
pds[p] = 0;
do
{
if (used[pds[p]]) pds[p]++;
else break;
}
while (pds[p] < cnt);
} else {
p++;
opr[p] = add;
}
}
}

}
else
{
if (pds[p] >= cnt)
{
if (p==3){
p--;
opr[p]++;
} else if (p==4) {

p--;
used[pds[p]] = 0; // 释放当前操作数

// 搜索直到第一个可用数或出界
pds[p]++;
while (pds[p] < cnt)
{
if (used[pds[p]]) pds[p]++;
else break;
}

} else { // p==1
p--; // p <== 0 will exit while (p > 0);
}
}
else
{
used[pds[p]] = 1;
exp[p] = datas[pds[p]];

if (p==1 || p==4) {
p++;
opr[p] = add;
} else { // p==0 || p==3
p++;
pds[p] = 0;
do
{
if (used[pds[p]]) pds[p]++;
else break;
}
while (pds[p] < cnt);
}

}
}

}
while (p > 0);

}

if (sumA + sumB == 0) {
printf("NOT found any solution\n\n");
} else {
printf("A form: %d B form: %d\n\n", sumA, sumB);
}

}
return 0;
}
24game
渐入佳境
渐入佳境
帖子: 54
注册时间: 2016年09月02日 22:09
联系:

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

帖子 24game »

4 到 6 叶的 二叉树 形态:

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

4 叶 3 层
O
/ \
/ \
O O
/ \ / \
O O O O

5 叶 5 层
O
/ \
O O
/ \
O O
/ \
O O
/ \
O O

5 叶 4 层 A
O
/ \
/ \
O O
/ \ / \
O O O O
/ \
O O

5 叶 4 层 B
O
/ \
/ \
O O
/ \
/ \
O O
/ \ / \
O O O O

6 叶 6 层
O
/ \
O O
/ \
O O
/ \
O O
/ \
O O
/ \
O O

6 叶 5 层 A
O
/ \
/ \
O O
/ \ / \
O O O O
/ \
O O
/ \
O O

6 叶 5 层 B
O
/ \
O O
/ \
/ \
O O
/ \ / \
O O O O
/ \
O O

6 叶 5 层 C
O
/ \
O O
/ \
O O
/ \
/ \
O O
/ \ / \
O O O O

6 叶 4 层 A
O
/ \
/ \
/ \
O O
/ \ /\
/ \ / \
O O O O
/\ /\
/ \ / \
O O O O

6 叶 4 层 B
O
/ \
/ \
/ \
O O
/ \ /\
/ \ / \
O O O O
/\ /\
/ \ / \
O O O O
上次由 24game 在 2016年09月04日 10:23,总共编辑 1 次。
24game
渐入佳境
渐入佳境
帖子: 54
注册时间: 2016年09月02日 22:09
联系:

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

帖子 24game »

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

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

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


输入
1  5  5  9
输出
1 5 + 5 9 <- *          (1 + 5) * (9 - 5)               (1 + 5) * (9 - 5)
1 5 + 9 5 - * (1 + 5) * (9 - 5) (1 + 5) * (9 - 5)
1 5 + 5 9 <- * (1 + 5) * (9 - 5) (1 + 5) * (9 - 5)
1 5 + 9 5 - * (1 + 5) * (9 - 5) (1 + 5) * (9 - 5)
5 1 + 5 9 <- * (5 + 1) * (9 - 5) (1 + 5) * (9 - 5)
5 1 + 9 5 - * (5 + 1) * (9 - 5) (1 + 5) * (9 - 5)
5 9 <- 1 5 + * (9 - 5) * (1 + 5) (1 + 5) * (9 - 5)
5 9 <- 5 1 + * (9 - 5) * (5 + 1) (1 + 5) * (9 - 5)
5 1 + 5 9 <- * (5 + 1) * (9 - 5) (1 + 5) * (9 - 5)
5 1 + 9 5 - * (5 + 1) * (9 - 5) (1 + 5) * (9 - 5)
5 9 <- 1 5 + * (9 - 5) * (1 + 5) (1 + 5) * (9 - 5)
5 9 <- 5 1 + * (9 - 5) * (5 + 1) (1 + 5) * (9 - 5)
9 5 - 1 5 + * (9 - 5) * (1 + 5) (1 + 5) * (9 - 5)
9 5 - 5 1 + * (9 - 5) * (5 + 1) (1 + 5) * (9 - 5)
9 5 - 1 5 + * (9 - 5) * (1 + 5) (1 + 5) * (9 - 5)
9 5 - 5 1 + * (9 - 5) * (5 + 1) (1 + 5) * (9 - 5)
A form: 0 B form: 16


本楼代码在输入
3  3  3  8
得输出
(3 + 3 - 3) * 8
(3 - (3 - 3)) * 8
(3 - 3 + 8) * 3
(8 - (3 - 3)) * 3
8 / (3 / (3 * 3))
3 * 3 / 3 * 8
3 * 3 * 8 / 3
3 / (3 / 3) * 8
8 / (3 / 3 / 3)
3 * 8 / (3 / 3)
3 / (3 / 3 / 8)
(3 + 8 - 3) * 3
(3 - (3 - 8)) * 3
3 + 3 * 8 - 3
3 - (3 - 3 * 8)
3 / (3 / (3 * 8))
3 * 3 / (3 / 8)
3 / (3 / 8 / 3)
3 * 8 + 3 - 3
3 * 8 - (3 - 3)
3 * 8 * 3 / 3
如果做 去括号(括号内的减法, 除法反向), 同优先级运算串联时次序置换, 可以将上面结果归为 4 类(同一类中都认为是同一形式)

(3 + 3 - 3) * 8
(3 + 3 - 3) * 8
(3 - (3 - 3)) * 8
(3 - 3 + 8) * 3
(3 - 3 + 8) * 3
(8 - (3 - 3)) * 3
(3 + 8 - 3) * 3
(3 - (3 - 8)) * 3
3 * 8 * 3 / 3
8 / (3 / (3 * 3))
3 * 3 / 3 * 8
3 * 3 * 8 / 3
3 / (3 / 3) * 8
8 / (3 / 3 / 3)
3 * 8 / (3 / 3)
3 / (3 / 3 / 8)
3 / (3 / (3 * 8))
3 * 3 / (3 / 8)
3 / (3 / 8 / 3)
3 * 8 * 3 / 3
3 * 8 + 3 - 3
3 + 3 * 8 - 3
3 - (3 - 3 * 8)
3 * 8 + 3 - 3
3 * 8 - (3 - 3)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LEN (7)
#define LEN1 (6*6*6*4*3*2*2)

// const int LEN1 = (6*6*6*4*3*2*2);

typedef struct rational_number
{
int numerator, denominator;
} Rational;

typedef struct binary_expression
{
int val, op_type;
char *Infix, *stdInfix;
struct binary_expression *left, * right;
} B_exp;

char *stdInfixs[LEN1];
int cnt_stdInfixs;

Rational new_Rational(int n, int d)
{
Rational r;
r.numerator = n;
r.denominator = d;
return r;
}

enum oper
{
none = 0, add, rev_subtract, subtract, multiply, rev_division, division
};

char *operators[] =
{
"", " + ", " <- ", " - ", " * ", " </ ", " / "
};

char *oprs[] =
{
"","+","<-","-","*","</","/"
};

enum exp_type
{
number = 0, operator
};

Rational calc(Rational a, Rational b, int t)
{

if (!a.denominator || !b.denominator) return new_Rational(0, 0);

if (t == division && b.numerator == 0) return new_Rational(0, 0);

switch (t)
{
case add:
return new_Rational(a.numerator * b.denominator + b.numerator * a.denominator, a.denominator * b.denominator);
break;

case rev_subtract:
return calc(b, a, subtract);
break;

case subtract:
return new_Rational(a.numerator * b.denominator - b.numerator * a.denominator, a.denominator * b.denominator);
break;

case multiply:
return new_Rational(a.numerator * b.numerator, a.denominator * b.denominator);
break;

case rev_division:
return calc(b, a, division);
break;

case division:
return new_Rational(a.numerator * b.denominator, a.denominator * b.numerator);
break;
}

return new_Rational(0, 0);
}

int opr_level(int opr)
{
if (opr < add) return 0;
else if (opr >= multiply) return 2;
else return 1;
}

int opr_dir_sensitive(int opr)
{
if (opr == none || opr == add || opr == multiply) return 0;
else return 1;
}

char * add_parentheses(char * str)
{
char temp[100] = "";
return strcat(strcpy(str, strcat(strcpy(temp, "("), str)), ")");
}

void writeExp(int exp[], int exp_t[], int len)
{

// code for 中缀表达式 begin
B_exp bin_expS[LEN], *bin_expStk[LEN];
int ps = 0;
// code for 中缀表达式 end

int i;
for (i = 0; i < len; i++)
{

// code for 中缀表达式 begin
// init bin_expS[i];

// 中缀式标准式: 每一个有交换律运算的 左式 和 右式 比较, 小的做左式

bin_expS[i].Infix = (char *) malloc(sizeof (char) * 100);
bin_expS[i].stdInfix = (char *) malloc(sizeof (char) * 100); // 标准式


*(bin_expS[i].Infix) = '\0';
*(bin_expS[i].stdInfix) = '\0';

bin_expS[i].val = 0;
bin_expS[i].op_type = none;
bin_expS[i].left = NULL;
bin_expS[i].right = NULL;

// code for 中缀表达式 end



// if (i > 0 && ((t=='A' && ~i & 1) || (t=='B' && (i==2 || i==5 || i==6 ))))
if (exp_t[i] == operator)
{
printf("%s", oprs[exp[i]]);

// code for 中缀表达式 begin
if (exp[i] == rev_division || exp[i] == rev_subtract)
{
bin_expS[i].op_type = exp[i] + 1;
bin_expS[i].left = bin_expStk[ps - 1];
bin_expS[i].right = bin_expStk[ps - 2];
}
else
{
bin_expS[i].op_type = exp[i];
bin_expS[i].right = bin_expStk[ps - 1];
bin_expS[i].left = bin_expStk[ps - 2];
}
ps -= 2;
bin_expStk[ps++] = &(bin_expS[i]);


/* 加括号原则
1

子运算的运算优先级 低于 当前运算
+ - 低于 * /

2

子运算的运算优先级 同于 当前运算
子运算 是 当前运算 - 或者 / 的右项( <- </ 的左项), 且当前运算是有向运算(无交换律的运算)

即, 当前运算 是 - 或者 / 或者 <- 或者 </

而子运算 是 - 的 减数, 或者是 / 的除数

*/

if (bin_expS[i].left -> op_type != none)
if (opr_level(bin_expS[i].left -> op_type) < opr_level(bin_expS[i].op_type))
{
add_parentheses(bin_expS[i].left ->Infix);
add_parentheses(bin_expS[i].left ->stdInfix);
}

if (bin_expS[i].right -> op_type != none)
if ((opr_level(bin_expS[i].right -> op_type) < opr_level(bin_expS[i].op_type))
||
(
(opr_level(bin_expS[i].right -> op_type) == opr_level(bin_expS[i].op_type))
&&
opr_dir_sensitive(bin_expS[i].op_type)
)
)
{
add_parentheses(bin_expS[i].right ->Infix);
add_parentheses(bin_expS[i].right ->stdInfix);

}

strcat(strcat(strcpy(bin_expS[i].Infix, bin_expS[i].left ->Infix), operators[bin_expS[i].op_type]),
bin_expS[i].right->Infix);

if (opr_dir_sensitive(bin_expS[i].op_type))
{
strcat(strcat(strcpy(bin_expS[i].stdInfix, bin_expS[i].left ->stdInfix), operators[bin_expS[i].op_type]),
bin_expS[i].right->stdInfix);
}
else
{

if (strcmp(bin_expS[i].right ->stdInfix, bin_expS[i].left ->stdInfix) < 0)
{
strcat(strcat(strcpy(bin_expS[i].stdInfix, bin_expS[i].right ->stdInfix), operators[bin_expS[i].op_type]),
bin_expS[i].left->stdInfix);
}
else
{
strcat(strcat(strcpy(bin_expS[i].stdInfix, bin_expS[i].left ->stdInfix), operators[bin_expS[i].op_type]),
bin_expS[i].right->stdInfix);
}
}

// code for 中缀表达式 end


}
else
{
printf("%d", exp[i]);


// code for 中缀表达式 begin

bin_expS[i].val = exp[i];
bin_expS[i].op_type = none;

sprintf(bin_expS[i].Infix, "%d", bin_expS[i].val);
sprintf(bin_expS[i].stdInfix, "%d", bin_expS[i].val);

// 数压栈
bin_expStk[ps++] = &(bin_expS[i]);

// code for 中缀表达式 end
}

if (i < len - 1) printf(" ");


}
printf("\t\t%s\t\t%s", bin_expStk[ps - 1]->Infix, bin_expStk[ps - 1]->stdInfix); // 中缀表达式
printf("\n");

int existing;
existing = 0;
for (i=0; i<cnt_stdInfixs; i++)
{
if (strcmp(stdInfixs[i], bin_expStk[ps - 1]->stdInfix) == 0)
{
existing = 1;
break;
}
}
if (!existing)
{
if (stdInfixs[cnt_stdInfixs] == NULL)
{
stdInfixs[cnt_stdInfixs] = (char *) malloc(sizeof (char) * 100);
*(stdInfixs[cnt_stdInfixs]) = '\0';
}

strcpy(stdInfixs[cnt_stdInfixs++], bin_expStk[ps - 1]->stdInfix);
}
}

int main()
{

int datas[] = {1, 5, 5, 9};

int cnt = sizeof (datas) / sizeof (datas[0]);
int len = cnt * 2 - 1;
int pMAX = cnt * 2 - 2;

int used[cnt], exp[len], exp_t[len], pds[len], opr[len], p, i, sumA, sumB, L1;
Rational result[len];


for (i=0, L1 = LEN1; i< L1; i++) stdInfixs[i] = NULL;


while (1)
{
for (i=0, L1 = LEN1; i< L1; i++)
if (stdInfixs[i] != NULL)
{
free(stdInfixs[i]);
stdInfixs[i] = NULL;
}

cnt_stdInfixs =0;

printf("input 4 numbers, separate by space\n");
scanf("%d%d%d%d", &datas[0], &datas[1], &datas[2], &datas[3]);

sumA = sumB = 0;

for (i = 0; i < cnt; i++)
{



// A 形态

/*
// O
// / \
// O O
// / \
// O O
// / \
// O O
*/


for (p = 0; p < cnt; p++) used[p] = 0;

p = 0;
pds[p] = i;
used[pds[p]] = 1;
exp[p] = datas[pds[p]];
exp_t[p] = number;

result[p] = new_Rational(exp[p], 1);

opr[p] = 0;

do
{
if (~p & 1)
{

if (opr[p] > division)
{
p--;

used[pds[p]] = 0; // 释放当前操作数

// 搜索直到第一个可用数或出界
pds[p]++;
while (pds[p] < cnt)
{
if (used[pds[p]]) pds[p]++;
else break;
}
}
else
{

if (p > 0)
{
exp[p] = opr[p];
exp_t[p] = operator;

result[p] = calc(result[p - 2], new_Rational(exp[p - 1], 1), exp[p]);
}

if (p >= pMAX)
{
// 检测并输出
if ((result[p].denominator != 0 && result[p].denominator * 24 == result[p].numerator))
{
writeExp(exp, exp_t, sizeof (exp) / sizeof (exp[0]));
sumA++;
}

opr[p]++;
}
else
{
p++;
pds[p] = 0;
do
{
if (used[pds[p]]) pds[p]++;
else break;
}
while (pds[p] < cnt);
}
}

}
else
{

if (pds[p] >= cnt)
{
p--;
opr[p]++;
}
else
{
used[pds[p]] = 1;
exp[p] = datas[pds[p]];
exp_t[p] = number;

p++;
opr[p] = add;
}
}

}
while (p > 0);


/* B 形态

// O
// / \
// / \
// O O
// / \ / \
// O O O O
//
// a b +-* / c d +-* / +-* /
// c d
// d
//
// 0 1 2 3 4 5 6
*/


for (p = 0; p < cnt; p++) used[p] = 0;

p = 0;
pds[p] = i;
used[pds[p]] = 1;
exp[p] = datas[pds[p]];
exp_t[p] = number;

result[p] = new_Rational(exp[p], 1);

opr[p] = 0;

do
{
if (p == 2 || p == 5 || p == 6)
{
if (opr[p] > division)
{
p--;

if (p == 1 || p == 4)
{

used[pds[p]] = 0; // 释放当前操作数

// 搜索直到第一个可用数或出界
pds[p]++;
while (pds[p] < cnt)
{
if (used[pds[p]]) pds[p]++;
else break;
}
}
else
{

opr[p]++;

}
}
else
{

if (p > 0)
{
exp[p] = opr[p];
exp_t[p] = operator;

if (p == 2 || p == 5)
{
result[p] = calc(new_Rational(exp[p - 2], 1), new_Rational(exp[p - 1], 1), exp[p]);
}
else
{
result[p] = calc(result[2], result[5], exp[p]);
}
}

if (p >= pMAX)
{
// 检测并输出
if (/* 1 || */ (result[p].denominator != 0 && result[p].denominator * 24 == result[p].numerator))
{
writeExp(exp, exp_t, sizeof (exp) / sizeof (exp[0]));
sumB++;
}

opr[p]++;
}
else
{
if (p == 2)
{
p++;
pds[p] = 0;
do
{
if (used[pds[p]]) pds[p]++;
else break;
}
while (pds[p] < cnt);
}
else
{
p++;
opr[p] = add;
}
}
}

}
else
{
if (pds[p] >= cnt)
{
if (p == 3)
{
p--;
opr[p]++;
}
else if (p == 4)
{

p--;
used[pds[p]] = 0; // 释放当前操作数

// 搜索直到第一个可用数或出界
pds[p]++;
while (pds[p] < cnt)
{
if (used[pds[p]]) pds[p]++;
else break;
}

}
else // p==1
{
p--; // p <== 0 will exit while (p > 0);
}
}
else
{
used[pds[p]] = 1;
exp[p] = datas[pds[p]];
exp_t[p] = number;

if (p == 1 || p == 4)
{
p++;
opr[p] = add;
}
else // p==0 || p==3
{
p++;
pds[p] = 0;
do
{
if (used[pds[p]]) pds[p]++;
else break;
}
while (pds[p] < cnt);
}

}
}

}
while (p > 0);

}

if (sumA + sumB == 0)
{
printf("NOT found any solution\n\n");
}
else
{
printf("A form: %d B form: %d\n\n", sumA, sumB);

printf("merged infix expression : %d\n\n", cnt_stdInfixs);

for (i=0; i<cnt_stdInfixs; i++) puts(stdInfixs[i]);

printf("\n\n");
}

}
return 0;
}
回复

在线用户

正浏览此版面之用户: 没有注册用户 和 0 访客