算法分析實验二报告.docVIP

《算法设计与分析》实验报告 目 录 实验内容描述和功能分析. 算法过程设计. 程序调试及结果（附截图）. 源代码（附源代码）. 实验内容描述和功能分析. 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的不同分解式。 例如： 输入：12，输出：8 邮局选址问题 内容描述：在一个按照东西和南北方向划分成规整街区的城市里，n个居民点散乱地分布在不同的街区中。用x 坐标表示东西向，用y坐标表示南北向。各居民点的位置可以由坐标(x,y)表示。街区中任意2 点(x1,y1)和(x2,y2)之间的距离可以用数值|x1-x2|+|y1-y2|度量。居民们希望在城市中选择建立邮局的最佳位置，使n个居民点到邮局的距离总和最小。 编程任务：给定n 个居民点的位置,编程计算n 个居民点到邮局的距离总和的最小值。 功能分析：输入由多组测试数据组成。 每组测试数据输入的第1 行是居民点数n，1≤n≤10000。接下来n 行是居民点的位置，每行2 个整数x 和y，-10000≤x，y≤10000。 对应每组输入，输出的第1 行中的数是n 个居民点到邮局的距离总和的最小值。 例如：输入：5 输出：10 1 2 2 2 1 3 3 -2 3 3 算法过程设计. 1.整数因子分解问题 通过函数的定义和相关变量的定义，根据数学上整数因子的分解算法，来对程序进行设计。 邮局选址问题 通过题目给定的意思，可以知道其数学算法，通过调用库函数来实现程序的设计和结果的实现。 三、程序调试及结果（附截图）. 1.整数因子分解问题 邮局选址问题 四、源代码（附源代码）. 1.整数因子分解问题 #includestdio.h #includemath.h struct DP { int num; int sum; } d[50000]={0}; int max=0; void qsort(int low,int high,struct DP key[]) { int i=low,j=high; struct DP tag=key[i]; if(ij) { do { while(tag.numkey[j].num ij) j--; if(ij) { key[i]=key[j]; i++; while(tag.num=key[i].num ij) i++; if(ij) { key[j]=key[i]; j--; } } }while(ij); key[i]=tag; qsort(low,j-1,key); qsort(i+1,high,key); } } int dfs(int left) { int i,p; int l,r,m; int count=0; l=0; r=max; while(l=r) { m=(l+r)1; if(d[m].numleft) l=m+1; else r=m-1; } p=l; if(d[p].sum) return d[p].sum; for(i=1;i=d[i].num