《习题课1》ppt课件.ppt

习题课——1 第一章 算法及基础知识 1-6 请对冒泡排序算法进行描述，并对其复杂性进行分析。 算法描述： Void BubbleSort(int score[ ]) { int i,j,temp; for(i=0;i=n-2;i++) for(j=0;jn-1;j++) if(score[j]score[j+1]) { temp=score[j]; score[j]=score[j+1]; score[j+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 请输入A塔盘子的个数：; int n = 1; cin 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 int[n],*Hold = new int[n]; char Place[] = {A, B, C}; int i, j, temp; for(i=0; i n; i++) { BitStr[i] = 0; Hold[i] = 1; } temp = 3 - (n % 2); int TotalMoves = (1 n) - 1; for (i=1; i = TotalMoves; i++) { for (j=0 ; BitStr[j] != 0; j++) { BitStr[j] = 0; } BitStr[j] = 1; Disk = j+1; if (Disk == 1) { fromPole = Hold[0]; toPole = 6