算法分析与设计(李清勇)——分治.docx

《算法分析与设计(李清勇)——分治.docx》由会员分享，可在线阅读，更多相关《算法分析与设计(李清勇)——分治.docx（8页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、4-1 整数分解问题#include #include #define N 100int fenjie(int n);void main()int n; int count;printf(input a numbern);doscanf(%d,&n);while(n0);count=fenjie(n);printf(%d,count);int fenjie(int n)int i;int k=0;int temp=0;int aN;for(i=2;isqrt(n);i+)if(n%i=0) ak=i; k+; for(i=0;ik;i+) for(j=0;ik;i+) if(ai*aj=n)

2、printf(%d=%d*%dn,n,ai,aj); temp+; return temp;#include#includevoidsuanfa();voidzdlch(intb);voidsurt(intk);intN;/全局变量油井数ints100;/n个油井y轴坐标intsumin;/输油管道最小长度voidmain()inti;sumin=0；scanf(%d,&N);for(i=0;iN;i+)scanf(%d,&si);scanf(%d,&si);suanfa();/调用关键算法函数printf(%dn,sumin);voidsuanfa()if(N%2=0)/当油井数是偶数时su

3、rt(N/2);elsesurt(N+1)/2);/油井是奇数时voidsurt(intk)/从大到小第k个数是b调用suanfa(b)函数求出路程intj=0,b,l,m;inta=N;inti;while(j!=k)b=s0;for(i=0;i=b)b=si;l=i ;m=sl;sl=sa-1;sa-1=m;a-;j+;zdlch(b);Voidzdlch(intb)/求最小长度的总和inti;for(i=0;iN;i+)sumin=sumin+(int)fabs(b-si);4-4 麦森书问题#include#include#include#include#include usingna

4、mespacestd;intf505;/后500位数voidmul(inta)/乘以ainti,j,k,temp=0;for(i=0;i500;i+)temp=temp+fi*a;fi=temp%10;temp=temp/10;voidsub(intx)/减xf0-=x;intk=0;while(k500&fk0)fk=fk+10;fk+1-;k+;intmain()intn;while(scanf(%d,&n)!= EOF)inti,j,k;memset(f,0,sizeof(f);f0=1;/这里是分成210一段，那样就可以将乘法次数减少1/10/若还想更快，可以再分大点，比如220这样，

5、不过最好不要超过intfor(i=0;in/10;i+)mul(1024);for(i=0,k=1;in%10;i+)k=k*2;/分段后剩余的部分mul(k);sub(1);printf(%dn,int(n*log(2)/log(10)+1);/输出for(i=0,k=499;i10;i+)for(j=0;j50;j+)printf(%d,fk);k-;printf(n);4-5分治法，循环赛事日程表#include stdafx.h #include #include using namespace std; void Table(int k,int n,int *a); void inp

6、ut(int &k); void output(int *a,int n);int main()int k; input(k); int n=1;/n=2k(k=1)个选手参加比赛for(int i=1; i=k; i+)n *= 2;/根据n动态分配二维数组aint *a = new int *n+1;for(int i=0;i=n;i+)ai = new intn+1;Table(k,n,a);cout循环赛事日程表为：endl;output(a,n);/释放空间for(int i=0;i=n;i+)delete ai;delete a;return 0;void input(int &k

7、)cout请输入k值：k;void output(int *a,int n)for(int i=1; i=n; i+)for(int j=1; j=n; j+)coutaij ;coutendl;void Table(int k,int n,int *a)for(int i=1; i=n; i+)a1i=i;/设置日程表第一行int m = 1;/每次填充时，起始填充位置for(int s=1; s=k; s+)n /= 2;for(int t=1; t=n; t+)for(int i=m+1; i=2*m; i+)/控制行for(int j=m+1; j=2*m; j+)/控制列aij+(t

8、-1)*m*2 = ai-mj+(t-1)*m*2-m;/右下角等于左上角的值aij+(t-1)*m*2-m = ai-mj+(t-1)*m*2;/左下角等于右上角的值m *= 2;4-6 放苹果问题 完全一致#include1. usingnamespacestd;2. intc(int,int);3. inti=0;4. voidmain()5. intn,m,count=0;6. cincount;7. while(count-)8. cinnm;9. coutc(n,m)endl;10. 11. 12. intc(intn,intm)13. if(n=1|mn)16. returnc(

9、n,n-1);17. else18. returnc(n,m-1)+c(n-m,m); 邮局选址在一个按照东西和南北方向划分成规整街区的城市里，n个居民点散乱地分布在不同的街区中。用x坐标表示东西向，用y坐标表示南北向。各居民点的位置可以由坐标(x,y)表示。街区中任意2点(x1,y1)和(x2,y2)之间的距离可以用数值|x1-x2|+|y1-y2|度量。居民们希望在城市中选择建立邮局的最佳位置，使n个居民点到邮局的距离总和最小。给定n个居民点的位置，编程计算n个居民点到邮局的距离总和的最小值。#includeintsum(inta10001,intn)ints=0,i;for(i=0;ia

10、n/2)s+=ai-an/2;elses+=an/2-ai;returns;voidpaixu(inta10001,intn)inti,j,tem;for(i=0;in;i+)for(j=i+1;jaj)tem=ai;ai=aj;aj=tem;intmain()inti,x,y,n,ax10001,ay10001;scanf(%d,&n);for(i=0;i largest_pancake:largest_pancake = stackilargest_index = iprint print(Insert Spatula in index, largest_index, Size, largest_pancake)return largest_indexdef flip(stack, index):newStack = stack:(index + 1)newStack.reverse()newStack += stack(index + 1):return newStackstack = 1, 4, 5, 2, 3, 8, 6, 7, 9, 0printnUnsorted:print stackprint nIterating:stack = sortPancakes(stack)print nSorted:print stackprint