« 「スクエア・カルテット問題」の高度じゃないコード | トップページ | 「バイバイマンを数えよう」の高度じゃないコード »

2016年2月22日 (月)

「プラス・マイナス・ゼロ問題」の高度じゃないコード

「高度じゃないコード」シリーズその4は「プラス・マイナス・ゼロ問題」です。

与えられた自然数 n(1 ≦ n ≦ 50)に対し、□1□2□3□4…□n = 0 の□に+か-のいずれかを入れて等式が成立する+と-の組み合わせは何通りあるかを求めよ。

数学の問題をプログラミングで解こう!「プラス・マイナス・ゼロ」問題解説

等式が成立した時、+と-を全て逆転しても等式は成立します。そして、左辺の計算の途中経過のマイナスの値をプラスにするには、そこまでの+と-を全て逆転すればいいので、最終的に0になる組み合わせの数を考える上での影響はありません。つまり、計算結果は絶対値で調べればいいということになります。

まず、n = 1 の時の左辺の計算結果は、+1 と -1 の2通りになりますが、絶対値として考えると、1 が2通りとなります。次に、その結果に 2 が加わった時は、1+2 で 3 と 1-2 の絶対値で 1 がそれぞれ2通りになります。そして、その結果に 3 が加わった時は、1+3 の 4、1-3 の絶対値の 2、3+3 の 6、3-3 の 0 がそれぞれ2通りになり、この n = 3 の時に初めて等式が2通りの組み合わせで成立することがわかります。さらに、その結果に 4 が加わった時は、0+4 の 4、0-4 の絶対値の 4、2+4 の 6、2-4 の絶対値の 2、4+4 の 8、4-4 の 0、6+4 の 10、6-4 の 2 がそれぞれ2通りになりますが、2 と 4 は2通りが2回被るので4通りとなります。また、n = 4 の時も等式が2通りの組み合わせで成立することがわかります。それ以降も同様に 1 つづつ数を増やしながら、出題された n の数まで繰り返します。

これを、Rubyでコーディングしたものを以下に示します。今回は、コードゴルフはせずに普通に組みましたが、例えば、1行目の s=[0]+[2] は s=[0,2] とできますし、試してみると s=0,2 と書いても問題ないようです。ここを、s=[1] として、1.upto としてもいいのですが、s=0,2 の時とした場合と文字数は変わりません。

さて、私は、最後の値を適用させる前の値をループさせましたが、解説のコードでは適用させた後の値をループさせています。なるほど、そちらのやり方ならループ内の式も1つで済むし、同じ値を何度も更新することがないので優れていますね。

|

« 「スクエア・カルテット問題」の高度じゃないコード | トップページ | 「バイバイマンを数えよう」の高度じゃないコード »

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/99795/63249951

この記事へのトラックバック一覧です: 「プラス・マイナス・ゼロ問題」の高度じゃないコード:

« 「スクエア・カルテット問題」の高度じゃないコード | トップページ | 「バイバイマンを数えよう」の高度じゃないコード »