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

    算法 EXP 218阅读 0评论

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


    为了简化说明,以三位数举例,

    因为153、135、315、351、513、531的立方和都是一样的,均等于 1^3+3^3+5^3 = 153

    而我们可以通过逐位检查 立方和153,发现1出现1次,3出现1次,5出现1次,而0~9中的其他数字均出现0次,出现的次数之和为3,刚好等于153的长度。

    由此我们可以得到 利用枚举0~9各个数字出现的次数,得到水仙花数

    得到21位水仙花数的具体方法为

    通过10层循环,枚举0~9这10个数字出现的次数(每个数字都可能出现0~21次),当所有数字出现次数之和等于21时,说明这时数字的组合有可能为21位水仙花数,
    进而求出 {[(每个数字的3次方)并分别乘以其出现的次数]后的值 之和sum}

    例如 当我们枚举到数字6出现了5次,8出现16次 时,由于8+16=21,此时我们计算sum=6^21*5+8^21*16,检查得到的和sum的各个位,若恰好出现5个6和16个8,说明这种数字组合使得其和为水仙花数

    为了减少程序运行时间,我们可以先把0~9的21次方及其不同的出现次数的值利用另外的程序打表,数值存储到本程序的3维数组valus[i][j][k],表示数字i的21次方 乘以 j(出现次数)得到的值。需要用到这些值时可直接调用,此时我们只需要计算的是10个大数连加,无需计算求幂和乘法,大大节约时间。

    valus[i][j][k]数组内容如下:

    数字 出现次数 0 1 2 …… 19 20 21
    0 0^21 0^21*0 0^21*1 0^21*2 …… 0^21*19 0^21*20 0^21*21
    1 1^21 1^21*0 1^21*1 1^21*2 …… 1^21*19 1^21*20 1^21*21
    2 2^21 2^21*0 2^21*1 2^21*2 …… 2^21*19 2^21*20 2^21*21
    3 3^21 3^21*0 3^21*1 3^21*2 …… 3^21*19 3^21*20 3^21*21
    4 4^21 4^21*0 4^21*1 4^21*2 …… 4^21*19 4^21*20 4^21*21
    5 5^21 5^21*0 5^21*1 5^21*2 …… 5^21*19 5^21*20 5^21*21
    6 6^21 6^21*0 6^21*1 6^21*2 …… 6^21*19 6^21*20 6^21*21
    7 7^21 7^21*0 7^21*1 7^21*2 …… 7^21*19 7^21*20 7^21*21
    8 8^21 8^21*0 8^21*1 8^21*2 …… 8^21*19 8^21*20 8^21*21
    9 9^21 9^21*0 9^21*1 9^21*2 …… 9^21*19 9^21*20 9^21*21

    剪枝

    9^21是一个21位数,9^21*10是一个22位数(超过21),即9^21最多出现9次,因此9只需从0~9次枚举其出现次数,而0不能做数字开头,0从0~20次枚举,其他数字从0~21次枚举。需要注意的是,在10层的多重枚举循环中, CPU切换循环层时也需要时间,所以一般来说将次数少的循环放在外层,将循环次数多的放在内层。故十重循环中将9放在最外层,然后是0 、1,然后是剩余的。

    其他位的水仙花也可采用一样的做法,只需改变valus[i][j][k]存储的内容 及 数字出现的次数 即可

    转载请注明:EXP 技术分享博客 » 21位大数的水仙花数

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

    表情

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

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