算法设计与分析实验考核复习题.docx

算法设计与分析实验考核复习题.docx

《算法设计与分析实验考核复习题.docx》由会员分享，可在线阅读，更多相关《算法设计与分析实验考核复习题.docx（14页珍藏版）》请在冰点文库上搜索。

算法设计与分析实验考核复习题

1、给定已经排好序的n个元素的数组，设计二分搜索方法的递归算法。

publicclassbinarySearch{

publicstaticvoidmain（String[]args）{

int[]a={1,3,5,7,9,11,13,15};

for（inti=0;i

{System.out.println（a）;

}

intb=9;

intresult=Binary（a,b,0,a.length-1）;

if（result>0）

System.out.println（result）;

elseSystem.out.println（"沒有這個數"）;

}

publicstaticintBinary（int[]a,intb,intleft,intright）

{

if（left>right）

return-1;

intmiddle=（left+right）/2;

if（b==a[middle]）

returnmiddle;

elseif（b>a[middle]）

returnBinary（a,b,middle+1,right）;

else

returnBinary（a,b,left,middle-1）;

}

}

2、试实现n个元素的归并排序算法，并分析其效率。

import java.util.Scanner;

public class MergeSort {

public static void main（String[] args） {

int n;

Scanner in=new Scanner（System.in）;

n=in.nextInt（）;

int[] a=new int[n];

for（int i=0;i

a[i]=in.nextInt（）;

}

System.out.println（"排序前的数组：

"）;

print（a）;

mergeSort（a）; 

System.out.println（"排序后的数组：

"）;

 print（a）;}

private static void mergeSort（int[] a） {

  sort（a,0,a.length-1）;

}

private static void sort（int[] a, int left, int right） {

if（left>=right）

return ;

int middle=（left+right）/2;

sort（a, left, middle）;

sort（a,middle+1,right）;

merge（a,left,middle,right）;}

private static void merge（int[] a, int left, int middle, int right） {

int[] b=new int[a.length];

int k=middle+1;

int i=left;

int j=left;

while（（left<=middle）&&（k<=right））{

if（a[left]<=a[k]）

b[i++]=a[left++];

else{

b[i++]=a[k++];}}

while（k<=right）{

b[i++]=a[k++];}

while（left<=middle）{

b[i++]=a[left++];}

while（j<=right）{

a[j]=b[j];j++;}}

private static void print（int[] a） {

for （int i = 0; i < a.length; i++） {

System.out.print（a[i]+"\t"）;} 

System.out.println（）;}}

3、最优服务次序问题

设有n个顾客同时等待一项服务。

顾客i需要的服务时间为ti,1≤i≤n。

应如何安排n个顾客的服务次序才能使平均等待时间达到最小?

平均等待时间是n个顾客等待服务时间的总和除以n。

对于给定的n个顾客需要的服务时间，编程计算最优服务次序。

Input

第一行是正整数n，表示有n个顾客。

接下来的1行中，有n个正整数，表示n个顾客需要的服务时间。

（n<10000）

Output

将编程计算出的最小平均等待时间输出

SampleInput

10

56121991000234335599812

SampleOutput

532.00

import java.util.Scanner;

public class test3 {

static  int n;

public static void main（String[] args） {

Scanner nn=new Scanner（System.in）;

n=nn.nextInt（）;

int[] a = new int[n];

Scanner in=new Scanner（System.in）;{

 for（int i=0;i

 a[i]=in.nextInt（）;}

sort（a）;

    Q（a）;}

private static void Q（int[] b） {

int[] c=new int [n];

int m=0;float ave;

for （int i = 0; i < b.length; i++） {

for （int j = 0; j <=i; j++） {

c[i]=c[i]+b[j];}}

for （int i = 0; i < c.length; i++） {

m=m+c[i];}

ave=m/n;

System.out.println（ave）;}

private static void sort（int [] a） {

int temp;

for （int i = 0; i < a.length-1; i++） {

for （int j = i+1; j < a.length; j++） {

if（a[i]>a[j]）{

temp=a[j];

a[j]=a[i];

a[i]=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的时候表示测试结束。

Output

将编程计算出的最少加油次数输出，每个测试用例输出一行。

如果无法到达目的地，则输出"NoSolution"。

SampleInput

77

12345166

51

505

00

SampleOutput

4

NoSolution

import java.util.Scanner;

public class test4 {

public static void main（String[] args） {

int n;int k;

Scanner b=new Scanner（System.in）;

n=b.nextInt（）;k=b.nextInt（）;

int[] a = new int[k+1];

Scanner in=new Scanner（System.in）;

for （int i = 0; i <=k; i++） 

a[i]=in.nextInt（）;

int sum=0;int s;s=n;

for （int i = 0; i <=k; i++） {

if（s

System.out.println（"No Solution"）;}

for （int j = 0; j<=k-1; j++） {

s=s-a[j];if（s-a[j+1]<0）{

s=n;sum++;}

}System.out.print（"  "+sum）;}

5、最长单调递增子序列。

求一个字符串的最长递增子序列的长度：

如：

dabdbf最长递增子序列就是abdf，长度为4

输入

第一行一个整数0

随后的n行，每行有一个字符串，该字符串的长度不会超过10000

输出

输出字符串的最长递增子序列的长度

样例输入

3

aaa

ababc

abklmncdefg

样例输出

1

3

7

importjava.util.ArrayList;

importjava.util.Scanner;

publicclasstest5{

publicstaticintQ（char[]a,intn）{

inti,j,k;intt=0;

int[]b=newint[n];

for（i=1,b[0]=1;i

for（j=0,k=0;j

if（a[j]

k=b[j];}b[i]=k+1;}

for（intl=0;l

if（b[l]>t）t=b[l];}

returnt;}

publicstaticvoidmain（String[]args）{

System.out.println（"Input"）;

Scannersc=newScanner（System.in）;

intm;m=sc.nextInt（）;

for（intj=0;j

Strings1=sc.next（）;char[]arr=s1.toCharArray（）;

intt=Q（arr,arr.length）;

System.out.println（t）;}}}

6、n皇后问题

在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。

你的任务是，对于给定的N，求出有多少种合法的放置方法。

Input

共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。

Output

共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。

SampleInput

1

8

5

0

SampleOutput

1

92

10

publicclassNq{

staticintn;staticint[]x;

staticlongsum;

publicstaticlongnqueen（intnn）{

n=nn;sum=0;

x=newint[n+1];

for（inti=0;i<=n;i++）

x[i]=0;backtrack

（1）;

returnsum;}

privatestaticbooleanplace（intk）{

for（intj=1;j

if（（Math.abs（k-j）==Math.abs（x[j]-x[k]））||（x[j]==x[k]））

returnfalse;returntrue;}

privatestaticvoidbacktrack（intt）{

if（t>n）{for（inti=1;i<=n;i++）

System.out.print（x[i]+"|"）;

System.out.println（）;sum++;}

else

for（inti=1;i<=n;i++）{

x[t]=i;if（place（t））

backtrack（t+1）;}}

publicstaticvoidmain（String[]args）{

longstart=System.currentTimeMillis（）;

Nq.nqueen（15）;

longfinish=System.currentTimeMillis（）;

System.out.println（finish-start）;

System.out.println（sum）;}}

7、编辑距离

　　编辑距离，又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。

许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。

　　以上的问题可以用众所周知的动态规划解决，现在的问题是：

如果新加入一种编辑操作：

交换相邻的两个字符；求两个字符串之间的编辑距离。

Input

　　两行仅包括小写字母的长度不超过1000的字符串。

Output

　　两个字符串的编辑距离。

SampleInput

pantera

aorta

SampleOutput

4

packagecn.wk.Exam;

publicclassSeven{

publicstaticintgetDistance（Strings1,Strings2）

{intlen1=s1.length（）;

intlen2=s2.length（）;

int[][]d=newint[len1+1][len2+1];

inti=0,j=0;

for（i=0;i<=len1;i++）

d[i][0]=i;

for（j=0;j<=len2;j++）

d[0][j]=j;

for（i=1;i

for（j=1;j

{if（s1.charAt（i-1）==s2.charAt（j-1））

{cost=0;}

intdelete=d[i-1][j]+1;

intinsert=d[i][j-1]+1;

intsubstitution=d[i-1][j-1]+cost;

d[i][j]=min（delete,insert,substitution）;

}return（d[len1][len2]）;}

publicstaticintmin（intd,inti,ints）

{inttemp=0;

if（d>i）temp=i;

elsetemp=d;

returns

s:

temp;}

publicstaticvoidmain（Stringargs[]）

{Strings1="kitten";Strings2="sitting";

System.out.println（getDistance（s1,s2））;}}

8、求逆序数

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。

一个排列中逆序的总数就称为这个排列的逆序数。

现在，给你一个N个元素的序列，请你判断出它的逆序数是多少。

比如132的逆序数就是1。

输入

第一行输入一个整数T表示测试数据的组数（1<=T<=5）

每组测试数据的每一行是一个整数N表示数列中共有N个元素（2〈=N〈=1000000）

随后的一行共有N个整数Ai（0<=Ai<1000000000），表示数列中的所有元素。

数据保证在多组测试数据中，多于10万个数的测试数据最多只有一组。

输出

输出该数列的逆序数

样例输入

2

2

11

3

132

样例输出

0

1

import java.util.Scanner;

public class test8 {

public static void main（String[] args） {

int n;int temp;int sum=0;

Scanner in=new Scanner（System.in）;

n=in.nextInt（）;

int[]a=new int [n];

for （int i = 0; i < a.length; i++） 

a[i]=in.nextInt（）;

for （int i = 0; i < a.length-1; i++） {

for （int j = i+1; j 

if（a[i]>a[j]）{

temp=a[i];

a[i]=a[j];

a[j]=temp;

sum++;

}}}System.out.println（sum）;}}

9、田忌赛马

你一定听过田忌赛马的故事吧？

   如果3匹马变成1000匹，齐王仍然让他的马按从优到劣的顺序出赛，田忌可以按任意顺序选择他的赛马出赛。

赢一局，田忌可以得到200两银子，输一局，田忌就要输掉200两银子，平局的话不输不赢。

请问田忌最多能赢多少银子?

输入：

 输入包含多组测试数据,每组测试数据的第一行是一个整数n（1<=n<=1000）,表示田忌和齐王都拥有n匹马。

接下来一行是n个整数，表示田忌的马的速度，下一行也是n个整数，表示齐王的马的速度。

输入的最后以一个0表示结束。

输出：

  对每组数据，输出一个整数，表示田忌至多可以赢多少银子，如果田忌赢不了，就输出一个负数，表示田忌最少要输多少银子。

样例输入：

3 

928371 

958774 

2 

2020 

2020 

2 

2019 

2218 

0 

样例输出：

200 

0 

0

import java.util.Scanner;

public class test9 {

public static  void main（String[] args） 

{int n;

Scanner in=new Scanner（System.in）;

n=in.nextInt（）;

int[]x=new int[n];

 int[]y=new int[n];

for （int i = 0; i < n; i++） {

y[i]=in.nextInt（）;}

for （int j = 0; j < n; j++） {

x[j]=in.nextInt（）;

}int sum=0;

int k=n-1;int j=0;

for （int i = 0; i < n; i++） {

if（j>k）

break;if（x[i]>=y[j]）{

k--;sum--;

}else{j++;sum++;}

}System.out.println（200*sum）;}}

10矩阵连乘问题

给定n个矩阵{A1,A2,...,An}，考察这n个矩阵的连乘积A1A2...An。

由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序，这种计算次序可以用加括号的方式来确定。

矩阵连乘积的计算次序与其计算量有密切关系。

例如，考察计算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（1≤n≤26），表示矩阵的个数。

接下来n行，每行有一个大写字母，表示矩阵的名字，后面有两个整数a,b，分别表示该矩阵的行数和列数，其中1

第n+1行是一个矩阵连乘的表达式，由括号与大写字母组成，没有乘号与多余的空格。

如果表达式中没有括号则按照从左到右的顺序计算，输入的括号保证能够配对。

Output

对于每组数据，输出仅一行包含一个整数，即将该矩阵连乘方案需要的数乘次数。

如果运算过程中出现不满足矩阵乘法法则的情况（即左矩阵列数与右矩阵的行数不同），则输出“error”。

SampleInput

3

A10100

B1005

C550

A（BC）

SampleOutput

75000