Knuth's power tree: Difference between revisions
Added Java
(Added Kotlin) |
(Added Java) |
||
Line 344:
<lang J> 90j83 ": (x:1.1) usepath 81
2253.24023604401248793730853803334956796672985248117050381481057734540658419009864481100</lang>
=={{header|Java}}==
{{trans|Kotlin}}
<lang Java>import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class PowerTree {
private static Map<Integer, Integer> p = new HashMap<>();
private static List<List<Integer>> lvl = new ArrayList<>();
static {
p.put(1, 0);
ArrayList<Integer> temp = new ArrayList<>();
temp.add(1);
lvl.add(temp);
}
private static List<Integer> path(int n) {
if (n == 0) return new ArrayList<>();
while (!p.containsKey(n)) {
List<Integer> q = new ArrayList<>();
for (Integer x : lvl.get(0)) {
for (Integer y : path(x)) {
if (p.containsKey(x + y)) break;
p.put(x + y, x);
q.add(x + y);
}
}
lvl.get(0).clear();
lvl.get(0).addAll(q);
}
List<Integer> temp = path(p.get(n));
temp.add(n);
return temp;
}
private static BigDecimal treePow(double x, int n) {
Map<Integer, BigDecimal> r = new HashMap<>();
r.put(0, BigDecimal.ONE);
r.put(1, BigDecimal.valueOf(x));
int p = 0;
for (Integer i : path(n)) {
r.put(i, r.get(i - p).multiply(r.get(p)));
p = i;
}
return r.get(n);
}
private static void showPow(double x, int n, boolean isIntegral) {
System.out.printf("%d: %s\n", n, path(n));
String f = isIntegral ? "%.0f" : "%f";
System.out.printf(f, x);
System.out.printf(" ^ %d = ", n);
System.out.printf(f, treePow(x, n));
System.out.println("\n");
}
public static void main(String[] args) {
for (int n = 0; n <= 17; ++n) {
showPow(2.0, n, true);
}
showPow(1.1, 81, false);
showPow(3.0, 191, true);
}
}</lang>
{{out}}
<pre>0: []
2 ^ 0 = 1
1: [1]
2 ^ 1 = 2
2: [1, 2]
2 ^ 2 = 4
3: [1, 2, 3]
2 ^ 3 = 8
4: [1, 2, 4]
2 ^ 4 = 16
5: [1, 2, 4, 5]
2 ^ 5 = 32
6: [1, 2, 4, 6]
2 ^ 6 = 64
7: [1, 2, 4, 6, 7]
2 ^ 7 = 128
8: [1, 2, 4, 8]
2 ^ 8 = 256
9: [1, 2, 4, 8, 9]
2 ^ 9 = 512
10: [1, 2, 4, 8, 10]
2 ^ 10 = 1024
11: [1, 2, 4, 8, 10, 11]
2 ^ 11 = 2048
12: [1, 2, 4, 8, 12]
2 ^ 12 = 4096
13: [1, 2, 4, 8, 12, 13]
2 ^ 13 = 8192
14: [1, 2, 4, 8, 12, 14]
2 ^ 14 = 16384
15: [1, 2, 4, 8, 12, 14, 15]
2 ^ 15 = 32768
16: [1, 2, 4, 8, 16]
2 ^ 16 = 65536
17: [1, 2, 4, 8, 16, 17]
2 ^ 17 = 131072
81: [1, 2, 4, 8, 16, 32, 64, 80, 81]
1.100000 ^ 81 = 2253.240236
191: [1, 2, 4, 8, 16, 32, 64, 128, 160, 176, 184, 188, 190, 191]
3 ^ 191 = 13494588674281093803728157396523884917402502294030101914066705367021922008906273586058258347</pre>
=={{header|Kotlin}}==
| |||