一道旧题目（数学类） - 辕门射虎 - 轩辕春秋文化论坛 20周年


	whws


	白衣伯爵谏议大夫

组别	白衣卿相
级别	左将军
好贴	6
功绩	166
帖子	1325
编号	82141
注册	2006-9-7
家族	云水兰若

#1

发表于 2006-10-25 10:09 资料个人空间短消息只看该作者

一道旧题目（数学类）

这是一位朋友两年前贴出的面试题，要求使用笔算完成，不借助工具书，整个估算过程能在面试时间内完成（十分钟时间），可能会用到高等数学知识。

下面是题目原文：

“只用笔算估算3000！是有多少位的数??需要高等数学的基本常识
什么想用电脑？没关系，如果想编程的话，那就把这个9000多位的数字计算出来吧 ”

我曾经用三种方法作出来过，但是没有一种是理想的。这道题目可以用伽马函数和斯特林渐进公式完成，也可以用平方差公式取整估算。还可以取ln再求导，取不等式两边夹，可以得到结果9128<a<9131。但是，要么是要用到一些冷僻的定理（必须借助工具书），要么就是太繁琐。所以一直不满意。据朋友说，这道题的正解极度简单，还正告我，如果我去面试就faint掉了。但是他没有告诉我正解。郁闷之极。因此贴在这里看看有没有更好的答案。

假定lg2、lg5、ln2、ln5都是已知。因为这在工科里这通常会被当作常数要求记忆。

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	天宫公主 (司徒家的颖颖)


	虞国公主 ★

组别	限制发言用户
级别	大将军
好贴	6
功绩	517
帖子	11552
编号	1037
注册	2004-10-25
来自	天津
家族	司徒实业

#2

发表于 2006-10-25 11:00 资料主页短消息只看该作者

设 D 为 3000! 的位数，[.] 为 Gauss step 函数（[x] = 不大于 x 的最小整数），则

D = [lg 3000!] = [(ln 3000!)/(ln 10)] = [(ln 1 + ln 2 + ... + ln 3000)/(ln 10)]

注意：(1/2)ln 1 + ln 2 + ... + ln 2999 + (1/2) ln 3000 :=: int_1^3000 ln x dx = x ln x - x |_1^3000 = 3000 (ln 3000 - 1) - 1. (Trapeziod approximation).

而且，这个积分估算的误差不大于 ((b-a)^2/12n^2)|f"(x_0)|, 其中 x_0 是 |f"(x_0)| 在有关取值范围的最大值。因此，我们可以通过这个公式去计算误差 < sum_{n=1}^2999 |(ln (n) + ln (n+1))/2 - int_n^{n+1} ln x dx| = sum_n O(1/n^2) 应该比较小（按理说应该搞成误差小于１，不过比较繁琐，需要分很多段考虑。例如 [1,2] 可能硬算误差比什么都好，因为 |f"(x_0)| 那一项在[1,2]上起不了什么作用。真的不行了，前面几项用 Simpson rule 加，后面的再用 Trapeziod rule，然后减去它们之间的差即可。Simpson's rule 的误差是 (b-a)^5/180n^4 |f^(4) (x_0) |. 有那个 1/180 在，对于 [1, x_0], x_0 比较小的时候非常有效）。

故而，D = [lg 3000!] :=: ((int_1^3000 ln x dx)+(1/2) ln 3000)/ln(10).

P.S. 楼上学数学的么？

[ 本帖最后由天宫公主于 2006-10-25 11:15 编辑 ]

[广告] 《精忠报国岳飞传完整版》火热发布


	shadewither

组别	百姓
级别	奋威校尉
功绩	1
帖子	106
编号	78831
注册	2006-8-12

#3

发表于 2006-10-25 17:27 资料短消息只看该作者

QUOTE:

原帖由 whws 于 2006-10-25 10:09 发表
这是一位朋友两年前贴出的面试题，要求使用笔算完成，不借助工具书，整个估算过程能在面试时间内完成（十分钟时间），可能会用到高等数学知识。

下面是题目原文：

“只用笔算估算3000！是有多少位的数??需要高等数学的基本常识
什么想用电脑？没关系，如果想编程的话，那就把这个9000多位的数字计算出来吧”

这个后一半简单

[广告] 《精忠报国岳飞传完整版》火热发布


	whws


	白衣伯爵谏议大夫

组别	白衣卿相
级别	左将军
好贴	6
功绩	166
帖子	1325
编号	82141
注册	2006-9-7
家族	云水兰若

#4

发表于 2006-10-25 19:54 资料个人空间短消息只看该作者

QUOTE:

原帖由 天宫公主 于 2006-10-25 11:00 发表
设 D 为 3000! 的位数，为 Gauss step 函数（ = 不大于 x 的最小整数），则

D = = =

注意：(1/2)ln 1 + ln 2 + ... + ln 2999 + (1/2) ln 3000 :=: int_1^3000 ln x dx = x ln x - x |_1^3000 = 300 ...

的确很简单，而且学过基本编程的人就该想到。我这么久都没能想到，的确太笨了。

我不是学数学的。不过你们提到那些定理及其证明，在网络上很容易搜到，拿来看就是了。

[广告] 真诚支持说岳，携手共创辉煌


	whws


	白衣伯爵谏议大夫

组别	白衣卿相
级别	左将军
好贴	6
功绩	166
帖子	1325
编号	82141
注册	2006-9-7
家族	云水兰若

#5

发表于 2006-10-25 19:54 资料个人空间短消息只看该作者

QUOTE:

原帖由 shadewither 于 2006-10-25 17:27 发表

这个后一半简单

是啊，学过汇编的人，应该都做过类似的题目。

[广告] 真诚支持说岳，携手共创辉煌