习题课1

习题课1,第一章 算法及基础知识,1-6 请对冒泡排序算法进行描述，并对其复杂性进行分析。算法描述：Void BubbleSort(int score ) int i,j,temp; for(i=0;i=n-2;i+) for(j=0;jscorej+1) temp=scorej; scorej=scorej+1; scorej+1=temp; 该算法的时间复杂性为O(n2),算法为稳定的排序方法。,1-7 给出求解汉诺塔问题的算法描述，并对其复杂性进行分析。 Hanoi Tower问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。计算结果非常恐怖(移动圆片的次数)18446744073709551615，众僧们即便是耗尽毕生精力也不可能完成金片的移动了。,1-7 给出求解汉诺塔问题的算法描述，并对其复杂性进行分析。算法思想： 将n个盘子从A座移动到C座上可以分解为三个步骤： （1）将A座上的n-1个盘子移动到座上（借助C座）（2）将A座上剩下的一个盘子移动到C座上。（3）将n-1个盘子从B座移动到C座上（借助A座）Void hanio(int n, char a, char b, char c) if(n=1) move(a,c) else hanio(n-1,a,c,b); move(a,c);hanio(n-1,b,a,c);,void move(char x, int n, char y) /汉诺塔的递归算法 cout 把编号为 n 的盘从 x 移到 y endl;void hanoi(int N, char A, char C, char B) if(N = 1) move(A, 1, B); else hanoi(N-1, A, B, C); move(A, N, B); hanoi(N-1, C, A ,B); int main() cout -汉诺塔递归实现-n endl; cout 说明：利用C塔将盘子从A塔移到B塔n endl; cout n; cout 移动步骤： endl; hanoi(n, A, C, B); system(PAUSE); return 0;该算法的时间复杂性为O(2n),using namespace std;static void hanoi(int n) /汉诺塔的非递归算法 int fromPole, toPole, Disk; int *BitStr = new intn,*Hold = new intn; char Place = A, B, C; int i, j, temp; for(i=0; i n; i+) BitStri = 0; Holdi = 1; temp = 3 - (n % 2); int TotalMoves = (1 n) - 1; for (i=1; i = TotalMoves; i+) for (j=0 ; BitStrj != 0; j+) BitStrj = 0; BitStrj = 1; Disk = j+1; if (Disk = 1) fromPole = Hold0; toPole = 6 - fromPole - temp; temp = fromPole; else fromPole = HoldDisk-1; toPole = 6 - Hold0 - HoldDisk-1; cout 把编号为 Disk 的盘子从 PlacefromPole-1 移到 PlacetoPole-1 endl; HoldDisk-1 = toPole; int main() cout -汉诺塔非递归实现-: n endl 说明：利用塔C将盘子从塔A移到塔Bn endl; cout n; hanoi(n); system(PAUSE); return 0;该算法的时间复杂性为O(n),第二章 贪心法,2-4 给定n位正整数a，去掉其中任意k(kb1 可知有：ab 2. n=2时，设有a=a2a1和b=b2b1, 当a2=b2,a1b1 ，可知有：ab 当a2b2，可知有：ab 3. n=k时，设有a=aka1和b=bkb1 当ak=bk,ak-1bk-1 ，可知有：ab 当akbk，可知有：ab,算法思想：1.当anan-1an-1a1时，删除从anan-k+1的k个数字。3.当anan-1a1序列，包含aiai-1时， 从最高位向低位扫描，碰见aiai-1，则删除ai-1; 重复步骤，k次，删除k个数字。,#include char min(string str, int* pos) char min = str0; *pos = 0; for(unsigned int i=1; i str.length(); i+) if(stri min) min = stri; *pos = i; return min; int main() cout -删除数问题- endl; cout 之贪心算法解决n endl; string number; unsigned int delNumber; cout number; cout delNumber; if(delNumber = number.length() cout 输入的数字太大 0) temp = number.substr(0, number.length()-digit+1); ch = min(temp, &pos); result += ch; number = number.substr(pos+1, number.length()-pos-1); digit-; cout n删除 delNumber 位数字后得到的最小整数为： result endl; system(PAUSE); return 0 ;,2-5数列极差问题。在黑板上写了N(N2000)个正数组成的一个数列，进行如下操作：每一次擦去其中两个数(设为a和b)，然后在数列中加入一个数a*b+1，如此下去，直至黑板上只剩下一个数。在所有按这种操作方式后得到的数中，最大的记为max，最小的记为min，则该数列的极差M=max-min。设计一个有效算法计算极差M。并说明算法的正确性。,分析：举例：设N=2，N个正数组成的数列为：7 ，6计算只有一种情况：7*6+1=43，max=min=43设N=3，N个正数组成的数列为：5，7 ，6计算有三种情况： （5,7,6）=217，（5,6,7）=218，（7,6,5）=216max=218,min=216, M=218-216=2,设N=4，N个正数组成的数列为：5，7 ，4，6计算有？种情况：4个数相乘有6中情况： （5,7）（4,6），（6,4）（5,4）（7,6），（6,7）（5,6）（7,4），（4,7）3个数相乘有2中情况：4,6，（57），4，（57），6,最大值出自：（4,5）,6,7 6,7,（4,5）最小值出自：7,6,5,4 （7,6）,5,4,第四章 贪心算法,算法描述：public class max_min static void sort1(int n,int a)int t;for(int i=0;in-1 ;i+)for(int j=i;jaj) t=ai;ai=aj;aj=t; static void sort2(int n,int b) int t; for(int i=0;in-1 ;i+) for(int j=i;jn ;j+) if(bi1;i-)sort1(i,a);a0=a0*a1+1;a1=a2;a2=a3;System.out.println(a0,a1,a2,a3=+a0+,+a1+,+a2+,+a3);max=a0;System.out.println(max=+max);for(int i=n;i1;i-)sort2(i,b);b0=b0*b1+1;b1=b2;b2=b3;System.out.println(b0,b1,b2,b3=+b0+,+b1+,+b2+,+b3);min=b0;System.out.println(min=+min);max=max-min;System.out.println(极差=+max);,第四章 贪心算法,1、最有子结构性质： 从上面的分析可知，问题的最优解来自子问题的最优解。故该问题具有最优子结构性质。2、贪心选择性质： （用数学归纳法证明） 当n=3时，已排序数列为：x1x2x3 max=(x1*x2+1)*x3+1=x1*x2*x3+x3+1; min=(x2*x3+1)*x1+1=x1*x2*x3+x1+1; mid=(x1*x3+1)*x2+1=x1*x2*x3+x2+1;,第四章 贪心算法,因为：x1x2x3所以：minmidmax 极差M=max-min当n=k时，有x1x2xk 反复执行三个数的情况，max=x1*x2*xk+xk+1;min=x1*x2*xk+x1+1;极差M=max-min,第三章 分治法,3-9 应用分治法完成下面的整数乘法计算：2348*3825 1、将两个四位数乘法转换成4个两位数乘法； 2、将两个两位数乘法转换成4个一位数乘法。,3-10 在一个由元素组成的表中，出现次数最多的元素称为众数。试写一个寻找众数的算法，并分析其计算复杂性。解：1. 选取一个基准元素； 2. 按基准元素将表中的元素一分为二，左边小于基准元素，右边大于基准元素，并统计等于基准元素的个数，记在si中，基准元素记在k中。 3. 如果左边的元素个数小于基准元素的个数，右边的元素个数也小于基准元素的个数，则该基准元素为众数，程序结束。 4. 如果左边的元素个数大于基准元素的个数，则执行1-3步，并将新的基准元素个数，与前一个基准元素个数进行比较，si保存较大者，k保存该基准元素。 5.如果右边的元素个数大于基准元素的个数，则执行1-3步，并将新的基准元素个数，与前一个基准元素个数进行比较，si保存较大者，k保存该基准元素。,4-4 在一个圆形操场的四周摆放着n堆石子。现要将石子有次序的合并成一堆。规定每次只能选相邻的两堆石子合并成新的一堆，并将