CHAPTER2_08_問題09

符号化・・・一定のルールに基づき別の文字列に置き換えること。
複合化・・・ルールに基づき文字列に置き換えたものを元の文字列に戻すこと

たとえば、アのルールではaという文字は0に置き換えるといっているので
a→0　が複合化で、0→aに戻すのが複合化といえる。

符号化した結果、複合化する時に複数通りの解釈ができてしまう場合NGなので(複合可能であって　と書かれているので）
まず、複合可能かどうか検証してみる。


■アのケース
□１文字の場合を考える
a→0、 0はaにしか変換できないので複合可能。

b→１、1はbにしか変換できないので複合可能。

c→00、00はcとaaの二通りに解釈ができるため複合可能ではない。

よって、アのケースは複合可能でないためこの時点でNG


■イのケース
□１文字の場合を考える
a→0、 0はaにしか変換できないので複合可能。

b→0１、01はbにしか変換できないので複合可能。

c→10、10はcにしか変換できないので複合可能。

d→11、11はdにしか変換できないので複合可能。

□２文字の場合を考える
aa→00、00はaaにしか変換できないので複合可能。

ab→001、001はabにしか変換できないので複合可能。

ac→010、010はacとbaの二通りの解釈ができるため複合可能ではない。

よって、イのケースは複合可能でないためこの時点でNG


■ウのケース
□１文字の場合を考える
a→0、 0はaにしか変換できないので複合可能。

b→10、10はbにしか変換できないので複合可能。

c→110、110はcにしか変換できないので複合可能。

d→111、111はdにしか変換できないので複合可能。

□２文字の場合を考える
aa→00、00はaaにしか変換できないので複合可能。

ab→010、010はabにしか変換できないので複合可能。

ac→0110、0110はacにしか変換できないので複合可能。

ad→0111、0111はadにしか変換できないので複合可能。

---

ba→100、00はbaにしか変換できないので複合可能。

bb→1010、1010はbbにしか変換できないので複合可能。

bc→10110、10110はbcにしか変換できないので複合可能。

bd→10111、10111はbdにしか変換できないので複合可能。

---

ca→1100、1100はcaにしか変換できないので複合可能。

cb→11010、11010はcbにしか変換できないので複合可能。

cc→110110、110110はccにしか変換できないので複合可能。

cd→110111、110111はcdにしか変換できないので複合可能。

---

da→1110、1110はdaにしか変換できないので複合可能。

db→11110、11110はdbにしか変換できないので複合可能。

dc→111110、111110はdcにしか変換できないので複合可能。

dd→111111、111111はddにしか変換できないので複合可能。

ウは複合に関しては問題なさそう。



■エのケース
□１文字の場合を考える
a→00、 00はaにしか変換できないので複合可能。

b→01、01はbにしか変換できないので複合可能。

c→10、10はcにしか変換できないので複合可能。

d→11、11はdにしか変換できないので複合可能。

□２文字の場合を考える
aa→0000、0000はaaにしか変換できないので複合可能。

ab→0001、0001はabにしか変換できないので複合可能。

ac→0010、0010はacにしか変換できないので複合可能。

ad→0011、0011はadにしか変換できないので複合可能。

---

ba→0100、0100はbaにしか変換できないので複合可能。

bb→0101、0101はbbにしか変換できないので複合可能。

bc→0110、0110はbcにしか変換できないので複合可能。

bd→0111、0111はbdにしか変換できないので複合可能。

---

ca→1000、1000はcaにしか変換できないので複合可能。

cb→1001、1001はcbにしか変換できないので複合可能。

cc→1010、1010はccにしか変換できないので複合可能。

cd→1011、1011はcdにしか変換できないので複合可能。

---

da→1100、1100はdaにしか変換できないので複合可能。

db→1101、1101はdbにしか変換できないので複合可能。

dc→1110、1110はdcにしか変換できないので複合可能。

dd→1111、1111はddにしか変換できないので複合可能。

エに関しても複合は問題なさそう。


次、a、b、c、dはそれぞれ50%、30%、10%、10%の確率で選択されるので
この確率とビット長さを掛け合わせると期待するビット長さが求まる。


ウ
aの時１ビット。これは50%で選択されるので１×０．５＝０．５
bの時2ビット。これは30%で選択されるので２×０．３＝０．６
cの時3ビット。これは10%で選択されるので３×０．１＝０．３
dの時3ビット。これは10%で選択されるので３×０．１＝０．３

０．５＋０．６＋０．３＋０．３＝１．７ビット


エ
aの時2ビット。これは50%で選択されるので２×０．５＝１．０
bの時2ビット。これは30%で選択されるので２×０．３＝０．６
cの時2ビット。これは10%で選択されるので２×０．１＝０．２
dの時2ビット。これは10%で選択されるので２×０．１＝０．２

１．０＋０．６＋０．２＋０．２＝２．０ビット

よって、ウの方式による符号化の方がビット長さが短くなる。

答え　ウ


圧縮プログラムなどいかにしてよく出現するものを、短く表現するか？
にかかっているので、ウの方式は頻繁に出る部分を１ビットで表現し、
複合化可能にするために、やむをえず、出現頻度が小さいとこでビット長さを増やし
一意に変換できるようにしている。

エは何も考えずに全て２ビットで表現した場合。

という見方ができる。

戻る

CHAPTER2_08_問題08

0～１までの乱数によってXとYの値を決定する時
Ｙ<Xを満たす回数の期待値は

もし、ＸがYより１００％大きい値がでるのであれば期待値は６００回やるので６００回が答えになる。

が、今回は乱数なので、どっちが大きいかは１／２といえる。

よって、６００回×１／２＝３００回　は期待できるといえる。

答え　ウ

戻る

CHAPTER2_08_問題06

■２個の文字AとBを使って１文字を作る時
２通りの中から１つ選ぶので２通り

■２個の文字AとBを使って２文字を作る時
２通り×２通り＝４通り

■２個の文字AとBを使って３文字を作る時
２通り×２通り×２通り＝８通り

■２個の文字AとBを使って４文字を作る時
２通り×２通り×２通り×２通り＝１６通り

■２個の文字AとBを使って５文字を作る時
２通り×２通り×２通り×２通り×２通り＝３２通り

■２個の文字AとBを使って６文字を作る時
２通り×２通り×２通り×２通り×２通り×２通り＝６４通り

■２個の文字AとBを使って７文字を作る時
２通り×２通り×２通り×２通り×２通り×２通り×２通り＝１２８通り

全て足し合わせたのが答え

２通り＋４通り＋８通り＋１６通り＋３２通り＋６４通り＋１２８通り

＝２５４通り

答え　イ

戻る

CHAPTER2_08_問題07

PからRまでのある組み合わせの時に、RからQまでいく手段通り分存在するので

PからRまでの組み合わせを求めて、RからQまでの組合せをもとめそれぞれ掛け合わせるとよい


■PからRまでの組み合わせを求める
PからRまで、４つのアクションが書かれたカードを拾う問題と考えると

４×３×２×１＝２４通りということになる、

ただし、
右は２つ重複がありその組み合わせは２通り
上は２つ重複がありその組み合わせは２通り

つまり
右→右→上→上　という組み合わせを考えた時に

右１右２上１上２
右１右２上２上１
右２右１上１上２
右２右１上２上１

の４パターン（右の２パターン×上の２パターン）分重複が発生している。
つまり、４通りあっても１通りとしかカウントされないので４で割ってあげる必要がある

＝２４／４＝６通り（P→R間の組み合わせ）

■RからQまでの組み合わせを求める
RからQまで、５つのアクションが書かれたカードを拾う問題と考えると

５×４×３×２×１＝１２０通りということになる、

ただし、
右は３つ重複がありその組み合わせは６通り
上は２つ重複がありその組み合わせは２通り

つまり
右→右→右→上→上　という組み合わせを考えた時に

右１右２右３上１上２
右１右２右３上２上１
右１右３右２上１上２
右１右２右３上２上１

右２右１右３上１上２
右２右１右３上２上１
右２右３右１上１上２
右２右１右３上２上１

右３右１右２上１上２
右３右１右２上２上１
右３右２右１上１上２
右３右２右１上２上１

の１２パターン（右の６パターン×上の２パターン）分、重複が発生している。
つまり、１２通りあっても１通りとしかカウントされないので１２で割ってあげる必要がある

＝１２０／１２＝１０通り（R→Q間の組み合わせ）


P→R間の組み合わせとR→Q間の組み合わせは個別に存在するので掛け合わせる必要がある
６通り×１０通り＝６０通り



(補足)

分子に重複を考慮しない時の組み合わせ
分母に重複分の組み合わせ分減らす考えで書いた式は、

世間一般で言うところの公式に当てはめたものと計算過程が全く変わりません。

単に上のように考えるのをすっ飛ばしたのが公式というわけです。


戻る

CHAPTER2_08_問題05

今回の組み合わせは順番を求められていないのでペアを求める問題です。

つまり、ABとBAは一緒。２つあっても１カウント

よって、１回目に引き当てるのは１０人いるので１０通り
２回目に引き当てるのは１人減った９人いるので９通り

最初に言ったとおり、順番関係なしのペアを求める問題なので
重複分は減らさないといけない。
ABとBAは２つあっても１カウントなので１／２する必要がある。

１０×９÷２＝４５通り

答え　ウ

戻る

CHAPTER2_08_問題04

aとbが両端になるということは
a→bのパターンとb→ａのパターンの２通りになる

間の組み合わせは一つずつ減っていくパターンの通り数を求めればよいので

c、d、e、f を並べる組合わせは、４×３×２×１
よって

２×（４×３×２×１）＝２×２４＝４８通り

答え　ウ


戻る

CHAPTER2_08_問題03

単純マルコフ過程・・・未来の挙動が現在の値だけで決定され、過去の挙動と無関係であるというお話。

なんでこんなことを書くかというと
いやー天気ですもん。一度崩れたらしばらく天気って崩れたりするでしょ。
たとえば梅雨シーズンとか。
一律前日の天気が何だから、こうなるってのはおかしーんじゃないの？
というつっこみに対応するために、いや、過去の挙動とは関係なく一律その確率で未来が確定するとしよう！
と言っている。

そんな大人な事情は気にしないでいきましょう。
直近の天気をきにしつつ確率を反映なんてなると、もはや情報処理の話じゃなくなっていくので。



さて、問題に戻ります。
雨の２日後が晴れであるには・・・
以下の組み合わせが考えられる

各組み合わせの確率を求めてそれらを足し合わせる。
（雨→晴れ）０．３　×　０．４（晴れ→晴れ）＝０．１２
（雨→曇り ）０．５　×　０．３（曇り→晴れ）＝０．１５
（雨→雨）　 ０．２　×　０．３（晴れ→晴れ）＝０．０６

０．１２＋０．１５＋０．０６＝０．３３

よって３３％の確率で雨の２日後に晴れが来る。

答え　エ


戻る

CHAPTER2_08_問題02

問題文より条件を整理する

先頭：

　数字のみ使える０～９

２番目以降：

　空白の後は空白のみ

　数字の後は数字 or 空白

上記３パターンそれぞれの組み合わせを求めて足し合わせるとよい

①数字→空白→空白
１０通り×１通り×１通り＝１０通り

②数字→数字→空白
１０通り×１０通り×１通り＝１００通り

③数字→数字→数字
１０通り×１０通り×１０通り＝１０００通り

１０＋１００＋１０００＝１１１０通り

答え　ア


戻る

CHAPTER2_08_問題01

くじを同時に２本引くということは、１本引いたらくじを戻さずにもう一度引くのと同じ意味。

１回目の当たりを引くには、５本中２本含むあたりをひけばいい
２／５

２回目の当たりを引くには、１本少なくなって４本中１本含むあたりをひけばいい
１／４

２／５　×　１／４＝１／１０

答え　ウ

戻る

CHAPTER2_08_問7

期待値は、ある値が発生する確率を足し合わせた物。
単なる定義です。

なので、この通り計算するだけです。
サイコロの１が出た時は、値は　５０。そして確率は１／６
サイコロの２が出た時は、値は１００。そして確率は１／６
サイコロの３が出た時は、値は１５０。そして確率は１／６
サイコロの４が出た時は、値は２００。そして確率は１／６
サイコロの５が出た時は、値は２５０。そして確率は１／６
サイコロの６が出た時は、値は３００。そして確率は１／６

５０×１／６　＋　１００×１／６　＋　１５０×１／６　＋　２００×１／６　＋　２５０×１／６　＋　３００×１／６
＝（５０＋１００＋１５０＋２００＋２５０＋３００）／６
＝１０５０／６
＝１７５

戻る

CHAPTER2_08_問6

右と上と書かれたプレートが合計７つあり
それらを１回ひいたら戻さずに７回引く場合を考えると

７×６×５×４×３×２×１＝５０４０通り

ただし、これは選ぶ物が全て重複がない場合。
重複があるので除外しないといけない。


例）
右→右→右→右→上→上→上のパターンを考えた

右だけ組み合わせを考えたとしても２４通り全て
右→右→右→右→上→上→上　と同じということになる。

上だけ組み合わせを考えたとしても６通り全て
右→右→右→右→上→上→上　と同じということになる。

さらに、
右１→右２→右３→右４→上？→上？→上？　の時に６通りだぶりが発生する
右１→右２→右４→右３→上？→上？→上？　の時に６通りだぶりが発生する


よって、選ぶもの全て重複ない時に比べ
ある一つの組み合わせに対し、
２４通り×６通り＝１４４通り　　だぶりが発生することになる。

1/144する必要がある。


よって、

＝５０４０／１４４＝３５通り

答え　３５通り


戻る

CHAPTER2_08_問5

同じ数字は何度用いてよいので、毎回６個の中から選ぶことになる。

６×６×６＝２１６

答え　２１６通り


戻る

CHAPTER2_08_問4

ペアで作る場合、最初に選ばれた場合と次に選ばれた場合の順番が関係なくなることに注意

最初に選ばれるのは、A～Gの７通り
次に選ばれるのは、１つ減った６通り

ただし、「AB」、「BA」は順番を考慮する時は、別ものであるが
ペアを選ぶ時は、順番を考慮しないため一緒とみなされる

AB、BA　で２個で１つとカウントする必要がある。
つまり組み合わせ分でわるとよい

＝２１通り

答え　２１通り


戻る

CHAPTER2_08_問3

答え　２４通り

戻る

CHAPTER2_08_問２

「晴れ」は０．４
「くもり」は０．４
「雨」は　０．２

１日目が「晴れ」、２日目は「晴れ」以外なので

１日目が「晴れ」、２日目が「くもり」と
１日目が「晴れ」、２日目が「雨」の
確率をそれぞれ求め足し合わせるとより

０．４×０．４＋０．４×０．２
＝０．１６＋０．０８
＝０．２４

答え　０．２４




参考

全ての組み合わせを求め足し合わせると
「晴れ」＋「くもり」＋「雨」＝０．４＋０．４＋０．２＝１となる
せっかくなので確認。

晴れ×晴れ＝０．４×０．４＝０．１６
晴れ×くもり＝０．４×０．４＝０．１６
晴れ×雨＝０．４×０．２＝０．０８

１日目が晴れの時
０．１６＋０．１６＋０．０８＝０．４

くもり×晴れ＝０．４×０．４＝０．１６
くもり×くもり＝０．４×０．４＝０．１６
くもり×雨＝０．４×０．２＝０．０８

１日目がくもりの時
０．１６＋０．１６＋０．０８＝０．４

雨×晴れ＝０．２×０．４＝０．０８
雨×くもり＝０．２×０．４＝０．０８
雨×雨＝０．２×０．２＝０．０４

１日目が雨の時
０．０８＋０．０８＋０．０４＝０．２

全ての組み合わせの合計
０．４＋０．４＋０．２＝１

よって、指示された事象の確率を求めてそれぞれを足し合わせるとよい


戻る

CHAPTER2_08_問１

２つのサイコロを振ったときの組み合わせは、以下の通り

１回目サイコロを振ると１から６の６通り存在し、
２回目は、１回目振った数字に対し、１～６の６通り存在するので

２つのサイコロを振ったときの組み合わせは６×６＝３６通り　となる。


①両方同じ目が出る確率

上記６通りよって

両方同じ目の組み合わせ／全体の組み合わせ　は

６／３６＝１／６

答え　１／６



②両方とも偶数が出る確率

１回目サイコロを振ると２，４，６の３通り存在し、
２回目は、１回目振った数字に対し、２，４，６の３通り存在するので

２つのサイコロを振ったときの組み合わせは３×３＝９通り　となる。

両方偶数の組み合わせ／全体の組み合わせ　は

９／３６＝１／４

答え　１／４



③両方違う目が出る確率

両方違う目が出る確率は、両方同じ目が出る確率の反対
両方同じ目は、１－１　～　６－６の６通りなので
それ以外が両方違う目の組み合わせとなるので３６－６＝３０

両方違う目の組み合わせ／全体の組み合わせ　は

３０／３６＝５／６

答え　５／６

ちなみに、全体から両方同じ目が出る確率を引くことでもとめるのでもよいです。

１－５／６＝６／６－１／６＝５／６



④少なくとも片方に１が出る確率

少なくとも片方に１が出る確率なので
１回目に１が出た時の組み合わせと２回目に１が出た時の組み合わせを考える
それぞれ６通りずつあるので１２通り
ただし、１－１は２回登場しているので－１してあげる必要がある

１２－１＝１１通り

１－１、１－２、１－３、１－４、１－５、１－６
　　　　 ２－１、３－１、４－１、５－１、６－１

少なくとも片方に１が出る組み合わせ／全体の組み合わせ　は

１１／３６

答え　１１／３６


戻る