《算法分析实验二报告》由会员分享，可在线阅读，更多相关《算法分析实验二报告（6页珍藏版）》请在金锄头文库上搜索。
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 (1n2000000000)，输出对应的n的不同分解式。 例如： 输入
2、：12，输出：82. 邮局选址问题内容描述：在一个按照东西和南北方向划分成规整街区的城市里，n个居民点散乱地分布在不同的街区中。用x 坐标表示东西向，用y坐标表示南北向。各居民点的位置可以由坐标(x,y)表示。街区中任意2 点(x1,y1)和(x2,y2)之间的距离可以用数值|x1-x2|+|y1-y2|度量。居民们希望在城市中选择建立邮局的最佳位置，使n个居民点到邮局的距离总和最小。 编程任务：给定n 个居民点的位置,编程计算n 个居民点到邮局的距离总和的最小值。功能分析：输入由多组测试数据组成。 每组测试数据输入的第1 行是居民点数n，1n10000。接下来n 行是居民点的位置，每行2 个
3、整数x 和y，-10000x，y10000。对应每组输入，输出的第1 行中的数是n 个居民点到邮局的距离总和的最小值。例如：输入：5 输出：10 1 2 2 2 1 3 3 -2 3 3二、 算法过程设计.1.整数因子分解问题通过函数的定义和相关变量的定义，根据数学上整数因子的分解算法，来对程序进行设计。2. 邮局选址问题 通过题目给定的意思，可以知道其数学算法，通过调用库函数来实现程序的设计和结果的实现。 三、程序调试及结果（附截图）.1.整数因子分解问题2. 邮局选址问题四、源代码（附源代码）.1.整数因子分解问题#include#includestruct DP int num; int
4、 sum; d50000=0;int max=0;void qsort(int low,int high,struct DP key) int i=low,j=high; struct DP tag=keyi; if(ij) do while(tag.numkeyj.num & ij) j-; if(i=keyi.num & ij) i+; if(ij) keyj=keyi; j-; while(ij); keyi=tag; qsort(low,j-1,key); qsort(i+1,high,key); int dfs(int left) int i,p; int l,r,m; int co
5、unt=0; l=0; r=max; while(l1; if(dm.numleft) l=m+1; else r=m-1; p=l; if(dp.sum) return dp.sum; for(i=1;i=di.num;i+) if(left%di.num=0) count+=dfs(left/di.num); dp.sum=count; return count;int main(void) int i,j,tmp; int n; scanf(%d,&n); tmp=sqrt(n); for(i=1;i=tmp;i+) if(n%i=0) dmax.num=i; max+; dmax.nu
6、m=n/i; max+; max-; qsort(0,max,d); d0.sum=1; printf(%dn,dfs(n); return 0;2.邮局选址问题#include#include#includeint cmp( const void *a , const void *b )return *(int *)a - *(int *)b; int main()int i,a10005,b10005,n,y,x;int sum;while(scanf(%d,&n)=1)for(i=0;in;i+)scanf(%d%d,&ai,&bi);qsort(b,n,sizeof(b0),cmp);qsort(a,n,sizeof(a0),cmp);y=b(n-1)/2;x=a(n-1)/2;sum=0;for(i=0;in;i+)sum=sum+fabs(bi-y);sum=sum+fabs(ai-x);printf(%dn,sum);return 0;
