题目259：可达数

欧拉计划

Reachable Numbers

A 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。
  

所有可达正整数的和为多少？

天之南

1. import java.util.HashSet;
   
2. 
   
3. public class ProjectEuler_259{
   
4.         static final int LEN = 9;
   
5.         static Fraction[][][] arr = new Fraction[LEN + 1][LEN + 1][];
   
6.         static HashSet<Fraction> tmp = new HashSet<>();
   
7.         static {
   
8.                 for (int i = 0; i <= LEN; i++) {
   
9.                         arr[i][i] = new Fraction[] { new Fraction(i) };
   
10.                 }
    
11.         }
    
12. 
    
13.         public static void main(String[] args) {
    
14. 
    
15.                 for (int len = 2; len <= LEN; len++) {
    
16.                         for (int i = 1, j = i + len - 1; j <= LEN; i++, j++) {
    
17.                                 tmp.clear();
    
18.                                 for (int k = i; k < j; k++) {
    
19.                                         if (len < 9)
    
20.                                                 tmp.addAll(cartessian(arr[i][k], arr[k + 1][j]));
    
21.                                         else
    
22.                                                 tmp.addAll(cartessianFix(arr[i][k], arr[k + 1][j]));
    
23.                                 }
    
24.                                 tmp.add(new Fraction(joint(i, j)));
    
25.                                 arr[i][j] = new Fraction[tmp.size()];
    
26.                                 tmp.toArray(arr[i][j]);
    
27.                         }
    
28.                 }
    
29.                
    
30.                 long sum = 0;
    
31.                 for (Fraction x : arr[1][LEN]) {
    
32.                         sum += x.toLong();
    
33.                 }
    
34.                 System.out.println(sum);
    
35. 
    
36.         }
    
37. 
    
38.         static HashSet<Fraction> cartessian(Fraction[] a, Fraction[] b) {
    
39.                 HashSet<Fraction> tmp = new HashSet<>();
    
40.                 for (Fraction x : a) {
    
41.                         for (Fraction y : b) {
    
42.                                 tmp.add(x.add(y));
    
43.                                 tmp.add(x.mul(y));
    
44.                                 tmp.add(x.sub(y));
    
45.                                 if (y.n != 0)
    
46.                                         tmp.add(x.div(y));
    
47.                         }
    
48.                 }
    
49.                 return tmp;
    
50.         }
    
51. 
    
52.         static HashSet<Fraction> cartessianFix(Fraction[] a, Fraction[] b) {
    
53.                 HashSet<Fraction> tmp = new HashSet<>();
    
54.                 for (Fraction x : a) {
    
55.                         for (Fraction y : b) {
    
56.                                 addFix(tmp, x.add(y));
    
57.                                 addFix(tmp, x.mul(y));
    
58.                                 addFix(tmp, x.sub(y));
    
59.                                 if (y.n != 0)
    
60.                                         addFix(tmp, x.div(y));
    
61.                         }
    
62.                 }
    
63.                 return tmp;
    
64.         }
    
65. 
    
66.         static int joint(int i, int j) {
    
67.                 int res = 0;
    
68.                 for (int x = j, pow = 1; x >= i; x--, pow *= 10) {
    
69.                         res = res + pow * x;
    
70.                 }
    
71.                 return res;
    
72.         }
    
73. 
    
74.         static void addFix(HashSet<Fraction> set, Fraction f) {
    
75.                 if (f.n > 0 && f.d == 1) {
    
76.                         set.add(f);
    
77.                 }
    
78.         }
    
79. 
    
80. }
    
81. 
    
82. //分数类
    
83. class Fraction {
    
84.         public int n = 0;//分子numerator
    
85.         public int d = 1;//分母denominator
    
86. 
    
87.         public Fraction() {
    
88.                
    
89.         }
    
90. 
    
91.         public Fraction(int z) {
    
92.                 this.n = z;
    
93.                 this.d = 1;
    
94.         }
    
95. 
    
96.         // addition, subtraction, multiplication, division:加减乘除运算
    
97.         public Fraction add(Fraction x) {
    
98.                 Fraction res = new Fraction();
    
99.                 res.n = this.n * x.d + this.d * x.n;
    
100.                 res.d = this.d * x.d;
     
101.                 res.simple();
     
102.                 return res;
     
103.         }
     
104. 
     
105.         public Fraction sub(Fraction x) {
     
106.                 Fraction res = new Fraction();
     
107.                 res.n = this.n * x.d - this.d * x.n;
     
108.                 res.d = this.d * x.d;
     
109.                 res.simple();
     
110.                 return res;
     
111.         }
     
112. 
     
113.         public Fraction mul(Fraction x) {
     
114.                 Fraction res = new Fraction();
     
115.                 res.n = this.n * x.n;
     
116.                 res.d = this.d * x.d;
     
117.                 res.simple();
     
118.                 return res;
     
119.         }
     
120. 
     
121.         public Fraction div(Fraction x) {
     
122.                 Fraction res = new Fraction();
     
123.                 res.n = this.n * x.d;
     
124.                 res.d = this.d * x.n;
     
125.                 res.simple();
     
126.                 return res;
     
127.         }
     
128.        
     
129.         //化简
     
130.         public void simple() {
     
131.                 if (n % d == 0) {
     
132.                         n = n / d;
     
133.                         d = 1;
     
134.                         return;
     
135.                 }
     
136.                 int min = Math.min(n, d);
     
137.                 for (int i = 2; i*i <= min; i++) {
     
138.                         while (n % i == 0 && d % i == 0) {
     
139.                                 n /= i;
     
140.                                 d /= i;
     
141.                         }
     
142.                 }
     
143.                 if (d < 0) {
     
144.                         n = -n;
     
145.                         d = -d;
     
146.                 }
     
147.         }
     
148. 
     
149.         public long toLong() {
     
150.                 return n / d;
     
151.         }
     
152. 
     
153.         @Override
     
154.         public int hashCode() {
     
155.                 final int prime = 31;
     
156.                 int result = 1;
     
157.                 result = prime * result + d;
     
158.                 result = prime * result + n;
     
159.                 return result;
     
160.         }
     
161. 
     
162.         @Override
     
163.         public boolean equals(Object obj) {
     
164.                 if (this == obj)
     
165.                         return true;
     
166.                 if (obj == null)
     
167.                         return false;
     
168.                 if (getClass() != obj.getClass())
     
169.                         return false;
     
170.                 Fraction other = (Fraction) obj;
     
171.                 if (d != other.d)
     
172.                         return false;
     
173.                 if (n != other.n)
     
174.                         return false;
     
175.                 return true;
     
176.         }
     
177. 
     
178.         @Override
     
179.         public String toString() {
     
180.                 if (d == 1)
     
181.                         return "" + n;
     
182.                 return n + "/" + d;
     
183.         }
     
184. }

复制代码

答案:20101196798