实验01熟悉环境和递归算法学号：姓名：日期：[实验目的]熟悉Java上机环境;基本掌握递归算法的原理方法.[预习要求]认真阅读算法设计教材,了解递归算法原理;设计用递归算法求解阶乘函数、Ackerman函数、排列问题、整数划分问题的递归程序.[实验题]将正整数n表示成一系列正整数之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。Hanoi塔问题设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座a上的圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：规则1：每次只能移动1个圆盘；规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。[实验步骤]设计并实现算法并准备测试用例,修改并调试程序,直至正确为止;应用设计的算法和程序求解问题;将程序整理成功能模块存盘备用.[实验内容]整数划分问题正整数n的不同的划分个数称为正整数n的划分数，记作p（n）。在正整数n的所有不同的划分中，将最大加数n1不大于m的划分个数记作q（n，m）。可以建立q（n，m）的如下递归关系。q（n，1）=1，n≥1。当最大加数n1不大于1时，任何正整数n只有一种划分形式。q（n，m）=q（n，n），m≥n。最大加数n1实际上不能大于n。因此，q（1，m）=1。q（n，n）=1+q（n，n-1）。正整数n的划分由n1=n的划分和n1≤n-1的划分组成。q（n，m）=q（n，m-1）+q（n-m，m），n>m>1。正整数n的最大加数n1不大于m的划分由n1=m的划分和n1≤m-1的划分组成。据此，可设计计算q（n，m）的递归算法如下。其中，正整数n的划分数p（n）=q（n，n）。排列问题设R=｛r1，r2，…rn｝是要进行排列的n个元素，Ri=R-｛ri｝。集合X中元素的全排列记为perm（X）。（ri）perm（X）表示在全排列perm（X）的每一个排列前加上前缀ri得到的排列。R的全排列可归纳定义如下：当n=1时，perm（R）=（r），其中r是集合R中唯一的元素。当r>1时，perm（R）由（r1）perm（R1），（r2）perm（R2），...（rn）perm（Rn）构成。依次递归定义，可设计产生perm（R）的递归算法如下：Hanoi塔问题当n=1时，问题比较简单，只要将编号为1的圆盘从塔座a直接移至塔座b上即可。当n>1时，需要利用塔座c作为辅助塔座。此时若能设法将n-1个较小的圆盘依照移动规则从塔座a移至塔座c，然后，将剩下的最大圆盘从塔座a移至塔座b，最后，再设法将n-1个较小的圆盘依照移动规则从塔座c移至塔座b。由此可见，n个圆盘的移动问题可分为两次n-1个圆盘的移动问题，这又可以递归地用上述方法来做。由此可以设计出解Hanoi塔问题的递归算法如下：其中，hanoi（n，a，b，c）表示将塔座a上自上而下，由大到小叠在一起的n个圆盘依移动规则移至塔座b上并仍按同样顺序叠放。在移动过程中，以塔座c作为辅助塔座。move（a，b）表示将塔座a上的圆盘移至塔座b上。[实验结果]整数划分问题排列问题Hanoi塔问题