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