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

読者です 読者をやめる 読者になる 読者になる

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

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

FizzBuzz問題とその解答(2):拡張FizzBuzz問題

前回、FizzBuzz問題について取り扱った。今回その拡張についてのプログラムを書いてみたので、紹介したい。


問題


a

練習問題


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

解答



kを自然数とする。

(i)b=kaのとき,BはAの部分集合となるので、AかつB = Bとなる。以上より、n(A または B) = n(A) + n(B) - n(B) = n(A) = [n/a](答)




(ii)b≠kaのとき、AかつBはlの倍数の集合となる。以上より、n(A または B) = n(A) + n(B) - n(AかつB) = [n/a] + [n/b]- [n/l](答)





自然数a,bの最小公倍数LCM(a,b)の計算法


ここからは自然数a,bの最小公倍数をLCM(a,b),最大公約数をGCD(a,b)と定義する。今回の問題で難しいのは、分岐を入れる前に自然数a,bの最小公倍数を求める必要がある。最小公倍数を求める手順として、


1:「ユークリッドの互除法」を用いてGCD(a,b)を求める。
2:公式GCD(a,b)*LCM(a,b)=ab*1を用いてLCM(a,b)を求める。


ここでユークリッドの互除法とは以下のような定理であった。
自然数aをbで割った余りをrとしたとき、
(i):r=0のとき,GCD(a,b) = b
(ii):r≠0のとき,GCD(a,b) = GCD(b,r)


例題


a>bを満たす整数a,bがある。このとき、以下の場合においてユークリッドの互除法を用いてGCD(a,b)を求めよ。
(1):a=42,b=18のとき
(2):a=96,b=46のとき


(1):GCD(42,18) = GCD(18,6) = GCD(6,0) = 6(答)
(2):GCD(96,46) = GCD(46,4) = GCD(4,2) = GCD(2,0) = 2(答)


ユークリッドの互除法ソースコード



ユークリッドの互除法の検証(単体テスト)


今回はbがaの倍数のときで、16行目に該当するとき、しないときに分けて検証していく。又万一(a,b)が反対に入力された時にきちんと表示されるかどうかを検証していく。GCD(9,3),GCD(42,18)の場合をそれぞれ検証。case1のとき最大公約数6が、case2のとき3が表示されていたので無事動作している。一方aとbを入れ替えた場合も問題なく計算されている。





b=kaの場合を除外していく


上記の練習問題では、b=kaであるかそうでないかに応じて場合分けを行った。ではb=kaのときどのようなが起こるか?前回のフローチャート通りに入力すると、LCM(a,b)=bとなるため、「FizzBuzz」と「Fizz」しか表示されないという問題が起こり、題意よりこの場合を除外しなくてはならない。このとき、与えられた,bの情報からkが整数であるかどうかを判定しなくてはならない。この場合bはaの倍数となるので、bをaで割った余りが0であるかで判定すればよい。


ソースコード



検証


今回はn=100、(a,b)=(2,5),(a,b)=(2,6)の場合をそれぞれ検証していく。(a,b)=(2,6)のときはエラーが表示され、(a,b)=(2,5)のときはLCM(2,5)=l=10となるので、1〜10まで検証すると以下のようになり、無事動作している。


(a,b)=(2,5)のとき



(a,b)=(2,6)のとき


*1:証明は「http://www.math.ucsd.edu/~cpopescu/Fall05/Math109/hwk7.pdf」のPloblem3.96参照