《算法设计与分析》课程实验报告-熟悉环境和递归算法

《算法设计与分析》课程实验报告专 业： 网络 工程 班 级： 1220551 学 号: 15 姓 名: 王 晓鑫 日期： 2025 年 10 月 20 日一、 实验题目熟悉环境和递归算法二、 实验目的（1）熟悉 Java 上机环境；（2）基本掌握递归算法的原理方法。三、 实验内容1、 将正整数 n 表示成一系列正整数之和： n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1,k≥1。正整数 n 的这种表示称为正整数 n 的划分.求正整数 n 的不同划分个数。 2、 设计一个递归算法生成 n 个元素{r1,r2，…，rn}的全排列.3、 Hanoi 塔问题设 a，b,c 是 3 个塔座。开始时,在塔座 a 上有一叠共 n 个圆盘,这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为 1，2，…,n,现要求将塔座 a 上的圆盘移到塔座 b 上,并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：规则 1：每次只能移动 1 个圆盘；规则 2:任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则 3：在满足移动规则 1 和 2 的前提下，可将圆盘移至 a，b，c 中任一塔座上。四、实验步骤1、 题目一(1) 问题分析正整数 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 的划分组成.(2) 算法描述 import java.util。Scanner;public class IntPartitioning ｛public static void main(String［］ args) ｛System。out。println（”请输入一个正整数:")；Scanner scanner=new Scanner（System。in）；int n=scanner。nextInt（）;System.out。println（”它的划分个数为:”+q(n，n）);}public static int q（int n，int m）{if(n〈1｜｜m<1)return 0;if(n==1|｜m==1)return 1;if(n〈m）return q(n,n）；if（n==m)return q（n,m—1）+1;return q（n，m-1）+q（n-m,m）；｝}(3) 运行结果 2...