计算机算法设计与分析课程设计.doc

成 绩 评 定 表
学生姓名
吴旭东
班级学号
36
专 业
信息与计算科学
课程设计题目
分治法解决棋盘覆盖问题；回溯法解决数字拆分问题
评
语
组长签字：

成绩

日期
20 年 月 日

课程设计任务书
学 院
理学院
专 业
信息与计算科学
学生姓名
吴旭东
班级学号
1309010236
课程设计题目
分治法解决棋盘覆盖问题；回溯法解决数字拆分问题
实践教学要求与任务:
要求：
1．巩固与加深对基本算法得理解与运用，提高综合运用课程知识进行算法设计与分析得能力。
2．培养学生自学参考书籍，查阅手册、与文献资料得能力。
3．通过实际课程设计，掌握利用分治法或动态规划算法，回溯法或分支限界法等方法得算法得基本思想，并能运用这些方法设计算法并编写程序解决实际问题。
4．了解与课程有关得知识，能正确解释与分析实验结果。
任务：
按照算法设计方法与原理，设计算法，编写程序并分析结果，完成如下内容：
1、 运用分治算法求解排序问题。
2、 运用回溯算法求解N后问题。
工作计划与进度安排:
第12周：查阅资料。掌握算法设计思想，进行算法设计。
第13周：算法实现，调试程序并进行结果分析。
撰写课程设计报告，验收与答辩。

指导教师：
201 年 月 日
专业负责人：
201 年 月 日
学院教学副院长：
201 年 月 日

摘要
算法分析就是对一个算法需要多少计算时间与 存储空间作定量得分析。算法（Algorithm）就是解题得步骤，可以把算法定义成解一确定类问题得任意一种特殊得方法。在 计算机科学中，算法要用 计算机算法语言描述，算法代表用计算机解一类问题得精确、有效得方法。
分治法字面上得解释就是“分而治之”，就就是把一个复杂得问题分成两个或更多得相同或相似得子问题，再把子问题分成更小得子问题……直到最后子问题可以简单得直接求解，原问题得解即子问题得解得合并。在一个2^k*2^k得棋盘上，恰有一个放歌与其她方格不同，且称该棋盘为特殊棋盘。
回溯法得基本做法就是深度优先搜索，就是一种组织得井井有条得、能避免不必要重复搜索得穷举式搜索算法。数字拆分问题就是指将一个整数划分为多个整数之与得问题。利用回溯法可以很好地解决数字拆分问题。将数字拆分然后回溯，从未解决问题。
关键词：分治法，回溯法，棋盘覆盖，数字拆分
目录
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问题描述
在一个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型骨架，我们可以给它们作上相同得标记。这样四个子棋盘就分别都与原来得大棋盘类似，我们就可以用递归算法解决。
。
1、4算法实现
#include<iostream、h>
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<tr+s && dc<tc+s)
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<tr+s && dc>=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<tc+s)
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次幂): ";
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<size;i++)
{
for(int j=0;j<size;j++)
cout<<board[i][j]<<"\t";
cout<<endl; 
} 
}
1、5结果分析

1、6算法分析
设T（n）就是算法ChessBoard覆盖一个2^k * 2^k棋盘所需要得时间，则从算法
得分治策略可知，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就是一个在渐进意义下最优得算法、
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
就是同一种拆分，因此该式子不能算
) 
另一个目得就是可以减少不必要得搜索，提高程序效率。

我们可以将待拆分得数对应路径图中得路口，将可拆分得数对应分叉得编号，这样对于
每个路口而言，它所拥有得分叉号就是变化得，规律就是：分叉得起始值取决于前一次所取数，
分叉得终止值取决于该路口数得中值。

2、3算法设计
在进行算法设计时我们必须要注意两点： 
一就是本问题需要解决如何记录某一路径中可取数得问题，为了解决这一问题，本程序加入了一个新得数组b，用来记录每一步所取得数。 
二就是当某一条路走完以后，我们必须回到某一个路口，而路口得值始终保持原来得数， 因此在递归调用中我们所使用得实际参数应就是独立得。本例中使用得就是形式参数m，实际参数就是a [ k ]，这样无论在某一级中a[k]得值怎样变化，m得值就是始终不变得。
2、4算法实现
#include<stdio、h>
#include<stdlib、h>
void splitN(int n,int m);//n就是需要拆分得数，m就是拆分得进度。
int x[1024]={0},total=0 ;//total用于计数拆分得方法数，x[]用于存储解
int main()
{
int n ;
printf("please input the natural number n:");
scanf("%d",&n);
splitN(n,1);
printf("There are %d ways to split natural number %d、\n",total,n);
system("PAUSE");
return 0 ;
}
void splitN(int n,int m)
{//n就是需要拆分得数，m就是拆分得进度。
int rest,i,j;
for(i=1;i<=n;i++)
{//从1开始尝试拆分。
if(i>=x[m-1])
{//拆分得数大于或等于前一个从而保证不重复
x[m]=i ;//将这个数计入结果中。
rest=n-i ;//剩下得数就是n-i，如果已经没有剩下得了，并且进度(总得拆分个数)大于1，说明已经得到一个结果。
if(rest==0&&m>1)
{
total++;
printf("%d\t",total);
for(j=1;j<m;j++)
{
printf("%d+",x[j]);
}
printf("%d\n",x[m]);
}
else
{
splitN(rest,m+1);//否则将剩下得数进行进度为m+1拆分。
}
x[m]=0;//取消本次结果，进行下一次拆分。环境恢复，即回溯
}
}
}
2、5结果分析

参考文献
[1] 张子阳．、NET之美．第一版．机械工业出版社．2014
[2] Mark Michaelis．C#本质论．第四版．人民邮电出版社．2014
[3] MoreWindows．白话经典算法之七大排序．第二版
[4] 王晓东．计算机算法设计与分析．第四版．电子工业出版社．2013