2
0

Fizz Buzz問題をやろう

おはこんばんにちわ。
最近アルゴリズムにハマっているプログラミング初学者です。

扱う問題は、
paiza Cランクの Fizz Buzz問題!

聞いたことはあったんだけど、やったこと無かったです!これはやるっきゃない🔥

この記事で使用する言語はC++です!

問題のイメージ

問題を見てみると、

$1$ から $N$ までの数について順に出力しますが、3の倍数で Fizz、5の倍数で Buzz
3の倍数でもあり5の倍数でもある場合は Fizz Buzz と出力したいのです。

イメージとしては下図のようになります。

Fizz_Buzz_line

世界のナベアツさんの、1から順に数を数えながら3と3の倍数の時だけアホになるネタを思い出しました。特に、数字が30を超えてから怒涛のラッシュが始まるところが好きです。

それは置いておいて、

ナベアツさんのネタと同じように、来るべき数字が来たら普通に言ってはいけません。
1、2、Fizz!!、4、Buzz!!!、と叫ばなければいけません。
(※出力にびっくりマークをつけてはいけません。)

また、Fizz Buzzと叫ぶときは3と5の公倍数(両方の倍数)であります。

ですので、うまく書かないと Fizz Buzzとだけ出力するべきタイミングで、
Fizz!、 Buzz! 、Fizz Buzz!!とトリプルで叫んでしまう可能性があります。

というのは、例えば $15$ という数字を判定しようとしているとき、

(手順)各々の値で上から順番に実行する
    1. 3の倍数なら "Fizz" を出力
    2. 5の倍数なら "Buzz" を出力
    3. 3の倍数でもあり5の倍数でもあるなら "Fizz Buzz" を出力

というロジックでプログラムを書いてしまうと、出力が

13、14、FizzBuzzFizz Buzz!!!、16、...

pose_ohno_man.png

...となってしまいます。

思いついた解法たち

思いついた解法を説明していきます!

Fizz Buzz 先打ち即逃げ打法

各値に対して、問答A、B、C を上から順番に行います。

  • 問答A: 値が「3の倍数」かつ「5の倍数」?
    • ⭕️ : Fizz Buzz
    • ❌ : 問答Bへ
  • 問答B: 値が3の倍数?
    • ⭕️ : Fizz
    • ❌ : 問答Cへ
  • 問答C: 値が5の倍数?
    • ⭕️ : Buzz
    • ❌ : その値をそのまま出力

とりあえず、3の倍数かつ5の倍数である数を先に潰してしまおうという作戦です。
野球で例えると(?)

  1. 判定すべき値(ボール)がこちらに向かって飛んできます!!

  2. 最初に、飛んできた値が「3の倍数かつ5の倍数であるか?」を判定!

  3. 2.で YES なら Fizz Buzz!!と打ち返します!

  4. 3.で Fizz Buzz だったすぐさま次の値にうつる(走って逃げろ!)

という戦法です。

baseball_homerun_woman.png

もちろん、あら Fizz Buzzくんではないのね、とわかり次第、

今度は、Fizz あるいは Buzzであるかどうかをチェックしにいきます。

FizzBuzzかよりも
Fizz BuzzFizz Buzz でないのか、
それを最初に考えて...

FizzBuzz かはその後考えよう!という作戦。

ある値の判定で、一度 Fizz Buzzくんが出た暁には、もうFizzくんかBuzzさんは出したらダメってことですからね〜。もう Fizz Buzz が出できたら、とっととトンズラして次の数(今調べた数に+1した数)にいきましょう。

ということです。

...そう、たとえ5の倍数でも、たとえ3の倍数であったとしても、
もしFizz Buzzだったら、Fizz とも Buzzとも言ってはならないのです...いいね?(こわーい)

この、先打ち即逃げ打法の、実装を考えてみます。
1つの数だけを判定すれば良いのではなく、$N$個の数を判定する必要があるので、
1重のループを使って、$1$ から $N$ まで順番に値を判定してあげればいいですよん。

countinue を使って実装

for 文を制御する命令の一つである continueを使います。
(※後に少し触れますがelse ifでもいけます。)

ループを回している時に、continueをすると、以降の処理をとばして、次のループに行けます。

#include <iostream>
using namespace std;
int main(){
    //・3の倍数かつ5の倍数のときには、"Fizz Buzz"
    //・3の倍数のときには、"Fizz"
    //・5の倍数のときには、"Buzz"
    
    int N;
    // 入力
    cin >> N;
    
    for(int i = 1; i <= N; i++){
        if(i%3 == 0 && i%5 == 0){
            cout << "Fizz Buzz" << endl;
            continue;
        }
        if(i%3 == 0){
            cout << "Fizz" << endl;
            continue;
        }
        if(i%5 == 0){
            cout << "Buzz" << endl;
            continue;
        }
        cout << i << endl;
    }
}

下は上のプログラムの出力結果です。標準入力として入力は$N=20$で統一します。

出力結果(N=20)
~ % 
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
Fizz Buzz
16
17
Fizz
19
Buzz

きちんと、3の倍数では Fizz、5の倍数では Buzz、3の倍数かつ5の倍数では Fizz Buzz と出力されていることがわかります。


ここで、もし、プログラムから continue; を消したら、
出力結果はどうなるのでしょうか?

場合分けできている...?
#include <iostream>
using namespace std;
int main(){
    //・3の倍数かつ5の倍数のときには、"Fizz Buzz"
    //・3の倍数のときには、"Fizz"
    //・5の倍数のときには、"Buzz"
    
    // 入力
    int N;
    cin >> N;
    
    for(int i = 1; i <= N; i++){
        if(i%3 == 0 && i%5 == 0){
            cout << "Fizz Buzz" << endl;
        }
        if(i%3 == 0){
            cout << "Fizz" << endl;
        }
        if(i%5 == 0){
            cout << "Buzz" << endl;
        }
        cout << i << endl;
    }
}

もし、Fizz Buzz と出力できたとしても、for ブロックのループを抜けないので、
次の処理も行われてしまいます。

  • 「 3の倍数なら Fizz
  • 「 5の倍数なら Buzz

また、for ブロック内の末尾に値を出力する行

cout << i << endl;

がありますが、
これは、各ループで毎回実行されてしまいます。

そのため、例えば判定しようとしている値が、「3の倍数でも5の倍数でもある」場合

  • Fizz Buzz
  • Fizz
  • Buzz
  • その値 (i)

を標準出力に出力してしまいます。

実行結果(ダメな例)
~ % 
20
1
2
Fizz
3
4
Buzz
5
Fizz
6
7
8
Fizz
9
Buzz
10
11
Fizz
12
13
14
Fizz Buzz
Fizz
Buzz
15
16
17
Fizz
18
19
Buzz
20

上の出力結果を見ると、期待した出力結果が得られていないことがわかります。

例えば、

  • 値が $15$ のとき、
    • Fizz Buzz
    • Fizz
    • Buzz
    • 15
  • 値が $12$ のとき、
    • Fizz
    • 12

と出力していますが、これは誤りです。


continue でなくても else if でもいい!

また、else if を使えば、直前の if 文の条件文が false だった場合はこの処理をするよ!と階層構造で書くことができ、適切に処理できます。

#include <iostream>
using namespace std;
int main(){
    //・3の倍数かつ5の倍数のときには、"Fizz Buzz"
    //・3の倍数のときには、"Fizz"
    //・5の倍数のときには、"Buzz"
    
    int N;
    // 入力
    cin >> N;
    
    for(int i = 1; i <= N; i++){
        if(i%3 == 0 && i%5 == 0){
            cout << "Fizz Buzz" << endl;
        }
        else if(i%3 == 0){
            cout << "Fizz" << endl;
        }
        else if(i%5 == 0){
            cout << "Buzz" << endl;
        }
        else cout << i << endl;
    }
}
上のプログラムの実行結果
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
Fizz Buzz
16
17
Fizz
19
Buzz

集合を考える作戦

入力として受け取る値 $N$ 以下の自然数について、次のように集合を定めます。

$A$: 3の倍数
$B$: 5の倍数

$A$ と $B$ との共通部分 $A\cap B$ は「3の倍数かつ5の倍数」の集合となります。
つまり($N$ が十分大きいとき) $A$と $B$ とは互いに素でない(排反でない)集合になります。

これゆえに、調べたい値に対して

  • 3の倍数ですか?($A$ の要素ですか?)
  • 5の倍数ですか?($B$ の要素ですか?)
  • 3の倍数かつ5の倍数ですか?($A\cap B$ の要素ですか?)

と単純に聞いてみるだけでは、期待している出力を得られず、ごちゃごちゃになりやすいのです。

3の倍数?
// 3の倍数ですか? 
// それとも、3の倍数では無いですか?
if(i%3 == 0){...}
5の倍数?
// 5の倍数ですか? 
// それとも、5の倍数では無いですか?
if(i%5 == 0){...}
3の倍数かつ5の倍数?
// 3の倍数かつ5の倍数ですか? 
// それとも、3の倍数かつ5の倍数では無いですか?
if(i%3 == 0 && i%5 == 0){...}

あらかじめ、もれなくダブりなく、
MECE(Mutually Exclusive, Collectively Exhaustive)
を意識して場合わけすることで、

FizzBuzzFizz Buzz 判定の見通しが格段によくなります。

先ほどとは違い、今度は互いに排反な4つの集合に切り分けます。

集合を次のように定義します。

$A$: 3の倍数であるが5の倍数でない
$B$: 3の倍数かつ5の倍数
$C$: 5の倍数だが3の倍数でない
$D$: 3の倍数でも5の倍数でもない

ベン図で描くと下のようになります。

3_5_comBenn_.png

上図で(上から順番に、先ほどの集合$A, B, C, D$ に対応します。)

  • 緑色(3の倍数であるが5の倍数でない): Fizz
  • 水色(3の倍数かつ5の倍数): Fizz Buzz
  • 橙色(5の倍数であるが3の倍数でない): Buzz
  • 白色/ベン図の外 (3の倍数でも5の倍数でもない) : (その値を出力)
#include <iostream>
using namespace std;
int main(){
    int N;
    cin >> N;
    for(int i = 1; i <= N; i++){
        if(i%3 == 0 && i%5 != 0) cout << "Fizz" << endl; 
        if(i%3 == 0 && i%5 == 0) cout << "Fizz Buzz" << endl;
        if(i%3 != 0 && i%5 == 0) cout << "Buzz" << endl;
        if(i%3 != 0 && i%5 != 0) cout << i << endl;
    }
}

このように場合わけを考えることで、
ある値で Fizz が出力されて Buzz も出力されて Fizz Buzz とも出力されてしまう...
ということを防ぐことができます。

また、if 文の順序を入れ替えてもきちんと判定することができます。

15で割ったときのあまりを考えてパターン網羅作戦!

もう少しマシな作戦名はなかったのか。

入力した値 $N$ 以下の自然数のマスが描かれたすごろくを考えましょう。
一直線に進むだけのちょ〜つまらないすごろくですが、

何やら、3マスごとに Fizz という謎の文字が...
おっと、5マスにごとに Buzz ...?
そして、15マスごとに Fizz Buzzって書かれているぞ...?

Fizz_Buzz_line Fizz_Buzz_line Fizz_Buzz_line

Fizz Buzz Fizz Buzz たちは、何かの倍数のタイミングで出力されるメッセージです。ですから、出現するタイミングが等間隔に並ぶ性質を持ちます。

このつまらないすごろくマップ上のあるマス $k\ (1\leq k\leq N)$ が、FizzBuzzFizz Buzz か、あるいは左記のパターンのいずれでもないか、を知るには、
15 周期で見たときどこの位置にいるのか?が分かればいいです。

それを調べるには、$15$ で割ったあまり($\mathrm{mod}\ 15$)を調べればいいですね。

$15$ 周期で、すごろくをテープのようにぐるぐると巻き付けるようにして表してみると、下図のようになります。

fizzbuzzcirc2.png

少しわかりにくくなるかもしれませんが、あえて愚直に調べてみます。
15枚ずつの束を作っていくイメージです。

  • $1$ から $15$ までの自然数で
    • Fizz が現れるタイミング: $ 3, 6, 9, 12$
    • Buzz が現れるタイミング: $ 5, 10$
    • Fizz Buzz が現れるタイミング: $ 15$
  • $16$ から $30$ までの自然数で
    • Fizz が現れるタイミング: $ 15\times 1+3, 15\times 1+6, 15\times 1+9, 15\times 1+12$
    • Buzz が現れるタイミング: $ 15\times1+5, 15\times1+10$
    • Fizz Buzz が現れるタイミング: $ 15\times1+15$
  • $31$ から $45$ までの自然数で
    • Fizz が現れるタイミング: $ 15\times 2+3, 15\times 2+6, 15\times 2+9, 15\times 2+12$
    • Buzz が現れるタイミング: $ 15\times2+5, 15\times2+10$
    • Fizz Buzz が現れるタイミング: $ 15\times2+15$

... ... ...

各々のタイミングについて、15で割ったあまりにだけに注目すると、

  • $1$ から $15$ までの自然数
  • $16$ から $30$ までの自然数
  • $31$ から $45$ までの自然数

いずれの場合も

  • Fizz が現れるタイミング: $ 3, 6, 9, 12\quad (\mathrm{mod}\ 15)$
  • Buzz が現れるタイミング: $ 5, 10\quad (\mathrm{mod}\ 15)$
  • Fizz Buzz が現れるタイミング: $0\quad (\mathrm{mod}\ 15)$

となっています。

「 $15$ で割ったときのあまり」について、「Fizz Buzz Fizz Buzzが現れるタイミングの集合」を検索し、どこの集合に入っているか?を調べることで、FizzBuzzFizz Buzz を分類できそうです。

それでは、実装方法を考えていきましょう。

まず、

  • Fizz が現れるタイミングの集合: f = {3, 6, 9, 12}
  • Buzz が現れるタイミングの集合: b = {5, 10}
  • Fizz Buzz が現れるタイミングの集合: fb = {0}

を先に用意しておきます。

次に、調べたい値について、「15で割ったときのあまり」が

  • 集合fの要素なら Fizz
  • 集合bの要素なら Bizz
  • 集合fbの要素なら Fizz Buzz

です。もし、上記のいずれでもない場合は今調べている値をそのまま出力すれば良いのでした。

vectorを使った実装
#include <iostream>
#include <vector>
using namespace std;
int main(){
    int N, k;
    cin >> N;
    vector<int> f = {3, 6, 9, 12};  //Fizz
    vector<int> b = {5, 10};  //Buzz
    vector<int> fb = {0};  //Fizz Buzz
    
    for(int i = 1; i <= N; i++){
        k = i % 15;
        if(count(f.begin(),f.end(),k)) cout << "Fizz" << endl;
        else if(count(b.begin(),b.end(),k)) cout << "Buzz" << endl;
        else if(count(fb.begin(),fb.end(),k)) cout << "Fizz Buzz" << endl;
        else cout << i << endl;
     }
}
setを使った実装
#include <iostream>
#include <set>
using namespace std;
int main(){
    int N, k;
    cin >> N;
    set<int> f{3, 6, 9, 12};
    set<int> b{5, 10};
    set<int> fb{0};
    
    for(int i = 1; i <= N; i++){
        k = i % 15;
        if(f.count(k)) cout << "Fizz" << endl;
        else if(b.count(k)) cout << "Buzz" << endl;
        else if(fb.count(k)) cout << "Fizz Buzz" << endl;
        else cout << i << endl;
     }
}

どうしても elseを使いたくなかったり、
並列な if(...){...} の条件分岐だけで書きたい場合、

  • FizzBuzzFizz Buzz が現れないタイミング: $1, 2, 4, 7, 8, 11, 13, 14\quad (\mathrm{mod}\ 15)$

を考えることで、

  • FizzBuzzFizz Buzz が現れないタイミングの集合:
    nfb = {1, 2, 4, 7, 8, 11, 13}

を先に用意しておけば一応書けます。入力ミスに注意します。(1敗)

差集合を計算できる関数を用いて nfb を求める方法もありそうですが、使うとコードがもっと長くなりそうという感じです。

setを使った実装2
#include <iostream>
#include <set>
using namespace std;
int main(){
    int N, k;
    cin >> N;
    set<int> f{3, 6, 9, 12};
    set<int> b{5, 10};
    set<int> fb{0};
    set<int> nfb{1, 2, 4, 7, 8, 11, 13, 14}; //3の倍数でも5の倍数でもない
    for(int i = 1; i <= N; i++){
        k = i % 15;
        if(f.count(k)) cout << "Fizz" << endl;
        if(b.count(k)) cout << "Buzz" << endl;
        if(fb.count(k)) cout << "Fizz Buzz" << endl;
        if(nfb.count(k)) cout << i << endl;
     }
}

この方法については、今回Fizz が「3の倍数」、Buzzが「5の倍数」と小さな数の倍数が与えられている問題設定であったからできる話であると考えます。「3」や「5」の部分の値がちょっとでも大きくなるとこの方法は大変そうです。なぜなら、事前に用意する集合(ベクトル)が大きくなり、数えもれやダブり等の入力ミスが起きやすいと考えられるからです。

おまけ

「お風呂にする?」
「ご飯にする?」
「それとも... お風呂 かつ・ご・は・ん?」

と聞かれるとき、

「お風呂かつご飯」で返事をするにはどうしたら良いでしょう?

「お風呂かつご飯」は「お風呂」でも「ご飯」でもあるから、
もし「お風呂にする?」と聞かれたら、「...はい!」 (Fizz !)と言ってしまう。
次に「ご飯にする?」と来てしまうと 「...もちろん!!」(Buzz!)と言ってしまう。

しかしこれではいけません。これらの質問は「答えないように」しなければいけません。

「お風呂にする?」
「...」(沈黙)
「ご飯にする?」
「...」(沈黙)
「お風呂かつご飯?」
「...YES!!!」(Fizz Buzz!)

と言うべきです。

...という「くだり」を考えましたが、かえって混乱を招きそうなのでやめました。

2
0
3

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
0