1、算法设计与分析实验考核复习题1、给定已经排好序的n个元素的数组，设计二分搜索方法的递归算法。public class binarySearch public static void main(String args) int a=1,3,5,7,9,11,13,15; for(int i=0;i0) System.out.println(result); else System.out.println(沒有這個數); public static int Binary(inta,int b,int left,int right) if(leftright) return -1; int midd
2、le=(left+right)/2; if(b=amiddle) return middle; else if(bamiddle) return Binary(a, b, middle+1, right); else return Binary(a, b, left, middle-1); 2、试实现n个元素的归并排序算法，并分析其效率。importjava.util.Scanner;publicclassMergeSortpublicstaticvoidmain(Stringargs)intn;Scannerin=newScanner(System.in);n=in.nextInt();in
3、ta=newintn;for(inti=0;i=right)return;intmiddle=(left+right)/2;sort(a,left,middle);sort(a,middle+1,right);merge(a,left,middle,right);privatestaticvoidmerge(inta,intleft,intmiddle,intright)intb=newinta.length;intk=middle+1;inti=left;intj=left;while(left=middle)&(k=right)if(aleft=ak)bi+=aleft+;elsebi+=
4、ak+;while(k=right)bi+=ak+;while(left=middle)bi+=aleft+;while(j=right)aj=bj;j+;privatestaticvoidprint(inta)for(inti=0;ia.length;i+)System.out.print(ai+t);System.out.println();3、最优服务次序问题 设有n 个顾客同时等待一项服务。顾客i需要的服务时间为ti ,1 in。应如何安排n 个顾客的服务次序才能使平均等待时间达到最小?平均等待时间是n 个顾客等待服务时间的总和除以n。对于给定的n个顾客需要的服务时间，编程计算最优服务
5、次序。Input 第一行是正整数n，表示有n 个顾客。接下来的1行中，有n个正整数，表示n个顾客需要的服务时间。(n 10000)Output 将编程计算出的最小平均等待时间输出Sample Input1056 12 1 99 1000 234 33 55 99 812Sample Output532.00importjava.util.Scanner;publicclasstest3staticintn;publicstaticvoidmain(Stringargs)Scannernn=newScanner(System.in);n=nn.nextInt();inta=newintn;Sca
6、nnerin=newScanner(System.in);for(inti=0;in;i+)ai=in.nextInt();sort(a);Q(a);privatestaticvoidQ(intb)intc=newintn;intm=0;floatave;for(inti=0;ib.length;i+)for(intj=0;j=i;j+)ci=ci+bj;for(inti=0;ic.length;i+)m=m+ci;ave=m/n;System.out.println(ave);privatestaticvoidsort(inta)inttemp;for(inti=0;ia.length-1;
7、i+)for(intj=i+1;jaj)temp=aj;aj=ai;ai=temp;4、加油次数。一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。 对于给定的n和k(k = 1000)个加油站位置，编程计算最少加油次数。Input 有多个测试用例。每个测试用例输入数据的第一行有2 个正整数n和k，表示汽车加满油后可行驶n公里，且旅途中有k个加油站。接下来的1 行中，有k+1 个整数，表示第k个加油站与第k-1 个加油站之间的距离。第0 个加油站表示出发地，汽车已加满油。第k+1 个加油站表示目的地。当输入n，k都是0的时候表
8、示测试结束。Output 将编程计算出的最少加油次数输出，每个测试用例输出一行。如果无法到达目的地，则输出No Solution。Sample Input 7 71 2 3 4 5 1 6 65 150 50 0Sample Output 4No Solutionimportjava.util.Scanner;publicclasstest4publicstaticvoidmain(Stringargs)intn;intk;Scannerb=newScanner(System.in);n=b.nextInt();k=b.nextInt();inta=newintk+1;Scannerin=ne
9、wScanner(System.in);for(inti=0;i=k;i+)ai=in.nextInt(); intsum=0;ints;s=n;for(inti=0;i=k;i+)if(sai)System.out.println(NoSolution);for(intj=0;j=k-1;j+)s=s-aj;if(s-aj+10)s=n;sum+;System.out.print(+sum);5、最长单调递增子序列。求一个字符串的最长递增子序列的长度：如：dabdbf最长递增子序列就是abdf，长度为4输入第一行一个整数0n20,表示有n个字符串要处理随后的n行，每行有一个字符串，该字符串的
10、长度不会超过10000输出输出字符串的最长递增子序列的长度样例输入3aaaababcabklmncdefg样例输出137import java.util.ArrayList;import java.util.Scanner;public class test5 public static int Q(char a,int n)int i,j,k;int t=0;int b=new intn;for (i=1,b0=1;in;i+) for (j= 0,k=0;ji;j+) if(ajai&kbj)k=bj;bi=k+1;for (int l = 0; l t) t=bl;return t;pu
11、blic static void main(String args) System.out.println(Input);Scanner sc=new Scanner(System.in);int m;m=sc.nextInt();for (int j = 0; j m; j+) String s1=sc.next();char arr=s1.toCharArray();int t=Q(arr,arr.length);System.out.println(t);6、n皇后问题在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成4
12、5角的斜线上。你的任务是，对于给定的N，求出有多少种合法的放置方法。Input共有若干行，每行一个正整数N10，表示棋盘和皇后的数量；如果N=0，表示结束。 Output 共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。Sample Input1850Sample Output19210public class Nq static int n;static intx;static long sum;public static long nqueen (int nn)n=nn;sum=0;x=new intn+1;for (int i = 0; i = n; i+)xi=0;ba
13、cktrack(1);return sum;private static boolean place(int k) for (int j = 1; j n) for (int i = 1; i = n; i+) System.out.print(xi+|);System.out.println();sum+; elsefor (int i = 1; i = n; i+) xt=i;if (place(t) backtrack(t+1);public static void main(String args) long start=System.currentTimeMillis();Nq.nq
14、ueen(15);long finish=System.currentTimeMillis();System.out.println(finish-start);System.out.println(sum);7、编辑距离编辑距离，又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。以上的问题可以用众所周知的动态规划解决，现在的问题是：如果新加入一种编辑操作：交换相邻的两个字符；求两个字符串之间的编辑距离。Input两行仅包括小写字母的长度不超过1000的字符串。Output两个字符
15、串的编辑距离。Sample InputpanteraaortaSample Output4package cn.wk.Exam;public class Seven public static int getDistance(String s1, String s2) int len1 = s1.length(); int len2 = s2.length(); int d = new intlen1+1len2+1; int i=0, j=0; for(i=0; i=len1; i+) di0 = i; for(j=0; j=len2; j+) d0j = j; for (i = 1; i
16、len1+1; i+) for (j = 1; j i) temp = i; else temp = d; return stemp?s:temp; public static void main(String args) String s1= kitten; String s2 =sitting; System.out.println(getDistance(s1, s2); 8、求逆序数在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。现在，给你一个N个元素的序列，请你判断出它的逆序数是多少。比如
17、1 3 2 的逆序数就是1。输入第一行输入一个整数T表示测试数据的组数（1=T=5)每组测试数据的每一行是一个整数N表示数列中共有N个元素（2=N=1000000）随后的一行共有N个整数Ai(0=Ai1000000000)，表示数列中的所有元素。数据保证在多组测试数据中，多于10万个数的测试数据最多只有一组。输出输出该数列的逆序数样例输入221 131 3 2样例输出01importjava.util.Scanner;publicclasstest8publicstaticvoidmain(Stringargs)intn;inttemp;intsum=0;Scannerin=newScanne
18、r(System.in);n=in.nextInt();inta=newintn;for(inti=0;ia.length;i+)ai=in.nextInt();for(inti=0;ia.length-1;i+)for(intj=i+1;jaj)temp=ai;ai=aj;aj=temp;sum+; System.out.println(sum);9、田忌赛马你一定听过田忌赛马的故事吧？ 如果3匹马变成1000匹，齐王仍然让他的马按从优到劣的顺序出赛，田忌可以按任意顺序选择他的赛马出赛。赢一局，田忌可以得到200两银子，输一局，田忌就要输掉200两银子，平局的话不输不赢。 请问田忌最多能赢多
19、少银子?输入： 输入包含多组测试数据,每组测试数据的第一行是一个整数n(1=n=1000),表示田忌和齐王都拥有n匹马。接下来一行是n个整数，表示田忌的马的速度，下一行也是n个整数，表示齐王的马的速度。 输入的最后以一个0表示结束。输出： 对每组数据，输出一个整数，表示田忌至多可以赢多少银子，如果田忌赢不了，就输出一个负数，表示田忌最少要输多少银子。样例输入：392 83 7195 87 74220 2020 20220 1922 180样例输出：20000importjava.util.Scanner;publicclasstest9publicstaticvoidmain(Stringar
20、gs)intn;Scannerin=newScanner(System.in);n=in.nextInt();intx=newintn;inty=newintn;for(inti=0;in;i+)yi=in.nextInt(); for(intj=0;jn;j+)xj=in.nextInt();intsum=0;intk=n-1;intj=0;for(inti=0;ik)break;if(xi=yj)k-;sum-;elsej+;sum+;System.out.println(200*sum);10矩阵连乘问题给定n个矩阵A1,A2,.,An，考察这n个矩阵的连乘积A1A2.An。由于矩阵乘法
21、满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序，这种计算次序可以用加括号的方式来确定。 矩阵连乘积的计算次序与其计算量有密切关系。例如，考察计算3个矩阵A1,A2,A3连乘积的例子。设这3个矩阵的维数分别为10*100，100*5，和5*50。若按(A1A2)A3计算，3个矩阵连乘积需要的数乘次数为10*100*5+10*5*50 = 7500。若按A1(A2A3)计算，则总共需要100*5*50+10*100*50 = 75000次数乘。 现在你的任务是对于一个确定的矩阵连乘方案，计算其需要的数乘次数。 Input输入数据由多组数据组成。每组数据格式如下：第一行是一个整数n (1n26)，表示矩阵的个数。接下来n行，每行有一个大写字母，表示矩阵的名字，后面有两个整数a,b，分别表示该矩阵的行数和列数，其中1a,b100。第n+1行是一个矩阵连乘的表达式，由括号与大写字母组成，没有乘号与多余的空格。如果表达式中没有括号则按照从左到右的顺序计算，输入的括号保证能够配对。Output对于每组数据，输出仅一行包含一个整数，即将该矩阵连乘方案需要的数乘次数。如果运算过程中出现不满足矩阵乘法法则的情况（即左矩阵列数与右矩阵的行数不同），则输出“error”。 Sample Input3A 10 100B 100 5C 5 50A(BC) Sample Output75000
