一道趣味算法题（数学题，可以编程求解）。

emacsnw

原帖由 局外人 于 2007-5-2 18:12 发表
n^1000000 如果有 d 个十进制位， 则 n^1000000/10^(d-4)  的整数部分就是前 4 位

用 log 和 pow 计算 d 和上面的这个值就可以了.

不错不错
原题的答案是1000001，它的1000000次方的前4位是2718，用数学方法就可以推出来的，呵呵。
不过楼上的代码求解很漂亮，赞一个。

bGFuZ3Vl

原帖由 emacsnw 于 2007-5-3 13:36 发表


不错不错
原题的答案是1000001，它的1000000次方的前4位是2718，用数学方法就可以推出来的，呵呵。
不过楼上的代码求解很漂亮，赞一个。

You mean it could be done through mathematical induction. Would you like to show how?

ArXoR

原帖由 局外人 于 5/3/07 10:08 发表
用 log 和 pow

[code]
#include <stdio.h>
#include <stdlib.h>
#include <math.h>


int
main (int argc, char **argv)
{
        unsigned long digits;
       
        double N, M, r;
        unsign ...

就差误差分析了, 把判定问题交给浮点数总是不怎么让人放心

ArXoR

原帖由 bGFuZ3Vl 于 5/3/07 13:41 发表


You mean it could be done through mathematical induction. Would you like to show how?

Represent (1000000 + 1)^1000000 in binomial series may help. I think.

emacsnw

原帖由 bGFuZ3Vl 于 2007-5-2 21:41 发表


You mean it could be done through mathematical induction. Would you like to show how?

我们知道自然对数的底数 e = lim_{n\to \infty}(1+1/n)^n
令 n = 1000000，那么1000001^1000000 = (n(1+1/n))^n=n^n(1+1/n)^n
n^n就是(10^6)^1000000，贡献了后面一大把0，因此头四位是由(1+1/n)^n决定的，分析一下e的泰勒展开式就知道(1+1/n)^n和e之间的误差小到可以忽略，因此这个数字的头几位应该是2.71828...

[ 本帖最后由 emacsnw 于 2007-5-2 23:13 编辑 ]

emacsnw

原帖由 ArXoR 于 2007-5-2 22:13 发表


就差误差分析了, 把判定问题交给浮点数总是不怎么让人放心

确实需要误差分析，不过这里问题不大，毕竟只要十进制的头4位数字，log后再exp或者pow求回来的数值应该是在误差允许的范围内的。

局外人

原帖由 emacsnw 于 2007-5-3 14:30 发表



我们知道自然对数的底数 e = lim_{n\to \infty}(1+1/n)^n
令 n = 1000000，那么1000001^1000000 = (n(1+1/n))^n=n^n(1+1/n)^n
n^n就是(10^6)^1000000，贡献了后面一大把0，因此头四位是由(1+1/n)^n决定的 ...

这个做法很狡猾啊，单从题目看，不大容易走上这条路。你要不说，我都不知道 e 的前 4 位是不同的，


e 约为：

2.718281828459045235360287471

1000001^1000000 约为：

2.718280469319376883819717579 E6000000

前 6 位是一样的

[ 本帖最后由 局外人 于 2007-5-3 15:12 编辑 ]

gta

看不懂，学习中