论坛 › 算法交流 › 求2^1000的各位数字之和

wayne 发表于 2009-3-17 09:24:13

求2^1000的各位数字之和

如题，求$2^1000$的各位数字之和。
我总感觉暗藏着什么好的算法，可就是思维堵住了，大伙帮帮我吧

gxqcn 发表于 2009-3-17 09:45:47

答案是 1366

似乎没有什么捷径。

wayne 发表于 2009-3-17 09:59:12

设10^n为a_n，则任何数都是a_i的线性和，可否通过某种递归的特性 将2^1000表达成a_i的线性和，最终令所有的a_i为l，从而得解？

无心人 发表于 2009-3-17 11:40:52

没有，因为数字和仅和数字相关
只要数字参与别的运算，即改变
且无任何规律

无心人 发表于 2009-3-17 11:42:40

Prelude Char> let digitsSum n = sum
Prelude Char> digitsSum (2^10000)
13561
Prelude Char> digitsSum (2^1000)
1366

wayne 发表于 2009-3-17 11:48:07

原帖由 无心人 于 2009-3-17 11:40 发表 http://bbs.emath.ac.cn/images/common/back.gif
没有，因为数字和仅和数字相关
只要数字参与别的运算，即改变
且无任何规律
你好像很确信没有啊，
这是project euler 上的第16题，就这样brute force，好像不是它的风格

wayne 发表于 2009-3-17 11:50:19

原帖由 无心人 于 2009-3-17 11:42 发表 http://bbs.emath.ac.cn/images/common/back.gif
Prelude Char> let digitsSum n = sum [ord(c) - ord('0') | cdigitsSum (2^10000)
13561
Prelude Char> digitsSum (2^1000)
1366
能问一下你的haskell用的是哪个外壳吗，好象不是winhugs

无心人 发表于 2009-3-17 11:53:57

GHCi

无心人 发表于 2009-3-17 11:55:20

:)

我想当然的，哈哈
有算法，请指教啦

litaoye 发表于 2009-3-17 14:25:20

是选择题?还是填空题?

填空的话没想出什么好的办法,选择的话,可以用mod 9判断一下!

查看完整版本: 求2^1000的各位数字之和