实验指导书实验

1、精选优质文档-倾情为你奉上算法设计与分析实验指导书（计算机科学与技术系）编写 兰州交通大学电子与信息工程学院2018年3月目 录实验1 递归与分治法.1实验一 递归与分治法一、 实验目的（1）理解递归程序运行过程中参数的变化情况，熟悉递归程序的复杂度分析与其他程序的区别。（2）通过实验掌握分治策略算法设计思想和方法；（3）培养学生的动手能力。二、实验仪器设备（1）计算机；（2）C+编译调试环境。三、实验原理掌握将算法转换为可运行程序的步骤。四、实验内容及注意事项（1）输出全排列。（2）正整数的划分个数。（3）汉诺塔问题。（4）二分查找。（5）大整数的乘法。（6）合并排序。（7）快速排序。（8）

2、棋盘覆盖问题。（8）循环赛日程表。五、实验步骤（1）输出全排列问题。#include<stdio.h>#include<stdlib.h>void Swap(int &a, int &b) int temp = a;a = b;b = temp;void Perm(int *list, int k, int m) if (k = m) for (int i = 0; i <= m; i+)printf("%d", listi);printf("n");elsefor (int i = k; i <= m

3、; i+) Swap(listk, listi);Perm(list, k + 1, m);Swap(listk, listi);int main() int list8 = 1,2,3,4,5,7,8,9 ;Perm(list, 0, 5);system("pause");return 0;（2）大整数的划分数#include <stdio.h>int split(int n, int m)if (n < 1 | m < 1) return 0;if (n = 1 | m = 1) return 1;if (n < m) return spl

4、it(n, n);if (n = m) return (split(n, m - 1) + 1);if (n > m) return (split(n, m - 1) + split(n - m), m);int main()printf("%d", split(6, 6);return 0;（3）汉诺塔问题#include <iostream>using namespace std;void TowersofHanoi(int n, char x, char y, char z)if (n)TowersofHanoi(n - 1, x, z, y);co

5、ut << "From" << x << "To" << y << endl;TowersofHanoi(n - 1, z, y, x);/int main()TowersofHanoi(3, 'A', 'B', 'C');system("pause");return 0;（4）二分查找#include <iostream>using namespace std;/非递归查找int BinarySearch(int

6、*array, int aSize, int key)if (array = NULL | aSize = 0)return -1;int low = 0;int high = aSize - 1;int mid = 0;while (low <= high)mid = (low + high) / 2;if (arraymid < key)low = mid + 1;else if (arraymid > key)high = mid - 1;elsereturn mid;return -1;/递归int BinarySearchRecursive(int *array,

7、int low, int high, int key)if (low > high)return -1;int mid = (low + high) / 2;if (arraymid = key)return mid;else if (arraymid < key)return BinarySearchRecursive(array, mid + 1, high, key);elsereturn BinarySearchRecursive(array, low, mid - 1, key);int main()int array10;for (int i = 0; i<10;

8、 i+)arrayi = i;cout << "No recursive:" << endl;cout << "position:" << BinarySearch(array, 10, 6) << endl;cout << "recursive:" << endl;cout << "position:" << BinarySearchRecursive(array, 0, 9, 6) << en

9、dl;system("pause");return 0;（5）大整数的乘法#include<cstdio>#include<cmath>#include <iostream>using namespace std;#define SIGN(A) (A > 0) ? 1 : -1) int divideConquer(int X, int Y, int n) int sign = SIGN(X) * SIGN(Y);int x = abs(X);int y = abs(Y);if (x = 0 | y = 0) return 0;el

10、se if (n = 1) return sign * x * y;else int A = (int)x / pow(10, (int)(n / 2);int B = x - A * pow(10, n / 2);int C = (int)y / pow(10, (int)(n / 2);int D = y - C * pow(10, n / 2);int AC = divideConquer(A, C, n / 2);int BD = divideConquer(B, D, n / 2);int ABDC = divideConquer(A - B), (D - C), n / 2) +

11、AC + BD;return sign * (AC * pow(10, n) + ABDC * pow(10, (int)(n / 2) + BD);int main() int x, y, n;printf("input 2 big numbers and the digit of them ,seperate with blank:");scanf("%d%d%d", &x, &y, &n);printf("x 和 y的乘积为：%d", divideConquer(x, y, n);system("

12、;pause");（6）合并排序#include <iostream>using namespace std;void Merge(int *array, int low, int middle, int high) /合并int *A = new inthigh - low + 1; /临时数组，存储个数为high - low + 1个数据int i = low;int j = middle + 1;int k = 0;while (i <= middle && j <= high) /直至前半部或后半部数据完全录入暂存if (arrayi

13、< arrayj) /如果前半部的数据小于后半部的，前半部数据暂存Ak+ = arrayi+;else /否则后半部数据暂存，并下标自加Ak+ = arrayj+;while (i <= middle) /保证前半部数据录入暂存Ak+ = arrayi+;while (j <= high) /保证后半部数据录入暂存Ak+ = arrayj+;for (i = low; i <= high; i+) /将暂存的数据重新填充至arraylow-arrayhigh中arrayi = Ai - low;void MergeSort(int *array, int low, in

14、t high)int middle; /分割问题if (low < high)middle = (low + high) / 2; /分割问题MergeSort(array, low, middle); /前半部MergeSort(array, middle + 1, high); /后半部Merge(array, low, middle, high); /合并int main()int n;cout << "输入需要排列数据的个数："cin >> n; /录入需要排列的个数int *array = new intn;cout <<

15、 endl << "请输入数据：" << endl;for (int i = 0; i < n; i+)cin >> arrayi; /录入未排序的数据MergeSort(array, 0, n - 1); /进行排序cout << "排列后数据：" << endl;for (int j = 0; j < n; j+) /输出排列结果cout << arrayj << " "cout << endl;system("p

16、ause");return 0;（7）快速排序#include<iostream>using namespace std;void quickSort(int a, int, int);int main()int array = 34,65,12,43,67,5,78,10,3,70 , k;int len = sizeof(array) / sizeof(int);cout << "The orginal array is:" << endl;for (k = 0; k < len; k+)cout << a

17、rrayk << ","cout << endl;quickSort(array, 0, len - 1);cout << "The sorted array is:" << endl;for (k = 0; k < len; k+)cout << arrayk << ","cout << endl;system("pause");return 0;void quickSort(int s, int l, int r)if (

18、l < r)int i = l, j = r, x = sl;while (i < j)while (i < j && sj >= x) / 从右向左找第一个小于x的数j-;if (i < j)si+ = sj;while (i < j && si < x) / 从左向右找第一个大于等于x的数i+;if (i < j)sj- = si;si = x;quickSort(s, l, i - 1); / 递归调用quickSort(s, i + 1, r);（8）棋盘覆盖在一个2k×2k 个方格组成

19、的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。问题: 用4种不同形态的L型骨牌, 覆盖给定特殊棋盘上除特殊方格以外的所有方格，且任何2个不得重叠。 特殊方格在棋盘上出现的位置有4k种情形。因而对任何k>=0，有4k种不同的特殊棋盘。易知，在任何一个2k * 2k的棋盘中，用到的L型骨牌个数恰为(4k -1)/3。 1) 当k>0时，将2k×2k棋盘分割为4个2k-1×2k-1 子棋盘, Figure (a)所示。2) 特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊

20、方格。3) 为将无特殊方格子棋盘转化为特殊棋盘，可以用一个骨牌覆盖3个较小棋盘的会合处，如 Figure(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。4) 递归地使用这种分割，直至棋盘简化为棋盘1×1。 #include<iostream>#include<iomanip> /包含设置域宽的头文件#include<stdlib.h> /标准库using namespace std;int tile = 0;int *(*board) = NULL; /定义指向指针的指针用于动态的创建用于存储骨牌号的数组void ChessBo

21、ard(int tr, int tc, int dr, int dc, int size)if (size = 1) return;int t = tile+, / L型骨牌号s = size / 2; / 分割棋盘 (注意逗号表达式的应用) / 覆盖左上角子棋盘if (dr < tr + s && dc < tc + s)/ 特殊方格在此棋盘中ChessBoard(tr, tc, dr, dc, s);else / 此棋盘中无特殊方格 / 用 t 号L型骨牌覆盖右下角boardtr + s - 1tc + s - 1 = t;/ 覆盖其余方格ChessBoard(

22、tr, tc, tr + s - 1, tc + s - 1, s);/ 覆盖右上角子棋盘 / 特殊方格在此棋盘中if (dr < tr + s && dc >= tc + s)ChessBoard(tr, tc + s, dr, dc, s);else / 此棋盘中无特殊方格/ 用 t 号L型骨牌覆盖左下角 boardtr + s - 1tc + s = t;/ 覆盖其余方格ChessBoard(tr, tc + s, tr + s - 1, tc + s, s);/ 覆盖左下角子棋盘if (dr >= tr + s && dc < t

23、c + s)/ 特殊方格在此棋盘中ChessBoard(tr + s, tc, dr, dc, s);else/ 用 t 号L型骨牌覆盖右上角boardtr + stc + s - 1 = t; / 覆盖其余方格ChessBoard(tr + s, tc, tr + s, tc + s - 1, s); / 覆盖右下角子棋盘if (dr >= tr + s && dc >= tc + s) / 特殊方格在此棋盘中ChessBoard(tr + s, tc + s, dr, dc, s);else / 用 t 号L型骨牌覆盖左上角boardtr + stc + s =

24、 t; /覆盖其余方格ChessBoard(tr + s, tc + s, tr + s, tc + s, s);int main()p1:int tx = 0, ty = 0, sp, dx, dy, zsize;/定义棋盘的左上角方格、特殊方格的行号和列号以及棋盘大小cout << "请输入特殊方格的行号:" cin >> dx; cout << endl; /提示用户输入cout << "请输入特殊方格的列号 :" cin >> dy; cout << endl;cout &l

25、t;< "请输入要填充特殊方格的数字: " cin >> sp; cout << endl;cout << "请输入棋盘的大小(棋盘大小必须为2的n方！) : "cin >> zsize; cout << endl;board = new int *zsize;for (int i = 0; i < zsize; i+)boardi = new intzsize; boarddx - 1dy - 1 = sp; /特殊方格用sp填充ChessBoard(tx, ty, dx - 1,

26、 dy - 1, zsize); /输出结果for (int j = 0; j < zsize; j+)for (int m = 0; m < zsize; m+)cout << setw(6) << boardjm; /域宽为6cout << endl;system("pause");goto p1;return 0;（9）循环赛日程表请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手。其中1in，1jn-1。8个选手的比赛日程表如下图： 算法思路：按分治策略，我

27、们可以将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。如上图，所列出的正方形表是8个选手的比赛日程表。其中左上角与左下角的两小块分别为选手1至选手4和选手5至选手8前3天的比赛日程。据此，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这样我们就分别安排好了选手1至选手4和选手5至选手8在后4天的比赛日程。依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。 算法步骤： 1

28、)用一个for循环输出日程表的第一行 for(int i=1;i<=N;i+) a1i = i 2)然后定义一个m值，m初始化为1，m用来控制每一次填充表格时i（i表示行）和j（j表示列）的起始填充位置。 3)用一个for循环将问题分成几部分，对于k=3，n=8，将问题分成3大部分，第一部分为，根据已经填充的第一行，填写第二行，第二部分为，根据已经填充好的第一部分，填写第三四行，第三部分为，根据已经填充好的前四行，填写最后四行。for (ints=1;s<=k;s+) N/=2; 4)用一个for循环对中提到的每一部分进行划分for(intt=1;t<=N;t+)对于第一部分

29、，将其划分为四个小的单元，即对第二行进行如下划分 同理，对第二部分（即三四行），划分为两部分，第三部分同理。 5)最后，根据以上for循环对整体的划分和分治法的思想，进行每一个单元格的填充。填充原则是：对角线填充 for(int i=m+1;i<=2*m;i+) /i控制行 for(int j=m+1;j<=2*m;j+) /j控制列 aij+(t-1)*m*2= ai-mj+(t-1)*m*2-m;/*右下角的值等于左上角的值 */ aij+(t-1)*m*2-m =ai-mj+(t-1)*m*2;/*左下角的值等于右上角的值 */ 运行过程： 1)由初始化的第一行填充第二行 2)由s控制的第一部分填完