lzmagic

博学审问慎思明辨笃行

日历

2008年11月

日

一

二

三

四

五

六

统计

随笔 - 16
文章 - 1
评论 - 5
引用 - 0

随笔分类(18)

随笔档案(16)

文章档案(1)

2008年12月 (1)

搜索

积分与排名

积分 - 4739
排名 - 367

阅读排行榜

评论排行榜

加减乘除24

/**
2

* 程序：加减乘除24
3

* 输入：四个1到13整数（输入四个0结束）
4

* 输出：加减乘除得到24的式子，否则输出"None."
5

* 思路：我们希望构造出满足形如 a[0] opr[0] a[1] opr[1] a[2] opr[2] a[3] = 24 的式子，采用回溯的思路，将右式不断缩小，
6

* 最后只剩下a[0]，然后再判断左式是否与它相等，相等的话就结束搜索，输出结果。
7

* 注：1）opr[i]指的是右式（不妨设为X）和a[i]的操作类型，一共有6种：
8

* ADD: X + a[i] (= a[i] + X，算为同一种)
9

* SUB_L: a[i] - X
10

* SUB_R: X - a[i]
11

* MUL: X * a[i] (= a[i] * X，算为同一种)
12

* DIV_L: a[i] / X
13

* DIV_R: X / a[i]
14

* 2）回溯中把右式分解出分子(u)和分母(d)主要是考虑一些特殊情况，例如3, 3, 7, 7和4, 4, 5, 5
15

* 作者：lzmagic
16

*/
17

#include <iostream>
19

using namespace std;
20

enum OPR { ADD, SUB_L, SUB_R, MUL, DIV_L, DIV_R };
22

int a[4]; // 操作数的数组
24

OPR opr[3]; // 操作符的数组
25

int top; // 当前要处理的操作符的下标
26

bool ok; // 是否成功的布尔值
27

void TB2 (int id)
29

{
30

if (id == 0)
31

{
32

cout << a[id];
33

return;
34

}
35

switch (opr[id - 1])
37

{
38

case ADD: cout << "( "; TB2 (id - 1); cout << " + " << a[id] << " )"; break;
39

case SUB_L: cout << "( " << a[id] << " - "; TB2 (id - 1); cout << " )"; break;
40

case SUB_R: cout << "( "; TB2 (id - 1); cout << " - " << a[id] << " )"; break;
41

case MUL: cout << "( "; TB2 (id - 1); cout << " * " << a[id] << " )"; break;
42

case DIV_L: cout << "( " << a[id] << " / "; TB2 (id - 1); cout << " )"; break;
43

case DIV_R: cout << "( "; TB2 (id - 1); cout << " / " << a[id] << " )"; break;
44

}
45

}
46

void Print()
48

{
49

cout << "24 = ";
50

TB2(3);
51

cout << endl;
52

}
53

void Swap (int & a, int & b)
55

{
56

int tmp = a; a = b; b = tmp;
57

}
58

void TB1 (int u, int d, int id) // u: up，表示右式的分子；d: down，表示右式的分母；TB: trackback，表示回溯。
60

{
61

if (id == 0)
62

{
63

if (d != 0 && u % d == 0 && u / d == a[id])
64

{
65

ok = true;
66

Print();
67

}
68

return;
69

}
70

for (int i = id; i >= 0; --i)
72

{
73

Swap (a[id], a[i]);
74

// ADD : X + a[id] = u / d <==> X = (u - a[id] * d) / d
76

opr[top--] = ADD;
77

TB1 (u - a[id] * d, d, id - 1); if (ok == true) break;
78

top++;
79

// SUB_L : a[id] - X = u / d <==> X = (a[id] * d - u) / d
81

opr[top--] = SUB_L;
82

TB1 (a[id] * d - u, d, id - 1); if (ok == true) break;
83

top++;
84

// SUB_R : X - a[id] = u / d <==> X = (a[id] * d + u) / d
86

opr[top--] = SUB_R;
87

TB1 (a[id] * d + u, d, id - 1); if (ok == true) break;
88

top++;
89

// MUL : X * a[id] = u / d <==> X = a[id] / (a[id] * d)
91

opr[top--] = MUL;
92

TB1 (u, a[id] * d, id - 1); if (ok == true) break;
93

top++;
94

// DIV_L : a[id] / X = u / d <==> X = (a[id] * d) / u
96

opr[top--] = DIV_L;
97

TB1 (a[id] * d, u, id - 1); if (ok == true) break;
98

top++;
99

100

// DIV_R : X / a[id] = u / d <==> X = (a[id] * u) / d
101

opr[top--] = DIV_R;
102

TB1 (a[id] * u, d, id - 1); if (ok == true) break;
103

top++;
104

105

Swap (a[id], a[i]);
106

}
107

}
108

109

int main()
110

{
111

for (int i = 0; i < 4; ++i)
112

cin >> a[i];
113

114

while (a[0] != 0 || a[1] != 0 || a[2] != 0 || a[3] != 0)
115

{
116

ok = false;
117

top = 2;
118

TB1 (24, 1, 3);
119

if (ok == false)
120

cout << "None." << endl;
121

122

for (i = 0; i < 4; ++i)
123

cin >> a[i];
124

}
125

126

return 0;
127

}

posted on 2008-10-21 08:13 lzmagic 阅读(1152) 评论(5) 编辑收藏引用所属分类: 回溯法

评论:

# re: 加减乘除24 天策魂之音 Posted @ 2008-10-22 19:58
与其光贴代码不如把思路share出来

何如？

而且关键代码一行注释也没-。- 回复更多评论
# re: 加减乘除24 金山毒霸2008 Posted @ 2008-10-22 21:42
没错，需要思路的介绍啊，期待中。回复更多评论
# re: 加减乘除24 canopus Posted @ 2008-10-23 09:48
很好，看懂了，收藏回复更多评论
# re: 加减乘除24 lzmagic Posted @ 2008-10-23 15:36
哈哈，改过来了，之前没太重视，谢谢大家的建议！回复更多评论
# re: 加减乘除24 QQ87567844 Posted @ 2008-11-03 20:27
if (ok == true) 等价于 if(ok) C++语句还没有学好。回复更多评论

刷新评论列表

标题

姓名

主页


验证码	*

内容(提交失败后,可以通过“恢复上次提交”恢复刚刚提交的内容)

Remember Me?

登录使用高级评论新用户注册返回页首恢复上次提交

[使用Ctrl+Enter键可以直接提交]

导航

常用链接

留言簿