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

编 著 说 明 本书是为配合《算法分析与设计实验教学大纲》而编写的上机指导，其目的是使学生消化理论知识，加深对讲授内容的理解，尤其是一些算法的实现及其应用，培养学生独立编程和调试程序的能力，使学生对算法的分析与设计有更深刻的认识。 上机实验一般应包括以下几个步骤： （1）、准备好上机所需的程序。手编程序应书写整齐，并经人工检查无误后才能上机。 （2）、上机输入和调试自己所编的程序。一人一组，独立上机调试，上机时出现的问题，最好独立解决。 （3）、上机结束后，整理出实验报告。实验报告应包括：题目、程序清单、运行结果、对运行情况所作的分析。 本书共分8～10个实验，其具体要求和步骤如下： 目 录 实验一、C/C++环境及递归算法 １ 实验二、递归与分治策略 20 实验三、动态规划算法（一） 24 实验四、动态规划算法（二） 27 实验五、贪心算法（一） 30 实验六、贪心算法（二） 32 实验七、回溯法（一） 35 实验八、回溯算法（二） 37 实验九、分支限界法 39 实验十：随机化算法（选学） 44 实验二、递归与分治策略 一、实验目的与要求 1、进一步熟悉C/C++语言的集成开发环境； 2、通过本实验加深对递归与分治策略的理解和运用； 二、实验内容： 1、分析并掌握“棋盘覆盖问题”的递归与分治算法示例； 2、分析并掌握“二分搜索问题”的递归与分治算法示例； 3、练习使用递归与分治策略求解众数问题或集合划分问题； 三、实验题 众数问题：给定含有N个元素的多重集合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 }，{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 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖； void chessBoard(int tr, int tc, int dr, int dc, int size) ?? { ????? if (size == 1) return; ????? int t = tile++,? // L型骨牌号 ??????? 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; // 用 t 号L型骨牌覆盖右下角 ???????? 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][t