下面的東西要編譯的話，妳壹定要看得懂的
問題描述:
有四個整數(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))
其中運算符對應關系有64種
運算數對應關系24種．
考慮6／（5／4 －1）＝ 24自定義數據類型cdata,包含整形的分子，分母．
最後排除重復(輸出成字符串再比較)
1，由於運算數相同的問題，直接比較就行了．
2，交換律的問題：
(( 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).都是運算符也保證順序的唯壹性.
3，分配律不認為重復．
4,結合律,如: a + b –c = a – c + b;由於只有三個運算符,故只會出現兩個運算符的結合律和三個運算符的結合律.我們先將-/變成加乘,全部是加(乘)的結合律好處理.a-(b*c),a-(b/c),a/(b+c),a/(b-c)不好處理,加個標記就行了.總***三個運算符,而結合律至少要兩個運算符,故b,c不會再包含運算符.
cdata的結構:
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
const double epsilon = 1E-14;
const double destination = 24;
const double CARD_VALUE_MIN = 1;
const double CARD_VALUE_MAX = 13;
const char symbol_array[] = {'+','-','*','/'};
double max(const double a,const double b);
bool approx_equal(const double a,const double b);
double calc_each(const double a,const double b,const int method);
void insert_element(vector<double> &v,const int pos,const double value);
bool print_formule(const vector<double> &v,const int formule_id,const int symb_a,
const int symb_b,const int symb_c);
void calc_elements(const vector<double> &v);
void calc_permutation(vector<double> queue,vector<double> to_permute); //只有對於沒有重復的數組才能產生正確的全排列
void calc_permutation_standard(vector<double> queue);
int rcount = 0;
int main(int argc,char *argv[])
{ if(argc < 5)
{
cout << "Calc point 24 verstion 0.1" << endl;
cout << "Usage: " << argv[0] << " <card1> <card2> <card3> <card4> " << endl;
return 1;
}
else
{
vector<double> card(4);
vector<double> helper(1);
for(int i = 0; i < 4; i++)
{
card[i] = atof(argv[i+1]);
if(card[i] < CARD_VALUE_MIN || card[i] > CARD_VALUE_MAX)
{
cout << "Invailed value of card!" << endl;
return 1;
}
}
/*if(card[0] == card[1] && card[0] == card[2] && card[0] == card[3])
calc_elements(card);
else
{
calc_elements(card);
calc_permutation(card,helper);
}*/
calc_permutation_standard(card);
cout << "The total result is " << rcount << endl;
}
return 0;
}
double max(const double a,const double b)
{ return a > b ? a : b;
}
bool approx_equal(const double a,const double b)
{ if(a == 0) return fabs(b) <= epsilon;
if(b == 0) return fabs(a) <= epsilon;
return fabs(a - b) / max(fabs(a),fabs(b)) <= epsilon;
}
double calc_each(const double a,const double b,const int method)
{ if(method == 0) return a + b;
if(method == 1) return a - b;
if(method == 2) return a * b;
if(method == 3 && b != 0) return a / b;
return -999;
}
void insert_element(vector<double> &v,const int pos,const double value)
{ v.push_back(0);
for(int i = v.size() - 2; i >= pos; i--)
v[i+1] = v[i];
v[pos] = value;
}
bool print_formule(const vector<double> &v,const int formule_id,const int symb_a,
const int symb_b,const int symb_c)
{ double r1,r2,result = 0;
if(formule_id == 0)
{
r1 = calc_each(v[0],v[1],symb_a);
if(approx_equal(r1,-999)) return false;
r2 = calc_each(r1,v[2],symb_b);
if(approx_equal(r2,-999)) return false;
result = calc_each(r2,v[3],symb_c);
}
else if(formule_id == 1)
{
r1 = calc_each(v[0],v[1],symb_a);
if(approx_equal(r1,-999)) return false;
r2 = calc_each(v[2],v[3],symb_b);//symb_c);
if(approx_equal(r2,-999)) return false;
result = calc_each(r1,r2,symb_c);//symb_b);
}
else if(formule_id == 2)
{
r1 = calc_each(v[1],v[2],symb_a);//symb_b);
if(approx_equal(r1,-999)) return false;
r2 = calc_each(v[0],r1,symb_b);//symb_a);
if(approx_equal(r2,-999)) return false;
result = calc_each(r2,v[3],symb_c);
}
else if(formule_id == 3)
{
r1 = calc_each(v[1],v[2],symb_a);//symb_b);
if(approx_equal(r1,-999)) return false;
r2 = calc_each(r1,v[3],symb_b);//symb_c);
if(approx_equal(r2,-999)) return false;
result = calc_each(v[0],r2,symb_c);//symb_a);
}
else if(formule_id == 4)
{
r1 = calc_each(v[2],v[3],symb_a);//symb_c);
if(approx_equal(r1,-999)) return false;
r2 = calc_each(v[1],r1,symb_b);//symb_b);
if(approx_equal(r2,-999)) return false;
result = calc_each(v[0],r2,symb_c);//symb_a);
}
if(approx_equal(result,-999)) return false;
if(approx_equal(result,destination))
{
if(formule_id == 0)
{
cout << "((" << v[0] << symbol_array[symb_a] << v[1] << ")" << symbol_array[symb_b]
<< v[2] << ")" << symbol_array[symb_c] << v[3] << "=" << destination << endl;
return true;
}
else if(formule_id == 1)
{
cout << "(" << v[0] << symbol_array[symb_a] << v[1] << ")" << symbol_array[symb_b]
<< "(" << v[2] << symbol_array[symb_c] << v[3] << ")=" << destination << endl;
return true;
}
else if(formule_id == 2)
{
cout << "(" << v[0] << symbol_array[symb_a] << "(" << v[1] << symbol_array[symb_b]
<< v[2] << "))" << symbol_array[symb_c] << v[3] << "=" << destination << endl;
return true;
}
else if(formule_id == 3)
{
cout << v[0] << symbol_array[symb_a] << "((" << v[1] << symbol_array[symb_b] << v[2]
<< ")" << symbol_array[symb_c] << v[3] << ")=" << destination << endl;
return true;
}
else if(formule_id == 4)
{
cout << v[0] << symbol_array[symb_a] << "(" << v[1] << symbol_array[symb_b] << "("
<< v[2] << symbol_array[symb_c] << v[3] << "))=" << destination << endl;
return true;
}
}
return false;
}
void calc_elements(const vector<double> &v)
{ int i,j,k,l;
for(l = 0; l < 5; l++)
{
for(i = 0; i < 4; i++)
{
for(j = 0; j < 4; j++)
{
for(k = 0; k < 4; k++)
{
if(print_formule(v,l,i,j,k))
{
rcount++;
}
}
}
}
}
}
void calc_permutation(vector<double> queue,vector<double> to_permute)
{ if(queue.size() == 0)
{
to_permute.pop_back();
calc_elements(to_permute);
}
else
{
vector<double> mir_queue = queue;
vector<double> mir_to_permute = to_permute;
vector<double> bak_vector;
double back_value = mir_queue[mir_queue.size() - 1];
mir_queue.pop_back();
for(int i = 0; i < mir_to_permute.size(); i++)
{
bak_vector = mir_to_permute;
insert_element(mir_to_permute,i,back_value);
calc_permutation(mir_queue,mir_to_permute);
mir_to_permute = bak_vector;
}
}
}
void calc_permutation_standard(vector<double> queue)
{ sort(queue.begin(),queue.end());
calc_elements(queue);
while(next_permutation(queue.begin(),queue.end()))
{
calc_elements(queue);
}
}