ChaseDream

标题: 求算法 [打印本页]

作者: true 时间: 2010-2-13 15:23
标题: 求算法
OG10th,316
Pat will walk from intersection X to intersection Y along a route thatis confined to the square grid of four streets and three avenues shownin the map above. How many routes from X to Y can Pat take that havethe minimun possible length?

(A)6
(B)8
(C)10（ANSWER）
(D)14
(E)16
AveA AveB AveC
| | |
4th St.----------------------Y------
| | |
3th St.------------------------
| | |
2th St.--------------------------
| | |
1th St.-----X----------------
| | |

数是数得出来，但是没有更好的算法？
不会画图。直接敲出来的。

作者: 飞行2010 时间: 2010-2-13 16:30
从X点开始到Y点，无论是先向北还是先向东，都只经过5各点，北3个，东2个。我们可以把一个方向固定，如把向北的固定，就是C5,2;把向东的固定就是C5,3结果的都是一样的。
其实这个和“一共有5个位置，任选3个放向上的箭头，剩下的就是放横向的2个箭头”是一个道理。两种方法都可以。
呵呵，不知道你明白了没有。

作者: true 时间: 2010-2-13 20:29
多谢楼上解析。
有所理解了。

其实就是个组合问题，5个格子，选三个北或者选两个东

作者: tommyting 时间: 2010-2-14 16:21
这道题OG上给的算法真的是很烂...

考试时没那个时间给你那样算的

欢迎光临 ChaseDream (https://forum.chasedream.com/)