2013《计算机算法设计与分析》习题及答案_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
2013《计算机算法设计与分析》习题及答案
上传于|0|0|暂无简介
阅读已结束，如果下载本文需要使用0下载券
想免费下载更多文档？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩12页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢君，已阅读到文档的结尾了呢~~
棋盘覆盖问题算法设计与分析论文算法,分析,问题,算法设计,棋盘问题,算法分析,设计和,棋盘覆盖,算法论文
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
棋盘覆盖问题算法设计与分析论文
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer--144.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口最安全的绿色软件下载基地！
扫码浏览手机端页面
热门搜索：
您的位置：
计算机算法设计与分析第二版 pdf格式
网友评分：6.8 分
软件星级：
软件大小：8.6M
软件语言：简体中文
软件分类：文学作品
软件授权：免费软件
更新时间：
软件类别：国产软件
软件官网：/
应用平台：Win All
软件标签：
计算机算法设计与分析第二版为计算机专业核心课程算法设计与分析教材。全书以算法设计策略为知识单元，系统介绍算法设计方法与分析技巧，此版为扫描版。
内容简介：主要内容包括：算法概述、递归与分治策略、动态规划、贪心算法、回溯法、分支限界法、概率算法、线性规划与网络流、NP完全性理论与近似算法等。书中既涉及经典与实用算法及实例分析，又包括算法领域热点追踪。为突出教材的可读性和可用性，章首增加了学习要点提示，章末配有难易适度的习题，并免费提供电子课件和其他教学参考资料（包括习题解题思路提示和上机实验安排等）。任课教师可按前言中所提供的方式索取。目录章节：第1章 算法概述 1.1 算法与程序 1.2 算法复杂性分析 习题1 第2章 递归与分治策略 2.1 递归的概念 2.2 分治法的基本思想 2.3 二分搜索技术 2.4 大整数的乘法 2.5 Strassen矩阵乘法 2.6 棋盘覆盖 2.7 合并排序 2.8 快速排序 2.9 线性时间选择 2.10 最接近点对问题 2.11 循环赛日程表 习题2 第3章 动态规划 3.1 矩阵连乘问题 3.2 动态规划算法的基本要素 3.3 最长公共子序列 3.4 最大子段和 3.5 凸多边形最优三角剖分 3.6 多边形游戏 3.7 图像压缩 3.8 电路布线 3.9 流水作业调度 3.10 0-1背包问题 3.11 最优二叉搜索树 3.12 动态规划加速原理 习题3 第4章 贪心算法4.1 活动安排问题 4.2 贪心算法的基本要素 4.3 最优装载 4.4 哈夫曼编码 4.5 单源最短路径 4.6 最小生成树 4.7 多机调度问题 4.8 贪心算法的理论基础 习题4 第5章 回溯法 5.1 回溯法的算法框架 5.2 装载问题 5.3 批处理作业调度 5.4 符号三角形问题 5.5 n后问题 5.6 0-1背包问题 5.7 最大团问题 5.8 图的m着色问题 5.9 旅行售货员问题 5.10 圆排列问题 5.11 电路板排列问题 5.12 连续邮资问题 5.13 回溯法的效率分析 习题5 第6章 分支限界法 6.1 分支限界法的基本思想 6.2 单源最短路径问题 6.3 装载问题 6.4 布线问题 6.5 0-1背包问题 6.6 最大团问题 6.7 旅行售货员问题 6.8 电路板排列问题 6.9 批处理作业调度 习题6 第7章 概率算法 7．1 随机数 7．2 数值概率算法 7．2．1 用随机投点法计算 值 7．2．2 计算定积分 7．2．3 解非线性方程组 7．3 舍伍德(Sherwood)算法 7．3．1 线性时间选择算法 7．3．2 搜索有序表 7．3．3 跳跃表 7．4 拉斯维加斯(Lss Vegas)算法 7．4．1 n后问题 7．4．2 整数因子分解 7．5 蒙特卡罗(Monte Carlo)算法 7．5．1 蒙特卡罗算法的基本思想 7．5．2 主元素问题 7．5．3 素数测试 习题7 第8章 线性规划与网络流 8．1 线性规划问题和单纯形算法 8．1．1 线性规划问题及其表示 8．1．2 线性规划基本定理 8．1．3 约束标准型线性规划问题的单纯形算法 8．1．4 将一般问题转化为约束标准型 8．1．5 一般线性规划问题的2阶段单纯形算法 8．1．6 单纯形算法的描述和实现 8．1．7 退化情形的处理 8．1．8 应用举例 8．2 最大网络流问题 8．2．1 网络与流 8．2．2 增广路算法 8．2．3 预流推进算法 8．2．4 最大流问题的变换与应用 8．3 最小费用流问题 8．3．1 最小费用流 8．3．2 消圈算法 8．3．3 最小费用路算法 8．3．4 网络单纯形算法 8．3．5 最小费用流问题的变换与应用 习题8 第9章 NP完全性理论与近似算法 9．1 计算模型 9．1．1 随机存取机RAM 9．1．2 随机存取存储程序机RASP 9．1．3 图灵机 9．2 P类与NP类问题 9．2．1 非确定性图灵机 9．2．2 P类与NP类语言 9．2．3 多项式时间验证 9．3 NP完全问题 9．3．1 多项式时间变换 9．3．2 一些典型的NP完全问题 9．4 NP完全问题的近似算法 9．4．1 近似算法的性能 9．4．2 顶点覆盖问题的近似算法 9．4．3 旅行售货员问题近似算法 9．4．4 集合覆盖问题的近似算法 9．4．5 子集和问题的近似算法 习题9 附录 C++概要 1．变量、指针和引用 2．函数与参数传递 3．c++的类 4．类的对象 5．构造函数与析构函数 6．运算符重载 7．友元函数 8．内联函数 9．结构 10．联合 11．异常 12．模板 13．动态存储分配 参考文献 收起信息返回顶部
计算机算法设计与分析第二版 pdf格式
高速下载通道：其它下载通道：
有问题？ &+&
可能感兴趣的软件
（您的评论需要经过审核才能显示）
共0人参与,0条评论
87M / 简体中文 / 6.41.1M / 简体中文 / 6.41.3M / 简体中文 / 0.141.9M / 简体中文 / 0.02.0M / 简体中文 / 0.0664KB / 简体中文 / 0.01.9M / 简体中文 / 0.0
分类下载排行
01《鬼吹灯》全集下载 电子书01文学作品 / 1.3M02《世界十大禁书集》典藏版 EXE电子书02文学作品 / 4.9M03弟子规全文 txt下载03文学作品 / 10KB04《网络玄幻小说合集》典藏版 第五季04文学作品 / 40.1M05藏地密码TXT全集05文学作品 / 1.3M06明清十大禁书合集 电子书06文学作品 / 2.4M07《网络玄幻小说合集》典藏版 第六季07文学作品 / 41.5M08《网络玄幻小说合集》典藏版 第四季08文学作品 / 26.9M09《网络玄幻小说合集》典藏版 第二季09文学作品 / 41.9M10《网络玄幻小说合集》典藏版 第一季10文学作品 / 41.9M
01《鬼吹灯》全集下载 电子书01文学作品 / 1.3M02你在为谁工作 精美水晶版02文学作品 / 2.2M03中国式管理 精美完全版03文学作品 / 1.8M04《怎样说话才打动人》精美完全版04文学作品 / 1.1M05冰火魔厨 全集 电子书05文学作品 / 2.0M06《网络玄幻小说合集》典藏版 第五季06文学作品 / 40.1M07《世界十大禁书集》典藏版 EXE电子书07文学作品 / 4.9M08《网络玄幻小说合集》典藏版 第二季08文学作品 / 41.9M09读大学，究竟读什么 精美完全版09文学作品 / 1.4M10明清十大禁书合集 电子书10文学作品 / 2.4M
热门与关键
微信公众号
微信号：kuhousy
扫描二维码添加
所有软件均来自网络如有版权问题请联系我们 - 浙公网安备 47号 - 浙ICP备号
Copyright & 2004- online services. All rights reserved.
请简要描述您遇到的错误，我们将尽快予以修订《计算机算法设计与分析》习题及答案_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
《计算机算法设计与分析》习题及答案
上传于|0|0|暂无简介
阅读已结束，如果下载本文需要使用2下载券
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩7页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢C C++（17）
最近又重新上了算法课，现在想来有点汗颜，大学期间已经学习了一个学期，到现在却依然感觉只是把老师讲过的题目弄懂了，并没有学到算法的一些好的分析方法和思路，碰到一个新的问题后往往感觉很棘手，痛定思痛之后觉得还是好好再学习一遍，争取能理解透彻每种算法的思路和核心，同时也劝诫各位同行们做事要脚踏实地，不能应付老师的作业，最后吃亏的还是自己啊。
二、棋盘覆盖问题
& & & &在一个由2^k *2^k个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘
为一特殊棋盘。现有四种L型骨牌如下图所示，要用这四种骨牌覆盖棋盘上除特殊方格之外的其他所有格子，且两个L型骨牌不能相互覆盖。
三、解题思路
对于复杂问题，我们的一种常用思路是简化问题，简化到我们能一眼能看出问题的答案，这里也一样。
当k=1时，问题简化为一个2*2的棋盘的问题，由于只有四个格子，且含有一个特殊格子，这样就只能用一个对应的L型骨牌覆盖了，问题已经很简单了。
在此我们重新定义四种L型骨牌：
在棋盘中，我们采用（行，列）来表示某一个格子，因为(x,y)这种表示对图像处理的人来说是有歧义的，我们更愿意认为第一维是行，第二维是列。
假设在2*2的棋盘中，特殊格子出现在(0,0)这个位子上，则我们要使用0型骨牌覆盖其余位置，同理，假设特殊格子出现在(0,1)这个位置上，我们要用1型骨牌覆盖其余位置，更具有一般性的，假设特殊格子出现在2*2的(row,col)这个位置上，我们要使用row*2+col型骨牌覆盖其余位置，row和col都是从0开始索引的。
当k=2时，问题变成了一个4*4的棋盘问题，这个时候问题略显复杂，我们就想啊，如果可以把它变成2*2的棋盘问题多好啊，好吧，我们就把它分成四个2*2的子棋盘，对于那个有特殊的格子的2*2子棋盘，很快变可以解决，剩下的三个呢？让我们画出图好好看看。
假设特殊格子出现在(0,2)这个位置，如图3所示，那么对于含有特殊格子的右上角的子棋盘我们用0型骨牌填充，如图4。那么剩余的三个子棋盘呢，这个时候我们发现左上角只能覆盖3型和2型，其他两种会有剩余空格，如果覆盖2型骨牌，后面的左下角必然无法完全覆盖（自己可以试一下），则只能使用3型骨牌覆盖，以此类推，我们也可以覆盖左下角和右下角此时只剩三个格子没有覆盖，如图5所示。现在仔细观测剩余的三个格子，我们发现他们都是分开在三个子棋盘里，那么这些空格子在子棋盘中是无法直接被覆盖的，因为每个子棋盘只剩一个空格子了，我们是不是可以把这个空格子当成一个特殊格子，这样四个子棋盘都是含有一个特殊格子的小棋盘，这样原问题就变成了四个同样的子问题，再求解了每个子棋盘后，我们再对三个假的子棋盘格子进行覆盖（如图6）。
那么如何选择空格作为子棋盘的特殊格子呢，通过观察我们发现，对于含有特殊格子的子棋我们不用指定特殊格子，对于剩下三个子棋盘，我们指定四个子棋盘的交界处的格子作为特殊格子。
现在我们归纳总结一下我们的解题方案：首先将大棋盘四等分分成四个2^(k-1)*2^(k-1)的子棋盘，然后对没有特殊格子的子棋盘指定假的特殊格子的位置，将原问题分解成四个子问题进行求解，当然四个子问题可能还不能直接求解，可能还有继续递归求解，假设已经求解了四个子问题，我们应该用特定的L型骨牌覆盖三个假的特殊格子，至此整个大棋盘已经求解完成。
我们会想整个求解过程，首先把问题简化，简化到直接看出答案的地步，然后分析稍微复杂一点的情况，总结规律，运用分治的思想，将问题化解成四个子问题，分别求解四个子问题，在求解子问题的过程中可能还会有子问题，不断的递归求解，最终每个子问题解决，大问题也解决。
五、代码实现
#include &iostream&
#include&memory.h&
int **chessB
int length=0;
int blueRow=-1;
int blueCol=-1;
void init();
void fillBoard(int **_chessBoard,int r,int c,int type);
void fillChessBoard(int **_chessBoard,int k,int blue_row,int blue_col,int baseRow,int baseCol);
void output(int **_chessBoard);
int main()
fillChessBoard(chessBoard,k,blueRow,blueCol,0,0);
output(chessBoard);
for(int i=0;i&i++)
delete [] chessBoard[i];
delete chessB
void init()
cout&&&please input number k:&&&
cout&&&please input blue grid coordinate:row column&&&
cin&&blueRow&&blueC
length=(1&&k);//长和宽均为2^k
//动态分配2^k数组
chessBoard=new int*[length];
for(int i=0;i&i++)
chessBoard[i]=new int[length];
//初始化为-1
memset(chessBoard[i],-1,length*sizeof(int));
chessBoard[blueRow][blueCol]=4;
void output(int **_chessBoard)
for(int i=0;i&i++)
for(int j=0;j&j++)
cout&&& &&&_chessBoard[i][j];
void fillBoard(int **_chessBoard,int r,int c,int type)
for(int i=0;i&2;i++)
for(int j=0;j&2;j++)
if((i*2+j)!=type)
if(_chessBoard[r+i][c+j]!=-1)
cout&&&error&&&
_chessBoard[r+i][c+j]=
void fillChessBoard(int **_chessBoard,int level,int blue_row,int blue_col,int baseRow,int baseCol)
if(level==1)
int type=(blue_row&&1)+blue_
fillBoard (_chessBoard,baseRow,baseCol,type);
//否则进行四等分，中间连接处自行填充
//新的四分格的宽度
int new_length=1&&(level-1);
int type=(blue_row/new_length)*2+blue_col/new_
for(int r=0;r&2;r++)
for(int c=0;c&2;c++)
if((r*2+c)==type)
fillChessBoard (_chessBoard,level-1,blue_row-r*new_length,blue_col-c*new_length,r*new_length+baseRow,c*new_length+baseCol);
fillChessBoard (_chessBoard,level-1,(new_length-1)*(1-r),(new_length-1)*(1-c),r*new_length+baseRow,c*new_length+baseCol);
fillBoard (_chessBoard,baseRow+new_length-1,baseCol+new_length-1,type);
六、代码解释
程序输入为棋盘大小的参数k、特殊格子的行和列，输出为整个棋盘，我们用4表示特殊格子，0-3分别表示0-3型的L型骨牌。fillBoard()函数是使用某种L型骨牌覆盖棋盘的函数。fillChessBoard()是递归求解整个问题的函数，输入为棋盘指针，参数level也就是k，blue_row,blue_col是特殊格子在子棋盘的坐标系的位置，baseRow和baseCol是子棋盘的(0,0)点在整个的大棋盘中的坐标。
持续跟新中，敬请关注
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：54817次
排名：千里之外
原创：35篇
转载：31篇
(2)(1)(1)(1)(3)(1)(7)(1)(1)(2)(2)(5)(5)(3)(1)(4)(7)(15)(3)(1)