24點(diǎn)游戲的算法，其中最主要的思想就是窮舉法。所謂窮舉法就是列出4個(gè)數(shù)字加減乘除的各種可能性，包括括號(hào)的算法。我們可以將表達(dá)式分成以下幾種：首先我們將4個(gè)數(shù)設(shè)為a，b，c，d，，其中算術(shù)符號(hào)有+，-，*，/，。其中有效的表達(dá)式有a，ab-cd，等等。列出所有有效的表達(dá)式。其中我們用枚舉類型將符號(hào)定義成數(shù)字常量，比如用1表示+，2表示-等。如下是我對(duì)窮舉法的一種編程語(yǔ)言。在編程的頭部要對(duì)變量做下定義。其中a，b，c，d的范圍是1到10。這就需要在定義變量的時(shí)候要有限制。在vc++中的編程中，在定義控件的變量范圍可以直接填寫(xiě)變量的最大和最小，在此編程中的最大是10，最小是1。這就給編程寫(xiě)語(yǔ)句帶來(lái)了方便。
運(yùn)用C/C++語(yǔ)言開(kāi)發(fā)工具Microsoft Visual C++ 6.0，利用它簡(jiǎn)單、明了的開(kāi)發(fā)特點(diǎn)對(duì)課本知識(shí)進(jìn)行系統(tǒng)的實(shí)踐，并且通過(guò)對(duì)各個(gè)知識(shí)點(diǎn)的運(yùn)用進(jìn)行所需的程序編寫(xiě)。首先，要充分理解每個(gè)程序涉及的算法，牢記實(shí)現(xiàn)算法的每一個(gè)步驟；其次，再在計(jì)算機(jī)上利用C語(yǔ)言編寫(xiě)出代碼，要求結(jié)構(gòu)清晰，一目了然；最后，要對(duì)程序進(jìn)行優(yōu)化，使程序?qū)崿F(xiàn)優(yōu)秀的運(yùn)行功能。在編寫(xiě)程序的過(guò)程中要充分理解并能熟練使用對(duì)應(yīng)的算法，竟可能多的涉及課本中的知識(shí)點(diǎn)。總之通過(guò)實(shí)行整體方案，最終使程序達(dá)到運(yùn)行狀態(tài)，并且實(shí)現(xiàn)良好的運(yùn)行效果。
故做了如下的計(jì)劃安排，將這項(xiàng)工程分為兩大部分：程序的設(shè)計(jì)和程序的調(diào)試。
首先在程序的設(shè)計(jì)部分由分為幾個(gè)步驟：
第一步：查閱有關(guān)歸并排序算法的資料。
第二步：設(shè)計(jì)這個(gè)項(xiàng)目的整體架構(gòu)和算法。
第三步：選擇一門程序設(shè)計(jì)語(yǔ)言進(jìn)行算法的描述。
其次，進(jìn)行程序的調(diào)試。
設(shè)計(jì)方法和內(nèi)容
在做某件事時(shí)，一個(gè)好的方法往往能起到事半功倍的效果。在這個(gè)課程的設(shè)計(jì)上，我選擇了Ｃ++語(yǔ)言作為算法的描述語(yǔ)言，因?yàn)椋?/span>++語(yǔ)言具有豐富的表達(dá)能力以及代碼的高效性，并且有著良好的移植性和靈活性。同時(shí)，采用“自頂向下，個(gè)個(gè)擊破”的程序設(shè)計(jì)思路和思想，充分運(yùn)用Ｃ++語(yǔ)言強(qiáng)大的功能。使該課程設(shè)計(jì)做起來(lái)更加的簡(jiǎn)單。
我將這個(gè)課程設(shè)計(jì)整體分成了兩個(gè)部分。一個(gè)是數(shù)據(jù)結(jié)構(gòu)定義部分和算法部分。這兩大部分有機(jī)的結(jié)合共同構(gòu)成了該課程設(shè)計(jì)的程序，運(yùn)行該程序就可以將該課程設(shè)計(jì)的功能實(shí)現(xiàn)了。
程序的設(shè)計(jì)思想和內(nèi)容
（一）算法一：
24點(diǎn)游戲的算法，其中最主要的思想就是窮舉法。所謂窮舉法就是列出4個(gè)數(shù)字加減乘除的各種可能性。我們可以將表達(dá)式分成以下幾種：首先我們將4個(gè)數(shù)設(shè)為a,b,c,d,，將其排序列出四個(gè)數(shù)的所有排序序列組合（共有A44=24種組合）。再進(jìn)行符號(hào)的排列表達(dá)式，其中算術(shù)符號(hào)有+，—，*，/，（，）。其中有效的表達(dá)式有a*(b-c/b)，a*b-c*d,等等。列出所有有效的表達(dá)式。其中我們用枚舉類型將符號(hào)定義成數(shù)字常量。如下是我對(duì)窮舉法的一種編程語(yǔ)言。在編程的頭部要對(duì)變量做下定義。其中a,b,c,d的范圍是1到10。這就需要在定義變量的時(shí)候要有限制。在vc++中的MFC編程中，在定義控件的變量范圍可以直接填寫(xiě)變量的最大和最小，在此編程中的最大是10，最小是1。這就給編程寫(xiě)語(yǔ)句帶來(lái)了方便（因?yàn)槠渥詣?dòng)會(huì)生成語(yǔ)句）。下面我介紹下窮舉法的主要實(shí)現(xiàn)，我們知道要實(shí)現(xiàn)24點(diǎn)的算法，就是通過(guò)4個(gè)數(shù)字，4個(gè)運(yùn)算符號(hào)和2對(duì)括號(hào)（最多為2對(duì)），通過(guò)各種組合判斷其結(jié)果是否為24。我們用a，b，c,d代替4個(gè)數(shù)字。考慮每種可能，總的算法就有7種可能。分別為：
1沒(méi)括號(hào)的（形如a*b*c*d）；
2有括號(hào)的（形如(a * b) * c * d）；
3有括號(hào)的（形如(a * b * c) * d）；
4有括號(hào)的（形如a * (b * c) * d）；
5有括號(hào)的（形如(a * b) * (c * d)）；
6有括號(hào)的（形如((a * b) * c) * d）；
7有括號(hào)的（形如(a * (b * c)) * d）。
接下來(lái)就是對(duì)每一種進(jìn)行分析判斷。
以上就是窮舉法的基本實(shí)現(xiàn)算法
首先窮舉的可行性問(wèn)題。我把表達(dá)式如下分成三類：
1、 列出四個(gè)數(shù)的所有排序序列組合（共有A44=24種組合）。
2、 構(gòu)筑一個(gè)函數(shù)，列出所有運(yùn)算表達(dá)式。
3、 輸入數(shù)據(jù)計(jì)算。
（二）算法二：
24點(diǎn)游戲的算法，還有另外一種算法。
把多元運(yùn)算轉(zhuǎn)化為兩元運(yùn)算，先從四個(gè)數(shù)中取出兩個(gè)數(shù)進(jìn)行運(yùn)算，然后把運(yùn)算結(jié)果和第三個(gè)數(shù)進(jìn)行運(yùn)算，再把結(jié)果與第四個(gè)數(shù)進(jìn)行運(yùn)算。在求表達(dá)式的過(guò)程中，最難處理的就是對(duì)括號(hào)的處理，而這種思路很好的避免了對(duì)括號(hào)的處理。基于這種思路的一種算法：
因?yàn)槟苁褂玫?/span>4種運(yùn)算符 – * / 都是2元運(yùn)算符，所以本文中只考慮2元運(yùn)算符。2元運(yùn)算符接收兩個(gè)參數(shù)，輸出計(jì)算結(jié)果，輸出的結(jié)果參與后續(xù)的計(jì)算。
由上所述，構(gòu)造所有可能的表達(dá)式的算法如下：
(1) 將4個(gè)整數(shù)放入數(shù)組中
(2) 在數(shù)組中取兩個(gè)數(shù)字的排列，共有 P(4,2) 種排列。對(duì)每一個(gè)排列，
(2.1) 對(duì) – * / 每一個(gè)運(yùn)算符，
(2.1.1) 根據(jù)此排列的兩個(gè)數(shù)字和運(yùn)算符，計(jì)算結(jié)果
(2.1.2) 改表數(shù)組：將此排列的兩個(gè)數(shù)字從數(shù)組中去除掉，將 2.1.1 計(jì)算的結(jié)果放入數(shù)組中
(2.1.3) 對(duì)新的數(shù)組，重復(fù)步驟 2
(2.1.4) 恢復(fù)數(shù)組：將此排列的兩個(gè)數(shù)字加入數(shù)組中，將 2.1.1 計(jì)算的結(jié)果從數(shù)組中去除掉
可見(jiàn)這是一個(gè)遞歸過(guò)程。步驟 2 就是遞歸函數(shù)。當(dāng)數(shù)組中只剩下一個(gè)數(shù)字的時(shí)候，這就是表達(dá)式的最終結(jié)果，此時(shí)遞歸結(jié)束。
在程序中，一定要注意遞歸的現(xiàn)場(chǎng)保護(hù)和恢復(fù)，也就是遞歸調(diào)用之前與之后，現(xiàn)場(chǎng)狀態(tài)應(yīng)該保持一致。在上述算法中，遞歸現(xiàn)場(chǎng)就是指數(shù)組，2.1.2 改變數(shù)組以進(jìn)行下一層遞歸調(diào)用，2.1.3 則恢復(fù)數(shù)組，以確保當(dāng)前遞歸調(diào)用獲得下一個(gè)正確的排列。
括號(hào) () 的作用只是改變運(yùn)算符的優(yōu)先級(jí)，也就是運(yùn)算符的計(jì)算順序。所以在以上算法中，無(wú)需考慮括號(hào)。括號(hào)只是在輸出時(shí)需加以考慮。
void Chazhao(int n) {
if (n == 1) {
if ( fabs(number[0] - VOLUE) <= LING ) //對(duì)于除法，要小心小數(shù)的精確位數(shù)
{ cout << biaodashi[0] << "\t\t";
Panduan = true;
count ++;
if((count % 3)==0) //使輸出時(shí)每行三個(gè)表達(dá)式
cout<<endl;
}
else
{ }
}
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]; //遞歸之后，n比以前小一位，所以可以不停向前賦值
expa = biaodashi[i];
expb = biaodashi[j];
biaodashi[j] = biaodashi[n - 1]; //遞歸之后，n比以前小一位，所以可以不停向前賦值
biaodashi[i]= '('+ expa + '+' + expb + ')'; //加法不需要分順序
number[i] = a + b;
Chazhao(n-1);
biaodashi[i]='('+ expa+ '-' + expb + ')'; //減法應(yīng)該分順序，減數(shù)以及被減數(shù)
number[i] = a - b;
Chazhao(n-1);
biaodashi[i] = '('+expb + '-' + expa + ')'; //減法應(yīng)該分順序，減數(shù)以及被減數(shù)
number[i] = b -a;
Chazhao(n-1);
biaodashi[i]= '('+ expa +'*'+ expb+ ')'; //乘法不需要分順序
number[i]=a*b;
Chazhao(n-1);
if (b != 0) {
biaodashi[i] ='('+expa+'/' + expb + ')'; //除法應(yīng)該分順序，除數(shù)以及被除數(shù)
number[i] = a / b;
Chazhao(n-1);
}
if (a != 0) {
biaodashi[i]='('+expb + '/'+ expa + ')'; //除法應(yīng)該分順序，除數(shù)以及被除數(shù)
number[i] = b / a;
Chazhao(n-1);
}
number[i] =a; //這4句語(yǔ)句是為了防止如果上面幾種可能都失敗了的話,
number[j]=b; //就把原來(lái)的賦值撤消回去,以無(wú)干擾的正確的進(jìn)入到下一次
biaodashi[i] = expa; //for循環(huán)隊(duì)列中。
biaodashi[j] = expb; //
}
}
}
附錄A 原程序代碼
算法一：
#include <iostream>
using namespace std;
int main()
{ float a,b,c,d;
fanhui: //做標(biāo)記
cout<<"請(qǐng)輸入4個(gè)數(shù)據(jù)"<<endl;
cout<<" 第一個(gè)數(shù)：";
cin>>a;
cout<<" 第二個(gè)數(shù)：";
cin>>b;
cout<<" 第三個(gè)數(shù)：";
cin>>c;
cout<<" 第四個(gè)數(shù)：";
cin>>d;
cout<<"輸出所有算法如下："<<endl;
if ((a<0)||(a>10)||(b<0)||(b>10)||(c<0)||(c>10)||(d<0)||(d>10))
{ cout<<"你輸入的輸入不對(duì)，重新輸入"<<endl;
goto fanhui; } // 返回標(biāo)記，重復(fù)輸入
int jisuan ( float x, float y, float z, float w); // a .b.c.d 的所有排列組合情況
jisuan(a,b,c,d); jisuan(a,b,d,c); jisuan(a,c,d,b);
jisuan(a,c,b,d); jisuan(a,d,b,c); jisuan(a,d,c,b);
jisuan(b,a,c,d); jisuan(b,a,d,c); jisuan(b,c,a,d);
jisuan(b,c,d,a); jisuan(b,d,c,a); jisuan(b,d,a,c);
jisuan(c,a,b,d); jisuan(c,a,d,b); jisuan(c,b,d,a);
jisuan(c,b,a,d); jisuan(c,d,a,b); jisuan(c,d,b,a);
jisuan(d,a,b,c); jisuan(d,a,c,b); jisuan(d,b,c,a);
jisuan(d,b,a,c); jisuan(d,c,a,b); jisuan(d,c,b,a);
return 0; }
int jisuan ( float x, float y, float z, float w) //運(yùn)算表達(dá)式的所有情況
{ if (x+y+z+w==24) cout<<x<<"+"<<y<<"+"<<z<<"+"<<w<<"=24"<<endl;
else if (x+y+z-w==24) cout<<x<<"+"<<y<<"+"<<z<<"-"<<w<<"=24"<<endl;
else if ((x+y)*(z+w)==24) cout<<"("<<x<<"+"<<y<<")*("<<z<<"+"<<w<<")=24"<<endl;
else if ((x-y)*(z+w)==24) cout<<"("<<x<<"-"<<y<<")*("<<z<<"+"<<w<<")=24"<<endl;
else if ((x-y)*(z-w)==24) cout<<"("<<x<<"-"<<y<<")*("<<z<<"-"<<w<<")=24"<<endl;
else if ((x+y+z)*w==24) cout<<"("<<x<<"+"<<y<<"+"<<z<<")*"<<w<<"=24"<<endl;
else if ((x-y-z)*w==24) cout<<"("<<x<<"-"<<y<<"-"<<z<<")*"<<w<<"=24"<<endl;
else if ((x+y-z)*w==24) cout<<"("<<x<<"+"<<y<<"-"<<z<<")*"<<w<<"=24"<<endl;
else if ((x*y*z)/w==24) cout<<"("<<x<<"*"<<y<<"*"<<z<<")/"<<w<<"=24"<<endl;
else if ((x*y)*(z+w)==24) cout<<"("<<x<<"*"<<y<<")*("<<z<<"+"<<w<<")=24"<<endl;
else if ((x*y)*(z-w)==24) cout<<"("<<x<<"*"<<y<<")*("<<z<<"-"<<w<<")=24"<<endl;
else if ((x*y)*z-w==24) cout<<"("<<x<<"*"<<y<<")*("<<z<<")-"<<w<<"=24"<<endl;
else if ((x*y)*z+w==24) cout<<"("<<x<<"*"<<y<<")*("<<z<<")+"<<w<<"=24"<<endl;
else if (x*y*z*w==24) cout<<x<<"*"<<y<<"*"<<z<<"*"<<w<<"=24"<<endl;
else if ((x+y)+(z/w)==24) cout<<"("<<x<<"+"<<y<<")+("<<z<<"/"<<w<<")"<<"=24"<<endl;
else if ((x+y)*(z/w)==24) cout<<"("<<x<<"+"<<y<<")*("<<z<<"/"<<w<<")"<<"=24"<<endl;
else if ((x*y)+z+w==24) cout<<"("<<x<<"*"<<y<<")+"<<z<<"+"<<w<<"=24"<<endl;
else if ((x*y)+z-w==24) cout<<"("<<x<<"*"<<y<<")+"<<z<<"-"<<w<<"=24"<<endl;
else if ((x*y)-(z/w)==24) cout<<"("<<x<<"*"<<y<<")-("<<z<<"/"<<w<<")"<<"=24"<<endl;
else if ((x*y)+(z/w)==24) cout<<"("<<x<<"*"<<y<<")-("<<z<<"/"<<w<<")"<<"=24"<<endl;
else if ((x*y)-z-w==24) cout<<"("<<x<<"*"<<y<<")-"<<z<<"-"<<w<<"=24"<<endl;
else if ((x*y)+(z*w)==24) cout<<"("<<x<<"*"<<y<<")+("<<z<<"*"<<w<<")"<<"=24"<<endl;
else if ((x*y)-(z*w)==24) cout<<"("<<x<<"*"<<y<<")-("<<z<<"*"<<w<<")"<<"=24"<<endl;
else if ((x*y)/(z*w)==24) cout<<"("<<x<<"*"<<y<<")/("<<z<<"*"<<w<<")"<<"=24"<<endl;
else if ((x*y)/(z-w)==24) cout<<"("<<x<<"*"<<y<<")/("<<z<<"-"<<w<<")"<<"=24"<<endl;
else if ((x*y)/(z+w)==24) cout<<"("<<x<<"*"<<y<<")/("<<z<<"+"<<w<<")"<<"=24"<<endl;
else cout<<"不可以組成24"<<endl;
return 0; }
算法二：
#include <iostream>
#include <string>
#include <math.h>
using namespace std;
const double LING = 1E-6;
const int CONT = 4;
const int VOLUE = 24;
double number[CONT];
string biaodashi[CONT];
bool Panduan = false; //判斷是否有解。
int count = 0;
void Chazhao(int n)
{
if (n == 1)
{
if ( fabs(number[0] - VOLUE) <= LING )
{
cout << biaodashi[0] << "\t\t";
Panduan = true;
count ++;
if((count % 3)==0) //使輸出時(shí)每行三個(gè)表達(dá)式
cout<<endl;
}
else
{ }
}
for(int i=0; i < n; i++)//查找
{
for (int j = i + 1; j < n; j++)//與其后面的查找進(jìn)行計(jì)算
{
double a, b;
string expa, expb;
a = number[i];
b = number[j];
number[j] = number[n - 1];
expa = biaodashi[i];
expb = biaodashi[j];
biaodashi[j] = biaodashi[n - 1];
biaodashi[i]= '('+ expa + '+' + expb + ')';
number[i] = a + b;
Chazhao(n-1);
biaodashi[i]='('+ expa+ '-' + expb + ')';
number[i] = a - b;
Chazhao(n-1);
biaodashi[i] = '('+expb + '-' + expa + ')';
number[i] = b -a;
Chazhao(n-1);
biaodashi[i]= '('+ expa +'*'+ expb+ ')';
number[i]=a*b;
Chazhao(n-1);
if (b != 0)
{
biaodashi[i] ='('+expa+'/' + expb + ')';
number[i] = a / b;
Chazhao(n-1);
}
if (a != 0)
{
biaodashi[i]='('+expb + '/'+ expa + ')';
number[i] = b / a;
Chazhao(n-1);
}
number[i] =a;
number[j]=b;
biaodashi[i] = expa;
biaodashi[j] = expb;
}
}
}
int main()
{
cout<<"請(qǐng)輸入四個(gè)數(shù):\n";
for (int i = 0; i < CONT; i++)
{
char ch[20];
cout<<"第"<<i+1<<"個(gè)數(shù):";
cin >>number[i];
itoa(number[i],ch, 10); //itoa()函數(shù)的作用是把第一個(gè)參數(shù)(數(shù)值)傳送(轉(zhuǎn)換)到第二個(gè)參數(shù)(字符串)中去，第三個(gè)參數(shù)(int型)是該數(shù)值在字符串里以什么進(jìn)制存放。
biaodashi[i] = ch;
}
cout<<endl;
Chazhao(CONT) ;
if(Panduan==true)
{
cout << "\n成功！" << endl;
cout<<"總共的計(jì)算方法共有： "<<count<<endl;
}
else
{
cout << "失敗！" << endl;
}
return 0;
}
posted on 2010-09-24 15:58
王秋林 閱讀(2221)
評(píng)論(0) 編輯 收藏 引用