第一次单元章节考核(2).doc

第一次单元章节考核要求：（1）要求动态通过键盘在对话框或命令行输入，而后显示结果（输入输出用scanner或system.in），本次考试的输入不要采用JOptionPane的输入方式；（2）程序检查过后点“提交”按钮，然后关机，走人！注意：（1）严格按照输入、输出的要求，否则一律0分，补考！题目如下：1. Ackerman函数的递归实现算法。输入：输入两个数字，先输入n，后输入m。输出：Ackerman函数计算后的值。示例：输入：4 2，输出：16Ackerman函数A(n，m)定义如下：有两个独立的整型变量m、n：import java.util.Scanner;public class Four public static void main(String args) / TODO 自动生成的方法存根Scanner sc=new Scanner(System.in);int n=sc.nextInt();int m=sc.nextInt();System.out.println(ack(n,m);public static int ack(int n,int m)if(n=0&m=0)return 1;if(n=1&m=0)return 2;if(n=2&m=0)return n+2;if(n=1&m=1) return ack(ack(n-1,m),m-1); return -1;2.全排列的递归实现算法。输入：先输入要求输入的字符的个数，后依次输入（或随机生成）每个字符（不能仅仅是数字）。输出：全排列的结果。示例：输入：3 / * 2，输出：/ * 2 / 2 * * / 2 * 2 / 2 * / 2 / * R的全排列可归纳递归定义如下：import java.util.Scanner;public class Four public static void main(String args) / TODO 自动生成的方法存根Scanner sc=new Scanner(System.in);int n=sc.nextInt();String a=new Stringn;for(int i=0;in;i+)ai=sc.next();all(a,0,a.length-1);public static void all(String a,int start,int end)if(start=end)for(int i=0;i=end;i+)System.out.print(ai+ );System.out.println();elsefor(int i=start;i=end;i+)String temp=astart;astart=ai;ai=temp;all(a,start+1,end);temp=astart;astart=ai;ai=temp;3.整数划分的递归实现算法。输入：输入整数划分的整数（只输入一次，即n=m）。输出：输入整数的划分个数值。示例：输入：7，输出：15q(n,m)的如下递归关系定义如下：正整数n的划分数p(n)=q(n,n)。 import java.util.Scanner;public class Nine public static void main(String args) / TODO 自动生成的方法存根Scanner sc=new Scanner(System.in);int n=sc.nextInt();System.out.println(q(n,n);static int q(int n,int m)if(n1|m1)return 0;if(n=1|m=1)return 1;if(nm)return q(n,n);if(n=m)return q(n,n-1)+1;return q(n,m-1)+q(n-m,m);4.二分搜索的递归实现算法。输入：先输入进行二分搜索元素的个数，然后按大小依次输入（或随机生成，然后排序）每个数字，最后输入要求搜索的元素。输出：要求搜索元素的下标（下标从0开始！）。示例：输入：6 1 5 5 9 6 9 6，输出3import java.util.Arrays;import java.util.Scanner;public class Twopublic static void main(String args) / TODO 自动生成的方法存根Scanner sc=new Scanner(System.in);int s=sc.nextInt();int a=new int s;for(int i=0;istop) return -1;int mid=(start+stop)/2;if(amid=key)return mid;if(amidkey)return er(a,start,mid-1,key);return er(a,mid+1,stop,key);5.合并排序的递归实现算法。输入：先输入进行合并排序元素的个数，然后依次随机输入（或随机生成）每个数字。输出：元素排序后的结果，数字之间不加任何标识符。示例：输入：8 11 1 2 4 8 6 15 8，输出：1 2 4 6 8 8 11 15import java.util.Scanner;public class One static int b;public static void main(String args) / TODO 自动生成的方法存根Scanner sc=new Scanner(System.in);int n=sc.nextInt(); b=new intn;int a=new intn;for(int i=0;ia.length;i+)ai=sc.nextInt();MergeSort(a, 0, n-1);for(int i=0;ia.length;i+)System.out.print(ai+ );public static void MergeSort(int a,int left,int right)if(leftright) int i=(left+right)/2;MergeSort(a,left,i);MergeSort(a,i+1,right);merge(a,b,left,i,right);Copy(a,b,left,right);static void merge(int x,int y,int l,int m,int r)int i=l,j=m+1,k=l;while(i=m)&(j=r)if(xi=xj)yk+=xi+;elseyk+=xj+;while(i=m)yk+=xi+;while(j=r)yk+=xj+;static void Copy(int a,int b,int m,int n)for(int i=m;i=n;i+)ai=bi;6.快速排序的递归实现算法。输入：先输入进行合并排序元素的个数，然后依次随机输入（或随机生成）每个数字。输出：元素排序后的结果。示例：输入：8 9 1 2 4 8 6 15 8，输出：1 2 4 6 8 8 9 15import java.util.Scanner;public class Twopublic static void main(String args)Scanner sc=new Scanner(System.in);int n=sc.nextInt();int a=new intn;for(int i=0;in;i+)ai=sc.nextInt();quicsort(a,0,a.length-1);for(int i=0;in;i+)System.out.print(ai+ ); public static void quicsort(int a,int star