算法分析实验二报告.doc

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

1、实验报告一、实验内容描述和功能分析.二、算法过程设计.三、程序调试及结果（附截图）.四、源代码（附源代码）.一、实验内容描述和功能分析.1.整数因子分解问题内容描述：大于1的正整数n可以分解为：n=xl*x2*...*xmo例如，当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(l

2、一个按照东西和南北方向划分成规整街区的城市里，n个居民点散乱地分布在不同的街区中。用x丛标表示东西启，用y坐标表示南北向。各居民点的位晝可以由坐标(x,y)表示。街区中任意2点(xl,y1)和(x2,y2)之间的距离可以用数值丨xl-x2

3、+1yl-y2

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

5、：10对应每组输入，输出的第1行中的数是n个居民点到邮局的距离总和的最小值。例如：输入：51222133-233二、算法过程设计.1.整数因子分解问题通过函数的定义和相关变量的定义，根据数学上整数因子的分解算法，来对程序进行设计。2•邮局选址问题通过题目给定的意思，可以知道其数学算法，通过调用库函数来实现程序的设计和结果的实现。三、程序调试及结果（附截图）•1•整数因子分解问题2.邮局选址问题四、源代码(附源代码).1.整数因子分解问题#include#includestructDP{intnum;intsum;}d[50000]={0};intma

6、x=O;voidqsort(intlowjnthigh,structDPkey[]){inti=lowj=high;structDPtag=key[i];{do{while(tag.num=key[i].num&&ivj)i++;{key[j]=key[i];j-s}}}while(i

7、r=max;while(l<=r){m=(l+r)»l;if(d[m].num

8、x++;d[max].num=n/i;max++;}}max—;qsort(0,max,d);d[0].sum=l;printf("%dn,dfs(n));return0;}1.邮局选址问题#include#include#inc1udeintcmp(constvoid,constvoid*b){return*(int*)a-*(int*)b;}intmain(){inti,a[l0005],b[l0005],n,y,x;intsum;while(scanf(,,%d',,&n)==1){for(i=0;i

9、nf(n%d%dH,&a[i],&b[i]);qsort(b,n,sizeof(b[0]),cmp);qsort(a,n,sizeof(a[0]),cmp);y=b[(n-1)/21;x=a[(n-l)/2];sum=0;for(i=0;i