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

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

《计算机算法设计与分析课程设计.docx》由会员分享，可在线阅读，更多相关《计算机算法设计与分析课程设计.docx（11页珍藏版）》请在冰点文库上搜索。

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

成绩评定表

学生姓名

吴旭东

班级学号

1309010236

专业

信息与计算科学

课程设计题目

分治法解决棋盘覆盖问题；回溯法解决数字拆分问题

评

语

组长签字：

成绩

日期

20年月日

课程设计任务书

学院

理学院

专业

信息与计算科学

学生姓名

吴旭东

班级学号

1309010236

课程设计题目

分治法解决棋盘覆盖问题；回溯法解决数字拆分问题

实践教学要求与任务:

要求：

1．巩固和加深对基本算法的理解和运用，提高综合运用课程知识进行算法设计与分析的能力。

2．培养学生自学参考书籍，查阅手册、和文献资料的能力。

3．通过实际课程设计，掌握利用分治法或动态规划算法，回溯法或分支限界法等方法的算法的基本思想，并能运用这些方法设计算法并编写程序解决实际问题。

4．了解与课程有关的知识，能正确解释和分析实验结果。

任务：

按照算法设计方法和原理，设计算法，编写程序并分析结果，完成如下内容：

1.运用分治算法求解排序问题。

2.运用回溯算法求解N后问题。

工作计划与进度安排:

第12周：

查阅资料。

掌握算法设计思想，进行算法设计。

第13周：

算法实现，调试程序并进行结果分析。

撰写课程设计报告，验收与答辩。

指导教师：

201年月日

专业负责人：

201年月日

学院教学副院长：

201年月日

摘要

算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。

算法（Algorithm）是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。

在计算机科学中，算法要用计算机算法语言描述，算法代表用计算机解一类问题的精确、有效的方法。

分治法字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

在一个2^k*2^k的棋盘上，恰有一个放歌与其他方格不同，且称该棋盘为特殊棋盘。

回溯法的基本做法是深度优先搜索，是一种组织得井井有条的、能避免不必要重复搜索的穷举式搜索算法。

数字拆分问题是指将一个整数划分为多个整数之和的问题。

利用回溯法可以很好地解决数字拆分问题。

将数字拆分然后回溯，从未解决问题。

关键词：

分治法，回溯法，棋盘覆盖，数字拆分

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^kx2^k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格三个子棋盘，将他们中的也假一个方格设为特殊方格。

如果是：

左上的子棋盘（若不存在特殊方格）----则将该子棋盘右下角的那个方格假设为特殊方格

右上的子棋盘（若不存在特殊方格）----则将该子棋盘左下角的那个方格假设为特殊方格

左下的子棋盘（若不存在特殊方格）----则将该子棋盘右上角的那个方格假设为特殊方格

右下的子棋盘（若不存在特殊方格）----则将该子棋盘左上角的那个方格假设为特殊方格

当然上面四种，只可能且必定只有三个成立，那三个假设的特殊方格刚好构成一个L型骨架，我们可以给它们作上相同的标记。

这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归算法解决。

。

1.4算法实现

#include

inttile=1;

intboard[100][100];

voidchessBoard（inttr,inttc,intdr,intdc,intsize）

{

if（size==1）

return;

intt=tile++;

ints=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）;

}

}

intmain（）

{

intsize;

cout<<"输入棋盘的size（大小必须是2的n次幂）:

";

cin>>size;

intindex_x,index_y;

cout<<"输入特殊方格位置的坐标:

";

cin>>index_x>>index_y;

chessBoard（0,0,index_x,index_y,size）;

for（inti=0;i

{

for（intj=0;j

cout<

cout<

} 

}

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

#include

voidsplitN（intn,intm）;//n是需要拆分的数，m是拆分的进度。

intx[1024]={0},total=0;//total用于计数拆分的方法数，x[]用于存储解

intmain（）

{

intn;

printf（"pleaseinputthenaturalnumbern:

"）;

scanf（"%d",&n）;

splitN（n,1）;

printf（"Thereare%dwaystosplitnaturalnumber%d.\n",total,n）;

system（"PAUSE"）;

return0;

}

voidsplitN（intn,intm）

{//n是需要拆分的数，m是拆分的进度。

intrest,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

{

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]MarkMichaelis．C#本质论．第四版．人民邮电出版社．2014

[3]MoreWindows．白话经典算法之七大排序．第二版

[4]王晓东．计算机算法设计与分析．第四版．电子工业出版社．2013