《算法设计与分析》实验二09770106刘东辉

学 号 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 #include using namespace std;

/*****************************************************

* 参数含义：

* 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=tc+s){ //检查特殊方块是否在右上角子棋盘中 ChessBoard(tr, tc+s, dr, dc, s); }

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. 算法实现

程序源代码（请写入必要的注释）。