算法分析经典算法题.docVIP

第一章 1.计算A+B的值： #includeiostream.h int main() { int a,b; cinab; couta+bendl;} 2.输入n个整数，找最大值：第一行为整数n，表示n个数。第二行输入n个整数。输出最大值 import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner input = new Scanner(System.in); int n = input.nextInt(); int arr[]=new int[n]; for(int i = 0;in;i++){ arr[i]=input.nextInt();} int max = arr[0]; for(int i = 1;in;i++){ if(arr[i]max){ max = arr[i];}} System.out.println(max);}} 第二章 1.士兵站队问题 在一个划分成网格的操场上，n个士兵散乱地站在网格点上。网格点由整数坐标(x,y)表示。士兵们可以沿网格边上、下、左、右移动一步，但在同一时刻任一网格点上只能有一名士兵。按照军官的命令，士兵们要整齐地列成一个水平队列，即排列成 (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 行中的数是士兵排成一行需要的最少移动步数。 #includeiostream #includecmath #includealgorithm using namespace std; int main() { int n; int x[10000],y[10000],z[10000]; while(cinn) { for(int i=0;in;i++) cinx[i]y[i]; sort(x,x+n); sort(y,y+n); int midy=y[(n+1)/2-1]; for(int i=0;in;i++) x[i]-=i; sort(x,x+n); int midx=x[(n+1)/2-1]; int total=0; for(int i=0;in;i++) total+=abs(x[i]-midx)+abs(y[i]-midy); couttotalendl;} return 0; } 中位数：设X[0:n-1]和Y[0:n-1]为两个数组，每个数组中含有n个已排好序的数。试设计一个O（logn）时间算法，找出X和Y的2n个数的中位数。 输入：第一行： n，为x和y数组的元素个数 第二行： x数组的n个数，用空格分隔 第三行： y数组的n个数，用空格分隔 输出：中位数两个，用空格分隔 import java.util.Scanner; public class Main{ public static void main(String[] args)throws Exception{ Scanner input = new Scanner(System.in); int n = input.nextInt(); int arr1[] = new int[n]; int arr2[] = new int[n]; for(int i=0;in;i++){ arr1[i]=input.nextInt();} for(int i=0;in;i++){ arr2[i]=input.nextInt();} int arr3[] = new int[2*n]; int t1 = 0; int t2 = 0