Question

c++的一道题目是：求出下面形式的算式，每个算式中有9个数位，正好用尽1到9这九个数字：

1)ooo+ooo=ooo(共有168种可能的组合）
2)o*oooo=oooo(共有2种可能的组合)
3)oo*ooo=oooo(共有7种可能的组合)
4)o*ooo=oo*ooo(共有13种可能的组合)
5)o*ooo=o*oooo(共有28种可能的组合)
6)oo*oo=oo*ooo(共有11种可能的组合)

Answer 1

#include <iostream>
#include <string>
#include <cstdlib>
#include <stack>
#include <vector>
#include <cmath>
#include <exception>

using namespace std;

class Equation
{
public :

/*
假设所有合法的表达式的计算结果都是正数
如果预见表达式重复，返回 REPEAT_EXPRESSION
例如 ：
123 + 456 和 456 + 123 重复
123 * 456 和 456 * 123 重复
*/
static const int REPEAT_EXPRESSION = -1;

static int calculate(string equation);
static int calculateFunction(int numA,char op,int numB);
static bool isOperator(char op);
static int getOperatorRank(char op);
static bool isExchengeableOperator(char op);

Equation(string pattern,string digitSet);
void printMatchResult();
private :
void match();
void matchFunction(bool isDigitUsed[],int startMatchPos);
// 等式的模式
string pattern;
// 替换等式中数字的数字集合
string digitSet;
// 替换后成立的等式结果
vector<string> matchResult;
};

Equation :: Equation(string pattern,string digitSet)
{
this->pattern = pattern;
this->digitSet = digitSet;
this->match();
}
// 输出结果
void Equation:: printMatchResult()
{
cout << "pattern:" + this->pattern <<endl;
for(int i = 0 ; i < this->matchResult.size(); i ++)
{
cout.width(4);
cout << (i+1) << " : ";
cout << this->matchResult[i] << endl;
}
}

void Equation :: match()
{
// 递归函数 matchFunction 需要的参数
bool* isDigitUsed = new bool[this->digitSet.size()];
for(int i = 0 ; i < this->digitSet.size() ; i ++ )
{
isDigitUsed[i] = false;
}
matchFunction(isDigitUsed,0);
free(isDigitUsed);
}
/*
将 this->pattern 中的数字用 this->digitSet 中的数字替换
得到一个所有替换后的表达式。

如果表达式成立，结果保存在 this-> matchResult 中
*/
void Equation :: matchFunction(bool isDigitUsed[],int startMatchPos)
{
if(startMatchPos == this->pattern.size())
{
string leftExpression = this->pattern.substr(0,this->pattern.find('=')) ;
string rightExpression = this->pattern.substr(this->pattern.find('=') + 1) ;

// cout << leftExpression << " = " << calculate(leftExpression) << " , "
// << rightExpression << " = " << calculate(rightExpression) << endl;

try
{
int leftExpressionValue = calculate(leftExpression);
int rightExpressionValue = calculate(rightExpression);
if( leftExpressionValue == rightExpressionValue &&
!(leftExpressionValue == REPEAT_EXPRESSION || rightExpressionValue == REPEAT_EXPRESSION ))
{
this->matchResult.push_back(this->pattern);
}
}
catch(string & msg)
{

}

return;
}

if(this->pattern.at(startMatchPos) == 'o')
{
for(int digitPoint = 0 ; digitPoint < this->digitSet.size(); digitPoint ++)
{
if(!isDigitUsed[digitPoint])
{
// 标记
this->pattern.at(startMatchPos) = this->digitSet.at(digitPoint);
isDigitUsed[digitPoint] = true;
// 递归
matchFunction(isDigitUsed,startMatchPos + 1);
// 回溯
isDigitUsed[digitPoint] = false;
this->pattern.at(startMatchPos) = 'o';
}
} // end for( digitPoint )
}

else
{
matchFunction(isDigitUsed,startMatchPos + 1);
}

}
// 判断是否是操作符
bool Equation :: isOperator(char op)
{
if(op == '+' || op == '-' || op == '*' || op == '/' || op == '@')
{
return true;
}
else
{
return false;
}
}

// 操作数可以左右互换的运算符
bool Equation :: isExchengeableOperator(char op)
{
if(op == '+' || op == '*' )
{
return true;
}
else
{
return false;
}
}

// 获取各种运算符的优先级
int Equation :: getOperatorRank(char op)
{
if(op == '+' || op == '-' )
{
return 0;
}
else if( op == '*' ||op == '/')
{
return 1;
}
else if(op == '@')
{
return -1;
}
}
// 计算简单表达式，只有一个运算符
int Equation :: calculateFunction(int numA,char op,int numB)
{
if(op == '+')
{
return numA + numB;
}
else if(op == '-')
{
return numA - numB;
}
else if(op == '*')
{
return numA * numB;
}
else if(op == '/')
{
return numA / numB;
}
}

// 计算复杂表达式 equation 的值
int Equation :: calculate(string equation)
{
stack<char> operators;
stack<int> data;

int preOperatorPos = -1;
equation.append("@");

for(int i = 0 ; i < equation.size() ; i ++)
{
if( isOperator(equation.at(i)) )
{
// 字符串形式的整数
string dataString = equation.substr(preOperatorPos+1).substr(0,i-preOperatorPos-1);
// 将字符串装换成整数，并放入
data.push(atoi(dataString.c_str()));

// 连续从【运算符栈中】取出优先级比【当前读到】的运算符大的运算符

while(operators.size() > 0 && getOperatorRank(equation.at(i)) <= getOperatorRank(operators.top()))
{
char op = operators.top();
operators.pop();
int numB = data.top();
data.pop();
int numA = data.top();
data.pop();

if( ((int)log10(numA)) == ((int)log10(numB)) && isExchengeableOperator(op) && numA > numB)
{
return REPEAT_EXPRESSION;
}
data.push(calculateFunction(numA,op,numB));
}

operators.push(equation.at(i));
preOperatorPos = i;
}
}
return data.top() ;
}

int main(int argc, char *argv[])
{
Equation e1 = Equation("ooo+ooo=ooo","123456789");
e1.printMatchResult();

Equation e2 = Equation("o*oooo=oooo","123456789");
e2.printMatchResult();

Equation e3 = Equation("oo*ooo=oooo","123456789");
e3.printMatchResult();

Equation e4 = Equation("o*ooo=oo*ooo","123456789");
e4.printMatchResult();

Equation e5 = Equation("o*ooo=o*oooo","123456789");
e5.printMatchResult();

Equation e6 = Equation("oo*oo=oo*ooo","123456789");
e6.printMatchResult();
return 0;
}
/*
运行结果：
pattern:ooo+ooo=ooo
1 : 124+659=783
2 : 125+739=864
3 : 127+359=486
4 : 127+368=495
5 : 128+367=495
6 : 128+439=567
7 : 129+357=486
8 : 129+438=567
9 : 129+654=783
10 : 129+735=864
11 : 134+658=792
12 : 135+729=864
13 : 138+429=567
14 : 138+654=792
15 : 139+428=567
16 : 139+725=864
17 : 142+596=738
18 : 142+695=837
19 : 143+586=729
20 : 145+692=837
21 : 146+583=729
22 : 146+592=738
23 : 152+487=639
24 : 152+784=936
25 : 154+629=783
26 : 154+638=792
27 : 154+782=936
28 : 157+329=486
29 : 157+482=639
30 : 158+634=792
31 : 159+327=486
32 : 159+624=783
33 : 162+387=549
34 : 162+783=945
35 : 163+782=945
36 : 167+328=495
37 : 167+382=549
38 : 168+327=495
39 : 173+286=459
40 : 173+295=468
41 : 175+293=468
42 : 176+283=459
43 : 182+367=549
44 : 182+394=576
45 : 182+457=639
46 : 182+493=675
47 : 182+754=936
48 : 182+763=945
49 : 183+276=459
50 : 183+492=675
51 : 183+546=729
52 : 183+762=945
53 : 184+392=576
54 : 184+752=936
55 : 186+273=459
56 : 186+543=729
57 : 187+362=549
58 : 187+452=639
59 : 192+384=576
60 : 192+483=675
61 : 192+546=738
62 : 192+645=837
63 : 193+275=468
64 : 193+482=675
65 : 194+382=576
66 : 195+273=468
67 : 195+642=837
68 : 196+542=738
69 : 214+569=783
70 : 214+659=873
71 : 215+478=693
72 : 215+748=963
73 : 216+378=594
74 : 216+738=954
75 : 218+349=567
76 : 218+376=594
77 : 218+439=657
78 : 218+475=693
79 : 218+736=954
80 : 218+745=963
81 : 219+348=567
82 : 219+438=657
83 : 219+564=783
84 : 219+654=873
85 : 234+657=891
86 : 235+746=981
87 : 236+718=954
88 : 236+745=981
89 : 237+654=891
90 : 238+419=657
91 : 238+716=954
92 : 239+418=657
93 : 241+596=837
94 : 243+576=819
95 : 243+675=918
96 : 245+673=918
97 : 245+718=963
98 : 245+736=981
99 : 246+573=819
100 : 246+591=837
101 : 246+735=981
102 : 248+319=567
103 : 248+715=963
104 : 249+318=567
105 : 251+397=648
106 : 254+619=873
107 : 254+637=891
108 : 257+391=648
109 : 257+634=891
110 : 259+614=873
111 : 264+519=783
112 : 269+514=783
113 : 271+593=864
114 : 271+683=954
115 : 273+546=819
116 : 273+591=864
117 : 273+645=918
118 : 273+681=954
119 : 275+418=693
120 : 275+643=918
121 : 276+318=594
122 : 276+543=819
123 : 278+316=594
124 : 278+415=693
125 : 281+394=675
126 : 281+673=954
127 : 283+671=954
128 : 284+391=675
129 : 291+357=648
130 : 291+384=675
131 : 291+546=837
132 : 291+573=864
133 : 293+571=864
134 : 294+381=675
135 : 296+541=837
136 : 297+351=648
137 : 314+658=972
138 : 317+529=846
139 : 317+628=945
140 : 318+627=945
141 : 318+654=972
142 : 319+527=846
143 : 324+567=891
144 : 324+657=981
145 : 327+519=846
146 : 327+564=891
147 : 327+618=945
148 : 327+654=981
149 : 328+617=945
150 : 329+517=846
151 : 341+586=927
152 : 342+576=918
153 : 346+572=918
154 : 346+581=927
155 : 352+467=819
156 : 354+618=972
157 : 354+627=981
158 : 357+462=819
159 : 357+624=981
160 : 358+614=972
161 : 362+457=819
162 : 364+527=891
163 : 367+452=819
164 : 367+524=891
165 : 372+546=918
166 : 376+542=918
167 : 381+546=927
168 : 386+541=927
pattern:o*oooo=oooo
1 : 4*1738=6952
2 : 4*1963=7852
pattern:oo*ooo=oooo
1 : 12*483=5796
2 : 18*297=5346
3 : 27*198=5346
4 : 28*157=4396
5 : 39*186=7254
6 : 42*138=5796
7 : 48*159=7632
pattern:o*ooo=oo*ooo
1 : 4*897=23*156
2 : 7*538=14*269
3 : 7*586=14*293
4 : 7*638=29*154
5 : 7*658=14*329
6 : 7*984=56*123
7 : 8*459=27*136
8 : 8*759=46*132
9 : 9*476=28*153
10 : 9*534=18*267
11 : 9*546=18*273
12 : 9*654=18*327
13 : 9*782=46*153
pattern:o*ooo=o*oooo
1 : 4*679=2*1358
2 : 4*769=2*1538
3 : 4*793=2*1586
4 : 6*583=2*1749
5 : 6*729=3*1458
6 : 6*792=3*1584
7 : 6*927=3*1854
8 : 7*534=2*1869
9 : 7*986=2*3451
10 : 8*394=2*1576
11 : 8*439=2*1756
12 : 8*459=1*3672
13 : 8*469=1*3752
14 : 8*537=1*4296
15 : 8*579=1*4632
16 : 8*592=1*4736
17 : 8*674=1*5392
18 : 8*679=1*5432
19 : 8*742=1*5936
20 : 8*794=1*6352
21 : 8*932=1*7456
22 : 8*942=1*7536
23 : 8*953=1*7624
24 : 8*954=1*7632
25 : 9*582=3*1746
26 : 9*638=1*5742
27 : 9*647=1*5823
28 : 9*836=1*7524
pattern:oo*oo=oo*ooo
1 : 46*79=23*158
2 : 54*69=27*138
3 : 54*93=27*186
4 : 58*67=29*134
5 : 58*69=23*174
6 : 58*73=29*146
7 : 58*96=32*174
8 : 63*74=18*259
9 : 64*79=32*158
10 : 73*96=12*584
11 : 76*98=14*532
*/

Answer 2

比较傻的穷举法：
int i1,i2,i3,i4,i5,i6,i7,i8,i9;
for(i1=1;i1<10;++i1)
for(i2=1;i2<10&&i2!=i1;++i2)
for(i3=1;i3<10&&i3!=i2&&i3!=i1;++i3)
for(i4=1;i4<10&&i4!=i3&&i4!=i2&&i4!=i1;++i4)
for(i5=1;i5<10&&i5!=i4&&i5!=i3&&i5!=i2&&i5!=i1;++i5)
for(i6=1;i6<10&&i6!=i5&&i6!=i4&&i6!=i3&&i6!=i2&&i6!=i1;++i6)
for(i7=1;i7<10&&i7!=i6&&i7!=i5&&i7!=i4&&i7!=i3&&i7!=i2&&i7!=i1;++i7)
for(i8=1;i8<10&&i8!=i7&&i8!=i6&&i8!=i5&&i8!=i4&&i8!=i3&&i8!=i2&&i8!=i1;++i8)
for(i9=1;i9<10&&i9!=i8&&i9!=i7&&i9!=i6&&i9!=i5&&i9!=i4&&i9!=i3&&i9!=i2&&i9!=i1;++i9)
{
//1)ooo+ooo=ooo(共有168种可能的组合）
if( i1*100 + i2*10 + i3 + i4*100 + i5*10 + i6 == i7*100 + i8*10 + i9 )
cout<<1)<<i1<<i2<<i3<<i4<<i5<<i6<<i7<<i8<<i9<<endl;

//2)o*oooo=oooo(共有2种可能的组合)
else f( i1*( i2*1000 + i3*100 + i4*10 + i5) == i6*1000 + i7*10 + i8*10 + i9 )
cout<<2)<<i1<<i2<<i3<<i4<<i5<<i6<<i7<<i8<<i9<<endl;
// 后面的自己写吧。。。
//3)oo*ooo=oooo(共有7种可能的组合)
//4)o*ooo=oo*ooo(共有13种可能的组合)
//5)o*ooo=o*oooo(共有28种可能的组合)
//6)oo*oo=oo*ooo(共有11种可能的组合)
}

Answer 3

你这个枚举一下就行了， 对于每个算式， 都用 9! 种排列去试。 你去查查 next_permutation()这个函数，是生成排列的。

#include<iostream>
#include<stdio.h>
#include <algorithm>

using namespace std;
int digit[9];
int convert(int s,int t)
{
int num=0;
for(int i=s;i<t;i++)
num*=10,num+=digit[i];
return num;
}
int main()
{
for(int i=0;i<9;i++)
digit[i]=i+1;

// 实现第三种作为示范
do
{
int x=convert(0,2);
int y=convert(2,5);
int z=convert(5,9);
if(x*y==z) printf("%d*%d=%d\n",x,y,z);
}while(next_permutation(digit,digit+9));

return 0;
}

第三种的答案是

12*483=5796
18*297=5346
27*198=5346
28*157=4396
39*186=7254
42*138=5796
48*159=7632

Answer 4

#include <iostream>
using namespace std;
int main()
{
int ans=0;
for(int i=100;i<=1000;i++)
{
int a=i%10;
int b=(i-a)/10%10;
int c=i/100;
if(a+b+c==5)
{
ans++;
}
}
cout<<ans<<endl;
return 0;
}