黄昏より暗きもの、血の流れより赤きもの

黄昏より暗きもの、血の流れより赤きもの

自分の好きな事を好きなように書いて行きます。

FizzBuzz問題とその解説

FizzBuzz問題とは「1 から順に数を数えていく。但し、その数が 3 で割り切れるならば数字の代わりに Fizz と、5 で割り切れるなら Buzz と言うゲーム。3 でも 5 でも割り切れる場合は、FizzBuzz の順に言う。」ゲームの事だ。今日はこの問題をプログラムで解くための手順について書こうと思う。とその前にこの問題を解くには数学の整数の知識や集合の知識を必要とする。まずこの問題を解く上での練習問題を用意したので見て欲しい。尚集合が苦手だという方は「和集合と共通部分」というサイトを見て欲しい。


練習問題(ノーマルモード)


自然数の全体集合をUとする。つまりある自然数をnとして、U={1,2,3,4,........,n}とUを定義する。又m

練習問題(イージーモード)


1から100までの自然数の集合がある。このうち3の倍数の集合をA、5の倍数の集合をBとする。このとき3の倍数の個数と5の倍数の個数の合計を求めよ。いま実数xを超えない最大の整数を[x]とする。自然数1からnまでにおけるkの倍数の個数は[k/n]となることは使ってよい。

解答(ノーマルモード)


n(A)=[n/m],n(B)=[n/l]で以下のベン図より、n(AUB) = n(A) + n(B) - n(A∩B)。





このときA かつ Bは、Uの部分集合である自然数mlの集合Cとなる。つまり、C = A かつ Bとなり、n(A かつ B) = [n/ml]となる。このとき、n(A または B) = [n/m] + [n/l] - [n/ml](答)


解答(イージーモード)


3の倍数の集合をA、5の倍数の集合をBとする。このとき求める個数は、n(A または B)となる。ここで,n(A) = [100/3] = 33,n(B) = [100/5] = 20,m(A∩B) = [100/15] = 6。以上より上図を参考に、n(A または B) = n(A) + n(B) - n(A∩B) = 33 + 20 - 6 = 57(個)(答)


背景


問題の状況を整理


話をもどしてFizzBuzz問題とは「1 から順に数を数えていく。但し、その数が3で割り切れるならば数字の代わりに Fizz と、5 で割り切れるなら Buzz と言うゲーム。3 でも 5 でも割り切れる場合は、FizzBuzzの順に言う。」ゲームの事だった。
ここで、自然数n,p(p≦n)について、nがpで割り切れるので,kを自然数としてn=kpが成立する。これはnはpの倍数であることが分かる。つまり「nがpで割り切れる」<=>「nがpの倍数」ということ(同値)が成立する。このことを整理して問題文を書き直すと以下のようになる。




  1. 1 から順に自然数を数えていく。現在数えてる自然数をNとする

  2. Nが3の倍数ならば数字の代わりに「Fizz

  3. Nが5の倍数ならば「Buzz」

  4. Nが15の倍数ならば「FizzBuzz」と発音する



分岐を組む順番


ここで、この問題で数える自然数は1,2,3,......,Nであった。その内数字以外で答えなくてはならないのは、3,5,15の倍数であった。ここで以下のベン図を見ても分かるとおり、15の倍数の集合は、3の倍数の集合Aと5の倍数の集合Bの共通部分(集合)である。





つまり共通部分とそうでない部分に分けて考える必要がある。数学的に説明すると、A/B = A∩(not B)と定義したとき、1:A∩B,2:A/B,3:B/A,4:not(AUB)の4つの部分集合に分けて考える必要がある。その点を踏まえると分岐を作る手順は以下のようになる。



  1. Nが15の倍数ならば「FizzBuzz」と表示(下図左)

  2. Nが15の倍数でない3の倍数ならば、「Fizz」と表示(下図中)

  3. Nが15の倍数でない5の倍数ならば、「Buzz」と表示(下図右)

  4. Nが1〜3のどれでもない場合は数字を表示(各図の白い部分)





上記の1を数え終わると、15の倍数(A∩B)は除外される。このため残った数字から3の倍数(A/B)、5の倍数(B/A)を取り除いていけば上記2,3は満たせる。最後に1,2,3全てを取り除いた数(not(AUB))を数字で表示すればよい。この流れをフローチャートで表すと以下のようになる。





ソースコード(C言語)



実行結果(C言語)および検証(テスト)


N=99のときの実行結果は、ideOne(http://ideone.com/clgJw)を参照してほしい。


検証する条件の整理


今度はソースコードの検証に入る。まず何を検証するべきかテストの要件を整理していく。今回はフローチャート図の分岐を全て通って、きちんと動作するかどうかを確認していけばよい。ここでFizzと表示される周期は3,Buzzと表示される周期は5,FizzBuzzと表示される周期は15である。つまり15の周期で同じ数字や符号が登場する。以上の点を踏まえ1〜15までの表示(1周期分)について検証していく。


検証内容と結果


先ほど言った内容をまとめると、テストとして以下の条件を満たしているか調べればよい。



  • 3,6,9,12のときFizzと表示されているか?

  • 5,10のときBuzzと表示されているか?

  • 15のときFizzBuzzと表示されているか?

  • 1,2,4,7,8,11,13,14のとき数字が表示されているか?


下を見ると、問題なく表示されている事がわかる。