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

    ACM-POJ EXP 126阅读 0评论

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


    POJ1496 基本一致

    大致题意

    输出某个str字符串在字典中的位置,由于字典是从a=1开始的,因此str的位置值就是 在str前面所有字符串的个数 +1

    规定输入的字符串必须是升序排列。不降序列是非法字符串

    不要求用循环输入去输入若干组字符串,但若输入非法字符串则输出0,且结束程序这是和 POJ1496 最猥琐的区别,很多同学只注意到规定str的长度不同,以为把str数组长度改一下直接复制就能AC再多刷一题了,殊不知老是WA却找不到原因,大概就是这里出问题了

    本题Str最长为10个字符

    解题思路

    组合数学题,(也属 递推数学,是因为杨辉三角和组合数之间的关系)


    第一步当然首先判断输入的str是否是升序序列

    若符合第一步,则首先计算比str长度少的所有字符串个数

    假设str为 vwxyz ,则其长度为5

    那么


    第二步就是关键了,长度为2的字符串,根据开头字母不同,就有25种不同情况,编程去处理是很困难的。这里必须要用数学方法去处理。

    所以用一个简单的循环就能计算出 比str长度少的所有字符串个数 了,这就是数学的威力,把受限的取法转换为不限制的取法


    第三步,就是求长度等于str,但值比str 小的字符串个数

    这个看我程序的注释更容易懂,所以这里就不再啰嗦了,值得注意的是这步我同样利用了公式(1),所以如果看到某些地方取字母的时候看上去好像没有遵守“升序规则”,本来要限制取字母的地方却没有限制,那一定是用公式(1)变换了


    第四步,把前面找到的所有字符串的个数之和再+1,就是str的值

    之所以+1,是因为此前的所有操作都只是找str之前的字符串,并不包括str本身


    最后,剩下一个问题就是怎样得到每一个 的值,这个我发现很多同学都是利用打表做的,利用的就是 组合数 与 杨辉三角 的关系(建立一个二维数组C[n],就能看到他们之间关系密切啊!区别就是顶点的值,杨辉三角为1,组合数为0)

    其实这个“关系”是有数学公式的:

    其实组合数也可以直接用计算方法做(n的规模可以至少扩展到1000),不过这里n的规模只有26,打表应该是更快的

    转载请注明:EXP 技术分享博客 » POJ1850 – Code

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

    表情

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

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