算法设计与分析实验报告一

《算法设计与分析》实验报告

实验一 递归与分治策略应用基础

学号：122208206101

姓名：蔡猛

班级：网络工程

日期：2013-2014学年第1学期

第九周

一、实验目的

1、理解递归的概念和分治法的基本思想

2、了解适用递归与分治策略的问题类型，并能设计相应的分治策略算法

3、掌握递归与分治算法时间空间复杂度分析，以及问题复杂性分析方法

二、实验内容

任务： 以下题目要求应用递归与分治策略设计解决方案，本次实验成绩按百分制计，完成各小题的得分如下，每小题要求算法描述准确且程序运行正确。

1、求n个元素的全排。（30分）

算法分析：用递归的方法，先将n个数分成两个部分，然后将两个部分交换位子，然后再

将这两个部分继续再分成四个部分，然后再将每个部分进行交换，然后就重复刚才的过程，直到不能再分为止，在这个过程中所产生的所有结果就是我们要求的全排列。

代码实现：

#include int n = 0;

void swap(int *a, int *b) { }

void perm(int list[], int k, int m) {

int i; if(k > 2) {

for(i = 0; i <= 2; i++)

printf(\"%d \

int m; m = *a; *a = *b; *b = m;

printf(\"\\n\"); n++;

}

else {

for(i = k; i <= 2; i++) {

swap(&list[k], &list[i]); perm(list, k + 1, 4); swap(&list[k], &list[i]);

} } }

int main() {

int list[] = {1, 2, 3,4}; perm(list, 0, 2); printf(\"total:%d\\n\ return 0;

}

2、解决一个2k*2k的特殊棋牌上的L型骨牌覆盖问题。（30分）

算法分析：用分治策略，将大的棋盘分割为下一级的棋盘，直到不能再分为止，然后再将

每一个小的棋盘填满，接着将一个一个小的棋盘再又合并成一个大的棋盘。

代码实现：

#include \"iostream\" using namespace std; int board[1025][1025]; int tile = 1;

//tr,tc棋盘左上角方格坐标， dr, dc特殊方格所在坐标， size为行数 void ChessBoard(int tr, int tc, int dr, int dc, int size) {

if(size == 1)

return;

int t = tile++; // L型骨牌号 int s = size / 2; //覆盖左上角子棋盘

if(dr < tr + s && dc < tc + s)

//特殊方格在此棋盘中

ChessBoard(tr, tc, dr, dc, s);

else{ }

//覆盖右上角子棋盘

if(dr < tr + s && dc >= tc + s)

//特殊方格在此棋盘中

//此棋盘无特殊方格，用 t 号 L 型骨牌覆盖右下角 board[tr + s - 1][tc + s - 1] = t; //覆盖其余方格

ChessBoard(tr, tc, tr + s - 1, tc + s - 1, s);

ChessBoard(tr, tc + s, dr, dc, s);

else{ }

//覆盖左下角子棋盘

if(dr >= tr + s && dc < tc + s)

ChessBoard(tr + s, tc, dr, dc, s); board[tr + s - 1][tc + s] = t;

ChessBoard(tr, tc + s, tr + s - 1, tc + s, s);

else{ }

board[tr + s][tc + 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{ }

board[tr + s][tc + s] = t;

ChessBoard(tr + s, tc + s, tr + s, tc + s, s);

int main(){ { { }

}

return 0;

}

for(j = 0; j < size; j++)

cout<tile = 1; cin>>x>>y; int size = 1<ChessBoard(0, 0, x, y, size); for(i = 0; i < size; i++) int k, x, y, i, j; while(cin>>k)

cout<3、设有n=2k个运动员要进行网球循环赛。设计一个满足要求的比赛日程表。（40分）

#include #include #include

void Table(double k, int **a) { int i, j, s, t, n = pow(2, k); for (i = 1; i <= n; i++) a[1][i] = i; int m = 1;

for (s = 1; s <= k; s++) { n /= 2;

for (t = 1; t <= n; t++)

for (i = m + 1; i <= 2 * m; i++) for (j = m + 1; j <= 2 * m; j++) {

a[i][j+(t-1)*m*2] = a[i-m][j+(t-1)*m*2-m]; a[i][j+(t-1)*m*2-m] = a[i-m][j+(t-1)*m*2]; } m *= 2; } }

printf(int **a, int n) { for(int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) printf(\" %d \printf(\"\\n\"); } }

void main() { printf(\"输入人数:\"); int n,r; scanf(\"%d\printf(\"比赛时间:\"); scanf(\"%d\

int **a = new int*[n+1]; for (int i = 0; i <= n; i++) a[i] = new int[n+1]; int k = log10(n)/log10(2); printf(\"日程表:\\n\"); int *b;

b=new int[n+1]; b[0]=0; printf(\" \");

for(int l=1;lb[1]=r++;

printf(\" %d日\}

printf(\"\\n\"); Table(k, a); printf(a, n); }

提交结果：算法设计分析思路、源代码及其分析说明和测试运行报告。

三、测试与分析 四、实验总结与体会

体会：这些题虽然能在书上找到原型，但是真正到自己做的时候发现

就算有关键代码自己还是不会，归更到底还是c/c++没有学好，所以平常需要多复习下已经学过的知识。