分类目录归档:airoot

关于开高次方的算法《天才与锻炼》-华罗庚 zt

关于开高次方的算法《天才与锻炼》-华罗庚
天才与锻炼

——从沙昆塔拉快速计算所想到的轰动听闻的消息
提问者写下一个201位的 数:916,748,679,200,391,580,986,609,275,
853,801,624,831,066,801,443,086,224,071,265,164,279,346,570,
408,670,965,932,792,057,674,808,067,900,227,830,163,549,248,
523,803,357,453,169,351,119,035,965,775,473,400,756,816,883,
056,208,210,161,291,328,455,648,057,801,588,067,711

解答者马上回答:这数的23次方根等于9位数546,372,891.

《环球》杂志的一篇文章中是这样说的(请参阅《环球》1982年第3期《胜过电子计
算机的人》一文):印度有一位37岁的妇女沙昆塔拉在计算这道题时速度超过了一台最
先进的电子计算机.这台在美国得过奖的最现代化、最尖端的产品Univac 1180型电子计
算机在算这道题时,要先馈入近2万个指令和数字单元,然后才能开始计算.它整整用了
一分钟时间才算出结果.而沙昆塔拉在教授在黑板上用了 4分钟写出这个201位数后,仅
用50秒钟就算出了以上的答案.美国报纸称她为数学魔术师,轰动一时!文章末尾还神
秘地说,在她快生孩子的一个星期,她的计算能力出了问题.
面对这样的问题怎么办?

看到上述消息,可能有以下几种态度:一是惊叹,望尘莫及,钦佩之至,钦佩之余
也就罢了.二是不屑一顾,我是高等数学专家,岂能为这些区 区计算而浪费精力.三是
我掌握着快速电子计算机,软件有千千万,她一次胜了我算个啥!老实说,有上述这些
思想是会妨碍进步的.第一种态度是没出息,不想和高手较量较量. 第二种态度是自命
不凡.实际上连计算也怕的人,能在高等数学上成为权威吗?即使能成,也是“下笔虽
有千言,胸中实无一策”,瞧不起应用,又对应用一无所能 的人.第三种是固步自封,
不想做机器的主人.动脑筋是推进科学发展的动力之一,而勤奋、有机会就锻炼是增长
我们能耐的好方法.人寿几何!我并不是说碰到所有的问题都想,而是说要经常动脑筋
,来考验自己.

在我们见到这问题的时候,首先发现文章中答数的倒数第二位错了,其次我们用普
通的计算器(Sharp 506)可以在20秒内给出答数.那位教授在黑板上写下那个201位数用
了4分钟,实际上在他写出8个数字后,我们就可算出答数了.所以说,沙昆塔拉以 50″
对1′胜了Univac 1180,而我们用Sharp 506小计算器以-3′40″胜了沙昆塔拉的50″.
但我们所靠的不是天才,而是普通人都能学会的方法.让我从头说起吧!
从开立方说起

文章中提到,沙昆塔拉在计算开方时,经常能纠正人们提出的问题,指出题目出错
了,可见他们是共同约定开方是开得尽的.现在我们也做这样的约定,即开方的答数都
是整数.

我国有一位少年,能在一分钟内开6位数的立方.少年能想得出这个方法是值得称道
的,但美中不足之处在于他没有把方法讲出来,因而搞得神秘化了.当然也考试了人们
,为什么少年能想得出的方法,一些成年人就想不出来,反而推波助澜造成过分的宣扬?

这问题对我是一个偶遇:在飞机上我的一位助手借了邻座一位香港同胞的杂志看,
我从旁看到一个数59,319,希望求这数的立方根.我脱口而出答数是 39.他问为什么,
我说,前二位不是说明答数的首位是3吗?尾数是9不是说明答数的末位应当是9吗?因
此答数不该是39吗?

然后,我告诉他,我的完整想法是:把六位数开立方,从前三位决定答数的第一位
,答数的第二位根据原数的末位而定:2、 8互换,3、7互换,其它照旧(这是因为1、2
、3、4、5、6、7、8、9立方的末位分别为1、8、7、4、5、6、3、2、9).例如314,432
的立方根是68,前三位决定6,末位是2,它决定答数的末位是8.

沙昆塔拉可以脱口而出地回答188,132,517的立方根是573.当然188决定了首位5
,末位7决定了3,但读者试想一下,中间的7怎样算?

归纳起来可以看出有两个方法:一个由头到尾,一个由尾到头.

习题:求90,224,199的五次方根.
我们怎样看出答数倒数第二位是错的

这一点比较难些,要运用一个结果:即a23的最后两位数和a3的最后两位数是完全
相同的.

913的最后两位数是71而不是11,而713的最后两位数才是11,因此答数中的9应当
改为7.先不管出现这个差错的原因是什么,我们这里已经做了一个很好的习题.想不到
竟是Univac1180把题目出错了,这事我们后面再讲它.

附记 我们来证明a23的最后两位数和a3的最后两位数相同.当a=2或5时,容易直接
验算.今假定a不能被2和5除尽,我们只要证明a20的末两位是01就够了.首先因a是奇数
,a2-1总能被8除尽,所以a20-1当然也能被8除尽.其次,因a4-1=(a-1)(a+1)[(a-2)(a+
2)+5],a不是5的倍数,所以a-2,a-1,a+1,a+2中肯定有一个是5的倍数.即b=a4-1是5
的倍数,而a20-1=(b+1)5-1=b5+5b4+10b3+10b2+5b. 因而a20-1是25的倍数.从而a20-1
是100的倍数.具备些数论知识的人也可从费尔马定理推出来.
我们怎样算

我们用的原则是:如果解答是L位整数,我们只要用前L位(有时只要L-1位)或后L位就够
了.用后L位的方法见附录二,先说前一方法.以前

当那位教授说要开201位数的23方时,以23除201余17,就能预测答数是9位数.当教授写
到第六、七位时,我们就在Sharp 506上按这六位和七位数,乘以1016,然后按开方钮
算出

(9.16748×1016)1/23=5.46372873,

(9.167486×1016)1/23=5.46372892,

这样我们定出了答数的前七位:5,463,728,后二位已由上节的方法决定了,因
此答数应该是546,372,871.其实,更进一步考虑,只需利用这个201位数的前八位数
字就能在计算器上得到它的23次方根(证明见下面的附记):

但不幸的是,把这个数乘23次方,结果与原来给的数不相符(见附录一).与原题比
较,发现原题不但尾巴错了,而且在第八和第九位之间少 了一个6.竟想不到Univac
1180把题目出错了,也许是出题的人故意这样做的.为什么沙昆塔拉这次没能发现这个
错误?看来她可能也是根据前八位算出了结果,而没对解答进行验算.

我们的习题没有白做,答数错了我们发现了,连题目出错了我们也纠正了.

结论是:在教授写到91,674,867时,我们在计算器上按上这八个数字。再乘1016,然
后按钮开23方就可算出答案,总共约用20″就够了,也就是比那个教授写完这个数还要
快3分40秒,比沙昆塔拉快了4分半钟.

既然已经知道答数是九位数,或者说在要求答数有九位有效数字时,我们就只需把
前八位或九位数字输入计算机就够了,而无需把201位数全部输入机器,进行一些多余
的计算.

附记 以a表示那个201位数,b也表示一个201位数,它的前L位与a相同,后面各位都是
零.由中值公式,可知存在一个ξ(b<ξ<a)使

当取L=8时,上式小于1/2,由b1/23的前九位(第十位四舍五入)就可给出a1/23.
虚构

下面讲一个虚构的故事,在沙昆塔拉计算表演后,有一天教授要给学生们出一道计
算题.一位助手取来了题目.是一个871位数开97方,要求答案有 9位有效数字.教授开始
在黑板上抄这个 数:456,378,192,765,431,892,634,578,932,246,653,
811,594,667,891,992,354,467,768,892,…… 当抄到二百多位后,教授的手
已经发酸了.“唉!”他叹了一口气,把举着的手放下甩了一下.这时一位学生噗嗤一声
笑了起来,对教授说,当您写出八位数字后, 我已把答案算出来了,它是588,415,
036.那位助手也跟着笑了.他说,本来后面这些数字是随便写的,它们并不影响答数.这
时教授恍然大悟,“哈 哈,我常给你们讲有效数字,现在我却把这个概念忘了.”
多余的话

我不否认沙昆塔拉这样的计算才能.对我来说,不要说运算了,就是记忆一个六、
七位数都记不住.但我总觉得多讲科学化比多讲神秘化好些, 科学化的东西学得会,神
秘化的东西学不会,故意神秘化就更不好了.有时传播神秘化的东西比传播科学更容易
些.在科学落后的地方,一些简单的问题就能迷惑 人.在科学进步的地方,一些较复杂
的问题也能迷惑人.看看沙昆塔拉能在一个科学发达的国家引起轰动,就知道我们该多
么警惕了,该多么珍视在实践中考验过的 科学成果了,该多么慎重地对待一些未到实
践中去过而夸夸其谈的科学能人了.

同时也可以看到,手中拿了最先进的科学工具,由于疏忽或漫不经心而造成的教训
.现代计算工具能计算得很快很准,但也有一个缺点,一旦算 错了,不容易检查出来.
对于计算象201位数字开23次方这类的问题——多少属于数学游戏性质的问题,算错了
无所谓,而对在实际运用中的问题算错了就不是玩的.“二万条指令”出错的可能性多
了,而在演算过程中想法少用或不用计算机演算,检查起来就不那么难了.这说明人应
该是机器的主人,而不是机器的奴隶. 至于大算一阵吓唬人的情况就更不值一提了.这
里我们还可以看到基本功训练的重要性.如果基本功较差,那么就是使用大型计算机来
演算201 位数开23次方也要1分多钟才能算完.而有了很好的基本功,就是用小计算器也
能花比1分钟少的时间算出来.

这是一篇可写可不写的文章,我之所以写出的原因,在于我从沙昆塔拉这件事中得
到了启发,受到教育,我想,这些也许对旁人也会是有用的.

 

你也可以是“中国雨人-周玮”

妙算16位数的开14次方,是不是很神奇? 不用羡慕嫉妒恨,你也可以的!

任意给16位数字,然后记住下面的速算表,按照前3个数字在表里查找,把对应的三位数字报出来就行了!

100 ==>> 13.9
101 ==>> 13.9
112 ==>> 14.0
123 ==>> 14.1
136 ==>> 14.2
150 ==>> 14.3
165 ==>> 14.4
182 ==>> 14.5
200 ==>> 14.6
221 ==>> 14.7
242 ==>> 14.8
266 ==>> 14.9
292 ==>> 15.0
321 ==>> 15.1
352 ==>> 15.2
386 ==>> 15.3
422 ==>> 15.4
463 ==>> 15.5
506 ==>> 15.6
553 ==>> 15.7
605 ==>> 15.8
661 ==>> 15.9
721 ==>> 16.0
787 ==>> 16.1
858 ==>> 16.2
935 ==>> 16.3

比如任意一个数:576(12345678901234)后半部为了显著告诉大家是14位数,那么它的14次方为15.7

抱歉,做完才发现咱们这个是17位数的开14次方….超过手指头的天马很容易弄错,那我们再来16位数字的:

10 ==>> 11.8
11 ==>> 11.9
12 ==>> 11.9
13 ==>> 12.0
15 ==>> 12.1
17 ==>> 12.2
19 ==>> 12.3
21 ==>> 12.4
23 ==>> 12.5
26 ==>> 12.6
29 ==>> 12.7
32 ==>> 12.8
36 ==>> 12.9
40 ==>> 13.0
44 ==>> 13.1
49 ==>> 13.2
55 ==>> 13.3
61 ==>> 13.4
67 ==>> 13.5
75 ==>> 13.6
83 ==>> 13.7
91 ==>> 13.8

因此16位的更简单,只要看头2个数字,就能对照表查出结果!

比如 用我们常用的电话号码开头,写一串16位数字:

13(01234567891234),查表得知结果为12.0 !乌拉,新的中国雨人诞生啦!

查的时候,如果落在中间的,比如90,落在83和91之间,那么取上面一档,也就是83对应的13.7

灵感见这里:

http://blog.sina.com.cn/s/blog_474068790102eco7.html

源码见这里:

#include <iostream>
#include <math.h>
#include <iomanip>
using namespace std;

int main()
{
float tmp;
int x=0,y=0;
for (int i =100;i<1000;i++)

{
tmp=pow(i,1.0/14);
x=tmp*100;
if (x>y) {
cout << fixed << setprecision(1);
cout << i << ” ==>> ” << tmp*10 << endl;
y=x;
}}

y=0;
for (int i =10;i<100;i++)

{
tmp=pow(i,1.0/14);
x=tmp*100;
if (x>y) {
cout << fixed << setprecision(1);
cout << i << ” ==>> ” << tmp*10 << endl;
y=x;
}}

return 0;

}

思路就是,一个大数N的X次开方,首先可以截断X以及X的(x)倍数位,这样大数开方,就变成短数N的开方再乘以x个10 。比如 13(01234567891234) 就变成了求13的14次方根再乘以10 !

大家记住这个表吧:

100 ==>> 13.9
101 ==>> 13.9
112 ==>> 14.0
123 ==>> 14.1
136 ==>> 14.2
150 ==>> 14.3
165 ==>> 14.4
182 ==>> 14.5
200 ==>> 14.6
221 ==>> 14.7
242 ==>> 14.8
266 ==>> 14.9
292 ==>> 15.0
321 ==>> 15.1
352 ==>> 15.2
386 ==>> 15.3
422 ==>> 15.4
463 ==>> 15.5
506 ==>> 15.6
553 ==>> 15.7
605 ==>> 15.8
661 ==>> 15.9
721 ==>> 16.0
787 ==>> 16.1
858 ==>> 16.2
935 ==>> 16.3
10 ==>> 11.8
11 ==>> 11.9
12 ==>> 11.9
13 ==>> 12.0
15 ==>> 12.1
17 ==>> 12.2
19 ==>> 12.3
21 ==>> 12.4
23 ==>> 12.5
26 ==>> 12.6
29 ==>> 12.7
32 ==>> 12.8
36 ==>> 12.9
40 ==>> 13.0
44 ==>> 13.1
49 ==>> 13.2
55 ==>> 13.3
61 ==>> 13.4
67 ==>> 13.5
75 ==>> 13.6
83 ==>> 13.7
91 ==>> 13.8

 

最全的是这个,15/16/17位数字的14次开方速算表(15位的不太精确):

1 ==>> 10.0
2 ==>> 10.5
3 ==>> 10.8
4 ==>> 11.0
5 ==>> 11.2
6 ==>> 11.4
7 ==>> 11.5
8 ==>> 11.6
10 ==>> 11.8
11 ==>> 11.9
12 ==>> 11.9
13 ==>> 12.0
15 ==>> 12.1
17 ==>> 12.2
19 ==>> 12.3
21 ==>> 12.4
23 ==>> 12.5
26 ==>> 12.6
29 ==>> 12.7
32 ==>> 12.8
36 ==>> 12.9
40 ==>> 13.0
44 ==>> 13.1
49 ==>> 13.2
55 ==>> 13.3
61 ==>> 13.4
67 ==>> 13.5
75 ==>> 13.6
83 ==>> 13.7
91 ==>> 13.8
101 ==>> 13.9
112 ==>> 14.0
123 ==>> 14.1
136 ==>> 14.2
150 ==>> 14.3
165 ==>> 14.4
182 ==>> 14.5
200 ==>> 14.6
221 ==>> 14.7
242 ==>> 14.8
266 ==>> 14.9
292 ==>> 15.0
321 ==>> 15.1
352 ==>> 15.2
386 ==>> 15.3
422 ==>> 15.4
463 ==>> 15.5
506 ==>> 15.6
553 ==>> 15.7
605 ==>> 15.8
661 ==>> 15.9
721 ==>> 16.0
787 ==>> 16.1
858 ==>> 16.2
935 ==>> 16.3

 

2014.4.3日补充:

关于第三题,那个128 乘以 (3.2的13次方根) 再乘以10的题目,我一直没想明白怎么算,因为他的结果是1400左右,这样模糊的数字,掩盖了其中的运算细节,让人不容易猜透。

不过天马想到一种速算方法了,思路就是:

把128 乘到方根里面去,然后再开方!

细节就是:128=1.28×10^2 =(1.28^13) 开13次方根 × 100

而13次方根,我也可以拿出一张速算表,反推1.28 ,得到一个值x=25,我先用计算器的出来了。

然后

x 乘以3.2=800,再查表,800对应14.0这样答案是1400附近

 

上面有点问题,看来要拆成0.128×1000 ,查0.128的13次方根,再乘以3.2,查表出1.4左右,更合理!

 

 

计算概率 期中考试

首先很高兴,终于考试过了,10题全过,15分全拿!
其次,过程真的很悲催,让我说出来感觉会舒服点!

碰到如下问题:
1 看不到start开始按钮
解决方法:详细看帮助,修改internet里的cookie,jave script等,并换用360 /ie /搜狐等多个浏览器,最后竟然能找到了

2 点了start按钮后,没有出试卷
解决方法:又是一阵乱忙,后来又专门装了google浏览器,没解决。最后是按照帮助里的方法,手动传文件,拿字符串,然后输入链接搞定的

3 做题,发现提交后显示编译错误
解决方法:用最简单的test程序测试,还是编译错误。换编码,换浏览器….都没解决。大约用了2天都每没搞定,我一度差点放弃,想不要期中考试的分数了。
到了最后一天,终于想起来联系助教了,加qq。在等待qq验证通过的时间里,我尝试了用提交里的上面一个按钮(上面的是提交output,下面的是提交附件,前面习题我都是提交附件的),结果就通过了……

4 一些题目有一些歧义
解决方法:根据给出的程序,可以大致了解清楚

5 有个算勾股定理的,要求输出不重复,可真难坏了我。不重复就是例如输出 3×3+4×4 =5×5 之后,就不输出 4×4 +3×3=5×5了
解决方法:一度想用反向,即用等号后面的5来界定,不过这样循环起来可就复杂了,另外后来也发现5对应的等式可能并不唯一。
后来仔细看给出的程序,发现给定的循环已经用巧妙的方法解决了这个问题,只要专心写勾股定理部分的代码就行了!

6 最后一题,有点想不明白为什么输入多一个空行,程序该怎么写呢?
解决方法:实在想不明白…..后来用最简单的输入,发现程序就过了。原来是我想多了……

总共我是用足了3天72个小时,整个考试至少有3天熬夜(没开考之前是为了看到题目),至少2天超过半夜12点…..另外我发现现在半夜的脑子不行了,看题看半天都还晕晕的…..

另外我是用记事本和vi写程序的,所以有些地方格式就没有写的太标准。先在win上用记事本写出来,然后到另一台服务器用g++编译测试,中间用vi进行修改,通过后再copy回记事本,然后再提交……
我是两台win的机器,所以代码就用金山网盘存储…..,

计算概率期中考试留念
skywalk
2013.11.27

近期正在学习李戈的计算概论A

计算概论A主要讲的是C++编程。 跟python比起来,c++细节很多,很多python里已经弄好的东西,在c++里都要自己编程搞定,怪不得说python代码要比c++的简洁很多。

下面是几个习题:

奇数求和:

#include <iostream>
using namespace std;
int main(){
int m,n,result=0;
cin >> m >>n;
while (m <=n){
if (m%2 ==1)
result +=m;
m++;
}
cout << result << endl;
return 0;

}

一句话中的元音字母个数统计:

#include <iostream>
using namespace std;

int main() {
char s[80]=””;
int ca,ce,ci,co,cu;
cin.getline(s,80);
ca=ce=ci=co=cu=0;
for (int i =0;i <80;i++)
{
if (s[i]==’a’)
ca++;
else if (s[i]==’e’)
ce++;
else if (s[i]==’i’)
ci++;
else if (s[i]==’o’)
co++;
else if (s[i]==’u’)
cu++;
else if (s[i]==’’)
break;
}

cout << ca << ” ” << ce << ” ” << ci << ” ” << co << ” ” << cu << endl;

return 0;
}

 

课程地址:

https://class.coursera.org/pkuic-001/class/index