Home
吐槽 源码研究 我的 算法挑战 网络 科学吧 文青 关于我

算法引论 笔记5

21 Aug 2013 by LelouchHe

说明

本篇内容继续第二章的习题

过去的一段时间,由于家人来京和工作变迁,着实忙了很长时间.当然,主要原因还是在研究lua.目前的研究还只是读代码写笔记,由于很粗糙,所以没有好意思在这里写,只在evernote上零星记点东西,预计着之后整理一番在贴这里

不过lua确实比较简单明了,看过之后,突然有了自己设计一种简单编程语言的冲动.等把lua看懂整理之后,我会简单的按照类似lua的方式尝试一下.之后可能需要看一些编译的书,或者看LuaJIT的源码.

这里推荐一本相关的书籍Parsing Techniques: A Practical Guide,看过几章发现非常之好.唯一痛恨的是无法转成合适的kindle格式放到kindle里看.伤心至极啊

2.14

简单来说,1,2,3,4,5可以组成任意1-9的数,而后面的10,20,40就相当于二进制数一样,只不过个位是0而已.所以二者结合起来,就可以表示任意正整数

但这样并没有利用归纳法来证明,而且类比于二进制的说法也有欠严谨.下面尝试用归纳法来证明

$n = 1, 2, 3, 4, 5, 6$时假设都成立(之所以看到6的原因很显然吧)归纳基础成立

  1. $k \le n - 1$时,假设成立
  2. 当$k = n$时.选取不同的数相加得n,其中一个很自然的想法就是把所有的数都取出来.这样的数一般是要大于n的,这样,就得到了我们的底线.假设$S(n)$是前n个数之和,则有 \(S(n) = \left \\\{ \begin{aligned} {\frac{n (n + 1)}{2}} & \, & n \le 5 \\\\ {10 \cdot 2 ^ {n - 5}} & \, & n \gt 5 \end{aligned} \right.\) 当$n \ge 2$时,$S(n) > n$,所以$S(n - 1) > n - 1$,亦即为了组成$n - 1$,并不需要前$n - 1$个数.假设其中X没有被用到,那么n就可以有X和$n - X$来组成.又$n - X \le n - 1$,根据归纳假设,其成立.所以归纳假设成立
  3. 原命题成立

ps:

其实一个很自然的想法就是枚举全部的前n-1项,分别讨论第n个数是否需要或可以用它来组成.这样固然是归纳的一个思路(在很多情况下,分类处理是必须的),但比较庞大.通过证明肯定存在这样的X来简化讨论

pss:

这个证明实际上是错的,一开始我也没有注意,直到看到了下一题,这个错误和下一个题一起说

2.15

本题和上题基本类似,同样可以得到和公式: \(S(n) = \left \\\{ \begin{aligned} {\frac{n (n + 1)}{2}} & \, & n \le 3 \\\\ {6 \cdot 2 ^ {n - 3}} & \, & 3 \lt n \le 6 \\\\ {48 + (15 n - 51)(n - 6)} & \, & n \gt 6 \end{aligned} \right.\) 乍看之下,和上一题一模一样,$n \ge 2$时,$S(n) > n$.但本题的数列必然是无法满足假设的

那为什么2.14可以,2.15就错呢?

如果仔细思考一下,可以看到2.14有2个重要的条件没有用到:

  1. 不同的数字
  2. 等比数列

对于1,如果最后得到的$n - X \ge X$怎么办?n既然已经使用过了X,显然$n - X$就不可以了,这相当于在前几项中挖空.但题目并没有这样的条件.所以我们只能改进归纳方式,或修改归纳假设(即做个强的归纳假设,但此处不表).需要讨论二者的关系.如果$n - X < X$,则万事谐矣

对于2,可以看到,n如果不是等比数列中的一个的话(这样就不用拼凑结果了),那么有$Y < n < 2 Y$(n在等比数列的数之间).挑选一个特殊的X,即不大于n的最大的数,那么就有$X < n < 2 X$,即$n - X < X$,得到了想要的结果.

1/2合并,自然可以导出2.14的成立.但2.15却没有这样的条件,所以必然无法成立了

ps:

2.14的重要条件没有利用到,结果让2.15走到了死胡同.这2个问题看起来简单,但却费了我很长的时间来琢磨.充分的利用条件,不丢弃条件.虽然不是所有条件都要用到,但如果不用一个条件,还是希望有充足的理由来支持这种浪费的行为

2.16

首先要提醒的是,不要错误的理解题意.此三角形并不是说任意三边组成的图形即可.一开始我也以为是这样,觉得任意普通位置的三条直线,必然有1个三角形,还怎么证明?

这里说的是三角形区域,不允许被其他直线贯穿

(审题啊..方向错了..归纳再好..有什么用啊)

$n = 3$时,假设成立.归纳基础成立

  1. $k \le n - 1$时成立,即至少有1个三角形
  2. 当$k = n$时.nth边与构成原三角形的三边有如下的关系:
    • 无交点: 这样肯定没有任何影响.其实也不可能,平行不是一般位置
    • 1个交点/1边/1边1点: 不满足一般位置,不可能出现
    • 2边: 会形成新的三角形区域
  3. 所以原先的三角形会保留,归纳假设成立
  4. 原命题成立

ps:

审题是重要的,想好再作答,一步一步来

2.17

2.16的证明颇为保守,1个三角形有些过于少了.此题就是2.16的扩展版,自然可以顺着其思路下来

按照题意,其实可以理解为”每增加1条边,至少增加1个三角形”,从这里入手

n=3,4时,假设成立.归纳基础成立

  1. $k \le n - 1$时成立,即k条边,至少有k-2个三角形
  2. 当$k = n$时.此时,有:
    • 由于n-1边时,至少有k-2个三角形,又根据2.16知,添加1边,不会减少三角形个数.所以此时至少有$(n - 1) - 2$个三角形.剩下的就是增加1边,增加1三角形的证明了(之前提到过)
    • 考虑去掉第n-1边,现在有n-1条边(原先的n-2条和第n条),至少(n-1)-2个三角形.由于第n条边并不影响原n-1边组成三角形的情况(2.16的结论),因此第n条边把n-2条边的三角形数从(n-2)-2提升到(n-1)-2,增加了1个三角形,当把第n-1边拿回时,则整体至少多1个三角形,即$(n - 1) - 2 + 1 = n - 2$个三角形
  3. 所以假设成立.
  4. 原命题成立

ps:

不知道诸位能看懂关键的第二步么?它其实表达了这样的意思:第n条边的加入与否并不影响原先本就存在的三角形.但是当1条新边加入后,三角形数至少加1(归纳假设).因此把n-1去掉之后添加第n条边,必然也是成立的(还是归纳假设,此时仍有$k = n - 1$),亦即第n边增加了1个三角形.所以证明了不仅不减少,反而至少增加1个三角形的论证

同2.16的一个显著不同是,没有使用到分类.此处的讨论完全是抽象的,并没有考量边与边的对应位置关系,而是抽象的思考边和三角形数量的关系,从而得到加1至少增1的结论

分类不是目的,分类还是为归纳服务

2.18

n=3时,假设成立(额..),归纳基础成立

  1. $k \le n - 1$时,假设成立
  2. 当$k = n$时.前n-1点可以形成一个凸包,n-1点在单位圆中(归纳假设),即表明凸包于圆中.第n点与这凸包的关系有:
    • n在凸包内/边: 显然n点同在圆内
    • n不在凸包内: 那么新的凸包中,n必然为凸包顶点.由于前n-1均于圆中,则两两必小于直径.假设第n点于圆外,则表示第n点与某点大于直径.但这样的2点必不可能与第三点共于单位圆.所以n点必在圆内
  3. 假设成立
  4. 原命题成立

ps:

从后来可以看到,凸包有什么用呢?(悲剧..),为了不高估自己,所以我决定还是留下凸包的说法,毕竟这是我的思考.一开始考虑2的时候,直接觉得任3点共圆,那第n点必然于圆中了.但其实这就是要证明的.不能把未知到已知的直接证明,那还不如不证

不过我还是有疑虑,第2步的正确性尚不确定.这样有确切的论证么?所以还是得思考

另外一点,在思考这个题时,我曾陷入误区,以为单位圆是固定的.其实,单位圆是可以随着点数的变动而变动的,不让一看单位圆,就立马陷入钉圆于原点的定势思维