下载文档原格式
第一章作业1.证明下列Ο、Ω和Θ的性质1）f=Ο(g)当且仅当g=Ω(f)证明：充分性。
若f=Ο(g)，则必然存在常数c1>0和n0，使得∀n≥n0，有f≤c1*g(n)。
由于c1≠0，故g(n) ≥ 1/ c1 *f(n)，故g=Ω(f)。
必要性。
同理，若g=Ω(f)，则必然存在c2>0和n0，使得∀n≥n0，有g(n) ≥ c2 *f(n).由于c2≠0，故f(n) ≤ 1/ c2*f(n)，故f=Ο(g)。
2）若f=Θ(g)则g=Θ(f)证明：若f=Θ(g)，则必然存在常数c1>0，c2>0和n0，使得∀n≥n0，有c1*g(n) ≤f(n) ≤ c2*g(n)。
由于c1≠0，c2≠0，f(n) ≥c1*g(n)可得g(n) ≤ 1/c1*f(n)，同时，f(n) ≤c2*g(n)，有g(n) ≥ 1/c2*f(n)，即1/c2*f(n) ≤g(n) ≤ 1/c1*f(n)，故g=Θ(f)。
3）Ο(f+g)= Ο(max(f,g))，对于Ω和Θ同样成立。
证明：设F(n)= Ο(f+g)，则存在c1>0，和n1，使得∀n≥n1，有F(n) ≤ c1 (f(n)+g(n))= c1 f(n) + c1g(n)≤ c1*max{f,g}+ c1*max{f,g}=2 c1*max{f,g}所以，F(n)=Ο(max(f,g))，即Ο(f+g)= Ο(max(f,g))对于Ω和Θ同理证明可以成立。
4）log(n!)= Θ(nlogn)证明：∙由于log(n!)=∑=n i i 1log ≤∑=ni n 1log =nlogn ，所以可得log(n!)= Ο(nlogn)。
∙由于对所有的偶数n 有，log(n!)= ∑=n i i 1log ≥∑=n n i i 2/log ≥∑=nn i n 2/2/log ≥(n/2)log(n/2)=(nlogn)/2-n/2。
当n ≥4，(nlogn)/2-n/2≥(nlogn)/4，故可得∀n ≥4，log(n!) ≥(nlogn)/4，即log(n!)= Ω(nlogn)。
递推算法在程序编辑过程中，我们可能会遇到这样一类问题，出题者告诉你数列的前几个数，或通过计算机获取了数列的前几个数，要求编程者求出第N项数或所有的数列元素（如果可以枚举的话），或求前N项元素之和。
这种从已知数据入手，寻找规则，推导出后面的数的算法，称这递推算法。
典型的递推算法的例子有整数的阶乘，1，2，6，24，120…，a[n]=a[n-1]*n(a[1]=1)；前面学过的2n，a[n]=a[n-1]*2(a[1]=1)，菲波拉契数列：1，2，3，5，8，13…，a[n]=a[n-1]+a[n-2](a[1]=1,a[2]=2)等等。
在处理递推问题时，我们有时遇到的递推关系是十分明显的，简单地写出递推关系式，就可以逐项递推，即由第i项推出第i+1项，我们称其为显示递推关系。
但有的递推关系，要经过仔细观察，甚至要借助一些技巧，才能看出它们之间的关系，我们称其为隐式的递推关系。
下面我们来分析一些例题，掌握一些简单的递推关系。
例如阶梯问题：题目的意思是：有N级阶梯，人可以一步走上一级，也可以一步走两级，求人从阶梯底走到顶端可以有多少种不同的走法。
这是一个隐式的递推关系，如果编程者不能找出这个递推关系，可能就无法做出这题来。
我们来分析一下：走上第一级的方法只有一种，走上第二级的方法却有两种（两次走一级或一次走两级），走上第三级的走法，应该是走上第一级的方法和走上第二级的走法之和（因从第一级和第二级，都可以经一步走至第三级），推广到走上第i级，是走上第i-1级的走法与走上第i-2级的走法之和。
很明显，这是一个菲波拉契数列。
到这里，读者应能很熟练地写出这个程序。
在以后的程序习题中，我们可能还会遇到菲波拉契数列变形以后的结果：如f(i)=f(i-1)+2f(i-2)，或f(i)=f(i-1)+f(i-2)+f(i-3)等。
我们再来分析一下尼科梅彻斯定理。
定理内容是：任何一个整数的立方都可以写成一串连续的奇数和，如：43=13+15+17+19=64。
Program算法设计与分析基础中文版答案习题1.15..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立.Hint:根据除法的定义不难证明:●如果d整除u和v, 那么d一定能整除u±v;●如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。
数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。
故gcd(m,n)=gcd(n,r)6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?Hint:对于任何形如0<=m<n的一对数字,Euclid算法在第一次叠代时交换m和n, 即gcd(m,n)=gcd(n,m)并且这种交换处理只发生一次.7.a.对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法?(1次)b. 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次除法?(5次)gcd(5,8)习题1.21.(农夫过河)P—农夫W—狼G—山羊C—白菜2.(过桥问题)1,2,5,10---分别代表4个人, f—手电筒4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c=0的实根,写出上述算法的伪代码(可以假设sqrt(x)是求平方根的函数)算法Quadratic(a,b,c)//求方程ax^2+bx+c=0的实根的算法//输入:实系数a,b,c//输出:实根或者无解信息If a≠0D←b*b-4*a*cIf D>0temp←2*ax1←(-b+sqrt(D))/tempx2←(-b-sqrt(D))/tempreturn x1,x2else if D=0 return –b/(2*a)else return “no real roots”else //a=0if b≠0 return –c/belse //a=b=0if c=0 return “no real numbers”else return “no real roots”5.描述将十进制整数表达为二进制整数的标准算法a.用文字描述b.用伪代码描述解答：a.将十进制整数转换为二进制整数的算法输入：一个正整数n输出：正整数n相应的二进制数第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n第二步：如果n=0，则到第三步，否则重复第一步第三步：将Ki按照i从高到低的顺序输出b.伪代码算法DectoBin(n)//将十进制整数n转换为二进制整数的算法//输入：正整数n//输出：该正整数相应的二进制数，该数存放于数组Bin[1...n]中i=1while n!=0 do {Bin[i]=n%2;n=(int)n/2;i++;}while i!=0 do{print Bin[i];i--;}9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略) 对这个算法做尽可能多的改进.算法MinDistance(A[0..n-1])//输入:数组A[0..n-1]//输出:the smallest distance d between two of its elements习题1.31.考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去.a.应用该算法对列表”60,35,81,98,14,47”排序b.该算法稳定吗?c.该算法在位吗?解:a. 该算法对列表”60,35,81,98,14,47”排序的过程如下所示:b.该算法不稳定.比如对列表”2,2*”排序c.该算法不在位.额外空间for S and Count[] 4.(古老的七桥问题)习题1.41.请分别描述一下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度. a.删除数组的第i 个元素(1<=i<=n)b.删除有序数组的第i 个元素(依然有序) hints:a. Replace the i th element with the last element and decrease the array size of 1b. Replace the ith element with a special symbol that cannot be a value of the array ’s element(e.g., 0 for an array of positive numbers ) to mark the i th position is empty. (“lazy deletion ”)第2章 习题2.17.对下列断言进行证明:(如果是错误的,请举例) a. 如果t(n )∈O(g(n),则g(n)∈Ω(t(n)) b.α>0时,Θ(αg(n))= Θ(g(n)) 解:a. 这个断言是正确的。
数列与数列的性质讲解与习题实例数列是数学中的一个重要概念，它是由一系列有序的数按照一定的规律排列而成。
数列不仅在数学中具有重要意义，也广泛应用于其他领域，如物理、经济等。
本文将对数列的概念、性质进行讲解，并提供一些习题实例，以帮助读者更好地理解和运用数列。
一、数列的概念及表示方式数列是由一系列按照一定规律排列的数所组成的有序数集。
比如：1, 2, 3, 4, 5, ...就是一个从1开始的自然数列，其中每个数依次加1。
数列的表达方式有多种，常见的有列表法、通项公式和递推关系法。
1. 列表法：将数列的每一项按照一定的顺序列出来，用逗号隔开。
比如：1, 2, 3, 4, 5, ...就是一个数列的列表表示方式。
2. 通项公式：数列的通项公式是用一个变量n表示数列的项数，通过这个变量和一些常数表达数列的每一项。
比如：数列1, 4, 7, 10, ...的通项公式可以表示为an = 3n - 2。
3. 递推关系：数列的递推关系是通过前一项和后一项之间的关系来表示数列的。
比如：数列1, 1, 2, 3, 5, ...的递推关系可以表示为an = an-1 + an-2，其中an表示数列的第n项。
二、数列的性质数列具有一些重要的性质，掌握这些性质可以更好地理解数列，并在解题过程中作为辅助工具。
1. 单调性：数列可以是递增的（单调递增）或者递减的（单调递减），也可以是不增或不减的。
2. 有界性：数列可以是有上界或有下界的，也可以同时具有上下界，或者无界。
3. 整体性：数列的性质可以通过数列的前几项来确定，这样可以简化问题的分析和计算。
4. 规律性：数列的规律可以通过观察数列的前几项来找出，从而得到数列的通项公式或递推关系。
三、习题实例下面通过一些具体的习题实例来加深对数列的理解和应用。
习题1：求等差数列1, 3, 5, 7, ...的前n项和。
解析：这是一个公差为2的等差数列，可以使用等差数列的求和公式Sn = (a1 + an) * n / 2来解决。
习 题 三3-1 解下列递推关系：（1）⎩⎨⎧===+---1,001071021a a a a a n n n （2）⎩⎨⎧===++--1,00961021a a a a a n n n（3）⎩⎨⎧===+-2,00102a a a a n n （4）⎩⎨⎧==-=--121021a a a a a n n n（5）⎩⎨⎧===-+=---2,1,099210321a a a a a a a n n n n（解）（1）特征方程为010x 7x 2=+-。
解得2x 1=，5x 2=，故通解为n n n B A a 52⋅+⋅=分别令n ＝0，1，并代入初值1010==a a ,得关于系数A 、B 的方程组⎩⎨⎧=+=+1520B A B A 解得31-=A ，31=B 。
所以定解为 n a ＝()n n2531- （2）特征方程为0962=+-x x 。
解得321==x x ，故通解为()n n Bn A a 3⋅+=代入初值得⎩⎨⎧=+=1330B A A 解得0=A ，31=B 。
∴ 13331-==n nn n n a（3）特征方程为012=+x 。
解得i x ±=，故通解为()nn n i B i A a -⋅+⋅=代入初值得⎩⎨⎧=-=+2Bi Ai B A 解得i A -=，i B =。
∴ n a ＝()nn i i i i -+⋅-＝()11---+n n i i ＝()1111---+n n i )(可以看出，此数列为：0，2，0，－2，0，2，0，－2，……。
当然本数列可以不用特征根法求解，直接由解递推关系就可观察出2--=n n a a ，从而由初值即得结果。
（4）用特征根法求解可得解为n a ＝1。
本小题虽然是二阶递推关系，但由于其特殊性，并不一定要用特征根法求解，而用迭代法可能更容易计算出结果。
即0122a a a -=＝2×1－1＝1， 1232a a a -=＝2×1－1＝1，…… 立即可以观察出n a ＝1（n ＝0，1，2，…）。
（5）特征方程为09923=+--x x x 。
解得31-=x ，12=x ，33=x ，故通解为()n nn C B A a 33++-=代入初值得方程组⎪⎩⎪⎨⎧=++=++-=++2991330C B A C B A C B A 解得121-=A ，41-=B ，31=C 。
∴ ()n n n a 331413121⋅+---=＝()[]1131341--+--n n 3-2 求由A ，B ，C ，D 组成的允许重复的排列中AB 至少出现一次的排列数。
（解）设由A ，B ，C ，D 组成的字符串为s ＝()n c c c 21，串的长度为n ，满足条件的串有n a 个，则 n a ＝13-n a ＋()2242--+n n a ＋()3342--+n n a ＋……＋()0042+a即∑-=-=-1012n i i n n a a a ＋()14311--n 化简得221143----+-=-n n n n n a a a a ∴ ⎩⎨⎧====+----1044210221a a a a a a n n n n ,,解之得()()nn nn a 3263233263234---++-=3-3 求n 位二进制数中相邻两位不出现11的数的个数。
（解）设所求的数有n a 个，可将这样的数按左边第一位的值分成两类进行统计： （1） 第一位是0，这类数有1-n a 个；（2） 第一位是1，则按照题目条件，第二位就必须为0，故此类数有2-n a 个。
由加法法则，符合条件的数共有1-n a ＋2-n a 个。
因此，得n a 满足的递推关系为⎩⎨⎧==≥+=--3232121a a n a a a n n n ,,反推可得10=a ，所以⎥⎥⎦⎤⎢⎢⎣⎡⎪⎪⎭⎫ ⎝⎛--⎪⎪⎭⎫ ⎝⎛+=+++22225125151n n n n F a 3-4 利用递推关系求下列和（1）∑==nk n ks 02（解）由原式得⎩⎨⎧==+=-312121s s n s s n n , （3.2.2） 可以看出，1是齐次递推关系1-=n n s s 的特征根，故此非齐次定解问题的特解为*ns ＝()C Bn An n ++2＝Cn Bn An ++23 为了利用待定系数法确定待定常数A 、B 、C ，将*n s 代入（3.2.2）的第一式得()n C Bn An+++23-()()()()11123-+-+-n C n B n A ＝2n即()()C B A n B A An +-+--2332＝2n对任意的n ，上式成立的充分必要条件是n 的同次幂的系数相等，即方程组⎪⎩⎪⎨⎧=+-=-=003213C B A A B A 成立。
解之得 31=A ，21=B ，61=C 。
所以，（3.2.2）的特解为*ns ＝n n n 61213123++＝()()6121++n n n 从而得（3.2.2）的通解()()n n n n A n n n s s s 16121⋅+++=+=*其中A 为任意常数。
再由初值条件11=s 得()()612111++⋅＋A ＝1即0=A 。
所以（3.2.2）的定解，即和式的求和结果为()()6121++=n n n s n（2）()∑=-=nk n k k s 01（解）类似（1）得n s 满足的递推关系为⎩⎨⎧===-=--2021021s s s nn s s n n , 特解仍为*ns ＝()C Bn An n ++2＝()Cn Bn An ++23 但关于待定系数A 、B 、C 的方程则变为⎪⎩⎪⎨⎧=+--=-=013213C B A A B A 解之得 31A =，0B =，31C -=。
即特解为 *ns ＝n n 31313-＝()()311+-n n n 从而通解为n s ＝*ns ＋n s ＝()()311+-n n n ＋A再由初值条件0s 0=得0A =，所以n s ＝()()311+-n n n（3）()∑=+=nk n k k s 02（解）n s 满足的递推关系为⎩⎨⎧==+=--3021021s s n n s s n n ,,其特解为*ns ＝n n n 67233123++＝()()6721++n n n 通解为n s ＝*ns ＋n s ＝()()6721++n n n ＋nA 1⋅其中A 为任意常数。
以初值条件31=s 代入得()()6712111+⨯+⋅＋A ＝3即0=A 。
所以n s ＝()()6721++n n n（4）()()∑=++=nk n k k k s 021（解）n s 满足的递推关系为()()⎩⎨⎧==++=--6021101s s n n n s s n n ,,解之得n s ＝n n n n 234112341234+++＝()()()4321+++n n n n（解）设n 位四进制数中2和3必须出现偶数次的数有n a 个，2出现奇数次3出现偶数次的数为 n b 个，2出现偶数次3出现奇数次的数为 n c 个，两者都出现奇数次的数为 n d 个。
则对于满足题目要求的数而言，可将其按照最高位数字的值分为3类情况分别予以统计：（1）最高位是0或1，那么在后续的1-n 个数字中2和3还必须出现偶数次，这样的四进制数共有2 1-n a 个；（2）最高位是2，后1-n 位必须有奇数个2偶数个3，这样的数有1-n b 个；（3）最高位是3，后1-n 位必须有偶数个2奇数个3，这样的数有1-n c 个。
各类情形，没有重复的数。
由加法法则，得n a 满足的递推关系n a ＝21-n a ＋1-n b ＋1-n c 。
同理也可得n b 、n c 和n d 满足的递推关系，即⎪⎪⎩⎪⎪⎨⎧++=++=++=++=------------1111111111112222n n n n n n n n n n n n n n n n d c b d d c a c d b a b c b a a ， n ≥2 且知初值为21=a ，111==c b ，01=d 。
解之得∴ n a ＝1142--+n n ，（n ≥1）即所求的四进制数的个数。
3-6 试求由a ，b ，c 三个文字组成的n 位符号串中不出现aa 图像的符号串的数目。
（解）用n a 表示满足条件的串的个数，显然，1a ＝3，2a ＝23－1＝8，当n ≥3时，将符合要求的串分为两类：第一类： 第一字母不是a ，这样的串有21-n a 个；第二类： 首字母为a ，次字母必为b 或c ，这样的串有22-n a 个。
综合以上情况有()⎩⎨⎧==+=--8322121a a a a a n n n , 解之得n a ＝()()n n316323316323--+++ba ba ab b a ab b a ++++1000010001000设行列式的值为n d ，则将行列式按第一行展开得n n b a ba abb a ab b a d ++++=10000010001000＝()110000010001000-+++++n b a ba abb a ab b a b a－1100000100000001-+++n b a ba ab b a ab ab＝()2110000010001000--++++-+n n b a ba abb a ab b a ab d b a＝()b a +1-n d －ab 2-n d∴ ()⎩⎨⎧++=+=-+=--222121bab a d b a d abd d b a d n n n , 下面解递推关系，特征方程为()02=++-ab x b a x特征根为()221ba b a x -±+=,＝a ，b对于通解，需根据a 与b 的关系分两种情形进行讨论：（1）b a =≠0：此时特征根a x =为二重根，故通解为 n d ＝()n a Bn A +，其中A 、B 为任意常数。
代入21,=n 时的初值得关于A 、B 的方程组()()⎩⎨⎧=+=+22322a a B A aa B A 解之得1==B A ，所以行列式的值为n d ＝()n a n +1，1≥n（2）b a ≠：有两个不同的特征根a 和b ，通解是n d ＝n n Bb Aa +代入初值得⎩⎨⎧++=++=+2222b ab a B b A a ba bB aA 解之得b a a A -=，ab bB -= 故有n d ＝n n b a b b a b a a -+-＝b a b b a a n n ---++11 ＝nn n n n b ab b a b a a +++++---1221 ，1≥n3-8 在n ×m 方格的棋盘上，放有k 枚相同的车，设任意两枚不能互相吃掉的放法数为F k (n,m )，证明F k (n ，m )满足递推关系F k (n ，m)＝ F k (n -1，m )＋(m -k ＋1) F k-1(n -1，m )（证）将放法分为两类：其一是第一行无棋子，共有()m n F k ,1-种放法；其二是第一行有车（且只能有一个），可以随意选一个车出来，先将其余k －1个车放入下边的n －1行，有()m n F k ,11--种放法，然后再把选出来的车放入第一行的某个格子，但要求该格子所在的列没有车，有()1--k m 列可供选择，故第二类放法总共有()()m n F k m k ,111-+--种。
