算法引论——数学归纳法

原来我已经有两个月没有更新博客了。这段时间写了篇论文，做了个app，其间还生了一场病。现在论文还没发表，app的界面也还在等着老弟继续支援，不过应该下个月就能发布了。原本很有冲劲的，突然间感觉累了，所以还是看书了。

 

忘了是哪个牛人推荐的《算法引论》（Introduction to Algorithm, A creative approach）了，两个月前借的书，续借了一次，到现在才终于有幸翻开来。果然是一本好书，连第二章的《数学归纳法》都没让我却步。希望我能够坚持着把这本书看完，然后坚持每一章都做笔记。书本后面还有很多练习题，我也想尽量做一点。嗯，就是这样了。这一次总结的是第一章和第二章。

 

第一章是对算法的概念进行简要的描述，其中有一段话我觉得说得既亲切又贴切：“计算机能够处理数十亿、数万亿比特单位的信息，能在一秒内完成数百万条基本指令。在这个数量级上进行算法设计是一种崭新的实践，有很多方面会与我们的直觉相反，因为我们通常只对自己能感知的事物进行思考。”在后面的习题中，有一道题是拿了一堆数字让我们排序的，面对这一堆数字，如果不让我借助电脑，我只能选择了冒泡排序，而快排，感觉就像与我们的直觉相反，因为大脑并不能像计算机那样记住很多数字。然后是做了练习题里的1.3，题目如下：
考虑由下列数所组成的表。你的工作是删去尽可能少的数使得留下来的数以升序排列。例如下面，你可以把9、44后面的数字全删掉，得到2个升序的数，也可以把9、44以及后面的83留下来得到3个升序的数，那么第二种方案就比第一种方案要好。这是数据：
9 44 32 12 7 42 34 92 35 37 41 8 20 27 83 64 61 28 39 93 29 17 13 14 55
21 66 72 23 73 99 1 2 88 77 3 65 83 84 62 5 11 74 68 76 78 67 75 69 70 22
71 24 25 26
我手工做了一遍，后来也因此推导出了算法的过程，做了下面的实现：

#include<stdio.h>
//an integer array of num, return the longest array that is in order by remove some of the numbers.
int orderredNumber( int* numbers, int num, int*& result ){
	int* order = new int[num];
	int* levelMin = new int[num];
	int level=0;
	levelMin[level]=numbers[0];
	order[0]= level;
	for( int i=1; i<num; i++ ){
		int j=0;
		for( j=0; j<=level; j++ )
			if( numbers[i] < levelMin[j] ){
				order[i] = j;
				levelMin[j]=numbers[i];
				break;
			}
		if( j == level+1 ){
			levelMin[j]=numbers[i];
			order[i]=j;
			level++;
		}
	}
	
	result = new int[level+1];
	int level2 = level;
	int i;
	for( i=num-1; i>=0; i-- ){
		if( (order[i] == level2) ){
			result[level2] = numbers[i];
			level2--;
			break;
		}
	}
	
	for( i; i>=0; i-- ){
		if( level2 < 0 ){
			break;
		}
		if( (order[i] == level2) && (numbers[i]<result[level2-1]) ){
			result[level2] = numbers[i];
			level2--;
		}
	}
	
	delete levelMin;
	delete order;
	return level;
			
}

int main(){
	int data[55] = {9, 44, 32, 12, 7, 42, 34, 92, 35, 37, 41, 8, 20, 27, 83, 64, 61, 28, 39, 93, 
		29, 17, 13, 14, 55, 21, 66, 72, 23, 73, 99, 1, 2, 88, 77, 3, 65, 83, 84, 62, 5, 11, 74, 68, 
	76, 78, 67, 75, 69, 70, 22, 71, 24, 25, 26};
	int* result;
	int level;
	level = orderredNumber( data, 55, result );
	printf( "largerst number %d\n", level );
	//printf( "%d", result[level-1] );
	for( int i=0; i<=level; i++ )
		printf( "%d ", result[i] );
	printf( "\n" );
	delete result;
}	 

  

这是我靠”直觉“做出来的，也许存在更好的方法。如果没有分析错误的话，这个算法的复杂度是O(n)。

 

第二章用数学归纳法证明了一些命题。首先给出我们熟悉的数学归纳法的基本形式：
设T为欲证的定理，若T中含有变量n，n取一切自然数（即正整数），那么不必直接证明对于所有n，T都成立，只需要证明下面的两个条件成立：
1. 当n=1时，T成立；
2. 对任意n>1，如果n-1时T成立，那么n时T也成立。
由基本的数学归纳法产生了多种变形：
1. 强归纳法：如果对于带有参数n的命题P，当n=1时P成立；并且如果对每一个n(n>1)，若对任意小于n的自然数P成立时能推出n对命题P也成立，那么对任意自然数，P都成立。
2. 如果对于带有参数n的命题P，当n=1和n=2时P都成立，并且如果对每一个n(n>2),若n-2时P成立能推出n时P也成立，那么对任意自然数，P都成立。
3. 如果对于带有参数n的命题P，当n=1时P成立；并且如果对每一个n(n大于1且为2的整数幂)，若n/2时命题P成立能推出对n命题P也成立；那么对任意一个2的整数幂的自然数，P都成立。

 

下面是一些命题的证明。

1. 若平面上的直线，任意二线不平行且任意三线不共点，则称这些直线居一般位置。下面计算n条居一般位置的直线能在平面上构成多少个区域。当n=1时，直线把平面分成两个区域；再加上一条边，分成4个区域；当n=3时，总共有7个区域。可以看到，似乎添加第i条直线会增加i个区域。如果是这样的话，那么n条居一般位置的直线能在平面上构成多少个区域就可以用1+1+2+...+i+...n来计算了。所以首先要证明，添加第i条直线会增加i个区域。
（1）当n<=3时，命题成立。
（2）归纳假设：在n-1条居一般位置的直线的平面上添加一条直线，会增加n个区域。现在证明，在n条居一般位置的直线的平面上添加一条直线，会增加n+1个区域。重点在于，由于直线居一般位置，因此一条直线要么穿过某个域将其一分为二，要么与该域不相交；而且第n条直线跟第n+1条直线必然相交于某个域。假如未曾加上第n条直线，添加第n+1条直线会增加n个区域（我们的归纳假设）；把第n条直接重新放回去，与第n+1条直线相交于某区域R，原先第n+1条直线经过R时将R分割成两个域，所以只增加了一个域；现在R在n+1条直接未添加时就已经被分割成了两个域，也就说，第n+1条直线将被分割成两个域的R又分割成了4个域，因此增加了两个域，所以第n+1条直线增加了(n+1)个域。

 

2. 证明： 1/2 + 1/4 + 1/8 + ... + 1/2^n < 1
（1）当n=1时，1/2<1，命题成立。
（2）假设命题对n成立，即有1/2 + 1/4 + 1/8 + ... + 1/2^n < 1，现在必须证明，1/2 + 1/4 + 1/8 + ... + 1/2^n + 1/2^(n+1) < 1成立。
这里用到了比较巧妙的方法，首先由归纳假设有，1/2(1/2 + 1/4 + 1/8 + ... + 1/2^n) = 1/4 + 1/8 + .. + 1/2^(n+1) < 1/2，两边再同时加上1/2，即有：
1/2 + 1/4 + 1/8 + ... + 1/2^n + 1/2^(n+1) < 1

 

3. 证明：令G=(V,E)是一个有向图。G中存在一条独立集S(G)，使得G中的每一个节点都可以从S(G)的某一个节点通过一条长度不超过2的路达到。
（1）设n为G的结点数，当n<=3时命题成立。
（2）假设对任意结点数小于n的有向图（强归纳法），定理成立。现在证明，对于结点数为n的有向图，定理成立。设v为G中的某个结点，令N(v)={v}U{w|w属于V且(v,w)属于E}，令H为V-N(v)导出的子图，H的结点数小于n，由归纳假设，S(H)满足定理。
（2.1）假如S(H)U{v}是独立的，可以令S(G)=S(H)U{v}，此时N(v)中的每个结点都可以通过S(G)中的v经过一步到达；而不在N(v)中的结点可以通过原先的S(H)通过不到2步的路达到；
（2.2）假如S(H)U{v}不是独立的，那么肯定存在w属于S(H)与v相邻，此时N(v)中的结点可以由w通过v两步达到；而而不在N(v)中的结点可以通过原先的S(H)通过不到2步的路达到,此时S(G)=S(H)；

 

4. 证明：令G=(V,E)是连通的无向图，O是V中度数为奇数的节点的集合，我们可以把O中的节点分成节点对，在每一对中都能找到连接这两个节点的无重边的路。
（1）设m为G的边数，m=1时定理成立。
（2）假设定理对于所有边数小于m的连通无向图成立。
考虑有m条边的连通无向图G，令O是度数为奇数的节点的集合，如果O为空集，定理成立。否则，在O中任取两点，由于图连通，必然存在连通这两点的路。将该路连同结点删除，剩余的图的边比原来的少。然而此时图已经是不连通的了，我们修改归纳假设：定理对于所有边数小于m的无向图成立。对于边数为m的无向图，它可能不是连通的，而是被分成几个部分，由于同一部分连通，所以其O一定有偶数个结点。我们从中取两个节点并把连接这两点的路删除，所得到的图边数一定小于m，因此得证。

5. 这是柯西对对数学平均数和几何平均数定理的证明，确实如书上所言，非常漂亮。公式比较复杂，我决定截个图：