证明1/2+1/4+1/8+…+1/2^n<1.
n = 1, 1/2 < 1, 成立
假设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^(n+1)很难说还<1
1/2+1/4+1/8+…+1/2^n +1/2^(n+1)
= 1/2+(1/4+1/8+…+1/2^n +1/2^(n+1) )
= 1/2+1/2 (1/2+1/4+1/8+…+1/2^n )
< 1/2+1/2=1
原命题得证
独立集,节点集合,任一两节点不相邻
有向图 <a, b> 表示a与b相邻,b与a不相邻
证明:G(V, E)有向图,证明G中有一个独立集S(G),使G中每一个节点都能由S(G)中的点通过长度不超过2的路到达
n <= 3 时, 必然成立
假设节点数<n的有向图,命题成立
对于节点数为n的有向图
取一个点v
N(v)为所有与v相邻的点的集合 {w | <v, w> 在G中}
则对于图H = G - v - N(v)
根据假设有S(H)能满足命题要求
- 若S(G) = S(H) + {v} 是独立集,v又与所有N(v)一步到,则这个图中所有点都可由S(G) 两步内到
- 若S(H) + {v} 不是独立集,意味着S(H)中必然有一个p,存在边<p, v>,这样p可以经过两步到所有N(v), 从而S(G) = S(H), 满足要求
8. 格雷码
问题:产生n位元的所有格雷码。
格雷码(Gray Code)是一个数列集合,每个数使用二进位来表示,假设使用n位元来表示每个数字,任两个数之间只有一个位元值不同。
例如以下为3位元的格雷码: 000 001 011 010 110 111 101 100 。
如果要产生n位元的格雷码,那么格雷码的个数为2^n.
假设原始的值从0开始,格雷码产生的规律是:第一步,改变最右边的位元值;第二步,改变右起第一个为1的位元的左边位元;第三步,第四步重复第一步和第二步,直到所有的格雷码产生完毕(换句话说,已经走了(2^n) - 1 步)。
用一个例子来说明:
假设产生3位元的格雷码,原始值位 000
第一步:改变最右边的位元值: 001
第二步:改变右起第一个为1的位元的左边位元: 011
第三步:改变最右边的位元值: 010
第四步:改变右起第一个为1的位元的左边位元: 110
第五步:改变最右边的位元值: 111
第六步:改变右起第一个为1的位元的左边位元: 101
第七步:改变最右边的位元值: 100
如果按照这个规则来生成格雷码,是没有问题的,但是这样做太复杂了。如果仔细观察格雷码的结构,我们会有以下发现:
1、除了最高位(左边第一位),格雷码的位元完全上下对称(看下面列表)。比如第一个格雷码与最后一个格雷码对称(除了第一位),第二个格雷码与倒数第二个对称,以此类推。
2、最小的重复单元是 0 , 1。
所以,在实现的时候,我们完全可以利用递归,在每一层前面加上0或者1,然后就可以列出所有的格雷码。
第一步:产生 0, 1 两个字符串。
第二步:在第一步的基础上,每一个字符串都加上0和1,但是每次只能加一个,所以得做两次。这样就变成了 00,01,11,10 (注意对称)。
第三步:在第二步的基础上,再给每个字符串都加上0和1,同样,每次只能加一个,这样就变成了 000,001,011,010,110,111,101,100。
好了,这样就把3位元格雷码生成好了。
如果要生成4位元格雷码,我们只需要在3位元格雷码上再加一层0,1就可以了: 0000,0001,0011,0010,0110,0111,0101,0100,1100,1101,1110,1010,0111,1001,1000.
也就是说,n位元格雷码是基于n-1位元格雷码产生的。
9. 无重边的路
节点的度数之和 = 边的两倍
证明:G(V,E)无向连通图, O为度数为奇的节点的集合,一定为偶数。证明O可以分出两两组成的节点对,对每一对节点都能找到连接他们的与其他路劲无重边的路径。
边数m = 1, 显然成立
假设边数<m的连通的无向图满足命题
对于边数m的图
找到O中两个点,必然有一条路
删去这条路,只删边,不删点
原来奇点删路(两条边)后必然度还是奇数
剩下的点还在O中,必然边数<m,可以归纳假设
但无法保证剩下的还联通
增强归纳假设
假设边数<m的无向图(不需要条件连通)满足命题
这样删掉那条路之后
可以分成多个连通的子图
对于每个子图,边数<m,满足假设
这样在加上原来那条路
边数m的图成立
1. 由于常常要证明的东西是普遍认可的,是熟悉的,所以在证明的时候会偶尔忽略一些条件。如上面的无重边的路问题,很容易忽略删去这条路后原图是否还连通的判断,引发错误。
2. 基础假设需要注意题目的条件,有些会有特殊情况,比如有些n = 1, n = 2 都是对的,n -1 也可以推n的情况,我们会按照数学归纳法判断其正确。但就是特殊情况使得 n = 2 推不了n = 3, 那么整个归纳就错了。
数学归纳法的思想主要就是两种:
1. 知道基础解,然后可以由n的情况推n + 1。
2.知道基础解,知道n+1的情况,并能证明n+1的情况可以由n的情况推出。
计算机科学与数学密切相关,其中的递归便是用的数学归纳法的思想。
一般地,证明一个与正整数\(n\)有关的命题,可按下列步骤进行:
(1)归纳奠基:证明当\(n\)取第一个值\(n_0 (n_0∈N^*)\)时命题成立;
(2)归纳递推:假设当\(n=k(k≥n_0,k∈N^*)\)时命题成立,推出当\(n=k+1\)时命题也成立。
只要完成这两个步骤,就可以断定命题对从\(n_0\)开始的所有正整数\(n\)都成立.上述证明方法叫做数学归纳法。
二、...
最简单和常见的数学归纳法是证明当n等于任意一个自然数时某命题成立。证明分下面两步:
证明当 n= 1 时命题成立。
假设 n=m 时命题成立,那么可以推导出在 n=m+1 时命题也成立。(m代表任意自然数)
设 G=(V, E) 为一个有向图或无向图,假定 BFS 以给定结点 s∈Vs\in V 作为源节点在图 G 上运行。则在 BFS 终结时,对于每个结点 v∈Vv\in V,BFS 计
MERGE方法具有哨兵的写法:
什么是数学归纳法?数学归纳法(Mathematical Induction, MI)是一种数学证明方法,通常被用于证明某个给定命题在整个(或者局部)自然数范围内成立。除了自然数以外,广义上的数学归纳法也可以用于证明一般良基结构,例如:集合论中的树。这种广义的数学归纳法应用于数学逻辑和计算机科学领域,称作结构归纳法。
在数论中,数学归纳法是以一种不同的方式来证明任意