214 views
この記事は最終更新から 501日 が経過しています。
1. 力尽くで解いてしまったが…
基本情報技術者試験 平成30年度春期試験 問2
以下のような問題だ。
マス目の数が少ないので、ついつい力尽くで解いてしまった。
でも、もし本番でマス目の数が増えたならば…
力尽くでは試験時間を浪費してしまうだろう。
そこで…
最短経路の数を計算で求められるように訓練しておきたい
と思った。
高校生の頃にやったような気がするのだが
2. やってみる
Step 1 : 区間 P to R
初めに区間 P to R の移動を考えてみる。
最短経路を通る場合、下記のように → x 2回、↑ x 2回の合計 4回の移動の組合せになる。
→ → ↑ ↑
→ ↑ → ↑
→ ↑ ↑ →
：等々
まずは、→ → ↑ ↑ をそれぞれ異なるものとして、愚直に樹形図を描いてみる。
力尽くで求めた結果は 24通りだ。
上図の通り、これは 4P4の順列なので、以下の式で算出できる。
実際には、2回の横移動 → と → は区別しないので、これを同じものとして重複する組合せを削除する。
重複数が 2の場合、組合せの数が 1/2に減る。
【参考】
重複数が3の場合、組合せの数が 1/3! になる。
∵3個の場合の組合せは3!通りだから、この3個を区別しなければ 1/3!に減るのは当然だ。
【参考】
重複数がnの場合、組合せの数が 1/n! になる。
∵n個の場合の組合せはn!通りだから、このn個を区別しなければ 1/n!に減るのは当然だ。
同様に、2回の縦移動 ↑ と ↑ も区別しないので、こちらについても重複する組合せを削除する。
この結果、→ → (区別せず) ↑ ↑ (区別せず)の組合せは以下の通りになった。
Step 2 : 区間 R to Q
R to Qも同様に、→ → → ↑ ↑ の5回の移動の組合せとして、以下の通りに算出できる。
Step 3 : 全区間
上記の P to R, R to Qを直列に繋ぐと、組合せの数は以下の通り。
3. 所感
・盲目に公式を覚えるよりも、理屈で覚えてしまった方がスッキリする。
・少し復習すれば思い出せそうなので、今後も公式の暗記に頼らずに理論を確認しながら学習しよう。