• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ1942 – Paths on a Grid

    ACM-POJ EXP 156阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    大致题意

    给定一个矩形网格的长m和高n,其中m和n都是unsigned int32类型,一格代表一个单位,就是一步,求从左下角到右上角有多少种走法,每步只能向上或者向右走

    解题思路

    非常水的中学数学题,用组合

    简单建立一个数学模型

    只要给定了长m和高n,那么要从左下角走到右上角,不管怎么走,一定要往右走m次,往上走n次

    例如给定 m=5,n=4

    那么可以 上上上上上右右右右

    又可以 上右上右上右上右上

    等等。。。

    关键是“上”和“右”的先后问题,就是组合问题了

    那么数学模型就是

    从n+m个位置,选择n个位放“上” (那么剩下m个位一定是“右”)


    处理阶乘有三种办法

    (1) 传统意义上的直接递归,n的规模最多到20+,太小了,在本题不适用,而且非常慢

    (2) 稍快一点的算法,就是利用log()化乘为加,n的规模虽然扩展到1000+,但是由于要用三重循环,一旦n规模变得更大,耗时就会非常之严重,时间复杂度达到O(nm(n-m)),本题规定了n,m用unsigned int32类型,就是说n,m的规模达到了21E以上,铁定TLE的。而且就算抛开时间不算,还存在一个致命的问题,就是精度损失随着n的增加会变得非常严重。

    因为n有多大,就要进行n次对数运算,n规模一旦过大,就会丢失得非常严重了。所以这种方法是绝对不可取的,因为中途的精度丢失不是简单的四舍五入可以挽回的。

    (3) 拆分阶乘,逐项相除,再乘以前面所有项之积。这种方法用一个循环就OK了,时间复杂度只有O(n-m),非常可观。


    下面我根据程序详细说说算法(3)

    这是我写的函数原型,计算的是 aCb

    这种算法巧妙地利用了分子分母的关系,而不是把公示中的3个阶乘单独处理。

    例如当 a=5,b=2时

    由于用了 double去计算组合数,那么最后要转化为 无符号整型 时就要处理精度问题,有两种方法四舍五入+强制类型转换 或者 用 setprecision()函数

    详细看我的两个程序


    方法一:四舍五入+强制类型转换

    转载请注明:EXP 技术分享博客 » POJ1942 – Paths on a Grid

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址