(完整word版)实验报告格式----整数划分问题.docVIP

上机实验报告 课程名称 ：算法设计与分析 班级： 实验日期 ： 姓名 ： aina 学号 ： 指导教师： 实验名称 ：整数划分问题 实验序号： 实验成绩： 一、实验目的及要求 运用计算机语言 Java ，编写程序，解决整数划分问题 二、实验环境 WINDOWS XP ，Eclipse*** 三、实验内容 在 Java 中编程求解整数划分问题 将正整数 n 表示成一系列正整数之和， n n n ... n (其中，n n ... n 1, k 1) 1 2 k 1 2 k 正整数 n 的这种表示称为正整数 n 的划分。它的不同的划分个数称为正整数 n 的划分数，记作 p(n) 四、算法描述及实验步骤 在正整数的所有不同的划分中，将最大加数不大于的划分个数记作。可以建立 的如下递归关系。 （1） q(n,1) 1, n 1 当最大加数 n1 不大于 1 时，任何正整数 n 只有一种划分形式。即 n n 1 1 ... 1 （2） q(n,m) q(n,n), m n 最大加数 n1 实际上不能大于 n。因此， （3） q(n, n) 1 q(n, n 1) 正整数 n 的划分由 n1 n 的划分和 n1 n 1的划分组成。 （4） 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) 的递归式如下： 1 n 1, m 1 q(n, m) q(n, n) n m q(n, n 1) n m 1 q(n, m 1) q(n m, m) n m 1 由上分析，可写出如下算法： 主文件： includeiostream.h include 整数划分 .h void main() {int n; cout 输入一个整数 n=; cinn; coutq(n,n)\n; } 头文件： includeiostream.h int q(int n,int m) {if((n1)||(m1)) return 0; if((n==1)||(m==1)) 1 return 1; if(nm) return q(n,n); if(n==m) return q(n,m-1)+1; return q(n,m-1)+q(n-m,m); } 五、调试过程及实验结果 调试成功后，得到 --------------------Configuration: main - Win32 Debug-------------------- Compiling... Skipping... (no relevant changes detected) main.cpp main.obj - 0 error(s), 0 warning(s) 运行程序： 输入 6 可得如下结果： 2 输入 20 可得如下结果： 六、总结 这次实验让我学会了如何用 Java 语言编写程序解决划分问题。 七、附录（源程序清单） 主文件： includeiostream.h include 整数划分 .h void main() {int n; cout 输入一个整数 n=; cinn; coutq(n,n)\n; } 3 头文件： includeiostream.h int q(int n,int m) {if((n1)||(m1)) return 0; if((n==1)||(m==1)) return 1; if(nm) return q(n,n); if(n==m) return q(n,m-1)+1; return q(n,m-1)+q(n-m,m); } 4