《算法分析与设计》_实验指导书

《《算法分析与设计》_实验指导书》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编著说明本书是为配合《算法分析与设计实验教学大纲》而编写的上机指导，其目的是使学生消化理论知识，加深对讲授内容的理解，尤其是一些算法的实现及其应用，培养学生独立编程和调试程序的能力，使学生对算法的分析与设计有更深刻的认识。上机实验一般应包括以下几个步骤：（1）、准备好上机所需的程序。手编程序应书写整齐，并经人工检查无误后才能上机。（2）、上机输入和调试自己所编的程序。一人一组，独立上机调试，上机时出现的问题，最好独立解决。（3）、上机结束后，整理出实验报告。实验报告应包括：题目、程序清单、运行结果、对运行情况所作的分析。本书共分8～10个实验，其具体要求和步骤如下：目录实验一、C/C++环

2、境及递归算法１实验二、递归与分治策略20实验三、动态规划算法（一）24实验四、动态规划算法（二）27实验五、贪心算法（一）30实验六、贪心算法（二）32实验七、回溯法（一）35实验八、回溯算法（二）37实验九、分支限界法39实验十：随机化算法（选学）44实验二、递归与分治策略一、实验目的与要求1、进一步熟悉C/C++语言的集成开发环境；2、通过本实验加深对递归与分治策略的理解和运用；二、实验内容：1、分析并掌握“棋盘覆盖问题”的递归与分治算法示例；2、分析并掌握“二分搜索问题”的递归与分治算法示例；3、练习使用递归与分治策略求解众数问题或集合划分问题；三、实验题众数问题：给定含有N个元素的

3、多重集合S，每个元素在S中出现的次数称为该元素的重数，多重集合S中重数最大的元素称为多重集合S的众数，众数的重数称为多重集合S的重数，试求一个给定多重结合的重数和众数；例如：S={a,b,b,b,f,f,4,5}的重数是3，众数是b集合划分问题：N个元素的集合{1，2，…，N}可以划分为若干个非空集合的子集，例如，当N=4时，集合{1，2，3，4}可划分为15个不同的非空子集如下：{{1}，{2}，{3}，{4}}；{{1，2}，{3}，{4}}；{{1，3}，{2}，{4}}；{{1，4}，{2}，{3}}；{{2，3}，{1}，{4}}；{{2，4}，{1}，{3}}；{{3，4}，{

4、1}，{2}}；{{1，2}，{3，4}}；{{1，3}，{2，4}}；{{1，4}，{3，2}}；{{2，3，4}，{1}}；{{1，3，4}，{2}}；{{1，2，4}，{3}}；{{1，2，3}，{4}}；{{1，2，3，4}}；给定正整数N，计算出N个元素的集合{1，2，…，N}可以划分多少个非空集合的子集；四、实验步骤1．理解递归和分治策略的基本思想和算法示例；2．上机输入和调试算法示例程序；3．理解实验题的问题要求；4．上机输入和调试自己所编的实验题程序；5．验证并分析实验题的实验结果；6．整理出实验报告；五、递归与分治算法示例程序1、棋盘覆盖问题：在一个2k×2k个方格组成的

5、棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖；voidchessBoard(inttr,inttc,intdr,intdc,intsize)  {     if(size==1)return;     intt=tile++, //L型骨牌号       s=size/2; //分割棋盘     //覆盖左上角子棋盘     if(dr

6、,tc,dr,dc,s);     else{//此棋盘中无特殊方格        board[tr+s-1][tc+s-1]=t;//用t号L型骨牌覆盖右下角        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;//用t号L型骨牌覆盖左下角        //覆盖其余

7、方格        chessBoard(tr,tc+s,tr+s-1,tc+s,s);}       //覆盖左下角子棋盘     if(dr>=tr+s&&dc