算法分析经典算法题.doc

第一章1.计算A+B的值：#includeint 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 intn; for(int i = 0;in;i+) arri=input.nextInt(); int max = arr0; for(int i = 1;imax) max = arri; 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 行中的数是士兵排成一行需要的最少移动步数。#include#include#includeusing namespace std;int main() int n; int x10000,y10000,z10000; while(cinn) for(int i=0;ixiyi; sort(x,x+n); sort(y,y+n); int midy=y(n+1)/2-1; for(int i=0;in;i+) xi-=i; sort(x,x+n); int midx=x(n+1)/2-1; int total=0; for(int i=0;in;i+) total+=abs(xi-midx)+abs(yi-midy); couttotalendl; return 0; 2. 中位数：设X0:n-1和Y0: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 intn; int arr2 = new intn; for(int i=0;in;i+) arr1i=input.nextInt(); for(int i=0;in;i+) arr2i=input.nextInt(); int arr3 = new int2*n; int t1 = 0; int t2 = 0; for(int i = 0;i 2*n;i+) if(arr1t1=arr2t2) arr3i = arr1t1; t1+; else arr3i = arr2t2; t2+; if(t1=n) for(int j =0;j(2*n-t1-t2);j+) arr3t1+t2+j=arr2t2+j; break; if(t2=n) for(int j =0;j(2*n-t1-t2);j+) arr3t1+t2+j=arr1t1+j; break; System.out.print(arr3n-1+ +arr3n); 第三章1. 数字三角形问题：给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 对于给定的由 n行数字组成的数字三角形， 计算从三角形的顶至底的路径经过的数字和的最大值。输入：第 1 行是数字三角形的行数 n，1n100。接下来n行是数字三角形各行中的数字。所有数字在0.99之间。输出最大值#include using namespace std;const int M=100;int n;int aMM;int func()int i,j; for(i=n-1;i=1;i-) for(j=1;jai+1j+1) aij+=ai+1j; else aij+=ai+1j+1; return a11;int main() int i,j,max; cinn; for(i=1;i=n;i+) for(j=1;jaij; max=func(); coutmaxendl; return 0;2. 单调递增最长子序列：设计一个O(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。输入：第一行：n，代表要输入的数列的个数 第二行：n个数，数字之间用空格格开输出：最长单调递增子序列的长度。#include #define SIZE 1010 int main() int i, j, n, top, temp; int sSIZE; scanf(%d,&n); top = 0; s0=-1; for (i = 0; i stop) s+top = temp; else int low = 1, high = top; int mid; while(low 1; if (tempsmid) low = mid + 1; else high = mid - 1; slow = temp; printf(%dn,top); return 0; 第四章1. 会场安排问题：假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。 （这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。） 对于给定的k个待安排的活动，计算使用最少会场的时间表。输入：第一行有1 个正整数k，表示有 k个待安排的活动。接下来的k行中，每行有 2个正整数，分别表示 k个待安排的活动开始时间和结束时间。时间以0点开始的分钟计。输出最少会场数。#include #include using namespace std;int a10001,b10001; int main() int n,i,j=0; int count=0; cinn; for(i=0;iaibi; sort(a,a+n); sort(b,b+n); for(i=0;in;i+) if(aibj) count+; else j+; coutcountendl; return 0; 2. 汽车加油问题：一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。并证明算法能产生一个最优解。 对于给定的n和k个加油站位置，计算最少加油次数。输入：第一行有2 个正整数n和 k，表示汽车加满油后可行驶n公里，且旅途中有k个加油站。接下来的1 行中，有 k+1个整数，表示第 k个加油站与第k-1个加油站之间的距离。第0个加油站表示出发地，汽车已加满油。第k+1个加油站表示目的地。输出：最少加油次数。如果无法到达目的地，则输出“No Solution!”#include int main() int n,i,k; int j,flag; int a10001; int sum,p; while(scanf(%d%d,&n,&k)=2) for(i=0;i=k;i+) scanf(%d,&ai); sum = 0 ; p = n; flag = 1; for (j =0;j=k;j+) if (paj) flag = 0; break; p -= aj; if (j=k & paj+1) p = n ; sum+; if (flag=1) printf (%dn , sum); else printf (No Solution!n); return 0; 第五章1. 工作分配问题：设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij 。 设计一个算法，对于给定的工作费用，为每一个人都分配1 件不同的工作，并使总费用达到最小。输入：输入数据的第一行有1 个正整数n (1n20)。接下来的n行，每行n个数，表示工作费用。输出：最小总费用。#include#define MAX 1000;int n,c2121,v21,s,total; void backtrack(int i,int total) int j; if(total=s) return; if(in) s=total; return; else for(j=1;j=n;j+) if(vj=1) continue; if(vj=0) vj=1; backtrack(i+1,total+cij); vj=0;main() int i,j; scanf(%d,&n); for(i=1;i=n;i+) for(j=1;j=n;j+) scanf(%d,&cij); vj=0;s=MAX;backtrack(1,0);printf(%d,s);return 0;2. 用回溯法解0-1背包问题输入：第一行是物品数量n和背包总容量C 第二行是n件物品的价值 第三行是n件物品的重量输出背包的最大价值量。#includeint n,c,bestp;int p10000,w10000,x10000,bestx10000;void Backtrack(int i,int cp,int cw) int j; if(in) if(cpbestp) bestp=cp; for(i=0;i=n;i+) bestxi=xi; else for(j=0;j=1;j+) xi=j; if(cw+xi*wi=c)