最近10パズルを競って解く機会があって、その時にプログラムで答えを瞬時に出せないかと思い作り始めました。そもそも10パズルって何って人はググって、どうぞ。
C言語の入門書を読み終えたのでその復習として書きました。
やり方は色々あると思いますが今回は自分が用いた方法を説明していきます。
実際のコードはGithubに公開しましたのでそちらからどうぞ
(Macで作ったのでwinの方は各自でコンパイルしてください。)
前提条件
- ４つの数は1〜9の整数(0は含まない)
- 四則演算を使える(指数、対数、階乗などは使えない)
- 括弧はいくつ用いても良い
- 商で余りが出る場合は分数として考える
アルゴリズム
４つの整数を計算していく際に全てに共通していることが２つの数で行われることです。
1+3+5+7を考える時、まず1+3=4、その次に4+5=9のような感じです。
このことから、計算する順序は２つしかありません。
４つの整数をa,b,c,dとしたときに
- a+b+c+d
- (a+b)*(c+d)
1つ目は、先程の例のように計算したものに次の数をかけ合わせる方法です。
2つ目は、最初に計算したもの以外の２つの数を計算して、最後に２つをかけ合わせます。
プログラム
全体の大まかな流れとしては、
４つの整数を入力する→計算する→10になったものを抽出する→式を文字列で表示
使用している関数
- sort:配列に同じ値がある場合、ペアを左揃えにする
- calc:四則演算
- arith:符号を文字列に代入
- reverse:和差の後に積商を行う場合、括弧を文字列に代入する。可換でない演算を行った場合、文字列の整数の位置と符号を入れ替える。
- pair:同じ値の個数を数える。
- answer:表示する試行の取捨選択、文字列に整数を代入、文字列の表示。
計算は総当たりです。全部で何通りあるかというと、
-
1つ目の場合
最初の2つの選び方が6通り、次の数の選び方が2通りで12通り
四則演算は4種類ですが、交換法則より、a+b, a-b, b-a, ab, a/b, b/aの６種類を行います。
３回計算するので126^3=2592通り -
2つ目の場合
最初の２つでもう片方の２つも決まるので6/2の3通り
３回の計算なので3*6^3=748通り
これで全てを網羅したことになります。
実際のプログラムでは下図のような工程を経た分岐になります。
それぞれの計算結果をcalc1〜6とします。
例として、[a,b]は先程あげた6つの計算をし、[(a,b),c]はcalc1の結果とcで6つの計算をします。
なぜcalc2と3に別れるのかは後で書きます。
ここからは具体的に順序を追って説明していきます。
まず最初に、4つの整数を入力します。それを配列に代入します。
a[4] = {a, b, c, d}
calc1
次にcalc1を行うのですが、(a, b) (a, c) (a, d) (b, c) (b, d) (c, d)の組み合わせに6つの計算なので多次元配列になり
calc1[6][6]
イメージとしては
calc1までは共通ですがここから計算手順が分岐します。
calc4
calc4はcalc1同士を組み合わせるだけで最終段階に行くので1つ工程が少ない。
例えばcalc1の[a, b]はcalc1の[c, d]と計算すればいい。
calc4[3][6][6][6]
calc2,3,4,5
基本的にどの計算方法もやることは同じで、cとdのどちらを先に計算するかの違いだけです。
calc2はcalc1[6][6]とc、calc3はdと計算します。
calc2[6][6][6]
calc3[6][6][6]
calc4にd、calc5にcを計算します。
calc4[6][6][6][6]
calc5[6][6][6][6]
多少荒い説明でしたがこれで全通りの計算が終わりました。
データの取捨
次はその配列から10のものを抽出して式を表示します。
しかしこのままでは被りが出てしまいます。
例えば1234の場合、1+2+3+4と1+2+4+3の結果は同じですが、計算順序は違うので別のものとして配列に残っています。
そこで同じような計算をしているものは表示しないようにできたら良かったのですが、プログラムが思いつきませんでした。
仕方なくエクセルに半手動で結果を比較して、同じものをリストにしました。
それもGitに載せてあるので興味があったらどうぞ見てください。
比較する方法としては、整数と分数に分けます。
この場合上から2つ目と4つ目が式は違くても同じ結果になっているので除去対象になります。
入力された値に同じ数が入っている場合もあるので、1ペア、2ペア、3カード,4カードの分のリストも作りました。
ここからは結果が１０になった式を作り、表示する工程に入ります。
answerC
これがanswerCでの流れです。
この関数を呼び出す前にmainの方で条件をつけています。
以下の形なら呼び出されます。
この他にも形はありますが、つまり両端の演算が和差のどちらかで真ん中が積商の場合と、両端が積商のどちらかで真ん中が和差である場合です。
何故かと言うと、例えば(a×b)+(c-d)はa×b+c-dであり、これだとcalc4,5と計算瞬順序が違うだけで項は同じだからです。
実際に式を作る際は受け取った配列の要素番号を参照します。
1つ目の要素番号はcalc1で計算した整数の組み合わせで、2〜4つ目はどの四則演算を行ったかを表しています。
例)
calc4[2][4][3][2]=10
4つの整数{a, b, c, d}
[2]={a, d}{b, c}
[4] : a ÷ d
[3] : b × c
[2] : b × c - a ÷ d
answerCはある程度形が限られてくるのでこれで終わりです。
answerD
calc2,3で分岐したのは、このanswerD1,D2はやってることは大して変わらないのですが、コードが長く分かりづらくなってしまうからです。
このプログラムで最初にsortを使い配列を入れ替えた理由は、除外リストで用意したものは1ペアの場合{a,a,b,c}であり{a,b,a,c}ではないからです。
pairで同じ値の個数を数えて、帰ってきた値によって参照する除外リストを決めます。
文字列の符号と入れ替え、括弧はreverseで行っています。answerCでは関数を呼ぶことはなかったのですが、こっちは場合分けが多くD1とD2の2回なので関数を用いました。
answerD1の式生成方法
例)
calc5[4][5][3][1]=10
4つの整数{a, b, c, d}
[4]={b, d}
[5] : d ÷ b
[3] : d ÷ b × a
[1] : d ÷ b × a - c
answerD2だと上の場合aよりcを先に計算するので、d ÷ b × c - aになります。
とりあえずこれで全行程が終了したことになります。
mainも含めてみるとこんな感じです。
おわりに
同じ式の絞込とコードの重複があるので、頑張ればもう少し短くすることができますがこれで完成ということにしました。
本当はまだ括弧の位置や符号の変化、場合分けなど書いてないことが結構あるりますが長くなるのでここまでにします。