高分!求救啊!
0-10中任意输入四个数,每个数不重复,且必须只能用一次,运算符是加减乘除,判断表达式中是否有结果为24,有的话输出:
例如:4*3*2*1=24,则输出4*3*2*1=24,输出所有可能的结果
用C++编程
[解决办法]
24点C++源代码
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
const double PRECISION = 1E-6;
const int COUNT_OF_NUMBER = 4;
const int NUMBER_TO_BE_CAL = 24;
double number[COUNT_OF_NUMBER];
string expression[COUNT_OF_NUMBER];
bool Search(int n)
{
if (n == 1) {
if ( fabs(number[0] - NUMBER_TO_BE_CAL) < PRECISION ) {
cout < < expression[0] < < endl;
return true;
} else {
return false;
}
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
double a, b;
string expa, expb;
a = number[i];
b = number[j];
number[j] = number[n - 1];
expa = expression[i];
expb = expression[j];
expression[j] = expression[n - 1];
expression[i] = '( ' + expa + '+ ' + expb + ') ';
number[i] = a + b;
if ( Search(n - 1) ) return true;
expression[i] = '( ' + expa + '- ' + expb + ') ';
number[i] = a - b;
if ( Search(n - 1) ) return true;
expression[i] = '( ' + expb + '- ' + expa + ') ';
number[i] = b - a;
if ( Search(n - 1) ) return true;
expression[i] = '( ' + expa + '* ' + expb + ') ';
number[i] = a * b;
if ( Search(n - 1) ) return true;
if (b != 0) {
expression[i] = '( ' + expa + '/ ' + expb + ') ';
number[i] = a / b;
if ( Search(n - 1) ) return true;
}
if (a != 0) {
expression[i] = '( ' + expb + '/ ' + expa + ') ';
number[i] = b / a;
if ( Search(n - 1) ) return true;
}
number[i] = a;
number[j] = b;
expression[i] = expa;
expression[j] = expb;
}
}
return false;
}
void main()
{
for (int i = 0; i < COUNT_OF_NUMBER; i++) {
char buffer[20];
int x;
cin > > x;
number[i] = x;
itoa(x, buffer, 10);
expression[i] = buffer;
}
if ( Search(COUNT_OF_NUMBER) ) {
cout < < "Success. " < < endl;
} else {
cout < < "Fail. " < < endl;
}
}
Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=1436969
[解决办法]
http://www.wangwa.com/info/2006-12/49392.htm
1、概述
给定4个整数，其中每个数字只能使用一次；任意使用 + - * / ( ) ，构造出一个表达式，使得最终结果为24，这就是常见的算24点的游戏。这方面的程序很多，一般都是穷举求解。本文介绍一种典型的算24点的程序算法，并给出两个具体的算24点的程序：一个是面向过程的C实现，一个是面向对象的java实现。
2、基本原理
基本原理是穷举4个整数所有可能的表达式，然后对表达式求值。
表达式的定义： expression = (expression|number) operator (expression|number)
因为能使用的4种运算符 + - * / 都是2元运算符，所以本文中只考虑2元运算符。2元运算符接收两个参数，输出计算结果，输出的结果参与后续的计算。
由上所述，构造所有可能的表达式的算法如下：
(1) 将4个整数放入数组中
(2) 在数组中取两个数字的排列，共有 P(4,2) 种排列。对每一个排列，
(2.1) 对 + - * / 每一个运算符，
(2.1.1) 根据此排列的两个数字和运算符，计算结果
(2.1.2) 改表数组：将此排列的两个数字从数组中去除掉，将 2.1.1 计算的结果放入数组中
(2.1.3) 对新的数组，重复步骤 2
(2.1.4) 恢复数组：将此排列的两个数字加入数组中，将 2.1.1 计算的结果从数组中去除掉
可见这是一个递归过程。步骤 2 就是递归函数。当数组中只剩下一个数字的时候，这就是表达式的最终结果，此时递归结束。
在程序中，一定要注意递归的现场保护和恢复，也就是递归调用之前与之后，现场状态应该保持一致。在上述算法中，递归现场就是指数组，2.1.2 改变数组以进行下一层递归调用，2.1.3 则恢复数组，以确保当前递归调用获得下一个正确的排列。
括号 () 的作用只是改变运算符的优先级，也就是运算符的计算顺序。所以在以上算法中，无需考虑括号。括号只是在输出时需加以考虑。
[解决办法]
计算24点
作者： 来源：http://www.openitpower.com 日期：2005-5-29
问题描述:
有四个整数(0到10),运算符只有加减乘除,还有括号,每个数能且只能用一次,要求判断这些表达的结果中是否有24,如果有,输出过程,格式如下:
4*6*1*1 .(允许有括号).
注意:
1,中间结果允许出现分数,如: (5 1/5)*5;
2,不能有多余的括号.
3,不能出现两个负数相乘,如(1-4)*(1-9),看作(4-1)*(9-1)的重复,也不能出现8-8*(2-4).
4,避免交换律引起的重复.
5,避免结合律引起的重复.
6,由于数字相同的重复也不允许,如有两个2.
分析:
#1,#2,#3代表运算符,a,b,c,d代表运算数,对于表达式a #1 b #2 c #3 d根据运算顺序有如下六种可能.
1,运算顺序:#1,#2,#3 (( a #1 b) #2 c) #3 d
2,运算顺序:#1,#3,#2 ( a #1 b ) #2 ( c #3 d)
3,运算顺序:#2,#3,#1 a #1 (( b #2 c ) #3 d )
4,运算顺序:#2,#1,#3 (a #1 ( b #2 c ) ) #3 d
5运算顺序:#3,#1,#2 ( a #1 b ) #2 ( c #3 d )
6运算顺序:#3,#2,#1 a #1 ( b #2 ( c #3 d))
其中运算符对应关系有６４种
运算数对应关系２４种．
考虑６／（５／４ －１）＝ ２４自定义数据类型ＣData,包含整形的分子，分母．
最后排除重复(输出成字符串再比较)
１，由于运算数相同的问题，直接比较就行了．
２，交换律的问题：
(( a #1 b) #2 c) #3 d成立
如果＃都是＋或＊
那么，
(( b #1 a) #2 c) #3 d
(c #2 ( a #1 b)) #3 d
d #3 (c #2 ( a #1 b))
调整使不会出现小数加(乘)大数,再比较就行了,注意如果结果相同,还要比较过程,运算符在运算数之前,如:(2+4)*6而不是6*(2+4).都是运算符也保证顺序的唯一性.
３，分配律不认为重复．
4,结合律,如: a + b c = a c + b;由于只有三个运算符,故只会出现两个运算符的结合律和三个运算符的结合律.我们先将-/变成加乘,全部是加(乘)的结合律好处理.a-(b*c),a-(b/c),a/(b+c),a/(b-c)不好处理,加个标记就行了.总共三个运算符,而结合律至少要两个运算符,故b,c不会再包含运算符.
CData的结构:
左指针
分子
分母
符号(加减乘除)
右指针
当为运算数时,符号为字符#,指针为空.
当为符号时,分子和分母表示结果,左右指针分别指向运算数,注意最后调整使大的在左边(对加乘而言).
如:(5-1) * (2+4),整个过程为:
每个结点的指针用箭头代替,为了避免交换律引起的重复,将它调整成(2*4)*(5-1).不好意思,箭头丢了.
CData的函数有:
构造函数: 默认构造函数,复制构造函数,构造运算符的构造函数,构造运算数(分母默认为1)的构造函数.
析构函数.
重载运算符: 1, +-*/ 2, <,> ,==只比较分子和分母,不比较指针
3, = 右边的参数可以是整形
YueFen化简使得分子和分母不含有公约数,也不同时为负.
OutPut 将数据转化成字符串表达式,注意不能有多余的括号.
Adjust1调整使得对于+*,左边的运算数大于右边的,避免因交换律引起的重复.
Adjust2调整使避免两个负数相乘.
Adjust3 避免结合律产生的重复.
先把减转化成等效的加.
再分成情况讨论:
1,三个运算符相同.
2,运算符和左支相同.
2,运算符与右支相同.
4,左支的两个运算符相同(递归处理)
5,右支的两个运算符相同(递归处理).
对相同运算符部分,从大到小的顺序按列.不能从小到大.否则有出现-1 + 0 + 5 * 5;
再直接相加就行了.
void ChangeSubToAdd(); 将减法转变成相应的加法
void UndoSubToAdd(); 将减法还原
int GetOperand(CData **data);//返回操作数的个数,并使data的元素指向各操作数
bool IsOperSame(char ch);//运算符和左右支的运算符是否都是ch
int GetAddSubCount();//返回加减的总数,好判断是不需要考虑结合律
int GetMulDivCount();//返回乘除的总数,好判断是不需要考虑结合律
void ChangeDivToMul();//除化成乘
void UndoDivToMul();//除还原成乘
主模块函数简介及调用关系
CData cal(CData data1,int op,CData data2)
第一个和最后一个参数是运算数,op表示运算符0到3分别表示+-*/,它调用CData类的加减乘除.
void Add(CData data)
它调整data(避免重复),再调用CData类的OutPut将内容转化成字符串,再将这个字符串加进全局变量result中(不重复加).
void Do(int nData[4],int op[3])
运算数与操作符固定时,穷举5种情况,再调用Add 将结果加进去.
void Cal24Point(int input[4])
穷举所有可能:操作数和操作符的对应关系,再调用Do. 三个运算符之间没有任何联系,运算数能且只能用一次.
测试数据:
(1),1,5,5,5 (2)3,8,8,8 (3),1,2,3, 4 (4),2,4,5,6
(4),4,2,2,5 (5)1,2,2,6 (6),4,2,8,8 (4),0,3,8,8
再随机选几组数据.
【http://www.openitpower.com/wenzhang/115/12411_1.html】