算法分析经典算法题.doc

《算法分析经典算法题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章1.计算A+B的值：#includeintmain(){inta,b;cin>>a>>b;cout<

2、input.nextInt();intarr[]=newint[n];for(inti=0;imax){max=arr[i];}}System.out.println(max);}}第二章1.士兵站队问题在一个划分成网格的操场上，n个士兵散乱地站在网格点上。网格点由整数坐标(x,y)表示。士兵们可以沿网格边上、下、左、右移动一步，但在同一时刻任一

3、网格点上只能有一名士兵。按照军官的命令，士兵们要整齐地列成一个水平队列，即排列成(x,y),(x+1,y),…,(x+n-1,y)。如何选择x和y的值才能使士兵们以最少的总移动步数排成一列。计算使所有士兵排成一行需要的最少移动步数。输入：第1行是士兵数n，1?n?10000。接下来n行是士兵的初始位置，每行2个整数x和y，-10000《=x，y《=10000。输出：第1行中的数是士兵排成一行需要的最少移动步数。#include#include#include

4、lgorithm>usingnamespacestd;intmain(){intn;intx[10000],y[10000],z[10000];while(cin>>n){for(inti=0;i>x[i]>>y[i];sort(x,x+n);sort(y,y+n);intmidy=y[(n+1)/2-1];for(inti=0;i

5、n;i++)total+=abs(x[i]-midx)+abs(y[i]-midy);cout<

6、ssMain{publicstaticvoidmain(String[]args)throwsException{Scannerinput=newScanner(System.in);intn=input.nextInt();intarr1[]=newint[n];intarr2[]=newint[n];for(inti=0;i

7、[]=newint[2*n];intt1=0;intt2=0;for(inti=0;i<2*n;i++){if(arr1[t1]<=arr2[t2]){arr3[i]=arr1[t1];t1++;}else{arr3[i]=arr2[t2];t2++;}if(t1==n){for(intj=0;j<(2*n-t1-t2);j++){arr3[t1+t2+j]=arr2[t2+j];}break;}if(t2==n){for(intj=0;j<(2*n-t1-t2);j++){arr3[t1+t2

8、+j]=arr1[t1+j];}break;}}System.out.print(arr3[n-1]+""+arr3[n]);}}第三章1.数字三角形问题：给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。738810274445265对于给定的由n行数字组成的数字三角形，计算从三角形的顶至底的路径经过的数字和的最大值。输入：第1行是数字三角形的行数n，1≤n≤100。接下来n行是数字三角形各行中的数字。所有数字在0..9