實驗指導(dǎo)書實驗

1、精選優(yōu)質(zhì)文檔-傾情為你奉上算法設(shè)計與分析實驗指導(dǎo)書（計算機科學(xué)與技術(shù)系）編寫 蘭州交通大學(xué)電子與信息工程學(xué)院2018年3月目 錄實驗1 遞歸與分治法.1實驗一 遞歸與分治法一、 實驗?zāi)康模?）理解遞歸程序運行過程中參數(shù)的變化情況，熟悉遞歸程序的復(fù)雜度分析與其他程序的區(qū)別。（2）通過實驗掌握分治策略算法設(shè)計思想和方法；（3）培養(yǎng)學(xué)生的動手能力。二、實驗儀器設(shè)備（1）計算機；（2）C+編譯調(diào)試環(huán)境。三、實驗原理掌握將算法轉(zhuǎn)換為可運行程序的步驟。四、實驗內(nèi)容及注意事項（1）輸出全排列。（2）正整數(shù)的劃分個數(shù)。（3）漢諾塔問題。（4）二分查找。（5）大整數(shù)的乘法。（6）合并排序。（7）快速排序。（8）

2、棋盤覆蓋問題。（8）循環(huán)賽日程表。五、實驗步驟（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）大整數(shù)的劃分?jǐn)?shù)#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）大整數(shù)的乘法#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; /臨時數(shù)組，存儲個數(shù)為high - low + 1個數(shù)據(jù)int i = low;int j = middle + 1;int k = 0;while (i <= middle && j <= high) /直至前半部或后半部數(shù)據(jù)完全錄入暫存if (arrayi

13、< arrayj) /如果前半部的數(shù)據(jù)小于后半部的，前半部數(shù)據(jù)暫存Ak+ = arrayi+;else /否則后半部數(shù)據(jù)暫存，并下標(biāo)自加Ak+ = arrayj+;while (i <= middle) /保證前半部數(shù)據(jù)錄入暫存Ak+ = arrayi+;while (j <= high) /保證后半部數(shù)據(jù)錄入暫存Ak+ = arrayj+;for (i = low; i <= high; i+) /將暫存的數(shù)據(jù)重新填充至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 << "輸入需要排列數(shù)據(jù)的個數(shù)："cin >> n; /錄入需要排列的個數(shù)int *array = new intn;cout <<

15、 endl << "請輸入數(shù)據(jù)：" << endl;for (int i = 0; i < n; i+)cin >> arrayi; /錄入未排序的數(shù)據(jù)MergeSort(array, 0, n - 1); /進行排序cout << "排列后數(shù)據(jù)：" << endl;for (int j = 0; j < n; j+) /輸出排列結(jié)果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的數(shù)j-;if (i < j)si+ = sj;while (i < j && si < x) / 從左向右找第一個大于等于x的數(shù)i+;if (i < j)sj- = si;si = x;quickSort(s, l, i - 1); / 遞歸調(diào)用quickSort(s, i + 1, r);（8）棋盤覆蓋在一個2k×2k 個方格組成

19、的棋盤中，恰有一個方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。問題: 用4種不同形態(tài)的L型骨牌, 覆蓋給定特殊棋盤上除特殊方格以外的所有方格，且任何2個不得重疊。 特殊方格在棋盤上出現(xiàn)的位置有4k種情形。因而對任何k>=0，有4k種不同的特殊棋盤。易知，在任何一個2k * 2k的棋盤中，用到的L型骨牌個數(shù)恰為(4k -1)/3。 1) 當(dāng)k>0時，將2k×2k棋盤分割為4個2k-1×2k-1 子棋盤, Figure (a)所示。2) 特殊方格必位于4個較小子棋盤之一中，其余3個子棋盤中無特殊

20、方格。3) 為將無特殊方格子棋盤轉(zhuǎn)化為特殊棋盤，可以用一個骨牌覆蓋3個較小棋盤的會合處，如 Figure(b)所示，從而將原問題轉(zhuǎn)化為4個較小規(guī)模的棋盤覆蓋問題。4) 遞歸地使用這種分割，直至棋盤簡化為棋盤1×1。 #include<iostream>#include<iomanip> /包含設(shè)置域?qū)挼念^文件#include<stdlib.h> /標(biāo)準(zhǔn)庫using namespace std;int tile = 0;int *(*board) = NULL; /定義指向指針的指針用于動態(tài)的創(chuàng)建用于存儲骨牌號的數(shù)組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; / 分割棋盤 (注意逗號表達式的應(yīng)用) / 覆蓋左上角子棋盤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;< "請輸入要填充特殊方格的數(shù)字: " 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); /輸出結(jié)果for (int j = 0; j < zsize; j+)for (int m = 0; m < zsize; m+)cout << setw(6) << boardjm; /域?qū)挒?cout << endl;system("pause");goto p1;return 0;（9）循環(huán)賽日程表請按此要求將比賽日程表設(shè)計成有n行和n-1列的一個表。在表中的第i行，第j列處填入第i個選手在第j天所遇到的選手。其中1in，1jn-1。8個選手的比賽日程表如下圖： 算法思路：按分治策略，我

27、們可以將所有的選手分為兩半，則n個選手的比賽日程表可以通過n/2個選手的比賽日程表來決定。遞歸地用這種一分為二的策略對選手進行劃分，直到只剩下兩個選手時，比賽日程表的制定就變得很簡單。這時只要讓這兩個選手進行比賽就可以了。如上圖，所列出的正方形表是8個選手的比賽日程表。其中左上角與左下角的兩小塊分別為選手1至選手4和選手5至選手8前3天的比賽日程。據(jù)此，將左上角小塊中的所有數(shù)字按其相對位置抄到右下角，又將左下角小塊中的所有數(shù)字按其相對位置抄到右上角，這樣我們就分別安排好了選手1至選手4和選手5至選手8在后4天的比賽日程。依此思想容易將這個比賽日程表推廣到具有任意多個選手的情形。 算法步驟： 1

28、)用一個for循環(huán)輸出日程表的第一行 for(int i=1;i<=N;i+) a1i = i 2)然后定義一個m值，m初始化為1，m用來控制每一次填充表格時i（i表示行）和j（j表示列）的起始填充位置。 3)用一個for循環(huán)將問題分成幾部分，對于k=3，n=8，將問題分成3大部分，第一部分為，根據(jù)已經(jīng)填充的第一行，填寫第二行，第二部分為，根據(jù)已經(jīng)填充好的第一部分，填寫第三四行，第三部分為，根據(jù)已經(jīng)填充好的前四行，填寫最后四行。for (ints=1;s<=k;s+) N/=2; 4)用一個for循環(huán)對中提到的每一部分進行劃分for(intt=1;t<=N;t+)對于第一部分

29、，將其劃分為四個小的單元，即對第二行進行如下劃分 同理，對第二部分（即三四行），劃分為兩部分，第三部分同理。 5)最后，根據(jù)以上for循環(huán)對整體的劃分和分治法的思想，進行每一個單元格的填充。填充原則是：對角線填充 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控制的第一部分填完