在图6－9中,由点O(0,0)到点P(5,6)的最短路径共有(63)条。A.126B.128C.252D.256

Question

在图6-9中，由点O(0,0)到点P(5,6)的最短路径共有(63)条。

A．126

B．128

C．252

D．256

Answer 1

正确答案：C
解析：图6-9点O到点P的最短路径，即只能向上或向右走的所有路径。从点O走最短路径到点P可以分为两步：①从O到点(1,1)：共2条路径，分别是先向上和先向右走。②从点(1,1)到点户：设向右走一格的长度为x，向上走一格的长度为y，那么不管怎么走，从点(1,1)出发，总是要经过4个x，5个y，方能到达点p，所以一条从点(1,1)到点户的最短路径对应一个由4个x、 5个y共9个元素构成的排列；反之，给定一个这样的排列，按照x,y的含义，必对应一条从点(1,1)到点 p的最短路径。因此从点(1,1)到点户的最短路径与4个x，5个y的排列一一对应。故从点(1,1)到点p的最短路径计数转换为不尽相异元素的全排列问题，其解为从排列的9个位置中选出4个位置放x，剩下的 5个位置放y，计数结果为。按照乘法规则，从点O到点p的最短路径数为2×126=252条。