分类目录归档: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主要讲的是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

 

 

 

PyCharm 3.0 发布,提供免费开源版本PyCharm 发布最新的 3.0 版本,该版本新特性详见: http://www.jetbrains.com/pycharm/whatsnew/index.html 该版本最主要的是提供了免费开源的版本,开源版本提供的功能包括: 智能编辑器,支持代码自动完成和分析 自动化代码重构 图形化调试器和单元测试支持 内建版本控制集成等等

 

ZeroVM —— 开源轻量级虚拟化平台ZeroVM是第一个专门为云设计的虚拟机管理程序。当前架构的云是支离破碎的,因为它依赖于一个已经逐步消失的世界(客户端/服务器模型世界)里的虚拟机管理程序来进行设计。因此,我们构建了ZeroVM。

 

RabbitMQ 3.2.0 发布,AMQP 消息服务器基于Erlang的高级消息队列RabbitMQ 3.2.0发布。2013-10-24 之前版本2013-08-15的3.1.5 .遗留产品系列3.0.4,2.8.7 在高级消息队列里,RabbitMQ应该最主流的。此版本新特性包括联合队列,增强策略,消费者优先级,堵塞连接通知,认证失败通知等以及大量Bug修正。

 

WordPress 3.7 正式版发布,6大功能更新WordPress 3.7 已经发布,一起来看看 3.7 的主要更新: 后台小版本自动更新,比如从 3.7 自动升级到 3.7.1,升级后将有邮件通知 增强的密码强度评估,提高网站安全性 提高搜索结果的相关性,根据匹配程度排序结果,而不是发布日期,比如,标题中含有搜索关键词的文章将提前

 

TextMate 2.0 宣布开源以响应 OS X 的免费TextMate 的开发者 MacroMates 在周四 宣布 TextMate 2.0 发布,同时宣布 TextMate 整个项目开源,以响应苹果 OS X 系统的免费。现在可通过 Github 来获取 TextMate 源码。TextMate 采用 GPLv3 许可证。 TextMate是Mac下的著名的文本编辑器软件,与BBedit一起并称苹果机上的emacs和vim。

 

Lime —— 号称 Sublime Text 的开源实现Fredrik Ehnbom用Go语言开发了新代码编译器Lime,号称Sublime Text的开源实现。其兼容Sublime Text的快捷键设置,兼容Textmate的颜色主题及语法定义。

先来一个黄金数列生成函数:

>>> def gold(c=10):
b=a=1
while c>0:
b,a=a,b+a
print(b,b-100,b+100,b-1000,b+1000)
c -=1
>>> gold(30)
1 -99 101 -999 1001
2 -98 102 -998 1002
3 -97 103 -997 1003
5 -95 105 -995 1005
8 -92 108 -992 1008
13 -87 113 -987 1013
21 -79 121 -979 1021
34 -66 134 -966 1034
55 -45 155 -945 1055
89 -11 189 -911 1089
144 44 244 -856 1144
233 133 333 -767 1233
377 277 477 -623 1377
610 510 710 -390 1610
987 887 1087 -13 1987
1597 1497 1697 597 2597
2584 2484 2684 1584 3584
4181 4081 4281 3181 5181
6765 6665 6865 5765 7765
10946 10846 11046 9946 11946
17711 17611 17811 16711 18711
28657 28557 28757 27657 29657
46368 46268 46468 45368 47368
75025 74925 75125 74025 76025
121393 121293 121493 120393 122393
196418 196318 196518 195418 197418
317811 317711 317911 316811 318811
514229 514129 514329 513229 515229
832040 831940 832140 831040 833040
1346269 1346169 1346369 1345269 1347269
>>>

以计算机程序为例子,基督教就是有一个唯一的主进程,该主进程衍生出所有的子进程。子进程要完全相信并听命于主进程,否则总有一天会被主进程惩罚。整个程序系统是从唯一的主进程开始的。
佛教就是,子进程是(因果)循环的,可以去试图了解/沟通父进程,那样就会明了该进程/进程间以及与父进程的一些事情。但佛教不认为有一个唯一的总的主进程。也不知道程序系统怎样开始的。

这两种情况实际环境中都有。即两种宗教都有大量的信仰者。

对于大部分常规程序,更符合第一种,比如windows/unix系统。由唯一的引导程序引导,有主控制程序,如果哪个子程序不听话,就会被关掉(惩罚)。而且windows经常误击,也就是一些良性程序也会突然发生错误,关闭;当然一段时间之后,那个良性程序有可能会复活(某个软件崩溃后,大家是不是重新运行该软件?答案是:是的!)

而现在越来越多的网络系统/服务,更像第二种,比如大多数人无法知道谷歌网站是什么时候开始提供服务的,对很多人来说,谷歌就是一直存在的,然后交互….如果你多了解一点谷歌(搜索机制),那么搜索起来就会更方便/快捷/准确

前面也聊过,python最大的优势,就是能找到自己,并且修改自己的源代码,实现自我升级!

原帖:http://zhuoqiang.me/how-program-find-self.html

程序如何找自己
自我定位很重要,不但是对人,对程序来说也一样。如果能知道自己的路径位置,程序就可以通过相对定位找到身边的资源文件,这对于制作无需安装的绿色软件和各类插件很关键。下面列出几种程序的自我定位方法。

Windows API
Unix 平台
Python
Mac & iOS
Mozilla Gecko
Windows API

可利用 Win32 API GetModuleHandleEx 来取得内存地址所在的程序路径。如果传入可执行文件自身的某个函数地址,那就能获得自己的路径。该方法如下,默认是取自身的路径:

std::wstring get_module_path(void* address=NULL)
{
if (! address) {
address = (void*)(&get_module_path);
}

HMODULE handle = NULL;
BOOL const ret = ::GetModuleHandleExW(
GET_MODULE_HANDLE_EX_FLAG_FROM_ADDRESS,
//|GET_MODULE_HANDLE_EX_FLAG_UNCHANGED_REFCOUNT,
static_cast<wchar_t*>(address),
&handle);

if (ret != 0 && handle != NULL) {
wchar_t path_buffer[MAX_PATH] = {L’’};
DWORD const ret = ::GetModuleFileNameW(handle, path_buffer, MAX_PATH);
// We have to free it
::FreeLibrary(handle);
if (0 != ret) {
return path_buffer;
}
}

return L””; // not found
}
这个方法也能在 DLL 中使用,让动态库也能获取自身的位置,方便插件的编写。

Unix 平台

与 Win32 类似,在 POSIX 中 dladdr 函数也可以获取某个地址所在可执行文件的路径:

std::string get_module_path(void* address=NULL)
{
if (! address) {
address = (void*)(&get_module_path);
}

::Dl_info dl_info;
dl_info.dli_fname = 0;
int const ret = ::dladdr(address, &dl_info);
if (0 != ret && dl_info.dli_fname != NULL) {
return dl_info.dli_fname;
}
return “”;
}
该方法同样能让 so 动态库找到自身的位置,方便插件的编写。

Python

Python 内置变量 __file__ 的值就是脚本文件位置,很方便。不过一旦脚本被 py2exe 这类程序打包后,“ __file__“ 就不准确了。这时就需要用 sys.argv[0] 甚至 sys.executable 变量来取得打包后的程序文件的位置

import imp
import os
import sys
import os.path

def is_frozen():
return (hasattr(sys, “frozen”) or # new py2exe
hasattr(sys, “importers”) # old py2exe
or imp.is_frozen(“__main__”)) # tools/freeze

def get_self_path():
if is_frozen():
return os.path.abspath(sys.executable)
return os.path.abspath(sys.argv[0])
Mac & iOS

Mac 和 iOS 平台上标准的 App 结构都是把可执行文件和资源文件打包在程序束 (bundle) 中,苹果还提供专门的 API 来取得 bundle 的路径,从这点上来说,苹果上的软件都是绿色的。不过如果需要,你还是可以取得自身的路径,

char path[1024];
uint32_t size = sizeof(path);
if (_NSGetExecutablePath(path, &size) == 0) {
printf(“executable path is %sn”, path);
}
else {
printf(“buffer too small; need size %un”, size);
}
这种方法不管是对传统的 Unix 可执行文件或是 Apple 自己标准的 App 都适用。

Mozilla Gecko

Firefox 的扩展都基于 Gecko 架构提供的插件机制。要得到扩展自身的路径应该很方便才是,但实际上并非如此:

Components.utils.import(“resource://gre/modules/AddonManager.jsm”);
AddonManager.getAddonByID(“your@addon.name”, function(addon)
{
var uri = addon.getResourceURI(“relative/path/to/file”);
if (uri instanceof Components.interfaces.nsIFileURL)
{
// get the absolute path to the file inside Your@Addon.name
var absolute_file_path = uri.file.path;
}
});
这里,需要按扩展的名字去 AddonManager 中找出扩展对象,再通过扩展对象取得扩展包内相对位置的文件路径,使用起来不太方便。

其实,Gecko 中有更直接的方法。你可以在 manifest 文件里把需要引用的文件都声明成 resource,所有的 resource 都可以在扩展里通过 URI 名字直接获得路径

resource YOUR-ADDON-LIB path/to/libaddon.so ABI=Linux_x86-gcc3
resource YOUR-ADDON-LIB path/to/addon.dll ABI=WINNT_x86-msvc
const ioService = Cc[“@mozilla.org/network/io-service;1″].getService(Ci.nsIIOService);
var uri = ioService.newURI(‘resource://YOUR-ADDON-LIB’, null, null);
if (uri instanceof Components.interfaces.nsIFileURL) {
var lib = ctypes.open(uri.file.path);
/// …
}
在不同平台上,同一名字还能对应不同的资源文件,方便跨平台扩展的开发。在上面例子中,Win32 平台 js-ctypes 会使用 addon.dll 而 Linux 上则会使用 libaddon.so,这一切都由 gecko 帮着选择定位。我在 chmfox 里正是使用了这个手法。

人工智能,不光无法达到成年人的智能,即使是小孩子(婴幼儿)的智能,在某些方面,也是非常神奇并且难以达到的。

 

比如我们知道小孩子喜欢跟小孩子玩,确切点说,是喜欢跟同龄人以及比自己大的人(孩子)玩。我的女儿11个月大,明显的喜欢跟自己年龄相当,或者比自己大的孩子玩。但是,她是怎么能够判断出那个小孩比她大还是比她小呢? 我对此感到很惊奇,因为6-12个月大的小孩,我都很难快速的分辨出他们的月龄,并因此判断女儿是该喊他们哥哥姐姐还是弟弟妹妹,而女儿总是很快就能判断出来,至少从行为上,看不出有丝毫的犹豫时间。

这就是婴幼儿神奇的能力。我以成年人的思维方式,认为这种判断的程序为:

根据对方与自己的相似性,来判断是否跟他玩,而不是用成年人的思维:先估算年龄,再跟自己的年龄进行比较(婴幼儿本身就没有自己年龄的概念),根据比较结果判断是否跟他玩。

相似性的判断为:

1 外观相似性。如果对方跟自己体型差不多,就可以认为对方跟自己“合适”,当然体型大于自己的,也“合适”。 这是视觉

2 行为相似性。比如11个月的女儿,只会发出简单的“爸爸” “妈妈”等声音,只会做一些简单的动作,如果对方的行为跟自己相似或者还有比自己“复杂”的行为,那么就认为“合适” 这是。视觉和听觉

3 对11个月的女儿来说,她较少能够用触觉和味觉去感觉其它小朋友,顶多就是让她去跟对方握握手。但我观察到他们是有触碰的意愿的。

4 是否闻气味,这个不太确定,据说婴儿的嗅觉也是很灵敏的,只是慢慢长大反而不太敏感了。

可以看到,根据设想,婴幼儿采用的是模糊的匹配方式进行判断。而我,作为一个成年人,是先用精确的判断年龄大小,然后再跟女儿的年纪进行比较运算,这样两步来进行判断的。

 

从HTML文件中抽取正文的简单方案 zt

原帖:
http://www.pythonclub.org/python-files/html-body

英文原帖:
http://ai-depot.com/articles/the-easy-way-to-extract-useful-text-from-arbitrary-html/

 

译者导读:这篇文章主要介绍了从不同类型的HTML文件中抽取出真正有用的正文内容的一种有广泛适应性的方法。其功能类似于CSDN近期推出的“剪影”,能够去除页眉、页脚和侧边栏的无关内容,非常实用。其方法简单有效而又出乎意料,看完后难免大呼原来还可以这样!行文简明易懂,虽然应用了人工神经网络这样的算法,但因为FANN良好的封装性,并不要求读者需要懂得ANN。全文示例以Python代码写成,可读性更佳,具有科普气息,值得一读。

每个人手中都可能有一大堆讨论不同话题的HTML文档。但你真正感兴趣的内容可能隐藏于广告、布局表格或格式标记以及无数链接当中。甚至更糟的是,你希望那些来自菜单、页眉和页脚的文本能够被过滤掉。如果你不想为每种类型的HTML文件分别编写复杂的抽取程序的话,我这里有一个解决方案。

本文讲述如何编写与从大量HTML代码中获取正文内容的简单脚本,这一方法无需知道HTML文件的结构和使用的标签。它能够工作于含有文本内容的所有新闻文章和博客页面……

你想知道统计学和机器学习在挖掘文本方面能够让你省时省力的原因吗?

答案极其简单:使用文本和HTML代码的密度来决定一行文件是否应该输出。(这听起来有点离奇,但它的确有用!)基本的处理工作如下:

  • 一、解析HTML代码并记下处理的字节数。
  • 二、以行或段的形式保存解析输出的文本。
  • 三、统计每一行文本相应的HTML代码的字节数
  • 四、通过计算文本相对于字节数的比率来获取文本密度
  • 五、最后用神经网络来决定这一行是不是正文的一部分。

仅仅通过判断行密度是否高于一个固定的阈值(或者就使用平均值)你就可以获得非常好的结果。但你也可以使用机器学习(这易于实现,简直不值一提)来减少这个系统出现的错误。 现在让我从头开始……

转换HTML为文本

你需要一个文本模式浏览器的核心,它应该已经内建了读取HTML文件和显示原始文本功能。通过重用已有代码,你并不需要把很多时间花在处理无效的XML文件上。 我们将使用Python来完成这个例子,它的htmllib模块可用以解析HTML文件,formatter模块可用以输出格式化的文本。嗯,实现的顶层函数如下:

def extract_text(html):
    # Derive from formatter.AbstractWriter to store paragraphs.
    writer = LineWriter()
    # Default formatter sends commands to our writer.
    formatter = AbstractFormatter(writer)
    # Derive from htmllib.HTMLParser to track parsed bytes.
    parser = TrackingParser(writer, formatter)
    # Give the parser the raw HTML data.
    parser.feed(html)
    parser.close()
    # Filter the paragraphs stored and output them.
    return writer.output()

TrackingParser覆盖了解析标签开始和结束时调用的回调函数,用以给缓冲对象传递当前解析的索引。通常你不得不这样,除非你使用不被推荐的方法——深入调用堆栈去获取执行帧。这个类看起来是这样的:

class TrackingParser(htmllib.HTMLParser):
    """Try to keep accurate pointer of parsing location."""
    def __init__(self, writer, *args):
        htmllib.HTMLParser.__init__(self, *args)
        self.writer = writer
    def parse_starttag(self, i):
        index = htmllib.HTMLParser.parse_starttag(self, i)
        self.writer.index = index
        return index
    def parse_endtag(self, i):
        self.writer.index = i
        return htmllib.HTMLParser.parse_endtag(self, i)

LinWriter的大部分工作都通过调用formatter来完成。如果你要改进或者修改程序,大部分时候其实就是在修改它。我们将在后面讲述怎么为它加上机器学习代码。但你也可以保持它的简单实现,仍然可以得到一个好结果。具体的代码如下:

class Paragraph:
    def __init__(self):
        self.text = ''
        self.bytes = 0
        self.density = 0.0
class LineWriter(formatter.AbstractWriter):
    def __init__(self, *args):
        self.last_index = 0
        self.lines = [Paragraph()]
        formatter.AbstractWriter.__init__(self)
    def send_flowing_data(self, data):
        # Work out the length of this text chunk.
        t = len(data)
        # We've parsed more text, so increment index.
        self.index += t
        # Calculate the number of bytes since last time.
        b = self.index - self.last_index
        self.last_index = self.index
        # Accumulate this information in current line.
        l = self.lines[-1]
        l.text += data
        l.bytes += b
    def send_paragraph(self, blankline):
        """Create a new paragraph if necessary."""
        if self.lines[-1].text == '':
            return
        self.lines[-1].text += 'n' * (blankline+1)
        self.lines[-1].bytes += 2 * (blankline+1)
        self.lines.append(Writer.Paragraph())
    def send_literal_data(self, data):
        self.send_flowing_data(data)
    def send_line_break(self):
        self.send_paragraph(0)

这里代码还没有做输出部分,它只是聚合数据。现在我们有一系列的文字段(用数组保存),以及它们的长度和生成它们所需要的HTML的大概字节数。现在让我们来看看统计学带来了什么。

数据分析

幸运的是,数据里总是存在一些模式。从下面的原始输出你可以发现有些文本需要大量的HTML来编码,特别是标题、侧边栏、页眉和页脚。

虽然HTML字节数的峰值多次出现,但大部分仍然低于平均值;我们也可以看到在大部分低HTML字节数的字段中,文本输出却相当高。通过计算文本与HTML字节数的比率(即密度)可以让我们更容易明白它们之间的关系:

密度值图更加清晰地表达了正文的密度更高,这是我们的工作的事实依据。

过滤文本行

过滤文本行的最简单方法是通过与一个阈值(如50%或者平均值)比较密度值。下面来完成LineWriter类:

    def compute_density(self):
        """Calculate the density for each line, and the average."""
        total = 0.0
        for l in self.lines:
            l.density = len(l.text) / float(l.bytes)
            total += l.density
        # Store for optional use by the neural network.
        self.average = total / float(len(self.lines))
    def output(self):
        """Return a string with the useless lines filtered out."""
        self.compute_density()
        output = StringIO.StringIO()
        for l in self.lines:
            # Check density against threshold.
            # Custom filter extensions go here.
           if l.density > 0.5:
                output.write(l.text)
        return output.getvalue()

这个粗糙的过滤器能够获取大部分正确的文本行。只要页眉、页脚和侧边栏文本并不非常长,那么所有的这些都会被剔除。然而,它仍然会输出比较长的版本声明、注释和对其它故事的概述;在图片和广告周边的比较短小的文本,却被过滤掉了。 要解决这个问题,我们需要更复杂些的启发式过滤器。为了节省手工计算需要花费的无数时间,我们将利用机器学习来处理每一文本行的信息,以找出对我们有用的模式。

监督式机器学习


这是一个标识文本行是否为正文的接口界面: 所谓的监督式学习就是为算法提供学习的例子。在这个案例中,我们给定一系列已经由人标识好的文档——我们知道哪一行必须输出或者过滤掉。我们用使用一个简单的神经网络作为感知器,它接受浮点输入并通过“神经元”间的加权连接过滤信息,然后输后另一个浮点数。大体来说,神经元数量和层数将影响获取最优解的能力。我们的原型将分别使用单层感知器(SLP)和多层感知器(MLP)模型。 我们需要找些数据来供机器学习。之前的LineWriter.output()函数正好派上用场,它使我们能够一次处理所有文本行并作出决定哪些文本行应该输出的全局结策。从直觉和经验中我们发现下面的几条原则可用于决定如何过滤文本行:

  • 当前行的密度
  • 当前行的HTML字节数
  • 当前行的输出文本长度
  • 前一行的这三个值
  • 后一行的这三个值

我们可以利用FANN的Python接口来实现,FANN是Fast Artificial Neural NetWork库的简称。基本的学习代码如下:

from pyfann import fann, libfann
# This creates a new single-layer perceptron with 1 output and 3 inputs.
obj = libfann.fann_create_standard_array(2, (3, 1))
ann = fann.fann_class(obj)
# Load the data we described above.
patterns = fann.read_train_from_file('training.txt')
ann.train_on_data(patterns, 1000, 1, 0.0)
# Then test it with different data.
for datin, datout in validation_data:
    result = ann.run(datin)
    print 'Got:', result, ' Expected:', datout

尝试不同的数据和不同的网络结构是比较机械的过程。不要使用太多的神经元和使用太好的文本集合来训练(过拟合),相反地应当尝试解决足够多的问题。使用不同的行数(1L-3L)和每一行不同的属性(1A-3A)得到的结果如下:

有趣的是作为一个猜测的固定阈值,0.5的表现非常好(看第一列)。学习算法并不能仅仅通过比较密度来找出更佳的方案(第二列)。使用三个属性,下一个 SLP比前两都好,但它引入了更多的假阴性。使用多行文本也增进了性能(第四列),最后使用更复杂的神经网络结构比所有的结果都要更好,在文本行过滤中减少了80%错误。 注意:你能够调整误差计算,以给假阳性比假阴性更多的惩罚(宁缺勿滥的策略)。

结论

从任意HTML文件中抽取正文无需编写针对文件编写特定的抽取程序,使用统计学就能获得令人惊讶的效果,而机器学习能让它做得更好。通过调整阈值,你能够避免出现鱼目混珠的情况。它的表现相当好,因为在神经网络判断错误的地方,甚至人类也难以判定它是否为正文。 现在需要思考的问题是用这些“干净”的正文内容做什么应用好呢?