算法分析实验二报告

《算法分析实验二报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法设计与分析》实验报告目录一、实验内容描述和功能分析.二、算法过程设计.三、程序调试及结果（附截图）.四、源代码（附源代码）.一、实验内容描述和功能分析.1.整数因子分解问题内容描述：大于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共有多少种不同的分解式。功能分析：输入一行对应1个正整数n(1≤n≤2000000000)，输出对应的n的不同分解式。

2、例如：输入：12，输出：82.邮局选址问题内容描述：在一个按照东西和南北方向划分成规整街区的城市里，n个居民点散乱地分布在不同的街区中。用x坐标表示东西向，用y坐标表示南北向。各居民点的位置可以由坐标(x,y)表示。街区中任意2点(x1,y1)和(x2,y2)之间的距离可以用数值

3、x1-x2

4、+

5、y1-y2

6、度量。居民们希望在城市中选择建立邮局的最佳位置，使n个居民点到邮局的距离总和最小。编程任务：给定n个居民点的位置,编程计算n个居民点到邮局的距离总和的最小值。功能分析：输入由多组测试数据组成。每组测试数据输入的第1行是居民点数n，1≤n≤100

7、00。接下来n行是居民点的位置，每行2个整数x和y，-10000≤x，y≤10000。对应每组输入，输出的第1行中的数是n个居民点到邮局的距离总和的最小值。例如：输入：5输出：101222133-233二、算法过程设计.1.整数因子分解问题通过函数的定义和相关变量的定义，根据数学上整数因子的分解算法，来对程序进行设计。2.邮局选址问题通过题目给定的意思，可以知道其数学算法，通过调用库函数来实现程序的设计和结果的实现。三、程序调试及结果（附截图）.1.整数因子分解问题2.邮局选址问题四、源代码（附源代码）.1.整数因子分解问题#include

8、io.h>#includestructDP{intnum;intsum;}d[50000]={0};intmax=0;voidqsort(intlow,inthigh,structDPkey[]){inti=low,j=high;structDPtag=key[i];if(i=key[i].num&&i

9、while(i>1;if(d[m].num

10、[p].sum=count;returncount;}intmain(void){inti,j,tmp;intn;scanf("%d",&n);tmp=sqrt(n);for(i=1;i<=tmp;i++){if(n%i==0){d[max].num=i;max++;d[max].num=n/i;max++;}}max--;qsort(0,max,d);d[0].sum=1;printf("%d",dfs(n));return0;}2.邮局选址问题#include#include#include

11、h>intcmp(constvoid*a,constvoid*b){return*(int*)a-*(int*)b;}intmain(){inti,a[10005],b[10005],n,y,x;intsum;while(scanf("%d",&n)==1){for(i=0;i

12、sum=sum+fabs(b[i]-y);sum=sum+fabs(a[i]-x);}printf("%d",sum)