精品免费tv久久久久久久,国产精品久久久久乳精品爆,精品国产乱码久久久久软件

加減乘除24

Posted on 2008-10-21 08:13 lzmagic 閱讀(2405) 評論(7) 編輯收藏引用

/**
2

* 程序：加減乘除24
3

*    輸入：四個1到13整數(shù)（輸入四個0結(jié)束） 1/**//**
2 *    程序：加減乘除24
3 *    輸入：四個1到13整數(shù)（輸入四個0結(jié)束）
4 *    輸出：加減乘除得到24的式子，否則輸出"None."
5 *    思路：我們希望構(gòu)造出滿足形如 a[0] opr[0] a[1] opr[1] a[2] opr[2] a[3] = 24 的式子，采用回溯的思路，將右式不斷縮小，
6 *        最后只剩下a[0]，然后再判斷左式是否與它相等，相等的話就結(jié)束搜索，輸出結(jié)果。
7 *            注：1）opr[i]指的是右式（不妨設(shè)為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];            // 操作數(shù)的數(shù)組
24OPR opr[3];    // 操作符的數(shù)組
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

* 思路：我們希望構(gòu)造出滿足形如 a[0] opr[0] a[1] opr[1] a[2] opr[2] a[3] = 24 的式子，采用回溯的思路，將右式不斷縮小，
6

* 最后只剩下a[0]，然后再判斷左式是否與它相等，相等的話就結(jié)束搜索，輸出結(jié)果。
7

* 注：1）opr[i]指的是右式（不妨設(shè)為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]; // 操作數(shù)的數(shù)組
24

OPR opr[3]; // 操作符的數(shù)組
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

}

Feedback

# re: 加減乘除24 回復(fù) 更多評論

2008-10-22 19:58 by 天策魂之音

與其光貼代碼不如把思路share出來

何如？

而且關(guān)鍵代碼一行注釋也沒-。-

# re: 加減乘除24 回復(fù) 更多評論

2008-10-22 21:42 by 金山毒霸2008

沒錯，需要思路的介紹啊，期待中。

# re: 加減乘除24 回復(fù) 更多評論

2008-10-23 09:48 by canopus

很好，看懂了，收藏

# re: 加減乘除24 回復(fù) 更多評論

2008-10-23 15:36 by lzmagic

哈哈，改過來了，之前沒太重視，謝謝大家的建議！

# re: 加減乘除24 回復(fù) 更多評論

2009-04-15 14:22 by brightcoder

博主好強大，呵呵，搜索，又是搜索

# re: 加減乘除24 回復(fù) 更多評論

2009-06-18 13:09 by adad

6.7.8.9.10加減乘除怎么能=24

# re: 加減乘除24 回復(fù) 更多評論

2010-07-12 10:38 by 65666

想問下~為什么tb1函數(shù)要swap交換后在執(zhí)行后有swap

刷新評論列表

只有注冊用戶登錄后才能發(fā)表評論。
【推薦】100%開源！大型工業(yè)跨平臺軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

lzm

導(dǎo)航

常用鏈接

留言簿(2)

隨筆分類(13)

隨筆檔案(14)

收藏夾(4)

最新隨筆

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

加減乘除24

Feedback

# re: 加減乘除24 回復(fù) 更多評論

# re: 加減乘除24 回復(fù) 更多評論

# re: 加減乘除24 回復(fù) 更多評論

# re: 加減乘除24 回復(fù) 更多評論

# re: 加減乘除24 回復(fù) 更多評論

# re: 加減乘除24 回復(fù) 更多評論

# re: 加減乘除24 回復(fù) 更多評論