标题: 一道旧题目（数学类） [打印本页]
作者:
whws 时间: 2006-10-25 10:09 标题: 一道旧题目（数学类）
这是一位朋友两年前贴出的面试题，要求使用笔算完成，不借助工具书，整个估算过程能在面试时间内完成（十分钟时间），可能会用到高等数学知识。
下面是题目原文：
“只用笔算估算3000！是有多少位的数??需要高等数学的基本常识
什么想用电脑？没关系，如果想编程的话，那就把这个9000多位的数字计算出来吧 ”
我曾经用三种方法作出来过，但是没有一种是理想的。这道题目可以用伽马函数和斯特林渐进公式完成，也可以用平方差公式取整估算。还可以取ln再求导，取不等式两边夹，可以得到结果9128<a<9131。但是，要么是要用到一些冷僻的定理（必须借助工具书），要么就是太繁琐。所以一直不满意。据朋友说，这道题的正解极度简单，还正告我，如果我去面试就faint掉了。但是他没有告诉我正解。郁闷之极。因此贴在这里看看有没有更好的答案。
假定lg2、lg5、ln2、ln5都是已知。因为这在工科里这通常会被当作常数要求记忆。
作者:
天宫公主 时间: 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 时间: 2006-10-25 17:27
原帖由 whws 于 2006-10-25 10:09 发表
这是一位朋友两年前贴出的面试题，要求使用笔算完成，不借助工具书，整个估算过程能在面试时间内完成（十分钟时间），可能会用到高等数学知识。
下面是题目原文：
“只用笔算估算3000！是有多少位的数??需要高等数学的基本常识
什么想用电脑？没关系，如果想编程的话，那就把这个9000多位的数字计算出来吧”
这个后一半简单
作者:
whws 时间: 2006-10-25 19:54
原帖由 天宫公主 于 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 时间: 2006-10-25 19:54
原帖由 shadewither 于 2006-10-25 17:27 发表
这个后一半简单
是啊，学过汇编的人，应该都做过类似的题目。
| 欢迎光临 轩辕春秋文化论坛 (http://xycq.org.cn/forum/) |
Powered by Discuz! 5.0.0 |