【基本情報技術者試験平成20年秋期午前】問題・解説・解答

[TOP] [午前分野別] [午後分野別] [キーワード索引] [令和元年秋午前] [令和元年秋午後]

平成20年秋期基本情報技術者午前問07

問07　　 最短経路の組み合わせ

　図の線上を，点 P から点 R を通って，点 Q に至る最短経路は何通りあるか。

ア　16　　　　　イ　24　　　　　ウ　32　　　　　エ　60

解説

　図のように点 P から点 R にいく最短経路は６通りである。

　これは、上に２回、右に２回行く４つの組み合わせから２つをとる組み合わせであるから、

₄Ｃ₂＝４！／２！（４－２）！＝４！／２！×２！＝（４×３×２×１）／（（２×１）×（２×１））＝６となる。

　また、点 R から点 Q に至る最短経路は、同様に、上に２回、右に３回の組み合わせであるから
₅Ｃ₂＝５！／２！（５－２）！＝５！／２！×３！＝（５×４×３×２×１）／（（２×１）×（３×２×１））＝１０となる。

点 P から点 R を通って，点 Q に至る最短経路は、１０×６＝６０となる。