« 2016年1月 | トップページ | 2016年3月 »

2016年2月24日 (水)

「バイバイマンを数えよう」の高度じゃないコード

「高度じゃないコード」シリーズその5は「バイバイマンを数えよう」です。

バイバイマンは1日毎に体のサイズが倍増します。 そして、体の大きさが10を超えると、10の位の数のサイズと1の位の数のサイズの2匹に分裂します。 1日目にサイズ1のバイバイマンが1匹いる状態から開始し、1日目~100日目までのバイバイマンの数を出力してください。

バイバイマンのサイズは、1日毎に 1⇒2⇒4⇒8 と大きくなり、その翌日、1と6に分裂するので、ここで1匹増えます。そして、6の方がまた翌日に、1と2に分裂し、さらに1匹増えます。ということで、バイバイマンのサイズは、1・2・4・6・8 の5種類しか存在しません。そこで、それぞれのサイズのバイバイマンが何匹いるかを、a・b・c・d・e とすると、Rubyでは、a,b,c,d,e=d+e,a+d,b,e,c で翌日の匹数が計算できます。また、1匹増えるのは、分裂してサイズ1のバイバイマンが生まれた時なので、a の値を集計していけば、全部で何匹いるかがわかります。

続きを読む "「バイバイマンを数えよう」の高度じゃないコード"

| | コメント (0) | トラックバック (0)

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 の数まで繰り返します。

続きを読む "「プラス・マイナス・ゼロ問題」の高度じゃないコード"

| | コメント (0) | トラックバック (0)

« 2016年1月 | トップページ | 2016年3月 »