【和の法則】植木算問題解説！モレとダブリがない数え方【積の法則】

こんにちは。iQeda [@iQeeeda] です。

物を普通に数えると、人間はしばしば数え間違いを起こします。
しかし、数えたい物の性質・構造を理解して「数えるルール」を作れば間違いを防げます。

特にプログラミングでは、データを数えるルールを一般化しておかないとズレが生じます。

数え上げの基礎

あなたの目の前に並べられたカードがあって、それらを数えるとします。

この数え方だと、最後に宣言した数がカードの枚数になります。
これは「数えたいものに整数を対応づける」行為です。

「モレ」と「ダブリ」に注意する

こういう数え方ができるのはカードの枚数が少ないときです。
枚数が多くなると数え間違いが発生するからです。

数え間違いで注意すべきは「モレ」と「ダブリ」です。

この「モレ」と「ダブリ」の意味は正反対です。

数えたい物の性質・構造を理解する

「モレ」と「ダブリ」を防ぐには、数えたい物の性質・構造を理解することです。
これから物の性質・構造ごとに問題を出題していきます。

植木算とは

長さ 10 メートルの道に、端から 1 メートル間隔で木を植えるとします。
木は何本必要でしょうか。

答え

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 メートルの位置に木を植えるので、
答えは11 本です。「n メートル + 1」が木の本数になります。

0 をカウントするので +1 になるのですね。

単純に 10 / 1 と計算して出てくる答えは「木と木の間隔の個数」なので注意してください。

【問題1】最後の番号

プログラムのメモリ上に 100 個のデータがあります。
このデータを配列の 0 番目から格納していくと、最後のデータは配列の何番目になるでしょうか。

答え

答えは 99 番目です。
n 個あるものに対して 0 番から番号を振っていくと、最後の n 個目は n - 1 番になります。

植木算の本質

植木算では 0 の存在を見落とさないことが重要です。

和の法則とは

次は 2 つの集合に分かれているものを数えてみましょう。
以下、ハートのトランプは合計何枚あるでしょうか。

10 + 3 で、ハートの札は全部で 13 枚あることは簡単に分かります。

これは集合 A, B の要素数を足して、集合 A ∪ B の要素数を求める行為です。
つまり A ∪ B の要素数 = A の要素数 + B の要素数 です。

集合 A B 間の要素に「ダブリがない」場合だけ、この「和の法則」が成り立ちます。

【問題2】ライトを光らせるトランプ

A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K の 13 枚のトランプがあり、
「A を 1」「 J を 11」「Q を 12」「K を 13」 という整数で扱うことにします。

あなたの目の前には、トランプ 1 枚を入れることができる機械があります。
機械に入れるトランプの整数を n とすると、

このような法則でランプが光ったり、消えたりする場合、
A から順番にトランプを入れていくと、ライトが光るのは何枚のトランプでしょうか？

答え

答えは「 6 + 4 – 2 」で 8 枚となります。
ダブリがあったら引き算で帳尻を合わせる必要があるのです。

包含と排除の原理

2 の倍数 と 3 の倍数にはダブリ、つまり 6 の倍数という「共通の要素」があります。
集合で共通している要素を引くことを「包含と排除の原理」といいます。

「ダブっているものはいくつか？」を見抜くことが重要です。

積の法則とは

トランプにはハート・スペード・ダイヤ・クラブ 4 種類のスートがあり、
スートそれぞれに対して A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K の 13 種類のランクがあります。

以上を踏まえ、トランプ一組は全部で何枚あるでしょうか？ (ジョーカーなどは除く)

答え

文中で「それぞれに対して」という表現が出てくるとき、
掛け算だけで数を求めることができる場合は多いです。

4 種類のスートそれぞれに対して 13 種類のランクがあるので、
4 * 13 = 52 で 52 枚のカードが存在することがわかります。

また、これは 2 つの集合から「要素のペア」を作成する行為ともいえます。

// スート
集合A = {
    ハート, スペード, ダイヤ, クラブ
}

// ランク
集合 B = {
    A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K
}

// 組み合わせ
集合 A * B = {
    (ハート, A), (ハート, 2), (ハート, 3), ..., (ハート, K),
    (スペード, A), (スペード, 2), (スペード, 3), ..., (スペード, K),
    (ダイヤ, A), (ダイヤ, 2), (ダイヤ, 3), ..., (ダイヤ, K),
    (クラブ, A), (クラブ, 2), (クラブ, 3), ..., (クラブ, K),
}

集合 A (スート) の要素と 集合 B (ランク) の要素の組み合わせはいくつか？
それを掛け算によって求めているのです。

このように掛け算ですべての要素の組をつくることを「積の法則」といいます。

【問題3】3 個のサイコロ

1 から 6 まであるサイコロを 3 回投げて、3 桁の数字を作ります。
全部で何通りの数字が作れるでしょうか？

答え

【問題4】32 個のランプ

光るか、消えるか 2 通りの状態だけあるランプを 32 個並べます。
ランプの点灯・消灯パターンの組み合わせはいくつあるでしょうか。

答え

32 ビットで表現できる整数は何通り？

ちなみに 32 ビットで表現できる数値の総数も同じです。

各ビットは「 0 か 1 」の 2 通りの値だけとるので、
32 ビットで表せる数値は 2^32 で 4294967296 通りになります。

CS シリーズ

次回

前回