浏览 2512 次
|
锁定老帖子 主题：请教飓风，N*N棋盘路线问题
精华帖 (0) :: 良好帖 (0) :: 灌水帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2008-12-18
在那个吵架贴中看到了飓风提到的这个问题 （那个贴现在找不到了？）
引用 我看到这么一个问题：一个棋盘N*N的方格，从左上格移动到右下格，每步只能向右或向下移动一格，移动路线不能穿越对角线，有多少条路径？
认真地思考了这个问题，结果在纸上涂了半个多小时没有头绪，感觉需要递推才能得到结果。 后来把整个帕斯卡三角画出来，意外地发现左右相邻两个数相减可以得到答案， 我也不知道为啥我会尝试这么干，反正后来用归纳法把这条公式证明了。 这样得到的答案太碰运气了...我想知道常规的组合分析过程，如何发现它？ 声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
|
发表时间：2008-12-19
http://sunyday.iteye.com/admin/blogs/295182
|
| 返回顶楼 | |
|
发表时间：2008-12-19
最后修改：2008-12-19
后来再想了一下明白了，唉，当时死脑筋。
LS，我说的问题不是你那个。 本来想把两个证法写出来，发现描述起来太麻烦，就算了。 |
| 返回顶楼 | |
|
发表时间：2008-12-19
Project Euler上有类似的题目. 去找了下是第15题, 可以google下别人的解答~~
|
| 返回顶楼 | |
|
发表时间：2008-12-19
hyf 写道 在那个吵架贴中看到了飓风提到的这个问题 （那个贴现在找不到了？）
引用 我看到这么一个问题：一个棋盘N*N的方格，从左上格移动到右下格，每步只能向右或向下移动一格，移动路线不能穿越对角线，有多少条路径？
认真地思考了这个问题，结果在纸上涂了半个多小时没有头绪，感觉需要递推才能得到结果。 后来把整个帕斯卡三角画出来，意外地发现左右相邻两个数相减可以得到答案， 我也不知道为啥我会尝试这么干，反正后来用归纳法把这条公式证明了。 这样得到的答案太碰运气了...我想知道常规的组合分析过程，如何发现它？ 到我有时间的，这个问题要证明，可以归纳，但是html里面弄公式丑啊，可以用画图，但是麻烦啊。等我下一个周1的，闲得时候来给大家写写。 |
| 返回顶楼 | |
|
发表时间：2009-01-11
最后修改：2009-01-11
2*N步里面取N个向右（或向下的）的取法，一个组合问题：
C(2*N,N) 或者 看成是N个向右，N个向下的全排列问题 （2*N)!/(N!*N!) 一本组合数学课本的课后题 |
| 返回顶楼 | |
