题目259：可达数
Reachable NumbersA positive integer will be called reachable if it can result from an arithmetic expression obeying the following rules:
[*]Uses the digits 1 through 9, in that order and exactly once each.
[*]Any successive digits can be concatenated (for example, using the digits 2, 3 and 4 we obtain the number 234).
[*]Only the four usual binary arithmetic operations (addition, subtraction, multiplication and division) are allowed.
[*]Each operation can be used any number of times, or not at all.
[*]Unary minus is not allowed.
[*]Any number of (possibly nested) parentheses may be used to define the order of operations.
[*]For example, 42 is reachable, since (1/23) * ((4*5)-6) * (78-9) = 42.
What is the sum of all positive reachable integers?
题目：
一个正整数如果由满足以下条件的算术表达式得到则称之为可达的。
[*]使用数字 1 到 9，按照顺序并且每个数字用且只用一次。
[*]任何连续的数字可以串联（例如，使用数字 2，3，4 我们将得到数字 234）。
[*]只允许有 4 种基本二元算术运算（加法，减法，乘法，除法）。
[*]任何一种运算可以使用任意次，或者不使用。
[*]不允许一元减法。（也就是负号）
[*]为了定义运算顺，可以使用任意个括号。
[*]例如，42 是可达的，因为 (1/23) * ((4*5)-6) * (78-9) = 42。
所有可达正整数的和为多少？
本帖最后由 天之南 于 2017-6-12 17:12 编辑
import java.util.HashSet;
public class ProjectEuler_259{
static final int LEN = 9;
static Fraction[][][] arr = new Fraction[];
static HashSet<Fraction> tmp = new HashSet<>();
static {
for (int i = 0; i <= LEN; i++) {
arr = new Fraction[] { new Fraction(i) };
}
}
public static void main(String[] args) {
for (int len = 2; len <= LEN; len++) {
for (int i = 1, j = i + len - 1; j <= LEN; i++, j++) {
tmp.clear();
for (int k = i; k < j; k++) {
if (len < 9)
tmp.addAll(cartessian(arr, arr));
else
tmp.addAll(cartessianFix(arr, arr));
}
tmp.add(new Fraction(joint(i, j)));
arr = new Fraction;
tmp.toArray(arr);
}
}
long sum = 0;
for (Fraction x : arr) {
sum += x.toLong();
}
System.out.println(sum);
}
static HashSet<Fraction> cartessian(Fraction[] a, Fraction[] b) {
HashSet<Fraction> tmp = new HashSet<>();
for (Fraction x : a) {
for (Fraction y : b) {
tmp.add(x.add(y));
tmp.add(x.mul(y));
tmp.add(x.sub(y));
if (y.n != 0)
tmp.add(x.div(y));
}
}
return tmp;
}
static HashSet<Fraction> cartessianFix(Fraction[] a, Fraction[] b) {
HashSet<Fraction> tmp = new HashSet<>();
for (Fraction x : a) {
for (Fraction y : b) {
addFix(tmp, x.add(y));
addFix(tmp, x.mul(y));
addFix(tmp, x.sub(y));
if (y.n != 0)
addFix(tmp, x.div(y));
}
}
return tmp;
}
static int joint(int i, int j) {
int res = 0;
for (int x = j, pow = 1; x >= i; x--, pow *= 10) {
res = res + pow * x;
}
return res;
}
static void addFix(HashSet<Fraction> set, Fraction f) {
if (f.n > 0 && f.d == 1) {
set.add(f);
}
}
}
//分数类
class Fraction {
public int n = 0;//分子numerator
public int d = 1;//分母denominator
public Fraction() {
}
public Fraction(int z) {
this.n = z;
this.d = 1;
}
// addition, subtraction, multiplication, division:加减乘除运算
public Fraction add(Fraction x) {
Fraction res = new Fraction();
res.n = this.n * x.d + this.d * x.n;
res.d = this.d * x.d;
res.simple();
return res;
}
public Fraction sub(Fraction x) {
Fraction res = new Fraction();
res.n = this.n * x.d - this.d * x.n;
res.d = this.d * x.d;
res.simple();
return res;
}
public Fraction mul(Fraction x) {
Fraction res = new Fraction();
res.n = this.n * x.n;
res.d = this.d * x.d;
res.simple();
return res;
}
public Fraction div(Fraction x) {
Fraction res = new Fraction();
res.n = this.n * x.d;
res.d = this.d * x.n;
res.simple();
return res;
}
//化简
public void simple() {
if (n % d == 0) {
n = n / d;
d = 1;
return;
}
int min = Math.min(n, d);
for (int i = 2; i*i <= min; i++) {
while (n % i == 0 && d % i == 0) {
n /= i;
d /= i;
}
}
if (d < 0) {
n = -n;
d = -d;
}
}
public long toLong() {
return n / d;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + d;
result = prime * result + n;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Fraction other = (Fraction) obj;
if (d != other.d)
return false;
if (n != other.n)
return false;
return true;
}
@Override
public String toString() {
if (d == 1)
return "" + n;
return n + "/" + d;
}
}
答案:20101196798
页:
[1]