计算机算法设计与分析课程设计
- 格式：doc
- 大小：98.50 KB
- 文档页数：13
……………………………………………………………最新资料推荐…………………………………………………
成 绩 评 定 表
学生姓名 吴旭东 班级学号 1309010236
专 业 信息与计算科学 课程设计题目 分治法解决棋盘覆盖问题；回溯法解决数字拆分问题
评
语
组长签字：
成绩
日期
20 年 月 日
课程设计任务书 ……………………………………………………………最新资料推荐…………………………………………………
学 院 理学院 专 业 信息与计算科学
学生姓名 吴旭东 班级学号 1309010236
课程设计题目 分治法解决棋盘覆盖问题；回溯法解决数字拆分问题
实践教学要求与任务:
要求：
1．巩固和加深对基本算法的理解和运用，提高综合运用课程知识进行算法设计与分析的能力。
2．培养学生自学参考书籍，查阅手册、和文献资料的能力。
3．通过实际课程设计，掌握利用分治法或动态规划算法，回溯法或分支限界法等方法的算法的基本思想，并能运用这些方法设计算法并编写程序解决实际问题。
4．了解与课程有关的知识，能正确解释和分析实验结果。
任务：
按照算法设计方法和原理，设计算法，编写程序并分析结果，完成如下内容：
1.运用分治算法求解排序问题。
2. 运用回溯算法求解N后问题。
工作计划与进度安排:
第12周：查阅资料。掌握算法设计思想，进行算法设计。
第13周：算法实现，调试程序并进行结果分析。
撰写课程设计报告，验收与答辩。
指导教师：
201 年 月 日 专业负责人：
201 年 月 日 学院教学副院长：
201 年 月 日 ……………………………………………………………最新资料推荐…………………………………………………
I
摘要
算法分析是对一个算法需要多少计算时间和 存储空间作定量的分析。算法（Algorithm）是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在 计算机科学中，算法要用 计算机算法语言描述，算法代表用计算机解一类问题的精确、有效的方法。
分治法字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。在一个2^k*2^k的棋盘上，恰有一个放歌与其他方格不同，且称该棋盘为特殊棋盘。
回溯法的基本做法是深度优先搜索，是一种组织得井井有条的、能避免不必要重复搜索的穷举式搜索算法。数字拆分问题是指将一个整数划分为多个整数之和的问题。利用回溯法可以很好地解决数字拆分问题。将数字拆分然后回溯，从未解决问题。
关键词：分治法，回溯法，棋盘覆盖，数字拆分 ……………………………………………………………最新资料推荐…………………………………………………
II
目录
1分治法解决期盼覆问题1
1.1问题描述1
1.2问题分析1
1.3算法设计1
1.4算法实现2
1.5结果分析3
1.6算法分析4
2回溯法解决数字拆分问题6
2.1问题描述6
2.2问题分析6
2.3算法设计7
2.4算法实现7
2.5结果分析8
参考文献9
……………………………………………………………最新资料推荐…………………………………………………
1
1分治法解决期盼覆问题
1.1问题描述
在一个2k×2k（k≥0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。显然，特殊方格在棋盘中出现的位置有4k中情形，因而有4k中不同的棋盘，图（a）所示是k=2时16种棋盘中的一个。棋盘覆盖问题要求用图（b）所示的4中不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且热河亮哥L型骨牌不得重复覆盖
1.2问题分析
用分治策略，可以设计解决棋盘问题的一个简介算法。
当k>0时，可以将2^k *2^k棋盘分割为4个2^k-1 * 2^k-1子棋盘。由棋盘覆盖问题得知，特殊方格必位于4个较小的子棋盘中，其余3个子棋盘中无特殊方格。为了将3个无特殊方格的子棋盘转化为特殊棋盘可以将一个L型骨牌覆盖这3个较小棋盘的会合处，所以，这3个子棋盘上被L型覆盖的方格就成为给棋盘上的特殊方格，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归的使用这种分割，直至棋盘简化为1*1棋盘为止。
。
1.3算法设计
将2^k x 2^k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格三个子棋盘，将他们中的也假一个方格设为特殊方格。如果是：
左上的子棋盘（若不存在特殊方格）----则将该子棋盘右下角的那个方格假设为特殊方格
右上的子棋盘（若不存在特殊方格）----则将该子棋盘左下角的那个方格假设为特殊方格
左下的子棋盘（若不存在特殊方格）----则将该子棋盘右上角的那个方格假设为特殊方格
右下的子棋盘（若不存在特殊方格）----则将该子棋盘左上角的那个方格假设为特殊方格
当然上面四种，只可能且必定只有三个成立，那三个假设的特殊方格刚好构成一个L型骨架，我们可以给它们作上相同的标记。这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归算法解决。
。
……………………………………………………………最新资料推荐…………………………………………………
2
1.4算法实现
#include
int tile=1;
int board[100][100];
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
chessBoard(tr, tc, dr, dc, s);
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
chessBoard(tr+s, tc, dr, dc, 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()
{
int size;
cout<<"输入棋盘的size(大小必须是2的n次幂): "; ……………………………………………………………最新资料推荐…………………………………………………
3
cin>>size;
int index_x,index_y;
cout<<"输入特殊方格位置的坐标: ";
cin>>index_x>>index_y;
chessBoard(0,0,index_x,index_y,size);
for(int i=0;i
{
for(int j=0;j
cout<
cout<
}
}
1.5结果分析
……………………………………………………………最新资料推荐…………………………………………………
4
1.6算法分析
设T（n）是算法ChessBoard覆盖一个2^k * 2^k棋盘所需要的时间，则从算法 ……………………………………………………………最新资料推荐…………………………………………………
5
的分治策略可知，T(k)满足如下递归方程T(k) = { O(1) k=0
4T(k-1)+O（1） k>0
解得此递归方程可得T(k) = O（4^k）。由于覆盖一个2^k *2^k棋盘所需的L型
牌个数为（4^k — 1）/3,故算法ChessBoard是一个在渐进意义下最优的算法. ……………………………………………………………最新资料推荐…………………………………………………
6
2回溯法解决数字拆分问题
2.1问题描述
整数的分划问题。
如，对于正整数n=6，可以分划为：
6
5+1
4+2, 4+1+1
3+3, 3+2+1, 3+1+1+1
2+2+2, 2+2+1+1, 2+1+1+1+1
1+1+1+1+1+1+1
用户从键盘输入 n （范围1~10） 。
2.2问题分析
很明显这是一道关于数的组合的问题，但形成组合的数是有一定的限制的。仔细分析一下题目，我们可以得到以下的结论：
(1)每一组数之和必须等于n；
(2)每一组数的个数是不固定的；
(3)等式中后一个数的大小必定大于或等于前一个数，因为这样做的目的有两个：一是 能够避免等式的重复，例如
n=2 2=1+1
n=3 3=1+2 3=1+1+1
3=2+1
(
可以看出为与
1+2
是同一种拆分，因此该式子不能算
)
另一个目的是可以减少不必要的搜索，提高程序效率。
我们可以将待拆分的数对应路径图中的路口，将可拆分的数对应分叉的编号，这样对于
每个路口而言，它所拥有的分叉号是变化的，规律是：分叉的起始值取决于前一次所取数，
分叉的终止值取决于该路口数的中值。
