题目93：利用四位数字以及算术法则，找出目标数的最长序列
本帖最后由 欧拉计划 于 2016-8-11 23:19 编辑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} 中每个数字一次（用且只用一次），以及四种算术运算 (+, −, *, /) 和括号，我们可以得到不同的目标正整数。
例如：
8 = (4 * (1 + 3)) / 2
14 = 4 * (3 + 1 / 2)
19 = 4 * (2 + 3) − 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 的形式给出你的答案。
看到国外达人写得很牛逼的迭代器算法：
答案1258
import itertools
def number_tuple(m):
for i in xrange(1, m-2):
for j in xrange(i+1, m-1):
for k in xrange(j+1, m):
for l in xrange(k+1, m+1):
yield (i,j,k,l)
def operations(t):
if len(t) == 1:
yield t
return
for i, e in enumerate(t):
for result in operations(t[:i] + t):
yield e * result
yield e + result
yield e - result
yield result - e
if result != 0:
yield e / float(result)
def consecutive_digits(digits):
for i in itertools.count(1):
if i not in digits:
return i - 1
max_digits = (0, None)
for t in number_tuple(9):
results = set(int(n) for n in operations(t) if int(n) == n and n > 0)
max_digits = max(max_digits, (consecutive_digits(results), t))
print ''.join(map(str, max_digits)) from itertools import *
op = [lambda x, y: x + y, lambda x, y: x - y,
lambda x, y: x * y, lambda x, y: x / y if y != 0 else 0]
def count(n):
s = set()
for d1, d2, d3, d4 in permutations(n):
for o1, o2, o3 in product(op, repeat = 3):
for r in :
if r == int(r):
s.add(int(r))
return next(filter(lambda x: x not in s, range(1, 999999)))
ans = max(combinations(range(10), 4), key = count)
print(''.join(map(str, ans)))
https://github.com/devinizz/project_euler/blob/master/page02/93.py 本帖最后由 guosl 于 2022-1-26 18:21 编辑
/*
答案：1258
可以表达从1到51之间的所有数
耗时：0.0586518秒
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int gcd(int x, int y)//求最大公因数，用于分数的既约
{
if (y == 0)
return x;
int z = x % y;
while (z != 0)
{
x = y;
y = z;
z = x % y;
}
return y;
}
struct stF//分数
{
int n, d;
stF(void)
{
n = 0;
d = 1;
}
stF(int x, int y = 1)
{
int z = gcd(x, y);
n = x / z;
d = y / z;
if (d < 0)
{
n = -n;
d = -d;
}
}
stF(const stF &f)
{
n = f.n;
d = f.d;
}
const stF& operator=(const stF &f)
{
n = f.n;
d = f.d;
return *this;
}
bool operator<(const stF &f) const
{
return (n*f.d < d*f.n);
}
bool operator==(const stF &f) const
{
return (n*f.d == d * f.n);
}
stF operator+(const stF &f) const
{
int x = n * f.d + d * f.n;
int y = d * f.d;
stF g(x, y);
return g;
}
stF operator-(const stF &f) const
{
int x = n * f.d - d * f.n;
int y = d * f.d;
stF g(x, y);
return g;
}
stF operator*(const stF &f) const
{
int x = n * f.n;
int y = d * f.d;
stF g(x, y);
return g;
}
stF operator/(const stF &f) const
{
int x = n * f.d;
int y = d * f.n;
stF g(x, y);
return g;
}
};
int main(void)
{
int nMax = 0;
char str;
str = 0;
for (int i0 = 1; i0 <= 6; ++i0)
{
for (int i1 = i0 + 1; i1 <= 7; ++i1)
{
for (int i2 = i1 + 1; i2 <= 8; ++i2)
{
for (int i3 = i2 + 1; i3 <= 9; ++i3)
{
int a;
a = i0;
a = i1;
a = i2;
a = i3;
vector<int> vr;
do
{
vector<stF> v1, v2, v3;
stF f0(a), f1(a), f2(a), f3(a);
//f0与f1以及f2与f3的各种计算
v1.push_back(f0 + f1);
v2.push_back(f2 + f3);
v1.push_back(f0 * f1);
v2.push_back(f2 * f3);
v1.push_back(f0 - f1);
v2.push_back(f2 - f3);
v1.push_back(f1 - f0);
v2.push_back(f3 - f2);
v1.push_back(f0 / f1);
v2.push_back(f2 / f3);
v1.push_back(f1 / f0);
v2.push_back(f3 / f2);
//(xxx) xx (xxx)的各种计算
for (auto itr1 = v1.begin(); itr1 != v1.end(); ++itr1)
{
for (auto itr2 = v2.begin(); itr2 != v2.end(); ++itr2)
{
stF g1 = *itr1, g2 = *itr2;
v3.push_back(g1 + g2);
v3.push_back(g1 * g2);
v3.push_back(g1 - g2);
v3.push_back(g1 / g2);
v3.push_back(g2 - g1);
v3.push_back(g2 / g1);
}
}
//将结果放入vr
for (auto itr = v3.begin(); itr != v3.end(); ++itr)
{
if (itr->n >= 1 && itr->d == 1)
vr.push_back(itr->n);
}
//(((xxx?xxx)?xxx)?xxx)的各种计算
v2.clear();
for (auto itr = v1.begin(); itr != v1.end(); ++itr)
{
stF g1 = *itr, g2 = stF(a);
v2.push_back(g1 + g2);
v2.push_back(g1 * g2);
v2.push_back(g1 - g2);
v2.push_back(g1 / g2);
v2.push_back(g2 - g1);
v2.push_back(g2 / g1);
}
v3.clear();
for (auto itr = v2.begin(); itr != v2.end(); ++itr)
{
stF g1 = *itr, g2 = stF(a);
v3.push_back(g1 + g2);
v3.push_back(g1 * g2);
v3.push_back(g1 - g2);
v3.push_back(g1 / g2);
v3.push_back(g2 - g1);
v3.push_back(g2 / g1);
}
//将结果放入vr
for (auto itr = v3.begin(); itr != v3.end(); ++itr)
{
if (itr->n >= 1 && itr->d == 1)
vr.push_back(itr->n);
}
} while (next_permutation(a, a + 4));//取四个数的下一个排列
//对结果排序去重
sort(vr.begin(), vr.end());
auto itr_end = unique(vr.begin(), vr.end());
//找出连续数
int k = 1;
for (auto itr = vr.begin(); itr != itr_end; ++itr, ++k)
{
if (*itr != k)
break;
}
//记录当前结果
if (k - 1 > nMax)
{
nMax = k - 1;
str = '0' + i0;
str = '0' + i1;
str = '0' + i2;
str = '0' + i3;
}
}
}
}
}
cout << str << endl << nMax << endl;
return 0;
} 修改如下：
通过使用集合 {1, 2, 3, 4} 中每个数字一次（用且只用一次），以及四种算术运算 (+, -, *, /) 和括号，我们可以得到不同的目标正整数。
例如：
8 = (4 * (1 + 3)) / 2
14 = 4 * (3 + 1 / 2)
19 = 4 * (2 + 3) - 1
36 = 3 * 4 * (2 + 1)
页:
[1]