实验报告2.2(递归法)
学号：201208070103 姓名：陈明班级：智能1201
第16 周
课程名称算法设计与分析实验课时 2
实验项目整数因子分解问题实验时间2015年1月10日
实验目的对于给定的正整数n，计算n共有多少种不同的分解式。实验环境Eclipse Luna, Java JDK1.7, Windows 8.1
实验内容（算法、程序、步骤和方法）一、算法策略
动态规划法。把1~number的约数预先存起来，需要用得时候，直接在前面取得。
二、算法设计（步骤）
1）把number的约数全部计算出来，存储在factor数组里面。
2）使用快速排序法QuickSort把factor按升序排序
3）使用动态规划法。把0~number的分解式的个数存在recordNum数组里面。
三、复杂度分析
1）时间复杂度：首先时计算约数因子，其次是快速排序，最后是动态规划，这三步伟主要耗时。
故时间复杂T(n)=O(n)+O(n*log n)+O(k) (其中k为number 的约数个数，故为常数级别)。
故T(n)故该算法的时间复杂度为 O(n*log n)
2）空间复杂度：O(n)
1）从控制台console输入数字，java封装类Scanner获得输入流；
2）获得的数字，赋值给number
数据记录
和计算
1）number=12时：
2）number=11时：
结论
（结果）
3）number=888888时：
小结1）动态规划法相对于递归法来说，当输入规模很大时，应该考虑动态规划法；
2）进行两个种方法的对比：
Number=888888
动态规划法：
递归法：
T(动态规划)=30毫秒，T(递归策略)=263毫秒
显然，从耗时上来看，动态规划法要优于递归策略！
指导老师
评议
成绩评定：指导教师签名：
