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

  • このエントリーをはてなブックマークに追加
  • Pocket

こんにちは。タクマ™ [@suwaru_blog] です。

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

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

今回は「植木算」と「和の法則・積の法則」を学び、
初歩的な「物の数え方」について学習しましょう。

数え上げの基礎

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

  • カードを 1 枚引いて「1」と宣言して、指でも数える
  • まだ数えていないカードから 1 枚引いて「2」と宣言して、指でも数える
  • まだ数えていないカードから 1 枚引いて「3」と宣言して、指でも数える

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

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

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

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

  • モレ
    • まだ数えていないものがあるのに、ぜんぶ数えたと判断する失敗
  • ダブリ
    • すでに数えたものを、また数えてしまう失敗

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

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

「モレ」と「ダブリ」がなければ、正しく数えることができるし、
「モレ」と「ダブリ」があれば、正しく数えることはできません。

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

植木算とは

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

答え

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

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

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

【問題1】最後の番号

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

答え

  • 1 番目のデータは 0 番目
  • 2 番目のデータは 1 番目
  • 3 番目のデータは 2 番目
  • 4 番目のデータは 3 番目
  • k 番目のデータは k – 1 番目
  • 100 番目のデータは 99 番目

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

植木算の本質

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

また、変数 n を使って数え方を一般化すると数える対象が多くなっても対応できます。
一般的なルールを元に整数の対応付けができれば、ある程度の数え間違いを防げます。

和の法則とは

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

  • ハートのトランプの字札が 10 枚 (集合A)
    • A, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
  • ハートのトランプの絵札が 3 枚 (集合B)
    • J, Q, K

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

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

A の要素数は |A| B の要素数は |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 とすると、

  • n が 2 の倍数なら、機械のランプが光る
  • n が 3 の倍数でも、機械のランプが光る
  • n が 2 の倍数でも 3 の倍数でもないとき、機械のランプが消える

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

答え

  • 1 以上 13 以下の 2 の倍数 (集合A)
    • 2, 4, 6, 8, 10, 12 (6枚)
  • 1 以上 13 以下の 3 の倍数 (集合B)
    • 3, 6, 9, 12 (4枚)
  • 2 の倍数、3 の倍数でダブっているもの: (集合ABの共通部分)
    • 6, 12 (2枚)

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

包含と排除の原理

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

集合 A と 集合 B の共通の要素数は |A ∩ B| と表せるため、
共通の要素数を引くことは |A ∪ B| = |A| + |B| - |A ∩ B| と書くことができます。

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

積の法則とは

トランプにはハート・スペード・ダイヤ・クラブ 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 (ランク) の要素の組み合わせはいくつか?
それを掛け算によって求めているのです。

集合 A の要素数と 集合 B の要素数の掛け算は |A * B| = |A| * |B| と表すことができます。

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

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

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

答え

  • 1 回目のサイコロ
    • 1, 2, 3, 4, 5, 6 の 6 通りの場合があります
  • 2 回目のサイコロ
    • 6 通りそれぞれに対して更に 6 通りあるので 6 * 6 (6^2) で 36 通りあります
  • 3 回目のサイコロ
    • 36 通りそれぞれに対して更に 6 通りあるので 6 * 6 * 6 (6^3) で答えは 216 通りになります

【問題4】32 個のランプ

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

答え

  • 1 個目のランプ
    • 2 通りの点灯パターンがあります
  • 2 個目のランプ
    • 2 通りそれぞれに対して 2 通りあるので 2 * 2 (2^2) で 4 通りあります
  • 3 個目のランプ
    • 4 通りそれぞれに対して 2 通りあるので 2 * 2 * 2 (2^3) で 8 通りあります
  • 32 個目のランプ
    • 2^32 で 4294967296 通りあります

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

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

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

つまり 2 進数 n ビットで表すことができる数字の総数は 2^n です。
これはプログラマなら知っておきましょう。

CS シリーズ

次回

前回

お仕事ください!

僕が代表を務める 株式会社 EeeeG では Web 制作・システム開発・マーケティング相談を行っています。
なにかお困りごとがあれば、Twitter DM や Web サイトからお気軽にご相談ください。

コメント

コメントを残す

*