小町算
Posted feedbacks - Java
Javaでは、evalがないので自前でParseを行って計算してみました。
括弧対応なしで、約1秒で 101通りの結果がでました。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 | import java.util.ArrayList;
import java.util.List;
public class Sample104 {
public static void komachi(int[] lhs, int rhs) {
if (lhs.length == 0) return;
List<Term> expression = new ArrayList<Term>();
expression.add(new TermValue(lhs[0]));
for (int index = 1; index < lhs.length; index++) {
List<Term> work = new ArrayList<Term>(expression);
expression.clear();
for (Term term: work) {
List<Term> list = createTerm(term, lhs[index]);
expression.addAll(list);
};
}
int counter = 1;
for (Term term: expression) {
if (term.getValue() == rhs) {
System.out.println(counter++ + ": " + term.toString() + " = " + rhs);
}
}
}
private static List<Term> createTerm(Term lhs, int r) {
List<Term> result = new ArrayList<Term>();
Operator[] operators = Operator.values();
for (int index = 0; index < operators.length; index++) {
result.add(new TermData(operators[index], lhs, new TermValue(r)));
}
return result;
}
public enum Operator {
None {
public int getPriority() { return 10; }
public double operate(double lhs, double rhs) { return lhs * 10 + rhs; }
public String toString() { return ""; }
},
Plus {
public int getPriority() { return 1; }
public double operate(double lhs, double rhs) { return lhs + rhs; }
public String toString() { return "+"; }
},
Minus {
public int getPriority() { return 1; }
public double operate(double lhs, double rhs) { return lhs - rhs; }
public String toString() { return "-"; }
},
Times {
public int getPriority() { return 2; }
public double operate(double lhs, double rhs) { return lhs * rhs; }
public String toString() { return "*"; }
},
Divide {
public int getPriority() { return 2; }
public double operate(double lhs, double rhs) { return lhs / rhs; }
public String toString() { return "/"; }
};
public abstract int getPriority();
public abstract double operate(double lhs, double rhs);
}
private static interface Term {
public boolean isOperate();
public double getValue();
}
private static class TermValue implements Term {
public final int value;
public TermValue(int val) {
value = val;
}
public boolean isOperate() { return false; }
public double getValue() {
return value;
}
public String toString() { return String.valueOf(value); }
}
private static class TermData implements Term {
public final Operator op;
public final Term lhs;
public final Term rhs;
/**
* 右辺は追加分と考えて、演算子の順序に従ってデータを正規化します。
*/
public TermData(Operator o, Term l, Term r) {
Operator operator = o;
Term lterm = l;
Term rterm = r;
if (l.isOperate()) {
TermData data = (TermData) l;
if (operator.getPriority() > data.op.getPriority()) {
rterm = new TermData(operator, data.rhs, rterm);
lterm = data.lhs;
operator = data.op;
}
}
op = operator;
lhs = lterm;
rhs = rterm;
}
public boolean isOperate() { return true; }
public double getValue() {
return op.operate(lhs.getValue(), rhs.getValue());
}
public String toString() {
return lhs.toString() + op.toString() + rhs.toString();
}
}
public static void main(String[] args) {
long start = System.currentTimeMillis();
komachi(new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9}, 100);
System.out.println();
long end = System.currentTimeMillis();
System.out.println("elipse: " + (end - start) + "(ms)");
}
}
|
dpp
#4509()
Rating0/2=0.00
古典的なパズルである小町算を解くプログラムを作成してください。
小町算とは：
1□2□3□4□5□6□7□8□9＝100
四角の中に、空白、＋、－、×、÷のいずれかを一つ入れ、等式が成り立つようにするパズルです。
解答例：
1－2－3＋4×56÷7＋8×9＝100
1＋234×5÷6－7－89＝100
参考： http://ja.wikipedia.org/wiki/%E5%B0%8F%E7%94%BA%E7%AE%97
手元で20数行ほどのPythonスクリプトを書いてみたところ、101個の解答が得られました。
[ reply ]