1经典经典 24 点程序算法点程序算法一、一、概述概述算算 24 点：任意给定四个整数，用加、减、乘、除以及适当的括号连接，无论顺序，使点：任意给定四个整数，用加、减、乘、除以及适当的括号连接，无论顺序，使 计算结果为计算结果为 24，也可能根本就无解如何用程序简单实现找到算式是程序初学者关注的问，也可能根本就无解如何用程序简单实现找到算式是程序初学者关注的问 题，百度上可以搜到许多这样的文章，有递归法、回溯法、穷举法但穷举法最为简单、题，百度上可以搜到许多这样的文章，有递归法、回溯法、穷举法但穷举法最为简单、 易于理解易于理解二、二、算法算法穷举法就是把四个数字的所有运算式进行尝试计算，要设法把所有排列一点不差地穷穷举法就是把四个数字的所有运算式进行尝试计算，要设法把所有排列一点不差地穷 举出，一、是四个整数位置的排列，用举出，一、是四个整数位置的排列，用 0,1,2,3 表示位置，排列是不能重复的，所以有表示位置，排列是不能重复的，所以有 P(4,4)种情况，即种情况，即 4！！=4*3*2*1=24 种；二、是三个运算符的变化，每个运算符为种；二、是三个运算符的变化，每个运算符为+-*/ ，可，可 以相同，所以，有以相同，所以，有 4*4*4=64 种种; 三、三个运算符的优先级，就是括号位置的变化，可能性三、三个运算符的优先级，就是括号位置的变化，可能性 为为 P(3,3)-1=6-1=5 种；所以，表达式的可能性为：种；所以，表达式的可能性为：24*64*5=7680 种，种，C 语言程序把这么多语言程序把这么多 表达式都计算一遍，几乎不到表达式都计算一遍，几乎不到 1 毫秒毫不费劲毫秒毫不费劲, 可见电脑的运行速度之快。
可见电脑的运行速度之快四个数位置的排列，可用四重循环实现，四个循环变量四个数位置的排列，可用四重循环实现，四个循环变量 i1,i2,i3,i4 对应数组下标的变化对应数组下标的变化, 不许它们之间相等，四个数放在数组不许它们之间相等，四个数放在数组 v[0]v[0]、、v[1]v[1]、、v[2]v[2]、、v[3]:v[3]:forfor (int(int i1=0;i1<4;i1++)i1=0;i1<4;i1++)forfor (int(int i2=0;i2<4;i2++)i2=0;i2<4;i2++) ifif (i2!=i1)(i2!=i1) //// 循环变量不许相同循环变量不许相同forfor (int(int i3=0;i3<4;i3++)i3=0;i3<4;i3++)ifif (i3!=i2(i3!=i2 i4<4;i4++)i4=0;i4<4;i4++)ifif (i4!=i3(i4!=i3 f1<4;f1++)f1=0;f1<4;f1++) //// 三重循环对运算符穷举三重循环对运算符穷举forfor (int(int f2=0;f2<4;f2++)f2=0;f2<4;f2++)forfor (int(int f3=0;f3<4;f3++)f3=0;f3<4;f3++) //// 运算符运算符 f1,f2,f3f1,f2,f3{ {//// op[f1],op[f2],op[f3]op[f1],op[f2],op[f3]就是排列结果，共有就是排列结果，共有 4*4*4=644*4*4=64 种种 } }上面两种排列组合后，四个数及运算符排列顺序就是形如：上面两种排列组合后，四个数及运算符排列顺序就是形如：a a ①① b b ②② c c ③③ d dv[i1],op[f1],v[i2],op[f2],v[i3],op[f3],v[i4]v[i1],op[f1],v[i2],op[f2],v[i3],op[f3],v[i4] 但运算符有优先级，一般是用括号表示。
我们可以规定运算符的优先级来代替括号设但运算符有优先级，一般是用括号表示我们可以规定运算符的优先级来代替括号设 四张牌为四张牌为 a a、、b b、、c c、、d d，运算符为，运算符为①①、、②②、、③③，表达式为，表达式为 a a ①① b b ②② c c ③③ d d 这这 3 3 个运算个运算 符的运算顺序有符的运算顺序有 3 3！！=6=6 种，分别是：种，分别是： 1 1．．①②③①②③ 2.①③②2.①③② 3.②①③3.②①③ 4.②③①4.②③① 5.③①②5.③①② 6.③②①6.③②① 等价的表达式分别是：等价的表达式分别是：21. .((a①b②)c③)da①b②)c③)d 2.(a①b)②(c③d)2.(a①b)②(c③d) 3.(a①(b②c))③d3.(a①(b②c))③d4.a①((b②c)③d)4.a①((b②c)③d) 5.(a①b)②(c③d)5.(a①b)②(c③d) 6.6. a①(b②(c③d))a①(b②(c③d)) 显然，显然，2 2 和和 5 5 是相同的，因此只考虑是相同的，因此只考虑 5 5 种情况。
这样，括号的问题就解决了为了简种情况这样，括号的问题就解决了为了简 单起见，这五种情况未用循环，大大减化了程序的复杂性，更易于理解单起见，这五种情况未用循环，大大减化了程序的复杂性，更易于理解对这组排列逐一进行运算，看是否是对这组排列逐一进行运算，看是否是 2424，就可以得到最终所有式子了在运算过程，就可以得到最终所有式子了在运算过程 中除法的特殊性中除法的特殊性————除数不能为零因为可能会用到除法，所以要考虑精度问题，这里通除数不能为零因为可能会用到除法，所以要考虑精度问题，这里通 过结果减去过结果减去 2424 取绝对值与一个接近取绝对值与一个接近 0 0 的小数的小数( (如如 0.001)0.001)比较，如小于它，即可判定结果是比较，如小于它，即可判定结果是 2424三、三、程序程序有了上面的算法分析，这个程序很简单，只用了最简单的基本语句，你可以改成任何有了上面的算法分析，这个程序很简单，只用了最简单的基本语句，你可以改成任何 程序语言：程序语言：/*------------------------------------------------------------*/*------------------------------------------------------------*| | 2424 点点( (穷举法穷举法) )算法程序算法程序 V1.0V1.0 | || | ByBy 叶宏叶宏 2012.6.272012.6.27 | |*------------------------------------------------------------*/*------------------------------------------------------------*/ #include#include “stdio.h““stdio.h“ //// 输入输出定义输入输出定义doubledouble cal(doublecal(double a,doublea,double b,intb,int op)op) //// op:op: 0:+,1:-,2:*,3:/0:+,1:-,2:*,3:/ { {switchswitch (op)(op) //// +-x/+-x/ 运算运算{ {casecase 0:0: return(a+b);return(a+b);casecase 1:1: return(a-b);return(a-b);casecase 2:2: return(a*b);return(a*b);} }ifif (b==0.0)(b==0.0) //// 分母为分母为 0 0return(999.0);return(999.0);elseelsereturn(a/b);return(a/b); } } boolbool isEqual(doubleisEqual(double d1,doubled1,double d2)d2) //// 两个浮点数是否近似相等两个浮点数是否近似相等{ {doubledouble d=d1-d2;d=d1-d2;ifif (d<0)(d<0)d=-d;d=-d; //// 求绝对值求绝对值return(d<=0.001);return(d<=0.001); } } voidvoid D24(intD24(int v0,intv0,int v1,intv1,int v2,intv2,int v3)v3) //// 穷举法求穷举法求 2424 点点{ {charchar op[4]={'+','-','*','/'};op[4]={'+','-','*','/'}; //// +:0+:0 -:1-:1 *:2*:2 /:3/:3intint v[4];v[4]; //// 输入四整数输入四整数v[0]=v0;v[0]=v0; v[1]=v1;v[1]=v1;v[2]=v2;v[2]=v2; v[3]=v3;v[3]=v3; //-----------//-----------四重循环开始穷举四个数字的位置四重循环开始穷举四个数字的位置: : 4!=244!=24 种种----------------------------------------------------3intint count=0;count=0; //// 计数成功次数计数成功次数forfor (int(int i1=0;i1<4;i1++)i1=0;i1<4;i1++)forfor (int(int i2=0;i2<4;i2++)i2=0;i2<4;i2++) //// 四重循环对四个数穷举四重循环对四个数穷举ifif (i2!=i1)(i2!=i1。