基本情報技術者 平成14年春期 午前問6

午前問6

図のA地点から,線上をたどってB地点に到達するための最短経路は,何通りあるか。ここで,縦1区画の長さはすべて等しく,横1区画の長さもすべて等しいものとする。
06.gif/image-size:220×120
  • [この問題の出題歴]
  • ソフトウェア開発技術者 H18秋期 問4

分類

テクノロジ系 » 基礎理論 » 応用数学

正解

解説

すべての経路を表すと下図のとおりです。
06_1.gif/image-size:300×183
06_2.gif/image-size:400×284
※最短経路なので、B地点から遠ざかる経路は選ばないこと

計算で求める場合は、コンビネーション(組み合わせ)を考えます。
まず、縦と横の区画数を数えます。

 縦:2区画
 横:3区画

つまり、いずれの経路を通ったとしてもA地点からB地点までの経路は、縦2区画、横3区画なので以下のように表せます。

 縦→縦→横→横→横
 縦→横→縦→横→横
 縦→横→横→縦→横
 縦→横→横→横→縦
 …

縦を基準にして考えると、5つから2つを選ぶ組み合わせを求めると…

(縦+横)C

で、最短経路を求めることができます。

 5C2=(5×4)÷(2×1)=10

または、横を基準にして考えると、5つから3つを選ぶ組み合わせを求めると…

 (縦+横)C

で、最短経路を求めることができます。

 5C3=(5×4×3)÷(3×2×1)=10

したがって、正解は「イ」です。
© 2010-2019 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop