算法实验指导书12级.doc

算法设计与分析实验指导书本实验指导书是为配合算法设计与分析课程实验而编写的，其目的是使学生消化算法理论知识，加深对课堂讲授内容的理解，尤其是一些典型算法的实现及其应用，培养学生独立编程和调试程序的能力，使学生对算法的设计与分析有更深刻的认识。一、上机实验应遵循以下步骤：（1）实验前，先准备好上机所需的程序。手编程序应书写整齐，并经自我检查无误后才能上机。（2）实验时，输入并调试自己所编的程序，独立上机调试，上机时出现的问题，最好能自己独立解决。（3）实验结束后，按照规定整理出实验报告，并在规定时间内提交。二、实验报告的内容：实验报告应该包括：实验名称、实验目的、实验题目、问题分析、程序清单、运行结果、实验结论（即算法的时间空间分析与改进建议）。三、需写出实验报告的实验：实验一、实验四、实验五。实验一 递归与迭代算法一、实验目的与要求1、 通过本实验掌握迭代算法和递归算法的基本思想及设计工作的主要步骤。2、 通过本实验加深对循环和递归过程的理解。3、 通过本实验加深对迭代过程的理解。4、 掌握两种算法策略的主要适用范围。二、实验题目：1、求2+22+222+2222（精确计算） n个22、从键盘输入任一正整数n（n=3），打印如下图所示的nn方阵（下图中n=7）。 1 2 3 4 5 6 7 24 25 26 27 28 29 823 40 41 42 43 30 922 39 48 49 44 31 1021 38 47 46 45 32 1120 37 36 35 34 33 12 19 18 17 16 15 14 133、完成给“余”猜数的游戏：心里先想好一个1100之间的整数x，然后输入3个除数a、b、c，再输入x分别除以a、b、c后所得到的余数ra、rb、rc，计算机能求出这个数x并输出x。4、用递归函数判断字符串str是否为“回文”。三、实验步骤1、 理解算法思想和问题要求。2、 编程实现题目要求。3、 上机输入和调试自己所编的程序。4、 验证分析实验结果。5、 按照规定格式撰写出实验报告（仅就1、3、4题写出实验报告）。实验二 分治算法一、实验目的与要求1、掌握分治法的基本设计思想；2、掌握分治法的适用范围。二、实验内容：1、给定线形序列集中n个元素和一个整数k，1kn，输出这n个元素中第k小元素的值及其位置。2、利用分治法求数列的最大子段和，改进教材上例15算法，记录问题的起始点和终止点。3、设a0:n-1是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。4、利用分治法求一组数据的和。四、实验步骤1、理解算法思想和问题要求。2、编程实现题目要求。3、上机输入和调试自己所编的程序。4、验证分析实验结果。实验三 贪婪算法一、实验目的与要求1、掌握贪婪算法的基本思想及设计框架；2、了解贪婪算法的主要适用范围及贪婪策略的选择。二、实验内容：1、键盘输入一个高精度的正整数n，去掉其中任意s个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n和s，寻找一种方案使得剩下的数字组成的新数最小。注意：利用教材例19（P154）中的算法设计1中介绍的第二种删除字符方式实现。2、54张扑克牌，两个人轮流拿牌，每人每次最少取1张，最多取4张，谁拿最后一张谁输。编写模拟计算机先拿牌且必胜的算法。3、最佳浏览路线问题。（教材P190，第11题）四、实验步骤1 理解算法思想和问题要求。2 编程实现题目要求。3 上机输入和调试自己所编的程序。4 验证分析实验结果。实验四 动态规划算法一、实验目的与要求1、掌握动态规划算法的基本思想及设计的框架；2、掌握动态规划算法的基本步骤。2、掌握动态规划算法的主要适用范围。二、实验内容：掌握动态规划算法的概念和基本思想。二、实验题：1、 编写求组合数（）的算法。2、 求一个数列的最长不下降子序列。要求用递归机制实现。3、 某工业生产部门根据国家计划的安排，拟将某种高效率的五台机器，分配给所属的A，B，C三个工厂，各工厂若获得这种机器后，可以为国家盈利如下表，问：这五台机器如何分配给各工厂，才能使国家盈利最大? 单位：万元 P SABC000013542710639111141211125131112 其中：p为盈利，s为机器台数。4、 有一个由数字1，2，.，9组成的数字串(长度不超过200)，问如何M(1=M=20)个加号插入这个数字串中，使得所形成的算术表达式的值最小。注意：(1)加号不能加在数字串的最前面或最末尾，也不应有两个或两个以上的加号相邻; (2)M保证小于数字串的长度。例如：数字串79846，若需加入两个加号，则最佳方案是79+8+46，算术表达式的值是133。输入格式：从键盘读入输入文件名。数字串在输入文件的第一行行首(数字串中间无空格且不换行)，M的值在输入文件的第二行行首。输出格式：在屏幕上输出最小的和。四、实验步骤1 理解算法思想和问题要求；2 编程实现题目要求；3 上机输入和调试自己所编的程序；4 验证分析实验结果；5 按照规定格式撰写出实验报告（仅就1、2、3题写出实验报告）。实验五 回溯法一、实验目的与要求1、掌握回溯算法的基本思想及设计框架；2、了解回溯算法的主要适用范围。二、实验内容：1、马的遍历。在n*m的棋盘中，马只能走日字。马从位置(x,y)处出发，把棋盘的每一点都走一次，且只走一次，找出所有路径。2、素数环问题。把从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。要求使用排列树搜索方法解决。3、输出自然数1到n所有不重复的排列，即n的全排列。4、旅行售货员问题：某售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。他要选定一条从驻地出