学 号 09770106
《算法设计与分析》
实验报告二
学专指成
生业导、
姓班教
名 刘东辉 级 师 绩
软件一班 唐国峰
电子与信息工程系 2011 年 11 月 17 日
实验二：典型算法的理解与应用
一、实验目的
本次实验是针对书上各章节所阐述的算法的相关应用练习，旨在加深学生对该部分知识的理解，提高学生运用该算法解决问题的能力。
二、实验步骤与要求
1．实验前复习课程所学知识以及阅读和理解指定的课外阅读材料； 2．学生独自完成实验指定内容；
3．实验结束后，用统一的实验报告模板编写实验报告。
4．提交说明：
（1）电子版提交说明：
a 需要提交Winrar压缩包，文件名为“《算法设计与分析》实验二_学号_姓名”， 如“《算法设计与分析》实验二_07770101_张三”。
b 压缩包内为一个“《算法设计与分析》实验二_学号_姓名”命名的顶层文件夹，
其下为两个文件夹，一个文件夹命名为“源程序”，另一个文件夹命名为“实验 报告电子版”。其下分别放置对应实验成果物。
（2）打印版提交说明：
a 不可随意更改模板样式。
b 字体：中文为宋体，大小为10号字，英文为Time New Roman，大小为10号
字。
c 行间距：单倍行距。
（3）提交截止时间：2011年11月17日16:00。
三、 实验项目
【分治策略】
1． 采用分治策略算法实现棋盘覆盖问题的求解；
2． 运用冒泡排序算法、合并排序算法、快速排序算法实现对给定数字序列的排序。
【动态规划】
1． 运用动态规划算法求解矩阵连乘问题； 2． 运用动态规划算法求解最长公共子序列问题； 3． 运用动态规划算法求解最大子段和问题； 4．运用动态规划算法求解0-1背包问题。
【贪心算法】
1． 运用贪心算法求解找零钱问题。
【回溯算法】
1． 运用回溯算法求解0-1背包问题； 2． 运用回溯算法求解4城市旅行商问题； 3． 运用回溯算法求解N后问题。
【分支限界算法】
1． 运用分支限界算法求解0-1背包问题； 2． 运用分支限界算法求解4城市旅行商问题。
【其他搜索算法】
1． 运用深度优先搜索算法求解马走棋盘问题； 2． 运用A*算法求解九宫问题。
四、 实验过程
【分治策略】
1题目分析和算法构造
在此论证算法设计中的一些必要的设计依据。
将棋盘平分四部分，一直分，知道含有特殊方格，看特殊方格在那一部分中，在延边用L型骨牌覆盖。 2算法实现
程序源代码（请写入必要的注释）。 棋盘
#include
/*****************************************************
* 参数含义：
* tr--当前棋盘左上角的行号
* tc--当前棋盘左上角的列号
* dr--当前特殊方格所在的行号
* dc--当前特殊方格所在的列号
*****************************************************/
int Board[100][100];//用来存放棋盘元素的数组 int tile=1; //L型骨牌的投放序号
void ChessBoard(int tr, int tc, int dr, int dc, int size) {
if(size==1){ //棋盘方格大小为,说明递归到最里层 return; }
int t=tile++; //每次递增 int s=size/2; //分割棋盘
if(dr else{ //不在，将该子棋盘右下角的方块视为特殊方块 Board[tr+s-1][tc+s-1]=t; ChessBoard(tr, tc, tr+s-1, tc+s-1, s); } if(dr else{ //不在，将该子棋盘左下角的方块视为特殊方块 Board[tr+s-1][tc+s]=t; ChessBoard(tr, tc+s, tr+s-1, tc+s, s); } if(dr>=tr+s && dc 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); } } void main() { int n; int size;//棋盘大小 cout<<\请输入一个数字n，将为您创建的n次方大小的棋盘：\ cin>>n; int x,y; size=(int)pow(2.0,(int)n); cout << \输入特殊方格的横坐标：\ cin >> x; cout << \输入特殊方格的纵坐标：\ cin >> y; cout << endl; ChessBoard(0,0,x,y,size); cout << \程序运行结果如下所示：\ for(int i=0;i cout << Board[i][j] << \ } cout << endl; } cout << endl; system(\} 3.运行结果 4经验归纳 棋盘覆盖的是基本思想基于分治策略，即是将棋盘平分四部分 1. 题目分析和算法构造 在此论证算法设计中的一些必要的设计依据。 N个数字来排队；两两相比小靠前；外层n-1；内层n-i-1。 2. 算法实现 程序源代码（请写入必要的注释）。
《算法设计与分析》实验二09770106刘东辉
