编程珠玑

按有用程度 按页码先后 最新笔记

• 

  第198页

  KingsamChen (math,english,computer science)

  问题A的答案，作者没有解释清楚，而某些版本的翻译甚至都是错的。 现在讲下我认为是正确的分析，仅供参考，除了MM之外，鄙人不对次正确性负责任。 在此之前，请先看这个笔记：http://book.douban.com/annotation/13378297/ 首先，32位的整数有2^32个，远大于40亿，所以必然有好多好多的missing elements 现在我们做一个假设：每次位检测之后，两个文件中整数个数不相等，则必然有一个文件要少。而由上面的推论（链接里... (更多)

  问题A的答案，作者没有解释清楚，而某些版本的翻译甚至都是错的。

  现在讲下我认为是正确的分析，仅供参考，除了MM之外，鄙人不对次正确性负责任。

  在此之前，请先看这个笔记：http://book.douban.com/annotation/13378297/

  首先，32位的整数有2^32个，远大于40亿，所以必然有好多好多的missing elements

  现在我们做一个假设：每次位检测之后，两个文件中整数个数不相等，则必然有一个文件要少。而由上面的推论（链接里），缺失的整数必然【应该】属于要少文件的集合中，这就确定了这一个二进制位是0还是1.

  换言之，每一趟检测都可以确定下相应二进制位，如此便可以确定下整个缺失的数。

  然后我们再审视前面的假设。如果两个文件中整数个数相同怎么办？

  做法是任取一个进行下一步即可。为什么？

  因为具有n个二进制位的整数集合的个数是2^n，这是一个偶数！

  （1）如果缺失的个数是奇数个，那么不可能导致相同的情况

  （2）由（1），缺失的个数必然是偶数个。但是这只是一个必要条件，还不是充要。要导致两个文件整数个数相同，除此之外，还要保证缺失的数中，检测位是0和1的个数相同（因为这是分离标准）。

  也就是说，如果发生两边文件整数个数相同，那么两边都必然有缺失的整数，所以任选一边都可以找到那个缺失的数。

  记住，缺失的数至少有一个，我们只需要找一个！

  下面给出实际例子演示：

  假设整数集合是具有3个二进制位的整数：0，1，10，11，101，110。缺失的整数有两个，100和111

  第一趟：

  A:0，10，110 和 B:1，11，101

  对于A，缺失的整数第一位是0，继续第二趟

  00 - 10，110 =》缺失的整数第二位是0，且第三位是1（如果第三位仍为0的话，这个数就是0，不是缺失的数）

  所以缺失的数是100

  同理，对于B，缺失的数的第一位是1。进行第二趟

  01，101 - 11 =》 第二位是1，且第三位也是1，推出缺失的数是111。

  下面分析下整个算法的复杂度。

  由于每趟检测之后，下一轮检测的整数个数都不会超过n/2，我们可以得到相应的递归表达式

  T(n) = T(n/2) + O(n)

  剩下的就很简单了，你爱用主定理用主定理，爱用递归树用递归树，爱用数学分析用数学分析。总之都可以得到结果。

  这个算法的复杂度是O(n)

  整个问题说明两点：

  1：教授总是NB的，这些东西在他们的眼里都是显然

  2：翻译总是不好的，尤其碰到外国语学院的学生或老师去翻译这种专业书籍。 (收起)

  2011-06-18 09:40:39   回应

  收藏

  推荐
• 

  第65页

  cherub

  72法则： 假设以年利率 r% 投资 y年，如果 r * y = 72，则本金差不多会翻倍。 此外，2^10 = 1024，i.e., 10次翻倍大约是1000倍；20次翻倍大约是100万倍；30次翻倍大约是10亿倍。 (更多)

  72法则：

  假设以年利率 r% 投资 y年，如果 r * y = 72，则本金差不多会翻倍。

  此外，2^10 = 1024，i.e., 10次翻倍大约是1000倍；20次翻倍大约是100万倍；30次翻倍大约是10亿倍。

  (收起)

  2011-11-28 17:31:46   回应

  收藏

  推荐
• 

  第109页

  疯语者

  排序： 库排序方法 ， 满足性能需求的时候 排序：自己写，不满足性能需求的时候，其实感觉这个有点废话。。 如果一个OS不能满足性能需求的时候，说不定都要自己实现一个小OS。 而ucos..和Linux，就是在这种背景下产生的。。 (更多)

  排序： 库排序方法 ， 满足性能需求的时候

  排序：自己写，不满足性能需求的时候，其实感觉这个有点废话。。 如果一个OS不能满足性能需求的时候，说不定都要自己实现一个小OS。 而ucos..和Linux，就是在这种背景下产生的。。 (收起)

  2011-10-25 15:14:19   回应

  收藏

  推荐

• 

  第1页

  木溪

  非常爽的一本书啊，程序员必备 (更多)

  非常爽的一本书啊，程序员必备 (收起)

  2011-01-26 15:55:08   1回应

  收藏

  推荐
• 

  第13页

  KingsamChen (math,english,computer science)

  第二段，中间译者少翻译了一句关键的话： Because the total range has a missing element, the smaller half must also have a missing element 原文：http://books.google.com/books?id=kse_7qbWbjsC&lpg=PA208&ots=DfwWwRzS7w&dq=programming%20pearls%20reingold&pg=PA208#v=onepage&q=reingold&f=false 第二章的问题A，我知道很多人都不知道什么意思。 作者没解释清楚，译者瞎翻译，我google到的很多解释都是错的... (更多)

  第二段，中间译者少翻译了一句关键的话：

  Because the total range has a missing element, the smaller half must also have a missing element

  原文：http://books.google.com/books?id=kse_7qbWbjsC&lpg=PA208&ots=DfwWwRzS7w&dq=programming%20pearls%20reingold&pg=PA208#v=onepage&q=reingold&f=false

  第二章的问题A，我知道很多人都不知道什么意思。

  作者没解释清楚，译者瞎翻译，我google到的很多解释都是错的。

  最后花了我将近5hrs才明白整个流程

  分析请见http://book.douban.com/annotation/13378340/ (收起)

  2011-06-18 09:34:48   4回应

  收藏

  推荐
• 

  第18页

  KingsamChen (math,english,computer science)

  第九题：顺序搜索和二分搜索代表了搜索时间和预处理时间的折中。处理一个n元表格时，需要执行多少次二分搜索才能弥补排序带来的消耗？ 某个分析方法： 如果采用顺序，查找k次，复杂度O(kn) 如果采用二分，查找k次，复杂度O(nlogn + klogn) 由于总可以采用正确的排序，使得上界不会超过nlogn，所以可以通过粗略的分析得到，当k>=logn时，二分效率要高于顺序。 但是由于常数的不确定性（时间复杂度表示中都忽略了常.. (更多)

  第九题：顺序搜索和二分搜索代表了搜索时间和预处理时间的折中。处理一个n元表格时，需要执行多少次二分搜索才能弥补排序带来的消耗？

  某个分析方法：

  如果采用顺序，查找k次，复杂度O(kn)

  如果采用二分，查找k次，复杂度O(nlogn + klogn)

  由于总可以采用正确的排序，使得上界不会超过nlogn，所以可以通过粗略的分析得到，当k>=logn时，二分效率要高于顺序。

  但是由于常数的不确定性（时间复杂度表示中都忽略了常数因子），所以logn只是一个大概甚至可能是比较模糊的分界。 (收起)

  2011-06-20 17:31:12   回应

  收藏

  推荐

• 

  第65页

  cherub

  72法则： 假设以年利率 r% 投资 y年，如果 r * y = 72，则本金差不多会翻倍。 此外，2^10 = 1024，i.e., 10次翻倍大约是1000倍；20次翻倍大约是100万倍；30次翻倍大约是10亿倍。 (更多)

  72法则：

  假设以年利率 r% 投资 y年，如果 r * y = 72，则本金差不多会翻倍。

  此外，2^10 = 1024，i.e., 10次翻倍大约是1000倍；20次翻倍大约是100万倍；30次翻倍大约是10亿倍。

  (收起)

  2011-11-28 17:31:46   回应

  收藏

  推荐
• 

  第109页

  疯语者

  排序： 库排序方法 ， 满足性能需求的时候 排序：自己写，不满足性能需求的时候，其实感觉这个有点废话。。 如果一个OS不能满足性能需求的时候，说不定都要自己实现一个小OS。 而ucos..和Linux，就是在这种背景下产生的。。 (更多)

  排序： 库排序方法 ， 满足性能需求的时候

  排序：自己写，不满足性能需求的时候，其实感觉这个有点废话。。 如果一个OS不能满足性能需求的时候，说不定都要自己实现一个小OS。 而ucos..和Linux，就是在这种背景下产生的。。 (收起)

  2011-10-25 15:14:19   回应

  收藏

  推荐
• 

  第94页

  疯语者

  dennis Ritchie 和Ken Thompson 最初在具有8192个18位字的机器上开发Unix操作系统的。。 (更多)

  dennis Ritchie 和Ken Thompson 最初在具有8192个18位字的机器上开发Unix操作系统的。。 (收起)

  2011-10-25 15:11:04   回应

  收藏

  推荐