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

    ACM-POJ EXP 176阅读 0评论

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


    大致题意

    有一串数字串,其规律为

    1 12 123 1234 12345 123456 1234567 12345678 123456789 12345678910 1234567891011 123456789101112······k

    输入位置n,计算这一串数字第n位是什么数字,注意是数字,不是数!例如12345678910的第10位是1,而不是10,第11位是0,也不是10。总之多位的数在序列中要被拆分为几位数字,一个数字对应一位。

    解题思路

    首先建议数学底子不好的同学,暂时放一放这题,太过技巧性了,连理解都很困难

    模拟分组,把1看做第1组,12看做第2组,123看做第3组……那么第i组就是存放数字序列为 [1,i]的正整数,但第i组的长度不一定是i

    已知输入查找第n个位的n的范围为(1 ≤ n ≤ 2147483647),那么至少要有31268个组才能使得数字序列达到有第2147483647位

    注意:2147483647刚好是int的正整数最大极限值( ),所以对于n用int定义就足矣。但是s[31268]存在超过2147483647的位数,因此要用unsigned 或long 之类的去定义s[]

    详细的解题思路请参照程序的注释。

    其中数学难点有2

    (int)log10((double)i)+1

    (i-1)/(int)pow((double)10,len-pos)%10

    非常技巧性的处理手法,其意义已在程序中标明


    另外要注意的就是log()和pow()函数的使用

    两个都是重载函数,函数原型分别为

    double log(double)

    float log(float)

    double pow(double , double)

    float pow(float ,float)

    所以当传参的类型不是double或float时,必须强制转换为其中一种类型,否则编译出错。一般建议用double


    转载请注明:EXP 技术分享博客 » POJ1019 – Number Sequence

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

    表情

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

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