|
|
Posted on 2008-10-21 08:13 lzmagic 閱讀(2439) 評論(7) 編輯 收藏 引用
1  /**//**
2 * 程序：加減乘除24
3 * 輸入：四個1到13整數（輸入四個0結束） 1/**//**
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
18#include <iostream>
19using namespace std;
20
21enum OPR { ADD, SUB_L, SUB_R, MUL, DIV_L, DIV_R };
22
23int a[4]; // 操作數的數組
24OPR opr[3]; // 操作符的數組
25int top; // 當前要處理的操作符的下標
26bool ok; // 是否成功的布爾值
27
28void TB2 (int id)
29{
30 if (id == 0)
31 {
32 cout << a[id];
33 return;
34 }
35
36 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
47void Print()
48{
49 cout << "24 = ";
50 TB2(3);
51 cout << endl;
52}
53
54void Swap (int & a, int & b)
55{
56 int tmp = a; a = b; b = tmp;
57}
58
59void 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
71 for (int i = id; i >= 0; --i)
72 {
73 Swap (a[id], a[i]);
74
75 // 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
80 // 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
85 // 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
90 // 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
95 // 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
109int 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}
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
18#include <iostream>
19using namespace std;
20
21enum OPR  { ADD, SUB_L, SUB_R, MUL, DIV_L, DIV_R };
22
23int a[4]; // 操作數的數組
24OPR opr[3]; // 操作符的數組
25int top; // 當前要處理的操作符的下標
26bool ok; // 是否成功的布爾值
27
28void TB2 (int id)
29{
30 if (id == 0)
31  {
32 cout << a[id];
33 return;
34 }
35
36 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
47void Print()
48{
49 cout << "24 = ";
50 TB2(3);
51 cout << endl;
52}
53
54void Swap (int & a, int & b)
55{
56 int tmp = a; a = b; b = tmp;
57}
58
59void 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
71 for (int i = id; i >= 0; --i)
72 {
73 Swap (a[id], a[i]);
74
75 // 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
80 // 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
85 // 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
90 // 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
95 // 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
109int 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}
Feedback
與其光貼代碼不如把思路share出來
何如？
而且關鍵代碼一行注釋也沒-。-
想問下~為什么tb1函數要swap交換后在執行后有swap
|