2016年11月读书笔记


挑战程序设计竞赛/C++函数速查手册/黑客与画家

挑战程序设计竞赛11.03
今天读了二叉搜索树的实现以及set和map的简单用法。
二叉搜索树实际上就是一颗二叉树,但它有一个特点,就是每个节点左二子的值小于它的值,右儿子的值大于它的值。
由于是一个树形结构,他能高效的进行插入,删除,查找。每次操作时间复杂度都在logn以内。
C++的stl里面有用二叉搜索树实现的set容器,可以很方便地直接调用。
还有map容器。下面是这两个容器的简单用法。

set的基本用法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <cstdio>
#include <set>
//set是一个有序的无重复的容器
//还有可以重复的multiset
using namespace std;

int main()
{
set<int> se;
se.insert(3);
se.insert(5);
se.insert(1);
set<int>::iterator ite;
for(ite=se.begin();ite!=se.end();ite++){
printf("%d ",*ite);
}
printf("\n");

ite=se.find(3);
if(ite==se.end()){
printf("查找3失败\n");
}else{
printf("查找3成功\n");
}
se.erase(1);
for(ite=se.begin();ite!=se.end();ite++){
printf("%d ",*ite);
}
return 0;
}
/*测试结果
1 3 5
查找3成功
3 5
*/

map的基本用法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
int main()
{
map<int , const char* > m;
m.insert(make_pair(10,"tom"));
m.insert(make_pair(30,"dom"));
m[20]="amy";

map<int , const char*>::iterator it;
it=m.find(30);
if(it!=m.end()){
printf("查找30成功\n");
}else{
printf("查找失败\n");
}

for(it=m.begin();it!=m.end();it++){
printf("%d %s\n",it->first,it->second);
}
printf("\n");
m.erase(30);
for(it=m.begin();it!=m.end();it++){
printf("%d %s\n",it->first,it->second);
}

return 0;
}
/*测试结果
查找30成功
10 tom
20 amy
30 dom

10 tom
20 amy
*/

挑战程序设计竞赛11.05
今天读了挑战程序设计竞赛的2.5,介绍了图的一些概念。
图的表示方法,邻接矩阵和邻接表。
邻接矩阵可以简单地建一个二维数组。
邻接表可以这样建造:
vector G[MAX_V];
// 边上有属性的时候
// struct edge{int to,cost;};
// vector G[MAX_V];

s指向t的时候
G[s].push_back(t);

挑战程序设计竞赛11.07
今天读的挑战程序设计竞赛的图的最短路问题,只看了一个dijkstra算法,但没怎么看明白。
又把昨天的bellman-ford算法看了一遍,比昨天理解的又透彻一些。
这两个算法都是单源最短路,就是固定一个起点,然后求这个点到其他所有点的最短距离的意思。
由于固定一个起点,首先应该想到的是先计算靠近它的点,然后往远处求。
所以根据这个思路写出一个递推式:记从起点s到顶点i的最短距离为d[i],
d[i]=min{d[j]+ (顶点j到i的权值)|e=(j,i)∈E }

黑客与画家11.16
今天又读了一部分黑客与画家,作者分析到c,c++,java这样的强类型语言很不好,并且说刚开始让人构思好软件的整个结构是不正确的。然后说语言应该是可以扩展的,例如动态语言变量类型不用提前定义,等用的之后直接用就可以。
我刚看到这个观点是很不认可的,先构思好整个结构怎么可能是不正确的?先把大体的框架写出来,才能保证之后的大方向是正确的啊,之后再给细节和小的模块给于补充就好了。关于语言变量直接用这一点,我只把他认为是他自己的态度,并没有觉得强类型变量不好,反而觉得这样是很严谨的。
但是又往后看看到,人平时思考问题是不可能那么全面完美的,等我们构思好整个框架时,写着写着才突然发现某个地方考虑的很不完善,需要修改,这种情况可能是很多的,那么这时候真的是需要语言有良好的扩展性了。可能是因为我没接触过动态语言的缘故吧,不知道动态语言还是有很多优点的。
黑客与画家11.19
一个人的道德观念应该是独立的,不应该被外界所流行的干扰。
在大众眼里,“黑客”(hacker)就是入侵计算机的人。可是,在程序员眼里,“黑客”指的是优秀程序员。这两个含义其实是相关的。对于程序员来说,“黑客”这个词的字面意思主要就是“精通”,也就是他可以随心所欲地支配计算机。
思想自由(intellectual freedom),指的是自由思考以及表达这种思考的权利。它是《世界人权宣言》第19条规定的一种人权。
黑客对于公民自由是非常敏感的,因为这对他们至关重要。
使用互联网软件,除了软件本身,大多数用户不需要知道别的事情。所有那些乱七八糟、经常变动的东西,都放在服务器端,由精通此道的专业人员维护。所以,大多数时候,你不需要一台全功能的电脑(即本身可以运行软件的电脑)。你所需要的设备只要有键盘、屏幕、浏览器就够了,可能还有无线网卡。这样的设备没准就是指手机。作者的这一预见现在算是实现一部分了吧,但看未来的趋势,以后会实现的更多。
数据不应该禁锢在一台遥远的桌子上的电脑里。

《c/c++函数与算法速查手册》11.21
今天看了同学的《c/c++函数与算法速查手册》,唉手册就是手册啊,需要的时候看就可以,闲着翻了看了看,还是有一些收获的。看了之后又深刻的感受到掌握一些库函数是很有必要的,它能提升我们的效率,节省很多力气。像是快速排序这样的,早就有现成的sort,如果自己去写就费不少力气。
当然,不能完全依赖库函数,对库函数源码进行理解才是最好的。
另外在电脑上的codeblocks试了试conio.h和graphics.h,都不能用,百度了后说没有这两个库。

《黑客与画家》11.25
技术会引起贫富差距的扩大。但是另一个方面,由于技术富人与普通人的生活方式差的小了。
作者认为:现代社会的收入差距扩大是一种健康的信号,一个社会需要有富人,是因为富人在致富的过程中创走出来的东西会让你们不再需要用马匹耕田。

普通话作文草稿11.26
我的家乡
我的家乡是山东省莱芜市,很久以前是从泰安独立出来的,面积挺小的,只有两个区,但是发展还可以。
我从这几个方面介绍一下莱芜吧,分别是莱芜的旅游景点,莱芜特产。

说起旅游景点,我们那里有国家4A级旅游区叫做雪野旅游区,雪野两个字分别是雪花的雪,田野的野。
雪野有一座湖叫做雪野湖,周围还有很多山,有山有水,景色非常漂亮。
这里举行过很多活动,其中一个是国际航空节。第一届航空节的时候我爸带我去看的,各种飞行器的表演给我留下了很深的印象。
另外还一个活动是美利达组织骑行比赛,因为修建了一条环湖公路,所以特别适合这种比赛。我也很喜欢骑行,但是那一次却很遗憾没有到场。

莱芜的特产也有很多,但是有一些比较特殊,并不能直接吃,比如说葱姜蒜就是我们那里的特产,虽然别的地方都有,但是不如我们那里的种植规模大。
每当跟同学开玩笑让带特产的时候,我就说我们那里的特产是葱姜蒜。
当然我们那里不只有这三种特产,还有美味的黄金酥,黄金酥是一种糕点,外面是一层皮,然后里面是馅。跟月饼特别像。

《黑客与画家》11.27
作者介绍了一下自己曾经做的一个过滤垃圾邮件的项目,其中用到贝叶斯公式,我刚开始还想不起来这是什么,然后百度后才发现原来就是这个式子:
P(B|A)=P(A|B)*P(B)/P(A),当时学的时候根本看不到这有什么实际作用,经过了解,原来很多领域对此有应用,这个式子还是挺重要的。
品味是有高低之分的,并不是自己有些时候安慰自己说的那样:我乐意,你有你的选择,我有我的选择。这样的话很多时候是在掩饰自己的心虚,
只想让对方赶紧住嘴。
不同的学科对“美”的认识有着惊人的相似度。一些优秀的原则反复的出现。
把东西做的简单是逼迫你直接面对真正的问题,当你不能用表面的装饰交差时,你就不得不做好真正的本质部分。

黑客与画家11.29

功能决定形式,正像数据决定程序结构。

推动人才成批涌现的最大因素就是,让有天赋的人聚在一起,共同解决某个难题。互相激励比天赋更重要,达·芬奇之所以成为达·芬奇,主要原因不仅仅是他的天赋,更重要的是他生活在当时的佛罗伦萨,而不是米兰。
正好比我做acm,更需要一个好的环境!
这个时代与以往没有任何不同!???

黑客与画家11.30

一种语言是一种思维方式,你越习惯一种语言,你就越习惯那种思维方式。

但是人不应该只用一种思维方式,所以我们也就不应该只用一种语言。

语言是会慢慢进化的,Java已经快要进化到头了???
随着电脑运行速度的提升,一些运行速度不快的语言可能会开始有一席之地。

语言浪费硬件的时间总比浪费程序员的时间要好。

当你设计语言的时候,心里牢牢记住这个目标是有好处的。
学习开车的时候,一个需要记住的原则就是要把车开直,不是通过将车身对齐画在地上的分隔线,而是通过瞄准远处的某个点。
即使你的目标只在几米开外,这样做也是正确的。
我认为,设计编程语言时,我们也应该这样做。
客户对你的软件使用的什么语言并不关心,关心的只是这个功能好不好用。

编程语言不仅仅是技术,也是一种习惯性思维,非常难于改变。
这是有些人不喜欢更换新的语言的原因。
Lisp语言刚设计出来的时候就很强大,接下来的二十年它提高了运行速度。
而那些所谓的主流语言把更快的运行速度作为设计的出发点,然后再用四十多年的时间一步步变得更强大。

黑客与画家12.02

人们真正注意到你的时候,不是第一眼看到你站在那里,而是发现过了这么久你居然还在那里。

为了写出优秀软件,你必须同时具备两种互相冲突的信念。
一方面,你要像初生牛犊一样,对自己的能力信心万丈;另一方面,你又要像历经沧桑的老人一样,对自己的能力抱着怀疑态度。

做数学研究时,你不会只为了方便读者理解而故意选择一种更麻烦的证明方式,你只会选择最直接、最简洁的证明。
我想,一般来说科学研究都是这样。科学观点不需要服从人类工程学(ergonomic)。

你也许不同意“交互式顶层解释器”为软件开发带来便利的说法,但是如果你接受它,同意易于使用的编程语言必须有一个这样的解释器,那么强制声明变量类型的做法就是与这个解释器不兼容,因此结论就是所有的静态类型语言都不易于编程。

!!!作者怎么可以拿一个假设来产生一个结论呢?安利lisp已经快到了让人反感的地步,
一直避重就轻地说lisp好,贬低其他语言,很多作者的结论(关于lisp的)根本是在偷换概念,
作者没掌握好一个度,过之不及啊。