整数因子问题
初中英语教材下载-斗茶歌
算法设计与分析实验报告
实验报告
学号：
课程名称
实验项目
姓名：
2
班级：
算法设计与分析 实验课时
整数因子问题
实验时间
大于1的正整数n可以分解为：n=x1*x2*…*xm。
例如，当n=12
时，共有8 种不同的分解式：
12=12；
12=6*2；
12=4*3；
实验目的 12=3*4；
12=3*2*2；
12=2*6；
12=2*3*2；
12=2*2*3。
编程实现对于给定的正整数n，计算n共有多少种不同的分解式。
实验环境
实验内容
（算法、程
序、步骤和
方法）
Visual C++
一、算法策略
用递归的思想解决问题。比如对12来说，第一个因子可能为
2,3,
4,6,12。将2开头的加上3开头的加4开头的加上6开头的加
上12开头的所有分解形式即可。对
2开头的，2X6=12，再递归分
解6，如此进行下去，分治的思想。
二、算法设计（步骤）
#include
long
total=0;
*主函数用来输入所要分解的整数，以及调用递归函数。*
int
main()
{
void solve(long n);
cout<<请输入整数n:
long n;
cin>>n;
solve(n);
cout<
}
*递归函数：当所得到的数等于1时，属于一种分解情况，分解总
数加一；然
后用循环依次用n对从2到n的数取余是否为0来确定
算法设计与分析实验报告
实验内容
（算法、程
序、步骤和
方法）
该数是否为该整数的一个因
子，如果为0则用该数对因子取商，然
后递归，总情况加一，最后可得出所有情况。*
void solve(long n)
{
if(n==1)
total++;
else
{
for(long i=2;i<=n;i++)
if(n%i==0)
solve(ni);
}
}
三、复杂度分析
时间复杂度：O(n^(1.5)logn)
空间复杂度为： O(n^0.5)
数据记录
和计算
结 论
输出的数据满足结论，用递归调用的动态规划法能够很好地解
（结 果） 决这个问题。
算法设计与分析实验报告
实验心得：通过这次实验，使我对递归方
法有了更深的理解，也让
我对C++编程更加熟悉，新掌握了几种编程思想，巩固了以往所学
小
结
的内容，知识点就是在这样的循环中得以加深印象，在练习中得以
加强理解。
指导老师
评 议
成绩评定：
指导教师签名：