《算法实验经典两道题》由会员分享，可在线阅读，更多相关《算法实验经典两道题（2页珍藏版）》请在金锄头文库上搜索。
1、实验一：递归函数的设计与实现实验目的：实验目的：掌握递归函数的设计与实现方法 实验原理实验原理: : 递归函数的设计 实验步骤：实验步骤：编写程序实现教材 P12 例 2-5 整数划分问题 问题描述：问题描述：整数划分问题是将一个正整数 n 拆成一组数连加并等于 n 的形式，且这组 数中的最大加数不大于 n。 思路：思路：递归函数的声明为 int split(int n, int m);其中 n 为要划分的正整数，m 是 划分中的最大加数(当 m n 时，最大加数为 n)，1 当 n = 1 或 m = 1 时，split 的值为 1，可根据上例看出，只有一个划分 1 或 1 + 1 + 1
2、+ 1 + 1 + 1可用程序表示为 if(n = 1 | m = 1) return 1;2 下面看一看 m 和 n 的关系。它们有三种关系(1) m n在整数划分中实际上最大加数不能大于 n，因此在这种情况可以等价为 split(n, n);可用程序表示为 if(m n) return split(n, n); (2) m = n这种情况可用递归表示为 split(n, m - 1) + 1，从以上例子中可以看出，就是最大 加数为 6 和小于 6 的划分之和用程序表示为 if(m = n) return (split(n, m - 1) + 1);(3) m n这是最一般的情况，在划分的大
3、多数时都是这种情况。从上例可以看出，设 m = 4，那 split(6, 4)的值是最大加数小于 4 划分数和整数 2 的 划分数的和。因此，split(n, m)可表示为 split(n, m - 1) + split(n - m, m)实验要求：实验要求：（1）使用 C+或 TC2.0（2）上机前要有源代码或流程图。实验二：归并排序的分治策略设计实验目的实验目的：掌握使用分治策略消除递归；基本掌握分治策略的原理方法。 实验原理实验原理: : 分治策略 实验步骤：实验步骤：利用分治策略编程实现合并排序，教材 P21-22； 问题描述：问题描述：合并排序（MERGE SORT） ，是用分之策略
4、实现对 n 个元素进行排序的算法。 合并的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列，因此它 又叫归并算法。 算法思想：算法思想：基本思想是将待排序元素分成大小大致相同的两个子集合，分别对两个子 集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。方案一：假设数组 A 有 N 个元素，那么可以看成数组 A 是又 N 个有序的子序列组成，每个子序列的长度为 1，然后再两两合并，得到了一个 N/2 个长度为 2 或 1 的有序子序列，再两两合并，如此重复，值得得到一个长度为 N 的有序数据序列为止，这种排序方法称为 2路合并排序。方案二：给定 n 个元素（也叫关键字）序列 a1, ., an，将其划分为两个集合 a1, ., an/2和an/2+1, ., an。每个集合各自进行排序，归并所得的有序序列可以得到一个新的有 n 个元素的有序序列。在其中，分解操作是得到两个相同大小的集合，而归并操作将两个有序集合合二为一。实验要求：实验要求：（1）使用 C+或 TC2.0 （2）上机前要有源代码或流程图。
