移动火柴使得等式成立，计算机解题算法问题

最近看了igoogle上的移动火柴使得等式成立的游戏，本人反映比较慢，到了移动3根火柴的时候要想比较长的时间，就想到是不是可以用计算机解题，一个数字类似LED显示，由7根火柴组成，还有+ - =运算符号，研究了算法，目前可以列出数字变换的所有可能的列表了，这个列表的算法我也费了很大的劲，我得到了一个结果，应该是正确的，不过我的算法我先不公布，想先看看大家有什么想法，集思广益，我的代码dephi写的。
列表如下：
编号：原始数字，移动次数，添加火柴数，得到结果
01: 0,0,0,0
02: 0,1,0,6
03: 0,1,0,9
04: 0,0,1,8
05: 1,0,0,1
06: 1,0,1,7
07: 1,0,2,4
08: 1,1,3,5
09: 1,1,3,2
10: 1,0,3,3
11: 1,1,4,6
12: 1,0,4,9
13: 1,0,4,0
14: 1,0,5,8
15: 2,0,0,2
16: 2,1,0,3
17: 2,2,0,5
18: 2,1,1,6
19: 2,1,1,0
20: 2,1,1,9
21: 2,0,2,8
22: 3,0,0,3
23: 3,1,0,5
24: 3,1,0,2
25: 3,0,1,9
26: 3,1,1,6
27: 3,1,1,0
28: 3,0,2,8
29: 4,0,0,4
30: 4,1,1,3
31: 4,1,1,5
32: 4,2,1,2
33: 4,1,2,6
34: 4,1,2,0
35: 4,0,2,9
36: 4,0,3,8
37: 5,0,0,5
38: 5,1,0,3
39: 5,2,0,2
40: 5,0,1,9
41: 5,1,1,0
42: 5,0,1,6
43: 5,0,2,8
44: 6,0,0,6
45: 6,1,0,0
46: 6,1,0,9
47: 6,0,1,8
48: 7,0,0,7
49: 7,1,1,4
50: 7,1,2,5
51: 7,1,2,2
52: 7,0,2,3
53: 7,1,3,6
54: 7,0,3,9
55: 7,0,3,0
56: 7,0,4,8
57: 8,0,0,8
58: 9,0,0,9
59: 9,1,0,6
60: 9,1,0,0
61: 9,0,1,8
要想得到一个数字去除n根火柴得到的数字，只要反过来从得到结果反查原始数字就可以了，为了列表精简没有列出。

算法中要注意排除重复项，最好不要使用计入列表时通过看列表有没有重复项再排除的做法。

19 个解决方案

#1

这个已经是老题了。基本就是爆搜。

#2

包含空和+、-、=符号的符号转换表
0001: 0,0,0,0
0002: 0,1,0,6
0003: 0,1,0,9
0004: 0,0,1,8
0005: 1,0,0,1
0006: 1,2,0,+
0007: 1,2,0,=
0008: 1,0,1,7
0009: 1,0,2,4
0010: 1,1,3,5
0011: 1,1,3,2
0012: 1,0,3,3
0013: 1,1,4,6
0014: 1,0,4,9
0015: 1,0,4,0
0016: 1,0,5,8
0017: 2,0,0,2
0018: 2,1,0,3
0019: 2,2,0,5
0020: 2,1,1,6
0021: 2,1,1,0
0022: 2,1,1,9
0023: 2,0,2,8
0024: 3,0,0,3
0025: 3,1,0,5
0026: 3,1,0,2
0027: 3,0,1,9
0028: 3,1,1,6
0029: 3,1,1,0
0030: 3,0,2,8
0031: 4,0,0,4
0032: 4,1,1,3
0033: 4,1,1,5
0034: 4,2,1,2
0035: 4,1,2,6
0036: 4,1,2,0
0037: 4,0,2,9
0038: 4,0,3,8
0039: 5,0,0,5
0040: 5,1,0,3
0041: 5,2,0,2
0042: 5,0,1,9
0043: 5,1,1,0
0044: 5,0,1,6
0045: 5,0,2,8
0046: 6,0,0,6
0047: 6,1,0,0
0048: 6,1,0,9
0049: 6,0,1,8
0050: 7,0,0,7
0051: 7,1,1,4
0052: 7,1,2,5
0053: 7,1,2,2
0054: 7,0,2,3
0055: 7,1,3,6
0056: 7,0,3,9
0057: 7,0,3,0
0058: 7,0,4,8
0059: 8,0,0,8
0060: 9,0,0,9
0061: 9,1,0,6
0062: 9,1,0,0
0063: 9,0,1,8
0064:  ,0,0, 
0065:  ,0,1,-
0066:  ,0,2,1
0067:  ,0,2,+
0068:  ,0,2,=
0069:  ,0,3,7
0070:  ,0,4,4
0071:  ,0,5,5
0072:  ,0,5,2
0073:  ,0,5,3
0074:  ,0,6,9
0075:  ,0,6,0
0076:  ,0,6,6
0077:  ,0,7,8
0078: +,0,0,+
0079: +,1,0,=
0080: +,2,0,1
0081: +,2,1,7
0082: +,1,2,4
0083: +,1,3,5
0084: +,1,3,2
0085: +,1,3,3
0086: +,2,4,0
0087: +,1,4,9
0088: +,1,4,6
0089: +,1,5,8
0090: -,0,0,-
0091: -,1,1,1
0092: -,0,1,+
0093: -,0,1,=
0094: -,1,2,7
0095: -,0,3,4
0096: -,0,4,5
0097: -,0,4,2
0098: -,0,4,3
0099: -,1,5,0
0100: -,0,5,9
0101: -,0,5,6
0102: -,0,6,8
0103: =,0,0,=
0104: =,1,0,+
0105: =,2,0,1
0106: =,2,1,7
0107: =,1,2,4
0108: =,1,3,5
0109: =,1,3,2
0110: =,1,3,3
0111: =,2,4,0
0112: =,1,4,9
0113: =,1,4,6
0114: =,1,5,8

#3

各位含义还是
编号：原始数字，移动次数，添加火柴数，得到结果 

#4

终于全部做完了，经过程序检验，iGoogle上存在错误题目，目前把10个移动1根火柴的题目，程序算出来的例子和结果发出来
9-6=5 to 9-6=3 with 1 Operates
9-6=5 to 8-3=5 with 2 Operates
9-6=5 to 8-5=3 with 2 Operates
9-6=5 to 0+5=5 with 2 Operates
9-6=5 to 3=8-5 with 2 Operates
9-6=5 to 5+0=5 with 2 Operates
9-6=5 to 9-3=6 with 2 Operates
9-6=5 to 3+0=3 with 3 Operates
9-6=5 to 3+3=6 with 3 Operates
9-6=5 to 3=9-6 with 3 Operates
9-6=5 to 5=8-3 with 3 Operates
9-6=5 to 5=0+5 with 3 Operates
计算结束
3+9=0 to 9-9=0 with 1 Operates
3+9=0 to 3+5=8 with 1 Operates
3+9=0 to 9=9-0 with 2 Operates
3+9=0 to 5+3=8 with 2 Operates
3+9=0 to 3+6=9 with 2 Operates
3+9=0 to 6-6=0 with 3 Operates
3+9=0 to 6+3=9 with 3 Operates
3+9=0 to 0-0=0 with 3 Operates
3+9=0 to 9-0=9 with 3 Operates
计算结束
2+6=1 to 2+5=7 with 1 Operates
2+6=1 to 2=9-7 with 3 Operates
计算结束
9-2=5 to 3+2=5 with 1 Operates
9-2=5 to 4+2=6 with 2 Operates
9-2=5 to 5-0=5 with 2 Operates
9-2=5 to 6-3=3 with 3 Operates
9-2=5 to 2+3=5 with 3 Operates
9-2=5 to 2-2=0 with 3 Operates
9-2=5 to 3-0=3 with 3 Operates
9-2=5 to 3-3=0 with 3 Operates
9-2=5 to 5=2+3 with 3 Operates
计算结束
3-2=6 to 3+2=5 with 1 Operates
3-2=6 to 2-2=0 with 2 Operates
3-2=6 to 4+2=6 with 2 Operates
3-2=6 to 3-3=0 with 2 Operates
3-2=6 to 5-0=5 with 3 Operates
3-2=6 to 2+3=5 with 3 Operates
3-2=6 to 2=2-0 with 3 Operates
3-2=6 to 3=3-0 with 3 Operates
3-2=6 to 3-0=3 with 3 Operates
计算结束
9+1=9 to 9-1=8 with 1 Operates
9+1=9 to 2+7=9 with 2 Operates
9+1=9 to 9-4=5 with 2 Operates
9+1=9 to 8-4=4 with 3 Operates
9+1=9 to 0+4=4 with 3 Operates
计算结束
3+6=0 to 3+5=8 with 1 Operates
3+6=0 to 3+6=9 with 1 Operates
3+6=0 to 6-6=0 with 2 Operates
3+6=0 to 9-9=0 with 2 Operates
3+6=0 to 8-6=2 with 3 Operates
3+6=0 to 6=6-0 with 3 Operates
3+6=0 to 0-0=0 with 3 Operates
3+6=0 to 9=9-0 with 3 Operates
3+6=0 to 9-0=9 with 3 Operates
3+6=0 to 5+3=8 with 3 Operates
计算结束
9+1=2 to 9-7=2 with 1 Operates
9+1=2 to 5+1=6 with 2 Operates
计算结束
3+9=9 to 3+6=9 with 1 Operates
3+9=9 to 3+5=8 with 1 Operates
3+9=9 to 6+3=9 with 2 Operates
3+9=9 to 9-0=9 with 2 Operates
3+9=9 to 9-9=0 with 2 Operates
3+9=9 to 5+3=8 with 2 Operates
3+9=9 to 0=9-9 with 3 Operates
3+9=9 to 9=9-0 with 3 Operates
计算结束

#5

穷举~~~

#6

10个移动2根火柴的例子，结果中几个Operates就是移动几根火柴，这里随便什么题目都把移动1根、2根、3根的结果都列出来了。
35+17=43 to 25+17=42 with 2 Operates
35+17=43 to 35+11=46 with 2 Operates
35+17=43 to 59-17=42 with 3 Operates
35+17=43 to 56+17=73 with 3 Operates
35+17=43 to 75+17=92 with 3 Operates
35+17=43 to 38+ 7=45 with 3 Operates
35+17=43 to 39+ 4=43 with 3 Operates
35+17=43 to 39+ 7=46 with 3 Operates
35+17=43 to 35=77-42 with 3 Operates
35+17=43 to 35+12=47 with 3 Operates
计算结束
16+53=39 to  6+93=99 with 2 Operates
16+53=39 to 16+23=39 with 2 Operates
16+53=39 to 46+33=79 with 3 Operates
16+53=39 to 78-53=25 with 3 Operates
16+53=39 to 76+03=79 with 3 Operates
16+53=39 to  5+93=98 with 3 Operates
16+53=39 to  6+63=69 with 3 Operates
16+53=39 to 10+69=79 with 3 Operates
16+53=39 to 10+53=63 with 3 Operates
16+53=39 to 19+59=78 with 3 Operates
16+53=39 to 15+23=38 with 3 Operates
16+53=39 to 16+62=78 with 3 Operates
16+53=39 to 16+67=83 with 3 Operates
16+53=39 to 16+39=55 with 3 Operates
16+53=39 to 16+73=89 with 3 Operates
计算结束
24+36=67 to 25+36=61 with 2 Operates
24+36=67 to 26+35=61 with 3 Operates
24+36=67 to 29+32=61 with 3 Operates
24+36=67 to 21+66=87 with 3 Operates
24+36=67 to 24+30=54 with 3 Operates
计算结束
14+23=48 to 19+23=42 with 2 Operates
14+23=48 to 14+28=42 with 2 Operates
14+23=48 to 14+26=40 with 2 Operates
14+23=48 to 77-29=48 with 3 Operates
14+23=48 to 13+33=46 with 3 Operates
14+23=48 to 13+29=42 with 3 Operates
14+23=48 to 15+25=40 with 3 Operates
14+23=48 to 14+25=39 with 3 Operates
14+23=48 to 14+22=36 with 3 Operates
14+23=48 to 14+24=38 with 3 Operates
计算结束
15+34=49 to 79-34=45 with 2 Operates
15+34=49 to 18+31=49 with 2 Operates
15+34=49 to 19+24=43 with 2 Operates
15+34=49 to 14+34=48 with 2 Operates
15+34=49 to 35+14=49 with 3 Operates
15+34=49 to 78-34=44 with 3 Operates
15+34=49 to 79-31=48 with 3 Operates
15+34=49 to 76-34=42 with 3 Operates
15+34=49 to 73-24=49 with 3 Operates
15+34=49 to  6+39=45 with 3 Operates
15+34=49 to  5+38=43 with 3 Operates
15+34=49 to 19+74=93 with 3 Operates
15+34=49 to 12+34=46 with 3 Operates
15+34=49 to 14+35=49 with 3 Operates
15+34=49 to 15=64-49 with 3 Operates
15+34=49 to 15+64=79 with 3 Operates
15+34=49 to 15+29=44 with 3 Operates
15+34=49 to 15+44=59 with 3 Operates
计算结束
16+57=49 to 18+31=49 with 2 Operates
16+57=49 to 76-27=49 with 3 Operates
16+57=49 to 18+61=79 with 3 Operates
16+57=49 to 18+27=45 with 3 Operates
16+57=49 to 15+34=49 with 3 Operates
16+57=49 to 16+37=53 with 3 Operates
计算结束
52-35=19 to 52-39=13 with 1 Operates
52-35=19 to 52-33=19 with 1 Operates
52-35=19 to 50-35=15 with 2 Operates
52-35=19 to 52-38=14 with 2 Operates
52-35=19 to 52-34=18 with 2 Operates
52-35=19 to 93-75=18 with 3 Operates
52-35=19 to 92-76=16 with 3 Operates
52-35=19 to 62-49=13 with 3 Operates
52-35=19 to 62-43=19 with 3 Operates
52-35=19 to 48-35=13 with 3 Operates
52-35=19 to 58-45=13 with 3 Operates
52-35=19 to 50-36=14 with 3 Operates
52-35=19 to 57-38=19 with 3 Operates
52-35=19 to 57-39=18 with 3 Operates
52-35=19 to 52=65-13 with 3 Operates
计算结束
25+19=47 to 28+13=41 with 2 Operates
25+19=47 to 23+18=41 with 2 Operates
25+19=47 to 38+ 9=47 with 3 Operates
25+19=47 to 39+ 8=47 with 3 Operates
25+19=47 to 26=73-47 with 3 Operates
25+19=47 to 26+17=43 with 3 Operates
25+19=47 to 25+12=37 with 3 Operates
计算结束
72-34=49 to 12+34=46 with 2 Operates
72-34=49 to 78-34=44 with 2 Operates
72-34=49 to 79-34=45 with 2 Operates
72-34=49 to 73-24=49 with 2 Operates
72-34=49 to 18+31=49 with 3 Operates
72-34=49 to 15+34=49 with 3 Operates
72-34=49 to 12+33=45 with 3 Operates
72-34=49 to 76-34=42 with 3 Operates
72-34=49 to 79-31=48 with 3 Operates
计算结束
26+25=61 to 36+25=61 with 1 Operates
26+25=61 to 26+35=61 with 1 Operates
26+25=61 to 35+26=61 with 2 Operates
26+25=61 to 28+23=51 with 2 Operates
26+25=61 to 25+36=61 with 2 Operates
26+25=61 to 86-35=51 with 3 Operates
26+25=61 to 06+25=31 with 3 Operates
26+25=61 to 96-35=61 with 3 Operates
26+25=61 to 32+29=61 with 3 Operates
26+25=61 to 22+39=61 with 3 Operates
26+25=61 to 23+28=51 with 3 Operates
26+25=61 to 26=25+01 with 3 Operates
26+25=61 to 26+05=31 with 3 Operates
计算结束

移动3根火柴的题目，有些题目实际上不需要移动3根火柴也有结果
74+9=87 to 18+9=27 with 3 Operates
74+9=87 to 19+8=27 with 3 Operates
74+9=87 to 76-9=67 with 3 Operates
74+9=87 to 76+5=81 with 3 Operates
74+9=87 to 79+2=81 with 3 Operates
74+9=87 to 72+9=81 with 3 Operates
74+9=87 to 75-8=67 with 3 Operates
74+9=87 to 75+6=81 with 3 Operates
74+9=87 to 74-5=69 with 3 Operates
74+9=87 to 74-9=65 with 3 Operates
计算结束
55+74=44 to 58-14=44 with 2 Operates
55+74=44 to 30+14=44 with 3 Operates
55+74=44 to 59-15=44 with 3 Operates
55+74=44 to 59-14=45 with 3 Operates
55+74=44 to 55+19=74 with 3 Operates
计算结束
26+10=67 to 38+19=57 with 3 Operates
26+10=67 to 39+18=57 with 3 Operates
26+10=67 to 25+42=67 with 3 Operates
计算结束
13+3=29 to 19+3=22 with 2 Operates
13+3=29 to 13+9=22 with 2 Operates
13+3=29 to 18+9=27 with 3 Operates
13+3=29 to 19+8=27 with 3 Operates
13+3=29 to 15+5=20 with 3 Operates
13+3=29 to 12-3=09 with 3 Operates
计算结束
54+19=46 to 59-13=46 with 2 Operates
54+19=46 to 94-78=16 with 3 Operates
54+19=46 to 94-18=76 with 3 Operates
54+19=46 to 67-19=48 with 3 Operates
54+19=46 to 64=19+45 with 3 Operates
54+19=46 to 33+13=46 with 3 Operates
54+19=46 to 58-13=45 with 3 Operates
计算结束
56-33=54 to 86-35=51 with 3 Operates
56-33=54 to 90-39=51 with 3 Operates
56-33=54 to 90-33=57 with 3 Operates
56-33=54 to 96-42=54 with 3 Operates
56-33=54 to 96-35=61 with 3 Operates
56-33=54 to 56+35=91 with 3 Operates
56-33=54 to 56-22=34 with 3 Operates
56-33=54 to 56-32=24 with 3 Operates
计算结束
55+76=46 to 30+16=46 with 3 Operates
55+76=46 to 36+10=46 with 3 Operates
计算结束
38+75=91 to 38+19=57 with 2 Operates
38+75=91 to 82+15=97 with 3 Operates
38+75=91 to 66+15=81 with 3 Operates
38+75=91 to 18+76=94 with 3 Operates
38+75=91 to 18+75=93 with 3 Operates
38+75=91 to 78+16=94 with 3 Operates
38+75=91 to 78+15=93 with 3 Operates
38+75=91 to 36-05=31 with 3 Operates
38+75=91 to 36-35=01 with 3 Operates
38+75=91 to 36+05=41 with 3 Operates
38+75=91 to 39+18=57 with 3 Operates
计算结束
14+19=39 to 14+18=32 with 2 Operates
14+19=39 to 14+16=30 with 2 Operates
14+19=39 to 34+ 5=39 with 3 Operates
14+19=39 to 44-15=29 with 3 Operates
14+19=39 to 44-19=25 with 3 Operates
14+19=39 to 71+19=90 with 3 Operates
14+19=39 to 74+ 9=83 with 3 Operates
14+19=39 to  4+35=39 with 3 Operates
14+19=39 to  4+79=83 with 3 Operates
14+19=39 to 18+19=37 with 3 Operates
14+19=39 to 19+18=37 with 3 Operates
14+19=39 to 19+13=32 with 3 Operates
14+19=39 to 13+19=32 with 3 Operates
14+19=39 to 15+15=30 with 3 Operates
14+19=39 to 11+79=90 with 3 Operates
14+19=39 to 14=49-35 with 3 Operates
计算结束
19+22=47 to 79-32=47 with 2 Operates
19+22=47 to 18+23=41 with 2 Operates
19+22=47 to 13+28=41 with 2 Operates
19+22=47 to 15+22=37 with 2 Operates
19+22=47 to 39-22=17 with 3 Operates
19+22=47 to 49+22=71 with 3 Operates
19+22=47 to 70-23=47 with 3 Operates
19+22=47 to 73-26=47 with 3 Operates
19+22=47 to  9+38=47 with 3 Operates
19+22=47 to 19+32=51 with 3 Operates
计算结束
33+44=32 to 28+44=72 with 3 Operates
33+44=32 to 23+49=72 with 3 Operates
33+44=32 to 38+14=52 with 3 Operates
33+44=32 to 33+19=52 with 3 Operates
计算结束

其中iGoogle一道题是错误的
55+76=46
55+76=46 to 30+16=46 with 3 Operates
55+76=46 to 36+10=46 with 3 Operates
iGoogle标准答案
55+76=46=>58+13=46

#7

恩，不错，其实LZ的表相当于把问题转化为图了，不过求解基本上还是靠搜索，没想到什么特好的方法！

#8

百度09年的初赛题.
不过百度这个题目也有很多局限的.
我枚举过的,侥幸拿了T-Shirt.

#9

上礼拜刚收到gcj的tshirt。感慨是，果然经济危机了。。。

#10

引用 9 楼 fancymouse 的回复:

上礼拜刚收到gcj的tshirt。感慨是，果然经济危机了。。。

我gcj的怎么没到...

#11

引用 9 楼 fancymouse 的回复:

上礼拜刚收到gcj的tshirt。感慨是，果然经济危机了。。。

上面不是11.10才发邮件说T-Shirt已寄出么?
你上个礼拜就收到了?内部搞的?

#12

收藏

#13

恩，lS两位有Tshirt都很棒，前途无量呀！
最后祝FM同志GCJ取得好成绩！（从另外一个帖子得知你这次成绩很好！）

#14

>上面不是11.10才发邮件说T-Shirt已寄出么? 
10月29号寄出来的。大概米国这里和国内不同吧。

>最后祝FM同志GCJ取得好成绩
偶gcj是爆了。r3爆0。现在只指望在wf里混个中等成绩了。

#15

引用 14 楼 fancymouse 的回复:

>上面不是11.10才发邮件说T-Shirt已寄出么?
10月29号寄出来的。大概米国这里和国内不同吧。

>最后祝FM同志GCJ取得好成绩
偶gcj是爆了。r3爆0。现在只指望在wf里混个中等成绩了。

FM在米国哪个学校?
非主流学校牛津?09WF的时候,一开始尽出其它队出不了的题,而且是一次通过...雷
GCJ...R3第一个可以做撒,第二个的小数据也可以水...

#16

>FM在米国哪个学校? 
这次regional把mit压掉了（嘘）

#17

雷,我把米搞成米字旗的米了...

#18

很争气呀（也包括飞雪同志）！趁着年轻，在算法方面走得再深一些吧！
不要听信那些什么中国学生只会搞奥赛没有创造力的言论，他们不懂未来这方面的人才需求有多大。
（不仅在中国，世界范围都是如此）
我们这一代的中国程序员，最终都将被你们轻松超越。

引用 16 楼 fancymouse 的回复:

>FM在米国哪个学校?
 这次regional把mit压掉了（嘘）

#19

穷举之

#20

• 火柴棍移动的一道面试题
• 用Java解决移动火柴的问题