题目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

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[0]
        return

    for i, e in enumerate(t):
        for result in operations(t[:i] + t[i+1:]):
            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[1]))

fc1735

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 [o3(o2(o1(d1, d2), d3), d4), o2(o1(d1, d2), o3(d3, d4))]:
        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

/*
答案：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[8];
  str[4] = 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[4];
          a[0] = i0;
          a[1] = i1;
          a[2] = i2;
          a[3] = i3;
          vector<int> vr;
          do
          {
            vector<stF> v1, v2, v3;
            stF f0(a[0]), f1(a[1]), f2(a[2]), f3(a[3]);
            //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[2]);
              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[3]);
              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] = '0' + i0;
            str[1] = '0' + i1;
            str[2] = '0' + i2;
            str[3] = '0' + i3;
          }
        }
      }
    }
  }
  cout << str << endl << nMax << endl;
  return 0;
}

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)