读《绿野仙踪》有感

三(1)班 陈一凡

我最近看了一本书叫《绿野仙踪》，这本书的作者是:莱曼·弗兰克·鲍姆 . 《绿野仙踪》以虚构的奥兹国为背景，讲述了美国堪萨斯州的小姑娘多萝茜被龙卷风卷到了一个叫孟奇金的地方，好心的女巫指点她到翡翠城去找奥兹国大术士帮忙送她回家。路上，她先后遇到了稻草人-----他需要一副脑子；铁皮樵夫-----他需要一颗心；胆小狮子-----他需要胆量。他们结伴而行，互相鼓励、互相帮助，克服了一个又一个困难，终于来到了翡翠城。由于他们的出色的表现，大术士帮助他们实现各自的愿望，稻草人得到了一副脑子；铁皮樵夫得到了一颗心；胆小狮子得到了胆量，多萝茜也如愿，带着小狗托托回到了家乡，回到了亲人身边.

在读书的过程中，多萝茜占据了我的思想，多萝茜似乎就是我好朋友，我的心也随着多萝茜的经历不时地欢喜、紧张、惊异、难过。她那勇敢的表现、善良的心地、坚强的意志，让我感到自己很渺小，为自己的懦弱而很不好意思。因为以前，我一看见狗就害怕。有时我会问自己：“如果我是多萝茜，我会不会像多萝茜一样勇敢地克服重重困难、并帮助其他人呢？”看完这部童话后，我决心像多萝茜一样鼓足勇气，用不懈地追求和奋斗的精神来面对各种困难，克服学习上、生活上的一切不利因素，勇敢地挑战自我，我相信我一定能做到！

我喜欢《绿野仙踪》，它让我有了好朋友---多萝茜；我喜欢《绿野仙踪》，它给我带来快乐；我喜欢《绿野仙踪》，它给我带来勇气；我喜欢《绿野仙踪》！

读《童年》有感

三(1)班 蒋馨怡

读了《童年》这本书，使我受益匪浅。和高尔基比童年，我们今天是多么幸

福啊。

高尔基出生在一个木工家庭，5岁时，父亲病故了，他的生活更加艰苦了，

他和妈妈就住在外祖父家里。由于家境贫困，他上学只好穿母亲的皮鞋，外祖母

的外套，黄色的衣衫和补丁裤子。 高尔基这样一身不协调的装束， 都引起同学

们的嘲笑。和高尔基相比，我们现在穿的全是自己的新衣服，想到这儿，我不禁

有些惭愧。尽管我们有这么好的条件，却生在福中不知福，常常挑三拣四，有的

衣服穿的时间长了就不愿意再穿。

高尔基为了上学，只得去捡垃圾换钱。每到不上学的日子，他就早早起来，

背着一个大布袋，走街串巷，捡一些破布头、烂纸片卖给废品加工厂。运气好才

能有半个卢布的收入，如果运气不好呢，高尔基上学的事就没了着落。再想想我

们，我们现在什么也不用操心，过着衣来伸手，饭来张口的好日子，相比之下，

我们有什么理由不珍惜自己幸福的生活，有什么理由不好好学习呢？捡垃圾换来

的钱成了高尔基的学费来源，但学校里那些有钱人的孩子并不理解高尔基的行

为，反而去嘲笑他，说他身上有臭味，我觉得并不是高尔基的身上有臭味，而是

那些有钱人的孩子故意嘲笑高尔基，他们才显得很臭。高尔基把别人的嘲笑变成

催促自己努力学习的动力。他发奋学习，刻苦读书，终于取得优异的成绩，受到

了同学们的喜爱和敬重。

我合书沉思，不仅思绪万千。与高尔基的童年比起来，我们是多么幸福，又

是多么奢侈呀。我们应该向高尔基学习，不管在多么恶劣的环境下，都要好好学

习，努力奋斗，朝着美好的未来不断前进。

读《笑猫日记之幸福的鸭子》有感

三(1)班 刘单词

读了《笑猫日记之幸福的鸭子》我觉得我收获最大的是快乐！和她们的生活

比起来，我觉得自己并没有他们生活的快乐！

它主要讲的是：这个暑假，“笑猫”和马小跳他们一道，来到了乡下张达外

婆的家。我们见到了巨人阿空、腊肠狗拖拖，和一只名叫麻花儿的女鸭子。麻花

儿有一双善于发现的眼睛和一颗容易被感动的心，她心中的幸福仿佛没有边际。

听着麻花儿像打饱嗝儿一样的快乐歌声，我们每个人心中的幸福，都在这个荷花

盛开的夏天，慢慢长大......

其中有一句话是我最喜欢的：不是所有的心都怀有思念，心中有思念也是一

种幸福。这是麻花儿讲过最经典的一句话。这个片段是我最喜欢的：“冰镇人”

游戏的比赛结果出来了：马小跳凭超长的毅力获得第一名，唐飞靠抗寒的脂肪获

得第二名，张达凭强壮的身体获得第三名。

我最喜欢的人物是：笑猫。因为我觉得猫会笑是不可思议的事情。它会微笑、

狂笑、冷笑、苦笑、嘲笑、狞笑和皮笑肉不笑。更加不可思议的事情是：它跳过

75片荷叶而且只跳了九次就成功了真棒！这本书让我明白了：幸福人人都可以

拥有只看你怎么对待它！如果你不好好对待那就是你的错，幸福来之不易，我们

应该好好珍惜幸福！比起那些在地震中失去亲人的孩子，我想我们的关心就是他

们幸福的来源！ 幸福，是偎依在妈妈温暖怀抱里的温馨； 幸福，是依靠在恋人

宽阔肩膀上的甜蜜；幸福，是抚摸儿女细嫩皮肤的慈爱；幸福，是注视父母沧桑

面庞的敬意。幸福是什么？幸福是一个谜，你让一千个人来回答，就会有一千种

答案。

读《西游记》有感

三(1)班 郭进远

我第三次读完这本重重的《西游记》时，心里有了不少的感触。 第一次时，

我觉得孙悟空很厉害，很会打架，会变许多样子；唐僧很无能；猪八戒像一只懒

“虫”；而沙和尚则是一个可有可无的角色。 第二次，我就觉得孙悟空很可爱；

唐僧非常的傻；猪八戒是一只傻呆呆的东西；而沙和尚则是一个忠心耿耿的徒弟。

而这一次，觉得孙悟空非常的机灵，且也非常的忠心；唐僧非常的善良、朴实而

又显得仁慈；猪八戒傻得可爱；沙和尚则给人一种忠诚而又老实的印象。 在《西

游记》中共有九九八十一重考验，最后，他们师徒四人经历了千辛万苦取得了真

经。 《西游记》的故事告诉我们一些道理：任何事一开始总是非常艰难的，但

只要能树立信心和勇气，经过努力，相信可以取得成功的！也就印证了一句老话：

万事开头难。 一开始只要坚持住了，经过不懈的努力，相信不久以后，成功一

定是归你所有的！ 当我翻开四大名著之一的《西游记》故事时，立刻被它吸引

住了。故事中倔强正直、机智勇敢的孙悟空，好吃懒做的猪八戒，任劳任怨的沙

僧和正直单纯的唐僧都被作者刻画得栩栩如生。这本书主要讲述了唐僧师徒四人

去西天取经的神话故事。这一路上，他们翻火焰山、打白骨精，历经了千难万险，

战胜了一个又一个妖魔鬼怪的阻挠，终于取到了真经成了仙。这本书通过这些故

事，体现出孙悟空不达目的不罢休的追求精神。这个故事深刻地告诉了我们正义

是一定会战胜邪恶的，因为真理永远存在，做每一件事情都要不达目的不罢休，

绝对不能气馁，这种精神正是我们青少年所需要的。而且，好吃懒做也是不行的，

只有机智灵敏、英勇果断才能事半功倍。我们在学习时，或者在生活中不应该遇

到一点挫折和困难就放弃，挫折和困难是可以克服的，动动脑筋，努力一把，咬

咬牙不就过去了吗？一旦战胜了困难和挫折，那胜利还会远吗？

读《三国演义》有感

三(1)班 高敏

我读了一本书，书名为《三国演义》，作者：罗贯中。

《三国演义》是一部跨度近一个世纪，出场约400个人物的历史长篇小说，以浩

瀚篇章，深入描绘了东汉群雄割据到三国归晋的历史画卷，其中，细致生动地展

现了魏蜀吴之间错综复杂的军事、政治斗争。而且，以曹操、刘备、孙权、关羽、

张飞、诸葛亮、赵云、魏延、黄忠等为艺术典型的这些数百个栩栩如生的艺术形

象，以决不相同的方式写下自己独特的一页，并由此将三国时代波澜壮阔的历史

背景和社会背景展现在读者面前。

几百年来，《三国演义》广泛流传，脍炙人口，已成为中国文学史上最具有

深远影响的巨著之一。

读《蚊子和狮子》

最近，我读了《伊索寓言》这本书，使我印象最深的是 《蚊子与狮子》，这

则寓言讲的是一只蚊子自认为能战胜狮子，想和狮子比比谁厉害，它吹着喇叭飞

到狮子那里，向狮子挑战。它冲到狮子的脸上，专咬狮子鼻子没有毛的地方。狮

子气得用爪子把脸都抓破了，还是抓不到蚊子，只好认输，要求停战。蚊子战胜

了狮子，非常得意，它继续吹着喇叭唱着凯歌，骄傲地在空中飞来飞去。不小心

粘到了蜘蛛网上，被蜘蛛抓住了。在临死的时候，它悲叹道：“我已经战胜了强

者，却被弱者所消灭。” 这则寓言告诉我们骄傲是没有好下场的，有些人虽然击

败过比自己强大的人，也会被比自己弱小的人击败。

读《莴苣姑娘》有感

今天，我读了这个故事以后，我有这样的感想。

这个故事是说在很久前，有一对勤劳的夫妇，他们一直盼望能生一个孩子，去一直未能如愿。他们便天天乞求上帝能赐给他们一个孩子。终于有一天，上帝被他们的虔诚所感动，仙棒一挥那个妻子就怀孕了。他们非常高兴，非常小心地孕育着这个小宝宝。

有一天，妻子从窗外看到了莴苣，妻子就非常想吃，可那个莴苣是一个巫婆中的，那幢房子也是她的，因此没有人敢靠近那幢房子，尽管如此，妻子还是非常想吃，丈夫看到妻子一天天消瘦，便壮着胆子，去偷了一大把莴苣，心想这些应该够妻子吃了，可谁也没想到，妻子竟然一天就把东西给吃完了。后来有一次丈夫再一次去偷莴苣时，就被巫婆抓到了，并答应巫婆，等她把孩子生下来以后，就要给她，这的莴苣就随便拿。后来，妻子剩下一个小女孩，巫婆当场酒吧她带走了，并取名为莴苣，巫婆就把她关在一座塔里，这塔没有门，只有一扇窗户。

有一次，一位王子来到这里，听到了莴苣的美妙歌声，谁知巫婆算好他会来，就把莴苣的头发给剪了下来，把她放到了一个鸟无人烟的地方，有一天，王子终于找到了她，并把她带回王国，从此过着幸福美满的生活。

这个故事告诉我们：做人不要随便那别人的东西，也不要随便偷别人的东西，不然吃亏的不是别人，而是你自己！

读<鲁滨逊漂流记>

读完<鲁滨逊漂流记>后,我感悟到了人生的道路中不能遇到困难就唉声叹气，应该勇于面对困难遇事还要乐观一些,都不要把任何事都看的那么绝对，要多想办法来解决问题,就像鲁滨逊一样虽然身陷荒岛确不坐叹命运不济，而是充分利用自己的头脑和双手，修建住所、种植粮食、驯养家畜、制造器具、缝制衣服，把荒岛改造成井然有序、欣欣向荣的家园。就像在发现有野人的时候刚开始手忙脚乱，可是最后他沉着冷静以他的勇气与智慧和“星期五”并肩作战，一起打退了野人，这也体现出一个人遇到困难只要沉着冷静的去应对就一定会有办法解决的，对人就像一颗种子他会想尽办法冲破泥土去感受太阳的温暖，当他经历晚千辛万苦回头望去，他已是枝繁叶茂的苍天大树了，在我们的旅途中不能只停留在原地，要时刻想着只要我努力明天会更好，这样才不会因满足于现状而自失。

读《命运》有感

前阵子在书城买了本书，叫《滴水藏海》，里边有300个经典的哲理故事。现在我来品味一篇小故事，叫《命运》。

《命运》讲的是连个孩子的命运，一个被高僧占卜为“状元”，另一个为“乞丐”。二十年后，当初的“状元”成了乞丐，而“乞丐”却成了“状元”。

上帝说：“我赋予每个人的天分之占他命运的三分之一，其余的在于他如何去把握。”

看了这段话，我很受触动。把握，把握命运，多简单的字眼，可是又有多少人真正把握住了自己的命运呢？不必埋怨自己的天分，更不必埋怨自己的命运，因为命运掌握在自己的手中，你随时都可以改变它的！只要你愿意!

读《尼尔斯企鹅历险记》有感

前几天，我读了一本名叫《尼尔斯企鹅历险记》的书，它讲述着这样一个有趣的故事：从前有一个小男孩，大概十四岁左右，个子又高又瘦，长着一头浅黄色的金发。他喜欢睡觉和吃饭，游手好闲而且很爱调皮捣蛋。一个晴朗的星期天的早晨，一只小狐仙来到男孩家偷东西。男孩想做个恶作剧，捉弄小狐仙，这使小狐仙非常生气。把男孩变得和小狐仙一样小。男孩走出家门，发现自己能和动物对话。因为他平时很爱欺负家里养的动物，现在动物们看见他这么小，便张口就骂男孩。这时，一队大雁飞了过来，招唤着男孩家的雄鹅一起飞，而男孩发现家里的一只大雄鹅要飞走了，便马上跳到雄鹅背上，想阻止雄鹅飞走，可雄鹅已经和大雁一起飞上了天空。男孩紧紧地抓住雄鹅的羽毛，不让自己滑下来。在这次旅行中男孩学会了和动物和睦相处，并且帮助雁群成功脱险。最后和雁群告别时男孩又变回了人。 读了这本书，我不仅累计了词汇量，掌握了写作的技巧，还了解了许多知识，读书的时候好像我就是故事中的主人公，好像带我游览了许多地方。 这个男孩在这次历险中遇到了重重困难，但他凭着勇敢、顽强的精神都克服了，使大雁们信任他。他也曾想过回家，但坚强的信念阻止了他。在这个路程上他什么天气都遇到过，可使他还是那么坚强，想办法克服。这种顽强的信念使我大受启发，困难就是成功路上的阶梯，你要敢于面对现实，登上阶梯，当你克服了困难时，就是往前迈了一大步!

 

第二篇：《编程珠玑》读书笔记v1.0.3

《编程珠玑》读书笔记《小C陪你读经典》系列

题外话

小C看了昨天状态下面的几条回复，到现在为止一直在想一个问题：究竟该给大家呈现什么样的内容，又究竟有多少同学在关注主页。

人人确实是一个不大适合搞学术的地方，但自小C 20xx年10月10日接手了建立初衷为服务广大计算机等级考试二级C考生的C语言公共主页以来，半年多来好友人数已比接手时翻了数倍，这里不得不感谢广大C友的支持，这也说明还是有很多同学在茶余饭后过来逛逛的。大家有时也会用不同的方式和语气给小C提意见，小C都一一认真看了，也进行了反思和改进，希望这些改进能在下一个阶段的管理中有所体现。

前言

中国有句古语：“莫求千招会，只要一招鲜。”看似很俗套的话，让小C的想法有了很大的改变。

如果每天都介绍一本书，最终结果小C是可以预料到的，就是大家都只了解了书的概况，而对书的内容却鲜有人认真研读，特别是《算法导论》等千页左右的砖头，大多数人是没有耐心坚持下来的，毕竟小C也是这么过来的。

因此，小C考虑再三，决定从头到尾地和广大C友共读一本著作，从而选择了计算机科学大师Jon Bentley的巨著《编程珠玑》(第二版)，这本全书不过200页的珠玑之作，主要讨论了计算机科学中最本质的问题：如何正确选择和高效地实现算法。并且，多数公司招聘时的面试题目，很大一部分也出自此书。

小C一年前曾经把《编程珠玑》和《编程珠玑II》都概略地过一遍，觉得很多东西都没消化掉，希望趁这次机会和大家一起重温一下经典。

系列日志将以一天介绍，一天解答习题的形式交替进行。

正文

作者简介

Jon Bentley 世界著名计算机科学家，被誉为影响算法发展的十位大师之一。他先后任职于卡内基-梅隆大学 ( 1976 – 1982 ) 、贝尔实验室( 1982 – 2001 ) 和Avaya实验室 (20xx年至今 ) 。在卡内基-梅隆大学担任教授期间，他培养了包括Tcl语言设计者John

Ousterhout、Java语言设计者James Gosling、《算法导论》作者之一Charles Leiserson在内的许多计算机科学大家。20xx年荣获Dr. Dobb’s程序设计卓越奖

2011/6/13 第1章 开篇 Cracking the Oyster

1.1 一次友好的对话

本章开篇就提出一个某程序员曾经问过作者的问题：怎样给一个磁盘文件排序？

相信很多同学都会像作者当年一样上来就犯错误，开始想如何解决，小C第一次读的时候犯了同样的错误，当然，此时大家都不会意识到自己已经陷入泥沼之中。这个陷阱就是“思维定势”。相信大家此时一定在联想自己熟悉的操作系统的磁盘文件排序方案。还没发现自己错了么？小C提个醒大家就都明白了：你知道系统已有的排序方式为什么不用么？按什么排序？要排多少文件么？你除了知道要排序之外，什么信息都没有！

这就是错误之所在，也是这一部分要告诉我们的：在解决问题前，需要一个准确的问题描述。随后，作者和程序员做了沟通，并询问了作者有兴趣的了解的相关问题。加粗部分是作者的问题：

为什么非要自己编写排序程序呢？为什么不用系统提供的排序功能？

我需要在一个大系统中排序。由于某些技术原因，不能使用系统中的文件排序功能。 需要排序的内容是什么？文件中有多少条记录？每条记录的格式是什么？

文件最多包含1000万条记录，每条记录都是7位的整数。

既然文件这么小，何必非要在磁盘上进行排序？为什么不在内存中进行排序?

尽管机器有许多MB的内存，但排序功能只是大系统中的一部分，所以估计到时候只有1MB的内存可用。

你还能告诉我其他一些与记录相关的信息吗？

每条记录都是7位正整数，再无其他相关数据。每个整数最多只出现一次。

1.2 准确的问题描述

本节中，作者对“如何对磁盘文件排序”进行了类似函数的需求编写，这种形式在我们日常的编程中也十分常用。

输入：一个最多包含n个正整数的文件，每个数都小于n，其中n=10的7次方。如果在输入文件中有任何整数重复出现，就是致命错误。没有其他数据与该整数相关联。

输出：按升序排列的输入整数的列表。

约束：最多有(大约)1MB的内存空间可用，有足够的磁盘存储空间可用。运行时间最多几分钟，运行时间为10秒就不需要进一步优化了。

1.3 程序设计

对于上述的问题描述，作者讨论了基于磁盘的归并排序和多趟排序，但最终认为，只有在输入文件中的所有整数都可以在可用1MB内存中表示时才能够实现该方案。问题的解决关键在于利用整数互异的特殊性，找到一种让大约800万个可用位来表示最多1000万个互异整数的数据结构。

1.4 实现概要

作者最终选择了BitMap来表示集合，小C觉得BitMap翻译成位图总觉得怪怪的，位向量倒是稍微好一些，不过也得拐个弯，而Map也有映射的意思，个人胡诌的一个词位映射在这里可能更为直观一些。7位十进制整数最大值加1之后是10,000,000，也就是表示小于1000万的整数，这里用一个1000万位的字符串来表示这个文件，但事实上存在一定的问题，1 MB = 1024 KB= 1024*1024 B = 1024*1024*8 Bit。最终能表示800万，而不是1000万个，这一点作者在文章中也做了说明：那个程序员后来找到了200万个稀疏位。

这里作者也相应提出了三个问题，也就是习题2、习题5和习题7。

小C这里做一下说明：由于习题量比较大，打上来也比较费时间，而且多了的话大家也不一定能够一一认真完成，不如挑几个短小精悍或比较有趣味性的让大家思考一下。

这里挑选习题2和习题5

1.5 原理

作者通过这个实例想阐明如下原理：

正确的问题。一旦明确了问题，战役就成功了90%。习题10、11和12。

BitMap数据结构。该数据结构描述了一个有限定义域内的稠密集合，其中的每一个元素最多出现一次并且没有其他任何数据与该元素相关联。

多趟算法。算法多趟读入其输入数据，看到习题5就该想到要使用两趟算法。

时间-空间折中与双赢。通过使用更多的时间，可以减少程序中所需的空间，减少程序的空间需求也会减少其运行时间。

简单的设计。简单的程序通常比具有相同功能的复杂程序更可靠、更安全、更健壮、更高效，且易于实现和维护。

程序设计的阶段。日后再提。

1.6 习题

习题2

如何使用位逻辑运算(例如与、或、移位)来实现位向量？

习题5

那个程序员说他有1MB的可用存储空间，但是我们概要描述的代码需要1.25MB的空间。如果1MB的空间是严格边界，你会推荐如何处理呢？你的算法运行时间又是多少？ 提示：考虑两趟算法。

习题10

在成本低廉的隔日送达时代之前，商店允许顾客通过电话订购商品，并在几天后上门自取。商品的数据库使用客户的电话号码作为其检索的主关键字（客户知道他们自己的电话号码，而且关键字几乎都是唯一的）。你如何组织商店的数据库，以允许高效地插入和检索操作？

提示：考虑散列，并且不要局限于计算机。

习题11

在20世纪80年代早期，洛克希德公司加里福利亚州桑尼维尔市工厂的工程师们每天都要将许多由计算机辅助设计（CAD）系统生成的图纸从工厂送到位于圣克鲁斯市的测试站。虽然仅有40公里远，但是用汽车快递服务每天都需要一个多小时的时间（由于交通阻塞和山路崎岖），花费100美元。请给出新的数据传输方案并估计每一种方案的费用。 提示：使用鸟类。

习题12

载人航天的先驱们很快就意识到需要在外太空的极端环境下实现顺利书写。民间盛传美国国家宇航局（NASA）花费100万美元研发出了一种特殊的钢笔来解决这个问题。那么，前苏联又会如何解决相同的问题呢？

提示：不使用钢笔你如何写字？

1.7 深入阅读

作者在这里提到了两本书，大家有兴趣可以去Google Books找来看看：

作者

Michael Jackson

Jams L. Adams 书名 《Software Requirements & Specification》 《Conceptual Blockbusting》

2011/6/14 第1章 开篇 Cracking the Oyster 习题解答

2.1 习题2

题目

如何使用位逻辑运算(例如与、或、移位)来实现位向量？

答案

/* Copyright (C) 1999 Lucent Technologies */

/* From 'Programming Pearls' by Jon Bentley */

/* bitsort.c -- bitmap sort from Column 1

* Sort distinct integers in the range [0..N-1]

* 排序在0到N-1范围内的无重复整数

*/

#define BITSPERWORD 32 // 表示一个整型含有32个位

#define SHIFT 5 // 单次位移量

#define MASK 0x1F // 掩码

#define N 10000000 // 表示有1000万个数

int a[1 + N/BITSPERWORD]; // 使用整型数组模拟定义1000万个位的数组

/*****************************************

* 函数声明： void set(int i);

* 参数列表： i：需要设置为1的位

* 返回值： 无

* 功能： 设置位数组中的从0开始的第i位为1

* 实现方法：

i>>SHIFT：将i向右移动5位，相当于将i除以32。因为一个int是32位，所以结果表示i在第几个int数组成员中。

举例说明，如果i是34，则结果是1，也就是从0开始的第1个int数组成员。

1<<(i&MASK)：使用掩码留下i的低5位再左移1位，相当于除以32所得的余数再左移1位。因为第一个是0，所以结果都需要左移1位。结果中1所在的位表示i在该int数组成员的第几位上。

这里可能说得不清楚，接上例，如果i是34，则i&MASK是2，二进制表示是10，再向左移动1位，得到100，也就反映出此时从0开始的第2位是1。

a[i>>SHIFT] |= (1<<(i & MASK) )：接上例，有了上一步就很容易了，直接相位或，把第1个int数组成员的第2位设置为1。

******************************************/

// 这里只详细说明set函数，原理都相同，所以对函数只进行了易于通常理解的翻译 // void set(int i) { a[i / 32] |= (1<<(i % 32)); } 设置位数组中的从0开始的第i位为1 // void clr(int i) { a[i / 32] &= ~(1<<(i % 32)); } 设置位数组中的从0开始的第i位为0 // int test(int i){ return a[i / 32] & (1<<(i % 32)); } 取出从0开始的第i位的值，用于检测 void set(int i) { a[i>>SHIFT] |= (1<<(i & MASK) ); }

void clr(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK) ); }

int test(int i) { return a[i>>SHIFT] & (1<<(i & MASK) ); }

int main()

{

int i;

for (i = 0; i < N; i++)

clr(i);

/* Replace above 2 lines with below 3 for word-parallel init

对每个数组元素进行初始化，并将以下三行语句缩减为上述两行

int top = 1 + N/BITSPERWORD;

for (i = 0; i < top; i++)

a[i] = 0;

*/

while (scanf("%d", &i) != EOF)

set(i);

for (i = 0; i < N; i++)

if (test(i))

printf("%d\n", i);

return 0;

}

2.2 习题5

题目

那个程序员说他有1MB的可用存储空间，但是我们概要描述的代码需要1.25MB的空间。如果1MB的空间是严格边界，你会推荐如何处理呢？你的算法运行时间又是多少？ 答案

使用BitMap表示1000万个数需要1000万位，或者说125万字节。考虑到没有以数字0或1开头的电话号码，我们可以将内存需求降低位100万字节。

另外一种做法是采用两趟算法，首先使用5 000 000/8 = 625 000个字的存储空间来排序0 – 4 999 999之间的整数，然后再第二趟排序5 000 000 – 9 999 999的整数。k趟算法可以在kn的时间和n/k的空间内完成对最多n个小于n的无重复正整数的排序。

2.3 习题10

题目

在成本低廉的隔日送达时代之前，商店允许顾客通过电话订购商品，并在几天后上门自取。商品的数据库使用客户的电话号码作为其检索的主关键字（客户知道他们自己的电话号码，而且关键字几乎都是唯一的）。你如何组织商店的数据库，以允许高效地插入和检索操作？ 答案

商店将纸质订单表格放在10*10的箱数组中，使用客户电话号码的最后两位作为散列索引。当客户打电话下订单时，将订单放到适当的箱中。当客户来取商品时，销售人员顺序搜索对应箱中的订单这就是经典的“用顺序搜索来解决冲突的开放散列”。电话号码的最后两位数字非常接近于随机，因此是非常理想的散列函数，而最前面的两位数字则很不理想因为一些市政机关使用相似的编号方式在记事本中记录事件。

2.4 习题11

题目

在20世纪80年代早期，洛克希德公司加里福利亚州桑尼维尔市工厂的工程师们每天都要将许多由计算机辅助设计（CAD）系统生成的图纸从工厂送到位于圣克鲁斯市的测试站。虽然仅有40公里远，但是用汽车快递服务每天都需要一个多小时的时间（由于交通阻塞和山路崎岖），花费100美元。请给出新的数据传输方案并估计每一种方案的费用。 答案

两地的计算机原先是通过微波连接的，但是当时测试站打印图纸所需的打印机却非常昂贵，因此，该团队在主厂绘制图纸，然后拍摄下来并通过信鸽把35mm的底片送到测试站，在测试站进行放大并打印成图片。鸽子来回一次需要45分钟，是汽车所需时间的一半，并且每天只需要花费几美元。在项目开发的16个月中，信鸽传送了几百卷底片，仅丢失了两卷（当地有鹰，因此没有让信鸽传送机密数据）。由于现在打印机比较便宜，因此可以使用微波链路解决该问题。

2.5 习题12

题目

载人航天的先驱们很快就意识到需要在外太空的极端环境下实现顺利书写。民间盛传美国国家宇航局（NASA）花费100万美元研发出了一种特殊的钢笔来解决这个问题。那么，前苏联又会如何解决相同的问题呢？

答案

根据该传闻，前苏联人用铅笔解决了这个问题。有关这个真实故事的背景请查看

。Fisher Space Pen公司成立于19xx年，其书写设备被俄罗斯航天局、水底探测人员和喜马拉雅登山探险队使用过。

2.6 课外阅读

因为四六级将在本周末进行，这里也应一下景，小C也贴一篇英文，是关于习题12的，也祝大家考出好成绩。

这个传说大家应该都挺熟悉的，但真实的故事是：其实美国宇航局最初也用铅笔，也没为研制这种笔掏一分钱，是Fisher公司自己掏钱研发的，然后拿去让美国宇航局测试，并最终一战成名的，这个故事最终以和谐的结尾收场：美国宇航局和苏联航天局都用上了这种“飞梭笔”。

所以说，很多传说都是神话！

大家如果觉得长，就直接看粗体部分，。

Fact or Fiction?: NASA Spent Millions to Develop a Pen that Would Write in Space, whereas the Soviet Cosmonauts Used a Pencil

The problem of weightless writing was not solved by either Soviet central planning or good old American sub-contracting, but by a private investor and a good idea

By Ciara Curtin | December 20, 2006 | 7

SPACE PEN: The AG-7 original space pen, pictured above, used pressure instead of gravity to make a specially formulated ink flow.Image: COURTESY OF THE FISHER SPACE PEN CO.

During the height of the space race in the 1960s, legend has it, NASA scientists realized that pens could not function in space. They needed to figure out another way for the astronauts to write things down. So they spent years and millions of taxpayer dollars to develop a pen that could put ink to paper without gravity. But their crafty Soviet counterparts, so the story goes, simply handed their cosmonauts pencils.

This tale with its message of simplicity and thrift--not to mention a failure of common sense in a bureaucracy--floats around the Internet, hopping from in-box to in-box, and even surfaced during a 2002 episode of the West Wing. But, alas, it is just a myth. Originally, NASA astronauts, like the Soviet cosmonauts, used pencils, according to NASA historians. In fact, NASA ordered 34 mechanical pencils from Houston's Tycam Engineering Manufacturing, Inc., in 1965. They paid $4,382.50 or $128.89 per pencil. When these prices became public, there was an outcry and NASA scrambled to find something cheaper for the astronauts to use.

Pencils may not have been the best choice anyway. The tips flaked and broke off, drifting in microgravity where they could potentially harm an astronaut or equipment. And pencils are flammable--a quality NASA wanted to avoid in onboard objects after the Apollo 1 fire. Paul C. Fisher and his company, the Fisher Pen Company, reportedly invested $1 million to create what is now commonly known as the space pen. None of this investment

money came from NASA's coffers--the agency only became involved after the pen was dreamed into existence. In 1965 Fisher patented a pen that could write upside-down, in frigid or roasting conditions (down to minus 50 degrees Fahrenheit or up to 400 degrees F), and even underwater or in other liquids. If too hot, though, the ink turned green instead of its normal blue.

That same year, Fisher offered the AG-7 "Anti-Gravity" Space Pen to NASA. Because of

the earlier mechanical pencil fiasco, NASA was hesitant. But, after testing the space pen intensively, the agency decided to use it on spaceflights beginning in 1967.

Unlike most ballpoint pens, Fisher's pen does not rely on gravity to get the ink flowing. The cartridge is instead pressurized with nitrogen at 35 pounds per square inch. This pressure pushes the ink toward the tungsten carbide ball at the pen's tip.

The ink, too, differs from that of other pens. Fisher used ink that stays a gellike solid until the movement of the ballpoint turns it into a fluid. The pressurized nitrogen also prevents air from mixing with the ink so it cannot evaporate or oxidize.

According to an Associated Press report from February 1968, NASA ordered 400 of Fisher's antigravity ballpoint pens for the Apollo program. A year later, the Soviet Union ordered 100 pens and 1,000 ink cartridges to use on their Soyuz space missions, said the United Press International. The AP later noted that both NASA and the Soviet space agency received the same 40 percent discount for buying their pens in bulk. They both paid $2.39 per pen instead of $3.98.

The space pen's mark on the Apollo program was not limited to facilitating writing in

microgravity. According to the Fisher Space Pen Company, the Apollo 11 astronauts also used the pen to fix a broken arming switch, enabling their return to Earth.

Since the late 1960s American astronauts and Russian cosmonauts have used Fisher's pens. In fact, Fisher has created a whole line of space pens. A newer pen, called the Shuttle Pen, was used on NASA's space shuttles and on the Russian space station, Mir. Of course, you don't have to go to space to get your hands on a space pen--earthbound folks can own one for the low, low price of $50.00.

2011/6/28 第2章 啊哈！算法 Aha! Algorithms

由于数据恢复不给力，只能从PDF转回来再继续往下写了，你们懂的。

前言提到了Martin Gardner一句经典，也是作者本章想要表达的思想：“看起来很困难的问题也可以有一个简单、意想不到的答案”。A problem that seems difficult may have a simple, unexpected solution.

3.1 三个问题

本章将讨论三个问题：

A．

给定一个最多包含40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数（在文件中至少缺失一个这样的数——为什么？）。在具有足够内存的情况下，如何解决该问题？如果有几个外部的“临时”文件可用，但是仅有几百字节的内存，又该如何解决该问题？

B．

将一个n元一维向量向左旋转（循环移位）i个位置。例如，当n = 8且i = 3时，向量abcdefgh旋转为defghabc。简单的代码使用一个n元的中间向量在n步内完成该工作。你能否仅使用数十个额外字节的存储空间，在正比于n的时间内完成向量的旋转？

C．

给定一个英语字典，找出其中的所有变位词集合。例如，“pots”、“stop”和“tops”互为变位词，因为每一个单词都可以通过改变其他单词中字母的顺序来得到。

3.2 无处不在的二分搜索

最常见的二分搜索的体现就是“猜大小”，相信大家都是玩过的。比如一个数在1到100之间，你来猜。如果整数在1到n之间，只需要log2n次，还记得那年图书馆威武的管理员大妈么？好吧，继续，如：n是1000，最多需要10次，如果n是1000万，最多20次。 作者此处给出了二分搜索的定义：初始条件是已知一个对象存在于一个给定的范围内，而一次探测操作可以告诉我们该对象是否低于、等于或高于给定的位置。二分搜索通过重复探测当前范围的中点来定位对象。如果一次探测没有找到该对象，那么我们当前的范围减半，然后继续下一次探测。当找到所需要的对象或范围为空停止。

A问题解决方案：首先回顾一下条件，输入为顺序文件，文件包含最多40亿个随机排列的32位整数，而我们的任务是找出一个不存在于该文件中的32位整数，也就是从大约2的32次方（4 294 967 296）个这样的整数。如果有足够内存，可以用第1章中的位图技术。但是，如果仅有几百个字节内存和几个稀疏顺序文件的情况下怎么才能找到缺失的整数?

这个问题的关键点在于想用二分搜索，必须定义一个范围，在范围内表示元素的方式和确定哪一半存在缺失整数。

灵机一动：通过统计中间点之上和之下的元素来探测范围：上面或下面的范围具有最多全部范围的一半元素，由于整个范围之内有一个元素缺失，因此所需的那一半范围必然也包含缺失元素。

这个后面会仔细讲的。

3.3 基本操作的威力

问题B仅使用几十个字节的额外空间将一个n元向量x在正比于n的时间内向左旋转i个位置。这也是编程中向量的基本操作之一，更重要的是对应于交换相邻不同大小的内存块，通常来说，运行时间和存储空间的约束比较严格。

给出了三种常规解决方案：直接移动法，定量移动法和分解-交换法。

灵机一动：将问题看作是把数组ab转换为ba，同时假定我们拥有一个函数可以将数组中特定部分的元素求逆。从ab开始，首先对a求逆，得到arb，然后对b求逆，得到arbr，最后整体求逆，得到(arbr)r。此时恰好是ba。我们写出如下旋转代码：

reverse(0, i-1);

reverse(i, n-1);

reverse(0, n-1);

3.4 排序

接下来是问题C。给定一本英语字典，字母全部小写，要求找出所有变位词分类。

变位词的数量是乘方级，所以。。。你们继续懂的，量是相当的大，作者打了个比方，22!大约是10的21次方，每百亿分之一秒执行一种排列，也要1.1乘以10的9次方秒也就相当于几十年。

灵机一动：标识字典中的每一个词，使得在相同变位词类中的单词具有相同的标识。然后将所有具有相同标识的单词集中在一起。这将原始的变位词问题简化为两个子问题：选择标识和集中具有相同标识的单词。 /* cbadefgh */ /* cbahgfed */ /* defghabc */

3.5 原理

本章几个问题其实说明了同一个解决方法有着不同的目的。排序可以产生有序的输出，但是在变位词程序中，排序为了将相同的元素集中到一起。

另外一个是二分搜索，这也是个极为高效的方法，唯一的缺陷就是整个表必须已知并事先排好序，大家在生活和编程中都可以应用二分思想。

再一个就是标识，类似于分类吧，也挺有用的。

本章的中心思想是在上一章问题定义之后，使用哪些基本操作来解决问题？

上面出现了很多灵机一动，事实上没有真正的灵丹妙药，问题的答案只能来源于解决问题和反思答案所获得的经验。

3.6 习题

习题2

给定包含4 300 000 000个32位整数的顺序文件，如何找出一个出现至少两次的整数。 提示：争取获得线性运行时间的算法。

习题8

给定一个n元实数集合、一个实数t和一个整数k，如何快速确定是否存在一个k元子集，其元素之和不超过t？

提示：考虑集合中最小的k个元素。

习题10

某一天，一个新研究员向托马斯·爱迪生报到。爱迪生要求他计算出一个空灯泡壳的容积。在使用测径仪和微积分进行数小时的计算后，这个新员工给出了答案——150立方厘米。而爱迪生在几秒钟之内就计算完毕并给出了结果“更接近155”。他是如何实现的呢？ 提示：阿基米德如何确定皇冠不是纯金的？

3.7 深入阅读

这里推荐了8.8节的相关书籍。

作者

Aho、Hopcroft、Ullman

Cormen、Leiserson、Rivest 书名 《Data Structures and Algorithms》 《Introduction to Algorithms》

2011/8/16第2章 啊哈！算法 Aha! Algorithms 习题解答

4.1 习题2

题目

给定包含4 300 000 000个32位整数的顺序文件，如何找出一个出现至少两次的整数。 答案

二分搜索通过递归搜索包含半数以上整数的子区间来查找至少出现两次的单词。我最初的解决方案不能保证每次迭代都将整数数目减半，所以log2n趟的最坏情况运行时间正比于nlogn。Jim Saxe经过观察发现，该搜索用不着考虑过多重复元素，从而可以把运行时间缩短为线性时间，如果他的搜索程序知道当前范围内的m个整数中一定有重复元素，那么程序只会在当前工作磁带上存储m+1个整数，此后过来的整数将会被丢弃。虽然他的方法经常会忽略输入变量，但其策略却足以确保至少能找到一个重复元素。

具体解释一下：

2^32 = 4 294 967 296 < 4 300 000 000，所以一定存在重复数字，又因为是顺序文件，所以重复数字必相邻，作者的意思就是寻找当前读入的m+1个数。如果没有找到，继续向后读入m+1个数，再进行查找。

4.2 习题8

题目

给定一个n元实数集合、一个实数t和一个整数k，如何快速确定是否存在一个k元子集，其元素之和不超过t？

答案

当且仅当包含k个最小元素的子集之和不超过t时，总和不超过t的k元子集是存在的。可以通过排序原始集合，在正比于nlogn的时间内找到该子集；也可以使用选择算法，在正比于n的时间内找到该子集。

继续插个嘴：

大家肯定在编程入门课的时候讲过类似的思想，比如找一个集合中最小的k个数，可以先排成升序，O(nlogn)，再取最前面的k个数。选择法的话，直接遍历，记录最小的k个数，每次和每个数相比较，O(nk)。当然也可以找出第k小的元素，然后再线性遍历。反正方法有很多。

4.3 习题10

题目

某一天，一个新研究员向托马斯·爱迪生报到。爱迪生要求他计算出一个空灯泡壳的容积。在使用测径仪和微积分进行数小时的计算后，这个新员工给出了答案——150立方厘米。而爱迪生在几秒钟之内就计算完毕并给出了结果“更接近155”。他是如何实现的呢？ 答案

爱迪生在灯泡壳中灌满了水，然后将这些水倒入一个具有刻度的圆柱体中。

这题应该都听到过了。