请高手帮我解释一下这个算24点的程序
#include "stdlib.h"
#include "stdio.h"
#include "string.h"
int digit[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int aDigit[4];
char szop[] = { '+', '-', '*', '/' };
int order3[3] = { 1, 2, 3 };
int order2[2];
int order1[1];
int orders[6][3] = {
1,2,3,
1,3,2,
2,1,3,
2,3,1,
3,1,2,
3,2,1
};
char aExp[4][32];
char szExp[32];
int aResult[4];
int aOrder[3];
void RemoveNumber(int total, int* pOrder, int num, int* pResult)
{
int cnt = 0;
for (int i=0; i<total; i++) {
if (pOrder[i] != num) {
pResult[cnt] = pOrder[i];
cnt++;
}
}
}
void OutputExpression(int* pDigit, char* szops, int* pOrder)
{
for (int cnt=0; cnt<4; cnt++) {
sprintf(aExp[cnt], "%d", pDigit[cnt]);
}
memcpy(aOrder, pOrder, sizeof(aOrder));
for (int i=0; i<3; i++) {
int order = aOrder[i];
char* szFormat = (i == 2) ? "%s %c %s" : "(%s %c %s)";
sprintf(szExp, szFormat, aExp[order-1], szops[pOrder[i]-1], aExp[order]);
strcpy(aExp[order-1], szExp);
memcpy(aExp[order], aExp[order+1], sizeof(aExp[0]) * (3 - order));
for (cnt=i+1; cnt<3; cnt++) {
if (aOrder[cnt] > order) {
aOrder[cnt]--;
}
}
}
static int nTotal = 0;
printf("% 5d) %s, %d%d%d, %s\n",
++nTotal,
szops,
pOrder[0],pOrder[1],pOrder[2],
szExp
);
}
int GetResult(int* pDigit, char* szOps, int* pOrder)
{
for (int cnt=0; cnt<4; cnt++) {
aResult[cnt] = pDigit[cnt];
}
memcpy(aOrder, pOrder, sizeof(aOrder));
int result = 0;
for (int i=0; i<3; i++) {
int order = aOrder[i];
char op = szOps[pOrder[i]-1];
int val1 = aResult[order-1];
int val2 = aResult[order];
if (op == '+') {
result = val1 + val2;
}
else if (op == '-') {
result = val1 - val2;
}
else if (op == '*') {
result = val1 * val2;
}
else if (op == '/') {
if (val2 == 0 || (val1 % val2) != 0) {
result = 0;
break;
}
result = val1 / val2;
}
aResult[order-1] = result;
memcpy(&aResult[order], &aResult[order+1], sizeof(aResult[0]) * (3 - order));
for (cnt=i+1; cnt<3; cnt++) {
if (aOrder[cnt] > order) {
aOrder[cnt]--;
}
}
}
return result;
}
void CalcResult(int* aDigit)
{
for (int i1=0; i1<4; i1++)
{
for (int i2=0; i2<4; i2++)
{
for (int i3=0; i3<4; i3++)
{
char szOps[8];
sprintf(szOps, "%c%c%c", szop[i1], szop[i2], szop[i3]);
for (int i=0; i<6; i++) {
if (GetResult(aDigit, szOps, orders[i]) == 24) {
OutputExpression(aDigit, szOps, orders[i]);
break;
}
}
}
}
}
}
void main()
{
int digit4[4] = { 1, 2, 6, 7 };
int digit3[3];
int digit2[2];
int digit1[1];
int aDigit[4];
for (int i4=0; i4<4; i4++) {
RemoveNumber(4, digit4, digit4[i4], digit3);
for (int i3=0; i3<3; i3++) {
RemoveNumber(3, digit3, digit3[i3], digit2);
for (int i2=0; i2<2; i2++) {
RemoveNumber(2, digit2, digit2[i2], digit1);
for (int i1=0; i1<1; i1++) {
aDigit[0] = digit4[i4];
aDigit[1] = digit3[i3];
aDigit[2] = digit2[i2];
aDigit[3] = digit1[i1];
CalcResult(aDigit);
}
}
}
}
}
这是一个24点的算法，但不知道作者的具体算法思想是什么，请哪位高人帮小弟解释一下，小弟在此多谢了！
问题点数：20、回复次数：5Top
1 楼Robinhoodgood（Steven）回复于 2003-06-04 20:20:11 得分 0
太难看了!
谁写的，一句注释都没有?Top
2 楼csdn13（苹果）回复于 2003-06-04 22:41:21 得分 0
不好意思什么是24点，帮解释一下，谢谢
Top
3 楼Raceman35（云卷云舒）回复于 2003-06-06 17:05:59 得分 0
所谓24点问题是四个数通过加减乘除和括号算出24。
例如：1，1，3，8 四个数就有 1*1*3*8=24
6，7，3，6 四个数就有 (6*7)-(3*6)=24 (3+7-6)*6=24
有些数字组合非常有意思：
1346 6/(1-3/4)
1668 6/(1-6/8)
1456 4/(1-5/6)
1555 5/(1-1/5)
3559 5*(3+9/5)
27710 7*(2+10/7)
3377 7*(3+3/7)
4477 7*(4-4/7)
3388 8/(3-8/3)
用程序求24点可保证无遗漏，
算24点本质上是一个排列产生所有可能的表达式的问题，
产生后如果计算结果是24，就保留，否则继续。
参与排列的元素有:
四个操作数全排列的可能性 4*3*2*1=24
在加减乘除四个符号中可重复取三个符号的可能性 4*4*4=64
由括号不同组合引起的不同表达式计算顺序的可能性 5
一般都用用三重循环来判断总共 24*64*5=7680 种不同情况
主要程序find(a,b,c,d)为三重大循环，
把排好的四个操作数operators[4]，
和选中并排好的三个操作符operands[3]，
交给计算函数test(operands,operators,i)
用五种计算顺序 i= 0 to 4,通过多次 calc(a, cOp, b)
产生结果value,通过多 equal(value,24)判定结果是否为24
合适则通过 print(operands,operators,i)打印这个表达式
程序中重要的是：
1）表达式中出现除零情况的处理: bOK的使用
2）表达式中出现非整数时（除法引起）的处理: float 替代 int
在CN Dev Forum中抄来一段程序
http://www.vchelp.net/cndevforum/subject_view.asp?subject_id=9665&forum_id=47
// New24.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdio.h>
#include <math.h>
bool equal(float f1, float f2);
float calc(float a, char cOp, float b);
float test(int num[], char oper[], int tree);
void print(int num[], char oper[], int tree);
int find(int a,int b,int c,int d);
int main()
{
//Find the Solution of according below Numbers
int ret=find(4,3,7,8);
printf("Total=%d Press Any Key\n",ret);
getchar();
return(0);
}
bool bOK;
//operator permutations select 3 from 4 repeatable 4*4*4=64
char cOperators[4] = {'+', '-', '*', '/'};
/*calculation sequence permutations only 5 candidates
1, (((a.b).c).d)
2, ((a.(b.c)).d)
3, ((a.b).(c.d))
4, (a.((b.c).d))
5, (a.(b.(c.d))) */
//operand permutations select 4 from 4 repeatable 4*3*2=24
int permutes[24][4] = {
{1,2,3,4},{3,1,2,4},{3,4,1,2},{2,3,4,1},{3,1,4,2},{1,3,2,4},
{2,1,3,4},{3,2,4,1},{3,4,2,1},{1,3,4,2},{3,2,1,4},{2,3,1,4},
{1,2,4,3},{4,1,2,3},{4,3,1,2},{2,4,3,1},{4,1,3,2},{1,4,2,3},
{2,1,4,3},{4,2,3,1},{4,3,2,1},{1,4,3,2},{4,2,1,3},{2,4,1,3},
};
int find(int a,int b,int c,int d)
{
int count=0;
int num[4];
num[0]=a; num[1]=b; num[2]=c; num[3]=d;
for(int k=0; k<24; k++){
//permutate number sequence;
int operands[4];
operands[0]=num[permutes[k][0]-1];
operands[1]=num[permutes[k][1]-1];
operands[2]=num[permutes[k][2]-1];
operands[3]=num[permutes[k][3]-1];
for(int j = 0; j < 64; j ++){
//permutate operators;
char operators[3];
operators[0] = cOperators[j/16];
operators[1] = cOperators[(j%16)/4];
operators[2] = cOperators[j%4];
for(int i = 0; i < 5; i ++) {
//permutate calculation sequence;
bOK=true;
float value=test(operands,operators,i);
if(equal(value,(float)24) && bOK){
count++;
printf("%03d:%d,%d,%d,%d:",count,operands[0],operands[1],operands[2],operands[3]);
printf("%c,%c,%c,%d\t",operators[0],operators[1],operators[2],i);
print(operands,operators,i);
}
}
}
}
return(count);
}
//calculate (a oper b)
float calc(float a, char cOp, float b)
{
if(!bOK)
return(0);
switch(cOp) {
case '+': return(a+b);
case '-': return(a-b);
case '*': return(a*b);
case '/':
if(b != 0){
return(a/b);
}else{
bOK=false;
return(0);
}
default:
bOK=false;
return(0);
}
}
//calculate one expression
float test(int num[], char oper[], int tree)
{
float a = (float)num[0];
float b = (float)num[1];
float c = (float)num[2];
float d = (float)num[3];
char cOp1 = oper[0];
char cOp2 = oper[1];
char cOp3 = oper[2];
switch(tree){
//perform calculation sequence
case 0: return calc(calc(calc(a,cOp1,b),cOp2,c),cOp3,d);
case 1: return calc(calc(a,cOp2,calc(b,cOp1,c)),cOp3,d);
case 2: return calc(calc(a,cOp1,b),cOp3,calc(c,cOp2,d));
case 3: return calc(a,cOp3,calc(calc(b,cOp1,c),cOp2,d));
case 4: return calc(a,cOp3,calc(b,cOp2,calc(c,cOp1,d)));
default: return 0;
}
}
//print the expression
void print(int num[], char oper[], int tree)
{
int a = num[0];
int b = num[1];
int c = num[2];
int d = num[3];
char cOp1 = oper[0];
char cOp2 = oper[1];
char cOp3 = oper[2];
switch(tree) {
case 0: printf("(((%d%c%d)%c%d)%c%d)\n",a,cOp1,b,cOp2,c,cOp3,d); return;
case 1: printf("((%d%c(%d%c%d))%c%d)\n",a,cOp2,b,cOp1,c,cOp3,d); return;
case 2: printf("((%d%c%d)%c(%d%c%d))\n",a,cOp1,b,cOp3,c,cOp2,d); return;
case 3: printf("(%d%c((%d%c%d)%c%d))\n",a,cOp3,b,cOp1,c,cOp2,d); return;
case 4: printf("(%d%c(%d%c(%d%c%d)))\n",a,cOp3,b,cOp2,c,cOp1,d); return;
}
return;
}
//two float numbers are almost equal?
bool equal(float f1, float f2)
{
return (fabs(f1 - f2) < 0.001);
}
以上程序在VC6 Win32 Console 运行
Top
4 楼Raceman35（云卷云舒）回复于 2003-06-06 17:09:59 得分 20
下面是程序的改进版本：(省略了函数test(), print(),equal())
为消除重复，定义了三级操作
SMART =1 减少操作数中的重复引起的无效循环，标准循环24次，四个数一样时循环1次。
SMART =2 利用加法和乘法交换率消除重复，强制第二操作数不小于第一操作数
SMART =3 三个操作数都是相同的（主要指加法和乘法），用结合律消除重复
SMART =4 下面情况：+(+(*)) (+)+(*) 似乎应用结合律消除，未实现
#define COUNT 统计有效表达式的个数
3888 522(SMART=0时) 31(SMART=3时)
4666 522(SMART=0时) 31(SMART=3时)
3338 510(SMART=0时) 30(SMART=3时)
4446 510(SMART=0时) 30(SMART=3时)
// New24.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdio.h>
#include <math.h>
#define SMART 0
//reduce duplicated results
// 1,1,4,6 SMART=0(456),=1(228),=2(76),=3(56),=4(?)
//SMART =1 operand permutations cut off tail of the list
//SMART =2 operator * and + exchange rule by force a<=b
//SMART =3 +++ *** /// --- select one
//SMART =4 +(+(*)) (+)+(*) + Combine Not Complished
//#define COUNT //Count Success Combinations
//#define FIND_ONE //Find One Result
#define PRINT_ALL //Print All Results
bool equal(float f1, float f2);
float calc(float a, char cOp, float b);
float test(int num[], char oper[], int tree);
void print(int num[], char oper[], int tree);
int find(int a,int b,int c,int d);
int normal(int num[4]);
int main()
{
int ret;
///////////////////////////
//Find the Solution of according below Numbers
ret=find(1,3,10,10);
if(ret>0)
printf("Total=%d Press Any Key\n",ret);
getchar();
return(0);
/////////////////////////////
//Find All Possible Number Combinations
for(int i=0;i<=9999;i++) {
int a=i/1000;
int b=(i%1000)/100;
int c=(i%100)/10;
int d=i%10;
if((a>b)||(b>c)||(c>d))
continue;
ret=find(a+1,b+1,c+1,d+1);
#ifdef COUNT
if(ret>0)
printf("%d,%d,%d,%d,%d\n",a+1,b+1,c+1,d+1,ret);
#endif
}
getchar();
return(0);
}
bool bOK;
//operator permutations select 3 from 4 repeatable 4*4*4=64
char cOperators[4] = {'+', '-', '*', '/'};
/*calculation sequence permutations only 5 candidates
1, (((a.b).c).d)
2, ((a.(b.c)).d)
3, ((a.b).(c.d))
4, (a.((b.c).d))
5, (a.(b.(c.d))) */
//operand permutations select 4 from 4 repeatable 4*3*2=24
//But duplicated number will reduce loop times
//1234 = 24 1233 = 12 1122 = 6 1222 = 4 1111 = 1
//The Pattern:
//----1222
//1222 2122 2212 2221 (1234 3124 3412 2341
//----1122
//1122 2112 2211 1221 2121 1212 (1234 3124 3412 2341 3142 1324
//----1233
//1233 3123 3312 2331 3132 1323 (1234 3124 3412 2341 3142 1324
//2133 3231 3321 1332 3213 2313 (2134 3241 3421 1342 3214 2314
int permutes[24][4] = {
{1,2,3,4},{3,1,2,4},{3,4,1,2},{2,3,4,1},{3,1,4,2},{1,3,2,4},
{2,1,3,4},{3,2,4,1},{3,4,2,1},{1,3,4,2},{3,2,1,4},{2,3,1,4},
{1,2,4,3},{4,1,2,3},{4,3,1,2},{2,4,3,1},{4,1,3,2},{1,4,2,3},
{2,1,4,3},{4,2,3,1},{4,3,2,1},{1,4,3,2},{4,2,1,3},{2,4,1,3},
};
// 'Don't change above list!!!
int find(int a,int b,int c,int d)
{
int count=0;
bool Smart3=false;
int num[4];
num[0]=a;
num[1]=b;
num[2]=c;
num[3]=d;
int MaxPermulation=normal(num);
for(int k=0; k<MaxPermulation; k++){
//permutate number sequence;
int operands[4];
operands[0]=num[permutes[k][0]-1];
operands[1]=num[permutes[k][1]-1];
operands[2]=num[permutes[k][2]-1];
operands[3]=num[permutes[k][3]-1];
for(int j = 0; j < 64; j ++){
//permutate operators;
char operators[3];
operators[0] = cOperators[j/16];
operators[1] = cOperators[(j%16)/4];
operators[2] = cOperators[j%4];
for(int i = 0; i < 5; i ++) {
//permutate calculation sequence;
bOK=true;
float value=test(operands,operators,i);
if(equal(value,(float)24) && bOK){
#if (SMART>2)
if((operators[0]==operators[1])&&(operators[0]==operators[2])&&Smart3)
continue;
if((operators[0]==operators[1])&&(operators[0]==operators[2]))
Smart3=true;
#endif
count++;
#ifndef PRINT_ALL
if(count>1)
continue;
#endif
#ifndef COUNT
printf("%03d:%d,%d,%d,%d:",count,operands[0],operands[1],operands[2],operands[3]);
printf("%c,%c,%c,%d\t",operators[0],operators[1],operators[2],i);
print(operands,operators,i);
#endif
#ifdef FIND_ONE
return(1);
#endif
}
}
}
}
return(count);
}
int normal(int num[4])
{
#if (SMART >0)
//reduce loop times 1234 = 24 1233 = 12 1122 = 6 1222 = 4 1111 = 1
//re_arrange number order, put duplication at the tail
//first sort num[4] from smaller to larger
for(int j=3;j>0;j--){
int max=-1;
int index;
for(int i=0;i<=j;i++){
if(num[i]>max){
index=i;
max=num[i];
}
}
max=num[index],num[index]=num[j],num[j]=max;
}
//move the duplicate number to the end
if(num[0]==num[3])
return 1; //1111
if(num[0]==num[2]){
num[0]=num[3];
num[3]=num[1];
return 4;} //1112 to 2111
if(num[1]==num[3])
return 4; //1222
if(num[0]==num[1] && num[2]==num[3])
return 6; //1122
if(num[0]==num[1]){
num[0]=num[2];
num[2]=num[1];
num[1]=num[3];
num[3]=num[2];
return 12;} //1123 to 2311
if(num[2]==num[3])
return 12; //1233
if(num[1]==num[2]){
num[1]=num[3];
num[3]=num[2];
return 12;} //1223 to 1322
#endif
return 24;
}
//calculate (a oper b)
float calc(float a, char cOp, float b)
{
if(!bOK)
return(0);
switch(cOp) {
case '+':
#if (SMART>1)
if(a>b){
bOK=false;
return(0);
} else
#endif
return(a+b);
case '-':
return(a-b);
case '*':
#if (SMART>1)
if(a>b){
bOK=false;
return(0);
} else
#endif
return(a*b);
case '/':
if(b != 0){
return(a/b);
}else{
bOK=false;
return(0);
}
default:
bOK=false;
return(0);
}
}
Top
5 楼xxking（小星）回复于 2003-06-12 06:31:56 得分 0
谢谢各位Top
