《算法谜题》书评

只能说，可以一看

##2. 手套选择具体思想就是，**化繁为简**。先考虑我们有2双灰色手套，那么要保证挑出的手套至少是一对灰色的，显然需要挑**2+1=3次**（如果只挑两次的话，运气不佳，刚好挑到了2个左手，那就不能满足条件）。现在将条件扩大，一共十双手套（忽略颜色，只考虑左右手），那么如果运气不好，只挑10次刚好是10个左手，显然不能满足要求(a)至少挑出一双颜色匹配的手套。因此，至少要挑10+1次。至于要求(b)所有颜色的手套都至少挑出一双匹配的，仍然考虑最糟糕的情况，假设调了16次，这16次恰好是5双黑色加3双棕色，少了灰色手套不满足要求，从前面的分析知道，为了挑出一对灰色的手套，需要再挑3次，因此至少要挑19次。##3. 矩形切割用2进制表示n##4. 士兵摆渡先考虑让1名士兵过河##5. 行列变换第一想法时,求行列式;)求行列式的算法太复杂,显然原书的答案更快,check每行(列),该行(列)是否在原来的矩阵中出现过.##6. 数数的手指显然,是个循环的问题,1000%8=0(abcdecb...)因此,是手指b(即食指)##7. 夜过吊桥我表示这题没想出来,当然,看答案后感觉不够通俗易懂,所以这里用自己的方式来讲解下.首先,我们把问题泛化一点,这样理解起来更容易些:假设桥的一边有4个人,其中有两个**大哥(A,B)**,过桥时间分别为10min和10min,另外有两个**小弟(c,d)**过桥时间分别为1min和1min,其他条件相同.显然直觉告诉我们,两个大哥一起过桥,然后两个小弟一起过桥这样最省时间,但问题是,只有一个手电筒,两个大哥先过桥后,手电筒还得要一位大哥送回来,送回来后这位大哥还得再过桥,这样时间都浪费在这位大哥身上了.至此我们发现,来回路上送手电筒的人很关键,所以典型的贪心算法就是每次都让跑得快的小弟**来回**送手电筒,所以c陪着A过桥(10min),再回来(1min),再陪着B过桥(10min),再回来(1min),再陪着d过桥(1min)一共23min.如图所示:这样的方案显然不够让人满意,因为两个大哥是分开过桥,假设现在不是两个大哥,而是十个大哥,那岂不是要分成十次过桥!这样子一想,还是觉得让两个大哥同时过桥效率更高.但是这又会遇到前面说过的问题,等于是绕回来了.等等,前面的问题是什么来着?两个大哥如果先过桥,得让其中一个大哥把手电筒送回去,这样时间都浪费在这位大哥上了.那有没有可能让小弟送回去呢?问题是对岸没有小弟啊!!!那能不能先派个小弟过去呢?当然可以!所以就得到了下图(方案2):这样效率高多了,假设有很多大哥,那么根据问题4(士兵摆渡)中的思想,先运送两个大哥,再运送两个大哥......OK,将我们的方案抽象出来描述就是,先派一个跑得快的小弟到对岸等着,然后跑的慢的两位大哥一起过,再让对岸的那个小弟把手电筒送回来,周而复始.那么再想一个问题,方案2是否一定比方案1快?显然,如果小弟跑的只比大哥稍稍快一点点,那么这样子先派小弟过去所浪费的时间也就太多了.通过分析可以发现,两种方案都可以将问题化解为送一对大哥到对岸的子问题.假设两个小弟过桥时间为$m_1, m_2, m_1 < m_2$两个大哥过桥时间为$n_1, n_2, n_1 \lt n_2, n_1 \ge m_2$,那么方案1解决该子问题所需时间为$t_1=n_2+m_1+n_1+m_1$注意小弟还得把手电筒送回来下一轮才能开始;方案2解决该子问题所需时间为$t_2=m_2+m_1+n_2+m_2$. 那么$t_2 < t_1$的条件是$2m_2 < m_1+n_1$回到题干中给出的条件,对应的,$m_1=1, m_2=2,n_1=5,n_2=10$, 那么左右两式相等，满足$2m_2< m_1+n_1$的约束，如果将条件$m_2=2$改为$m_2=3$，可以验证，两种方案所花的时间时相同的。##8. 拼图问题类似问题4,降低问题规模,如果不是500,而是3片,4片,5片呢?##9. 对称，转成上（下）三角矩阵，再等差求和##10. 联想到猜数字的问题：给定一个1-8之间的数，每猜一次会被告知大了还是小了或者猜对了。问猜至少几次？每猜一次，我们得到2个信息，是在A中，还是在B中。但是，如果换到天平称重的问题上，实际上我们可以得到3个信息，A中，B中，还是C中。因此，至少需要log3(x)次##13.被堵塞的路径其实是一个经典的组合问题.从A到B的最短路径是7步,可能的步数是C(7,3),即7步之中任选3步向下走.然后挑出经过P点的路径. $C(4,2) × C(3,1)$, 所以结果时, $C(7,3) - C(4,2) × C(3,1)$##14. 答案写错了吧???##15. 不变量的思想比较有意思,如果一个n*n的面板可以用一个由k个方格子组成的骨牌密铺的话,那么首先应当满足n*n 能被k整除##16. 3分钟可以煎3个饼!3分钟可以煎3个饼!3分钟可以煎3个饼!ok,搞清楚这个就行了##17. 吐槽下,题目的错别字很坑...应该时可能到达的方格的个数##18. 神奇的不变量##20. 没有更快的办法了么？##30. 题目有些没说清的地方，应该指出，有一把尺子，可以切出任意长度的棍子##36.题目的解答有点意思，就是可以看做一个队列，然后入队和出队后可以得到一个有限状态机。##40.该题的解题思想灰常重要。将棋盘上骑士的可移动位置映射到环形的状态空间中去，脱离了原始的马走日限制，利于分析。##43.每次数据规模减一，问题不变，从而解决n的问题##44.注意区分奇偶充分利用真币居多，假币只有一枚这一特性。##45.引申到A*算法，曼哈顿距离作为代价函数##46.同样采用减一和穷举的方法来考虑。##48.经典的动态规划问题