《具体数学》章节试读

《具体数学》的笔记-第8页 - 约瑟夫问题

J(5($\times$)($2^m$))
=2J(5($\times$)($2^{m-1}$))-1
=2($\times$)(2J(5($\times$)($2^{m-2}$))-1)-1
=2($\times$)2J(5($\times$)($2^{m-2}$))-2-1
=2($\times$)2($\times$)2J(5($\times$)($2^{m-3}$))-($2^2$)-2-1
=($2^3$)J(5($\times$)($2^{m-3}$))-($2^2$)-2-1
=($2^m$)J(5)-($2^{m-1}$)-($2^{m-2}$)-...-1
=($2^m$)J(5)-(($2^{m-1}$)+($2^{m-2}$)+...+1)
=($2^m$)J(5)-(($2^m$)-1)
=($2^m$)J(5)-($2^m$)+1
=3($\times$)($2^m$)-($2^m$)+1
=2($\times$)($2^m$)+1
=($2^{m+1}$)+1
有一个tricky的方法可以知道J(1000000)只需要19次计算：($2^{19}$)<1000000<($2^{20}$)

《具体数学》的笔记-第13页 - 约瑟夫问题

还有一个方法可以计算约瑟夫问题：2($\times$)n+1-($2^{m+1}$)不过貌似计算量差不多。1.17推广递归式稍微有点跳跃。有了变动基数的解，就不怕规则改变了：每隔两个删去一个人等等。

《具体数学》的笔记-递归问题 - 递归问题

从第一章开始就有点困难呃, 满目数学公式, 欲哭无泪...

《具体数学》的笔记-第10页 - 记号注释

前言里最后一句话，“对于每个错误，我们乐于给第一个报告该错误的读者支付2.56美元，无论它是数学错误、史实错误还是印刷错误”，刚读完，翻过来看到下一页的记号注释，就发现一个印刷错误。x的顶的定义写错了，大于等于号应该替换为小于等于号，你们说是不是。。

《具体数学》的笔记-第3页 - 1.1河内塔

通过证明我们可以爬到提子的最底一级（基础），并能从一个阶梯爬到上一个阶梯（递归），数学归纳法就证明了：我们可以在一架梯子上想爬多高就爬多高。

《具体数学》的笔记-第2页 - 河内塔

($T_0$)=0; ($T_n$)=2($T_{n-1}$)+1, n > 0
Try Wolframalpha with input: T(n) = 2T(n-1) + 1, T(0) = 0

《具体数学》的笔记-第2页 - 递归问题

聪明的数学家们不会羞于考虑小问题

《具体数学》的笔记-第1页 - 相关资料

1.他人的读后感
1）用了半年时间终于把具体数学看完了：
http://www.cnblogs.com/cc011/archive/2010/01/16/1649514.html
这本书的内容关于如何进行算法的时间复杂度分析，以及分析复杂问题的思路；
读这本书需要较好的数学基础，需要一些微积分、概率统计、数论的知识；
这本书是阅读TAOCP的基础；
读完此书可以再读一下Algorithms & CMM in practise，然后再读此书。

2）最近几个月潜心修练Concrete Mathematics的一点感想
http://www.cnblogs.com/cc011/archive/2009/02/15/1390893.html
潜心阅读，这才是在学习计算机科学。
3）读TAOCP的算法形式化定义以及归纳法的一点感受
http://www.cnblogs.com/cc011/archive/2010/05/09/1730963.html
去理解计算机科学中的科学二字的含义...
2.相关数学参考书籍
1）概率论
《概率导论》 http://book.douban.com/subject/4175522/
3.关于Knuth
1）解读高德纳：最伟大计算机程序员是如何诞生的
http://www.linux.cn/article-1099-1-rel.html

《具体数学》的笔记-第9页 - 约瑟夫问题

如果一位数据结构老师收到“约瑟夫问题”的这样一份答案，不知会怎么想：#include <stdio.h>
unsigned flp2(unsigned x) {
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
return x - (x >> 1);
}
int main()
{
unsigned x;
printf("Please input the number of people in Josephus Circle: ");
scanf("%d", &x);
printf("The _ONLY_ safe position is: %d\n", (x - flp2(x) << 1) + 1);
return 0;
}看了前两个例子没感觉有特别的地方，看到第三个问题的讲解及扩展，可以给这本书打五星了。