有 A B C D E F G H I J K ... 等N个数

A.com

并不是所有的序列都有解啊，譬如：1，1，1，1，1还不如出一个算24点的题呢

hbmhalley

回复 10# koolcoy


    除以3 -> 除以9

    还有，lz明明说的是 “A B C ...” 所以不超过26个数啥也不用管啊

qishking

hbmhalley 发表于 2012-04-28 12:33
回复 10# koolcoy

你这斯尽投机取巧

lu18887

xiangsiyu21945 发表于 2012-04-27 10:19
关键还包括了  AB + CD = E + F 这种类型，  1 ，2,3,4,4,6，  （  12 + 34 = 46）   ，现在 头都大了

这么复杂。。。

starwing83

这个题本身不满足最优化原则，我也没找到能满足最优化原则的预处理，估计是不能dp了，老实搜索吧……下面是Lua版本的：

1. local function dfs(t, lim)
   
2.     local len = #t
   
3.     local function search_(i, lim, a, b)
   
4.         if i == lim then return coroutine.yield(a+b) end
   
5.         search_(i+1, lim, a+b, t[i+1])
   
6.         search_(i+1, lim, a, b*10+t[i+1])
   
7.     end
   
8.     local function iter(i, lim, a, b)
   
9.         return coroutine.wrap(function() return search_(i, lim, a, b) end)
   
10.     end
    
11.     local results = {}
    
12.     for lv in iter(1, lim, 0, t[1]) do
    
13.         results[lv] = true
    
14.     end
    
15.     for rv in iter(lim+1, len, 0, t[lim+1]) do
    
16.         if results[rv] then
    
17.             return rv
    
18.         end
    
19.     end
    
20. end
    
21. 
    
22. local function print_result(t, lim, result)
    
23.     local function search_(i, lim, a, b, way)
    
24.         if i == lim then
    
25.             if a+b == result then coroutine.yield(way..b) end
    
26.             return
    
27.         end
    
28.         search_(i+1, lim, a+b, t[i+1], way..b.." + ")
    
29.         search_(i+1, lim, a, b*10+t[i+1], way)
    
30.     end
    
31.     local function iter(i, lim, a, b)
    
32.         return coroutine.wrap(function() return search_(i, lim, a, b, "") end)
    
33.     end
    
34.     for wl in iter(1, lim, 0, t[1]) do
    
35.         for wr in iter(lim+1, #t, 0, t[lim+1]) do
    
36.             print(wl.." = "..wr)
    
37.         end
    
38.     end
    
39. end
    
40. 
    
41. local function sum(t, a, b)
    
42.     local s = 0
    
43.     for i = a, b do
    
44.         s = s + t[i]
    
45.     end
    
46.     return s
    
47. end
    
48. 
    
49. local function solve(t)
    
50.     local len = #t
    
51.     for i = 1, len-1 do
    
52.         if sum(t, 1, i)%3 == sum(t, i+1, len)%3 then
    
53.             local res = dfs(t, i)
    
54.             if res then
    
55.                 print_result(t, i, res)
    
56.             end
    
57.         end
    
58.     end
    
59. end
    
60. 
    
61. solve {1, 1, 1, 2, 2, 3, 6, 7}
    

复制代码

输出：

lua  -- "noname\2012-05-03-1.lua"
1 + 1 + 12 + 2 = 3 + 6 + 7
1 + 11 + 2 + 2 = 3 + 6 + 7
11 + 1 + 2 + 2 = 3 + 6 + 7
Hit any key to close this window...

这个是找所有解的，只求一个解的看着加break吧……

mpstat

回复 15# starwing83


    这个是lua代码?

koolcoy

回复 15# starwing83

不懂lua，没看那个代码。

1. 除以9取余的那个剪枝还是值得做的。
2. N稍微大一点，穷搜就不行： 把等号的位置放下后，剩下的每两个数字之间的加号可有可无，总共2^(N-2)总可能性，指数级的复杂度，穷搜显然不现实。
   

控球之魂

没看出有啥很明显的polynomial time的算法 ， 干脆把所有情况都做一下， 指数级别复杂度。  
几年没写过程序了， 纯粹练习下基本语法，循环。

1. 
   
2. #include <iostream>
   
3. #include <vector>
   
4. #include <ctime>
   
5. #include <cstdlib>
   
6. using namespace std;
   
7. 
   
8. vector<int> generateSample(int size) {
   
9.     srand ( time(NULL) );
   
10.     vector<int> sample(size);
    
11.     for(int i=0; i < size; i++)
    
12.         sample[i] = rand() % 9 + 1;
    
13.     return sample;
    
14. }
    
15. 
    
16. void print(vector<int> vec) {
    
17.         for(int i=0; i < vec.size(); i++)
    
18.                 cout << vec[i] << " ";
    
19.         cout << endl;
    
20. }
    
21. 
    
22. void print(vector<vector<int> > vec) {
    
23.         for(int i = 0; i < vec.size(); i++)
    
24.                 print(vec[i]);
    
25. }
    
26. 
    
27. void generateAllCombination_aux(vector<int> sample, vector<vector<int> > & allcomb) {
    
28.         if (sample.size() == 1)
    
29.                 allcomb.push_back(sample);
    
30.         else {
    
31.                 vector<int> sub(sample.begin(), sample.end());
    
32.                 int tail = sub.back();
    
33.                 sub.pop_back();
    
34.                 generateAllCombination_aux(sub, allcomb);
    
35.                 int currSize = allcomb.size();
    
36.                 for(int i = 0; i < currSize; i++) {
    
37.                         allcomb.push_back(allcomb[i]);
    
38.                         int tmp = allcomb[currSize + i].back();
    
39.                         allcomb[currSize + i].pop_back();
    
40.                         allcomb[currSize + i].push_back(tmp*10 + tail);
    
41.                         allcomb[i].push_back(tail);
    
42.                 }
    
43.         }
    
44. }
    
45. 
    
46. vector<vector<int> > generateAllCombination(vector<int> sample) {
    
47.         vector<vector<int> > allcomb;
    
48.         generateAllCombination_aux(sample, allcomb);
    
49.         return allcomb;
    
50. }
    
51. 
    
52. int sum(vector<int> vec) {
    
53.         int total = 0;
    
54.         for(int i = 0; i < vec.size(); i++)
    
55.                 total += vec[i];       
    
56.         return total;
    
57. }
    
58. 
    
59. void printPlus(vector<int> vec) {
    
60.         for(int i = 0; i < vec.size() - 1; i ++)
    
61.                 cout << vec[i] << " + ";
    
62.         cout << vec.back();
    
63. }
    
64. 
    
65. void solve(vector<vector<int> > left, vector<vector<int> > right) {
    
66.         for(int i = 0; i < left.size(); i++)
    
67.                 for(int j=0; j < right.size(); j++)
    
68.                         if (sum(left[i]) == sum(right[j])) {
    
69.                                 printPlus(left[i]);
    
70.                                 cout << " = ";
    
71.                                 printPlus(right[j]);
    
72.                                 cout << endl;
    
73.                         }
    
74. }
    
75. 
    
76. void solve(vector<int> sample) {
    
77.         for (int pivot = 1; pivot < sample.size(); pivot++) {
    
78.                 vector<int> left(sample.begin(), sample.begin() + pivot);
    
79.                 vector<int> right(sample.begin() + pivot, sample.end());
    
80.                 vector<vector<int> > leftAllComb = generateAllCombination(left);
    
81.                 vector<vector<int> > rightAllComb = generateAllCombination(right);
    
82.                 solve(leftAllComb, rightAllComb);
    
83.         }
    
84. }
    
85. 
    
86. int main() {
    
87.         vector<int> sample = generateSample(12);
    
88.         cout << "sample : ";
    
89.         print(sample);  
    
90.         cout << endl;
    
91.         solve(sample);  
    
92.        
    
93.         return 0;
    
94. }
    
95. 
    

复制代码

min@min-PC ~/temp
$ ./a.exe
sample : 4 5 3 3 1 6 7 4 4 4 9 8

4 + 5 + 3 + 3 + 1 + 6 + 7 = 4 + 4 + 4 + 9 + 8
45 + 3 + 3 + 1 + 6 + 7 = 44 + 4 + 9 + 8
45 + 3 + 3 + 1 + 6 + 7 = 4 + 44 + 9 + 8
45 + 3 + 3 + 1 + 6 + 7 = 4 + 4 + 49 + 8
4 + 53 + 31 + 6 + 7 = 44 + 49 + 8
4 + 5 + 33 + 16 + 7 = 44 + 4 + 9 + 8
4 + 5 + 33 + 16 + 7 = 4 + 44 + 9 + 8
4 + 5 + 33 + 16 + 7 = 4 + 4 + 49 + 8
45 + 33 + 16 + 7 = 44 + 49 + 8
4 + 5 + 33 + 1 + 67 = 4 + 4 + 4 + 98
45 + 33 + 1 + 67 = 44 + 4 + 98
45 + 33 + 1 + 67 = 4 + 44 + 98
4 + 5 + 3 + 31 + 67 = 4 + 4 + 4 + 98
45 + 3 + 31 + 67 = 44 + 4 + 98
45 + 3 + 31 + 67 = 4 + 44 + 98

min@min-PC ~/temp
$ ./a.exe
sample : 9 8 1 3 2 2 5 9 7 4 8 4