うごく基本情報

平成27年度 秋期 問2

基礎理論 › グラフ理論・数値計算 △ ときどき出る

出典:平成27年度 秋期 基本情報技術者試験 午前 問2 の問題

出典:平成27年度 秋期 基本情報技術者試験 午前 問2

正解と解説を見る

正解:エ

覚えること:格子の最短経路の数 = 組合せ。右に m 回、上に n 回進むなら (m + n)C m 通り。途中の点を通るなら、前半と後半の数を掛ける。

P から R までは右に2、上に2進むので 4C2 = 6通りです。R から Q までは右に3、上に2進むので 5C2 = 10通りです。R を通る最短経路は 6 × 10 = 60通りです(エ)。足し算にすると 16通り(ア)になってしまいます。イの 24 とウの 32 は、この計算からは出てこない値です。

解説はこのサイトが作成したものです。

同じ問題が 平成30年度 春期 問2 にも出ています。