2022年实验报告格式----整数划分问题 .pdf

《2022年实验报告格式----整数划分问题 .pdf》由会员分享，可在线阅读，更多相关《2022年实验报告格式----整数划分问题 .pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、上机实验报告课程名称：算法设计与分析班级：实验日期：姓名：aina学号：指导教师：实验名称：整数划分问题实验序号：实验成绩：一、实验目的及要求运用计算机语言 Java，编写程序，解决整数划分问题二、实验环境WINDOWS XP，Eclipse*三、实验内容在 Java 中编程求解整数划分问题将正整数 n 表示成一系列正整数之和，knnnn.21)1,1.(21knn，nk其中正整数 n 的这种表示称为正整数n 的划分。它的不同的划分个数称为正整数n的划分数，记作 p(n)四、算法描述及实验步骤在正整数的所有不同的划分中，将最大加数不大于的划分个数记作。可以建立的如下递归关系。（1）1,1)1,

2、(nnq当最大加数 n1 不大于 1 时，任何正整数 n 只有一种划分形式。即nn1.11（2）nmnnqmnq),(),(最大加数 n1 实际上不能大于n。因此，名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 5 页 -1（3）)1,(1),(nnqnnq正整数 n 的划分由nn1的划分和11nn的划分组成。（4）1),()1,(),(mnmmnqmnqmnq正整数 n最大加数 n1 不大于 m 的划分mn1由的划分和11mn的划分组成。以上的关系实际上给出了计算),(mnq的递归式如下：11,1),()1,()1,(1),(1),(mnmnmnmnmmnqmnqnnqnnqm

3、nq由上分析，可写出如下算法：主文件：#include#include 整数划分.h void main()int n;coutn;coutq(n,n)n;头文件：#include int q(int n,int m)if(n1)|(m1)return 0;if(n=1)|(m=1)名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 5 页 -2 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-Wi

4、n32 Debug-Compiling.Skipping.(no relevant changes detected)main.cpp main.obj-0 error(s),0 warning(s)运行程序：输入 6 可得如下结果：名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 5 页 -3 输入 20 可得如下结果：六、总结这次实验让我学会了如何用Java 语言编写程序解决划分问题。七、附录（源程序清单）主文件：#include#include 整数划分.h void main()int n;coutn;coutq(n,n)n;名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 5 页 -4 头文件：#include 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);名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 5 页 -