应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » 其它 » Euler 工程第十六题：2的1000次方的各项和
52/1返回列表
查看: 2684  |  回复: 14
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看
本帖产生 2 个 程序强帖 ，点击这里进行查看
当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖

holmescn

金虫 (正式写手)

[交流] Euler 工程第十六题：2的1000次方的各项和 已有6人参与

这两天新版开通，版里很热闹，也就没有放题出来。今天放一个题吧。

已知2的15次方等于32768，其各项和为：3+2+7+6+8 ＝ 26 。
那么2的1000次方的各项和是多少呢？
回复此楼

» 猜你喜欢
1楼 2011-05-26 21:06:30
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)
★ ★ ★ ★ ★
微尘、梦想(金币+5): 谢谢交流！ 2011-05-29 16:22:21
LS的代码确实有点 quick & dirty。不过， 如果你理解了我的意思的话，可以写出如下更高效的代码。
CODE:
#include

int multiply(char* digits, int len, int factor, int times) {
    int i, j;
    int c, r;

    for(i = 0; i < times; i++) {
        c = 0;
        for(j = 0; j < len; j++) {
            r = digits[j] * factor + c;
            c = r / 10;
            digits[j] = r % 10;
        }

        if (c > 0) {
            digits[len] = c;
            len += 1;
        }
    }

    return len;
}

int main(int argc, char** argv) {
    char digits[500];
    int  len = 1;
    int  r, i;

    digits[0] = 1;

    len = multiply(digits, len, 8, 333);
    len = multiply(digits, len, 2, 1);

    printf("digits len = %d\n", len);

    r = 0;
    for(i = len - 1; i >= 0; i--) {
        r += digits[i];
        printf("%d", digits[i]);
    }
    printf("\nsum = %d\n", r);

    return 0;
}
赞一下(1人) 回复此楼
15楼2011-05-28 07:26:45
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
查看全部 15 个回答

huycwork

金虫 (著名写手)
★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
微尘、梦想(金币+2): 谢谢参与！ 2011-05-27 15:24:11
来个Perl版：
CODE:
#!/usr/bin/perl
use bigint;
$sum += $_ foreach(2**1000 =~ /(.)/g);
print "result:$sum\n";

结果：1366
赞一下(2人) 回复此楼
漩涡的中心有一块空地，空空的。
2楼2011-05-26 21:38:51
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

sudo

木虫 (正式写手)
★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
微尘、梦想(金币+2): 谢谢交流讨论！ 2011-05-27 15:24:41
引用回帖:
Originally posted by huycwork at 2011-05-26 21:38:51:
来个Perl版：
CODE:
#!/usr/bin/perl
use bigint;
$sum += $_ foreach(2**1000 =~ /(.)/g);
print "result:$sum\n";

结果：1366

咳，我突然想到一个好玩的东西...

对于一个数的大指数出来的各个位数，0-9的概率分布趋向于均匀分布~

那么我们可以做大致的估算：

2^1000的位数为

向下取整(1000 * log 2) + 1 = 302 位

对于每个位的期望为4.5，然后所有位的和就约等于

302 * 4.5 = 1359

很接近，数学真是奇妙啊，哈哈哈~

嗯，回到正题，这个题考的是两个东西：

1. 大数乘法
2. 整数动态规划，求最少大数乘法次数的步骤

好的C算法在一般PC上应该能把运算时间控制在0.5秒以内，嗯~

PS：土土地思考，从2^31=2147483648开始算的话：
2^31 * 2^31 = 2^62
2^62 * 2^62 = 2^124
2^124 * 2 = 2^125
2^125 * 2^125 = 2^250
2^250 * 2^250 = 2^500
2^500 * 2^500 = 2^1000
只需要6次大数乘法，嗯，不确保这是最优的分法...不过这么算已经挺快了...

[ Last edited by sudo on 2011-5-26 at 22:13 ]
赞一下(2人) 回复此楼
3楼2011-05-26 21:52:34
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)
★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
微尘、梦想(金币+1): 谢谢交流讨论！ 2011-05-27 15:26:19
引用回帖:
Originally posted by sudo at 2011-05-26 21:52:34:
咳，我突然想到一个好玩的东西...

对于一个数的大指数出来的各个位数，0-9的概率分布趋向于均匀分布~

那么我们可以做大致的估算：

2^1000的位数为

向下取整(1000 * log 2) + 1 = 302 位

对于 ...

这么说的话，这个好玩的东西还有另外一个扩展了：散列码，乘法运算的过程中，除了首位和末位之外，中间的所有位都与因数的位数相关，得出的结果中包含了各种离散的因素，得出的值也必定是均匀分散的。期望值应该也非常接近这样的猜测

这题以乘方来优化的话，乘法次数是少了许多，效率却不见提高许多，软件实现的大数类还是不如硬件geilivable啊……

突然想实现一个补码运算的大数类了
赞一下(2人) 回复此楼
漩涡的中心有一块空地，空空的。
4楼2011-05-26 22:29:58
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
查看全部 15 个回答
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
信息提示
关闭
请填处理意见
关闭