题目93：利用四位数字以及算术法则，找出目标数的最长序列

欧拉计划

Arithmetic expressions

By using each of the digits from the set, {1, 2, 3, 4}, exactly once, and making use of the four arithmetic operations (+, −, *, /) and brackets/parentheses, it is possible to form different positive integer targets.

For example,

8 = (4 * (1 + 3)) / 2
14 = 4 * (3 + 1 / 2)
19 = 4 * (2 + 3) − 1
36 = 3 * 4 * (2 + 1)

Note that concatenations of the digits, like 12 + 34, are not allowed.

Using the set, {1, 2, 3, 4}, it is possible to obtain thirty-one different target numbers of which 36 is the maximum, and each of the numbers 1 to 28 can be obtained before encountering the first non-expressible number.

Find the set of four distinct digits, a < b < c < d, for which the longest set of consecutive positive integers, 1 to n, can be obtained, giving your answer as a string: abcd.

题目：

通过使用集合 {1, 2, 3, 4} 中每个数字一次（用且只用一次），以及四种算术运算 (+, &#8722;, *, /) 和括号，我们可以得到不同的目标正整数。

例如：

8 = (4 * (1 + 3)) / 2
14 = 4 * (3 + 1 / 2)
19 = 4 * (2 + 3) &#8722; 1
36 = 3 * 4 * (2 + 1)

但是将相连接是不允许的，如 12 + 34。

使用集合 {1, 2, 3, 4} 可以得到 31 个目标数，其中最大的是 36。而且 1 到 28 中的每个数字都可以被表示，但是 29 不能被表示。

找出四个不同1位数的集合，a < b < c < d，能够形成最长的 1 到 n 的连续正整数集合。以 abcd 的形式给出你的答案。

jerryxjr1220

看到国外达人写得很牛逼的迭代器算法：
答案1258

1. import itertools
   
2. 
   
3. def number_tuple(m):
   
4.     for i in xrange(1, m-2):
   
5.         for j in xrange(i+1, m-1):
   
6.             for k in xrange(j+1, m):
   
7.                 for l in xrange(k+1, m+1):
   
8.                     yield (i,j,k,l)
   
9. 
   
10. def operations(t):
    
11.     if len(t) == 1:
    
12.         yield t[0]
    
13.         return
    
14. 
    
15.     for i, e in enumerate(t):
    
16.         for result in operations(t[:i] + t[i+1:]):
    
17.             yield e * result
    
18.             yield e + result
    
19.             yield e - result
    
20.             yield result - e
    
21.             if result != 0:
    
22.                 yield e / float(result)
    
23. 
    
24. def consecutive_digits(digits):
    
25.     for i in itertools.count(1):
    
26.         if i not in digits:
    
27.             return i - 1
    
28. 
    
29. max_digits = (0, None)
    
30. for t in number_tuple(9):
    
31.     results = set(int(n) for n in operations(t) if int(n) == n and n > 0)
    
32.     max_digits = max(max_digits, (consecutive_digits(results), t))
    
33. print ''.join(map(str, max_digits[1]))

复制代码

fc1735

1. from itertools import *
   
2. 
   
3. op = [lambda x, y: x + y, lambda x, y: x - y,
   
4.       lambda x, y: x * y, lambda x, y: x / y if y != 0 else 0]
   
5. 
   
6. def count(n):
   
7.   s = set()
   
8.   for d1, d2, d3, d4 in permutations(n):
   
9.     for o1, o2, o3 in product(op, repeat = 3):
   
10.       for r in [o3(o2(o1(d1, d2), d3), d4), o2(o1(d1, d2), o3(d3, d4))]:
    
11.         if r == int(r):
    
12.           s.add(int(r))
    
13.   return next(filter(lambda x: x not in s, range(1, 999999)))
    
14. 
    
15. ans = max(combinations(range(10), 4), key = count)
    
16. print(''.join(map(str, ans)))

复制代码

https://github.com/devinizz/project_euler/blob/master/page02/93.py

guosl

1. /*
   
2. 答案：1258
   
3.       可以表达从1到51之间的所有数
   
4. 耗时：0.0586518秒
   
5. */
   
6. #include <iostream>
   
7. #include <vector>
   
8. #include <algorithm>
   
9. using namespace std;
   
10. 
    
11. int gcd(int x, int y)//求最大公因数，用于分数的既约
    
12. {
    
13.   if (y == 0)
    
14.     return x;
    
15.   int z = x % y;
    
16.   while (z != 0)
    
17.   {
    
18.     x = y;
    
19.     y = z;
    
20.     z = x % y;
    
21.   }
    
22.   return y;
    
23. }
    
24. 
    
25. struct stF//分数
    
26. {
    
27.   int n, d;
    
28.   stF(void)
    
29.   {
    
30.     n = 0;
    
31.     d = 1;
    
32.   }
    
33.   stF(int x, int y = 1)
    
34.   {
    
35.     int z = gcd(x, y);
    
36.     n = x / z;
    
37.     d = y / z;
    
38.     if (d < 0)
    
39.     {
    
40.       n = -n;
    
41.       d = -d;
    
42.     }
    
43.   }
    
44.   stF(const stF &f)
    
45.   {
    
46.     n = f.n;
    
47.     d = f.d;
    
48.   }
    
49.   const stF& operator=(const stF &f)
    
50.   {
    
51.     n = f.n;
    
52.     d = f.d;
    
53.     return *this;
    
54.   }
    
55.   bool operator<(const stF &f) const
    
56.   {
    
57.     return (n*f.d < d*f.n);
    
58.   }
    
59.   bool operator==(const stF &f) const
    
60.   {
    
61.     return (n*f.d == d * f.n);
    
62.   }
    
63.   stF operator+(const stF &f) const
    
64.   {
    
65.     int x = n * f.d + d * f.n;
    
66.     int y = d * f.d;
    
67.     stF g(x, y);
    
68.     return g;
    
69.   }
    
70.   stF operator-(const stF &f) const
    
71.   {
    
72.     int x = n * f.d - d * f.n;
    
73.     int y = d * f.d;
    
74.     stF g(x, y);
    
75.     return g;
    
76.   }
    
77.   stF operator*(const stF &f) const
    
78.   {
    
79.     int x = n * f.n;
    
80.     int y = d * f.d;
    
81.     stF g(x, y);
    
82.     return g;
    
83.   }
    
84.   stF operator/(const stF &f) const
    
85.   {
    
86.     int x = n * f.d;
    
87.     int y = d * f.n;
    
88.     stF g(x, y);
    
89.     return g;
    
90.   }
    
91. };
    
92. 
    
93. int main(void)
    
94. {
    
95.   int nMax = 0;
    
96.   char str[8];
    
97.   str[4] = 0;
    
98.   for (int i0 = 1; i0 <= 6; ++i0)
    
99.   {
    
100.     for (int i1 = i0 + 1; i1 <= 7; ++i1)
     
101.     {
     
102.       for (int i2 = i1 + 1; i2 <= 8; ++i2)
     
103.       {
     
104.         for (int i3 = i2 + 1; i3 <= 9; ++i3)
     
105.         {
     
106.           int a[4];
     
107.           a[0] = i0;
     
108.           a[1] = i1;
     
109.           a[2] = i2;
     
110.           a[3] = i3;
     
111.           vector<int> vr;
     
112.           do
     
113.           {
     
114.             vector<stF> v1, v2, v3;
     
115.             stF f0(a[0]), f1(a[1]), f2(a[2]), f3(a[3]);
     
116.             //f0与f1以及f2与f3的各种计算
     
117.             v1.push_back(f0 + f1);
     
118.             v2.push_back(f2 + f3);
     
119.             v1.push_back(f0 * f1);
     
120.             v2.push_back(f2 * f3);
     
121.             v1.push_back(f0 - f1);
     
122.             v2.push_back(f2 - f3);
     
123.             v1.push_back(f1 - f0);
     
124.             v2.push_back(f3 - f2);
     
125.             v1.push_back(f0 / f1);
     
126.             v2.push_back(f2 / f3);
     
127.             v1.push_back(f1 / f0);
     
128.             v2.push_back(f3 / f2);
     
129.             //(xxx) xx (xxx)的各种计算
     
130.             for (auto itr1 = v1.begin(); itr1 != v1.end(); ++itr1)
     
131.             {
     
132.               for (auto itr2 = v2.begin(); itr2 != v2.end(); ++itr2)
     
133.               {
     
134.                 stF g1 = *itr1, g2 = *itr2;
     
135.                 v3.push_back(g1 + g2);
     
136.                 v3.push_back(g1 * g2);
     
137.                 v3.push_back(g1 - g2);
     
138.                 v3.push_back(g1 / g2);
     
139.                 v3.push_back(g2 - g1);
     
140.                 v3.push_back(g2 / g1);
     
141.               }
     
142.             }
     
143.             //将结果放入vr
     
144.             for (auto itr = v3.begin(); itr != v3.end(); ++itr)
     
145.             {
     
146.               if (itr->n >= 1 && itr->d == 1)
     
147.                 vr.push_back(itr->n);
     
148.             }
     
149.             //(((xxx?xxx)?xxx)?xxx)的各种计算
     
150.             v2.clear();
     
151.             for (auto itr = v1.begin(); itr != v1.end(); ++itr)
     
152.             {
     
153.               stF g1 = *itr, g2 = stF(a[2]);
     
154.               v2.push_back(g1 + g2);
     
155.               v2.push_back(g1 * g2);
     
156.               v2.push_back(g1 - g2);
     
157.               v2.push_back(g1 / g2);
     
158.               v2.push_back(g2 - g1);
     
159.               v2.push_back(g2 / g1);
     
160.             }
     
161.             v3.clear();
     
162.             for (auto itr = v2.begin(); itr != v2.end(); ++itr)
     
163.             {
     
164.               stF g1 = *itr, g2 = stF(a[3]);
     
165.               v3.push_back(g1 + g2);
     
166.               v3.push_back(g1 * g2);
     
167.               v3.push_back(g1 - g2);
     
168.               v3.push_back(g1 / g2);
     
169.               v3.push_back(g2 - g1);
     
170.               v3.push_back(g2 / g1);
     
171.             }
     
172.             //将结果放入vr
     
173.             for (auto itr = v3.begin(); itr != v3.end(); ++itr)
     
174.             {
     
175.               if (itr->n >= 1 && itr->d == 1)
     
176.                 vr.push_back(itr->n);
     
177.             }
     
178.           } while (next_permutation(a, a + 4));//取四个数的下一个排列
     
179.           //对结果排序去重
     
180.           sort(vr.begin(), vr.end());
     
181.           auto itr_end = unique(vr.begin(), vr.end());
     
182.           //找出连续数
     
183.           int k = 1;
     
184.           for (auto itr = vr.begin(); itr != itr_end; ++itr, ++k)
     
185.           {
     
186.             if (*itr != k)
     
187.               break;
     
188.           }
     
189.           //记录当前结果
     
190.           if (k - 1 > nMax)
     
191.           {
     
192.             nMax = k - 1;
     
193.             str[0] = '0' + i0;
     
194.             str[1] = '0' + i1;
     
195.             str[2] = '0' + i2;
     
196.             str[3] = '0' + i3;
     
197.           }
     
198.         }
     
199.       }
     
200.     }
     
201.   }
     
202.   cout << str << endl << nMax << endl;
     
203.   return 0;
     
204. }

复制代码

hveagle

修改如下：
通过使用集合 {1, 2, 3, 4} 中每个数字一次（用且只用一次），以及四种算术运算 (+, -, *, /) 和括号，我们可以得到不同的目标正整数。

例如：

8 = (4 * (1 + 3)) / 2
14 = 4 * (3 + 1 / 2)
19 = 4 * (2 + 3) - 1
36 = 3 * 4 * (2 + 1)