AOJ0041 Expression
問題リンク Expression
- 解法
基本は数字を4つ並べ替えて、計算順序と演算子を全通り試行する方針で解きました。
まず、各演算が再帰の形で表せます。
演算結果を表すクラスEを用意しています。メンバは演算結果の整数値xと、演算を表す文字列eです。例えば、3+5という演算結果はx=8, e="(3 + 5)"です。
数字4つを並び変えた結果は配列aに格納されているとして、再帰メソッドg()を呼びます。gには演算対象を表すlとrを渡します。トップレベルの呼び出しではl=0, r=3です。
g()は範囲[l,r]で計算することができる演算結果のリストList
l==rのときが再帰の基底で、数字1つを表すEを演算結果として返します(x=その数字, e="数字")。
かなり大がかりな解法となりましたが自分はこれで解きました。
- ソース
import java.util.ArrayList; import java.util.List; import java.util.Scanner; //Expression public class AOJ0041 { static int[] a; static int[] order; static boolean[] used; static String s; static class E{ public int x; public String e; public E(int x, String e) { this.x = x; this.e = e; } } static List<E> g(int[] a, int l, int r){ List<E> result = new ArrayList<E>(); if(r-l==0){ result.add(new E(a[l], ""+a[l])); return result; } if(r-l==1){ result.add(new E(a[l]+a[r], "("+a[l]+" + "+a[r]+")")); result.add(new E(a[l]-a[r], "("+a[l]+" - "+a[r]+")")); result.add(new E(a[l]*a[r], "("+a[l]+" * "+a[r]+")")); return result; } if(r-l==2){ List<E> t = g(a, l+1, r); for(E e:t){ result.add(new E(a[l]+e.x, "("+a[l]+" + "+e.e+")")); result.add(new E(a[l]-e.x, "("+a[l]+" - "+e.e+")")); result.add(new E(a[l]*e.x, "("+a[l]+" * "+e.e+")")); } t = g(a, l, r-1); for(E e:t){ result.add(new E(e.x+a[r], "("+e.e+" + "+a[r]+")")); result.add(new E(e.x-a[r], "("+e.e+" - "+a[r]+")")); result.add(new E(e.x*a[r], "("+e.e+" * "+a[r]+")")); } return result; } for(int i=l;i<r;i++){ List<E> t1 = g(a, l, i); List<E> t2 = g(a, i+1, r); for(E e1:t1){ for(E e2:t2){ result.add(new E(e1.x+e2.x, "("+e1.e+" + "+e2.e+")")); result.add(new E(e1.x-e2.x, "("+e1.e+" - "+e2.e+")")); result.add(new E(e1.x*e2.x, "("+e1.e+" * "+e2.e+")")); } } } return result; } static void f(int k){ if(!s.equals(""))return; if(k==4){ int[] t = new int[4]; for(int i=0;i<4;i++)t[i]=a[order[i]]; for(E e:g(t,0,3)){ if(e.x==10){ s = e.e; break; } } return; } for(int i=0;i<4;i++){ if(!used[i]){ used[i] = true; order[k] = i; f(k+1); used[i] = false; } } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true){ a = new int[4]; for(int i=0;i<4;i++)a[i]=sc.nextInt(); if((a[0]|a[1]|a[2]|a[3])==0)break; order = new int[4]; used = new boolean[4]; s = ""; f(0); System.out.println(s.equals("")?"0":s); } } }