算法分析（递归）

一、字母全排列

编写一个程序，使用递归算法输出一个一维字符数组中所有字符的全排列，假设字符都不一样。例如{‘a’,‘b’,‘c’}的全排列为(a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a)

输入 多组测试用例，每组输入一个正整数n(0<n<=26)。 输出 从a开始，连续n个字母的全排列，且每组输出之间用空格隔开。 例：输入：2 输出： ab ba

import java.util.Scanner; public class Main{ public static void main(String args[]){ Scanner reader = new Scanner(System.in); while(reader.hasNext()){ int n =reader.nextInt(); char[] a = Main.generatingStrings(n); prem(a,0,n); } } public static char[] generatingStrings(int n){ char b[] = new char[n]; for(int i=0;i<n;i++){ b[i]=(char)('a'+i); } return b; } public static void prem(char list[],int k,int n){ char t; if(k==n){ for(int i=0;i<n;i++){ System.out.print(list[i]); } System.out.println(); } for(int i=k;i<n;i++) { t=list[k]; list[k]=list[i]; list[i]=t; prem(list,k+1,n); t = list[i]; list[i] = list[k]; list[k] = t; } } }

二、九组数分数

1, 2,3…9 这九个数字组成一个分数，其值恰好为1/3，要求每个数字出现且只能出现一次，如何组合？编写程序输出所有的组合。

输出所有的结果，如果有多个，每条结果占一行。 结果的格式 : xxxx/xxxxx ，按照分子从小到大的顺序输出。

参

考字母全排列 注意：xxxx/xxxxx可能存在结果为3.89等其他小数取整为3 的结果。所以我们的判断条件是xxxx*3=xxxxx。

import java.util.Scanner; public class Main{ public static void main(String args[]){ int arr[] = new int[10]; for(int i=1;i<10;i++){ arr[i]=i; } prem(arr,1,9); } public static void prem(int list[],int k,int n){ int t; if(k==n){ if((list[1]*1000+list[2]*100+list[3]*10+list[4])*3==list[5]*10000+list[6]*1000+list[7]*100+list[8]*10+list[9]) { for(int i=1;i<=9;i++ ) { System.out.print(list[i]); if(i==4) { System.out.print("/"); } }System.out.println(); } } for(int i=n;i>=k;i--) { t=list[k]; list[k]=list[i]; list[i]=t; prem(list,k+1,n); t = list[i]; list[i] = list[k]; list[k] = t; } } }

三、数的划分

使用递归编写一个程序，求一个正整数n的所有划分个数。 输入3，输出3；输入4，输出5。

以3 为例 3=3； 3=2+1； 3=1+1+1；

以六为例 6=6； 6=5+1; 6=4+2 , 6=4+1+1; 6=3+3, 6=3+2+1,6=3+1+1+1; 6=2+2+2,6=2+2+1+1,6=2+1+1+1+1； 6=1+1+1+1+1+1；

不管是任何数字，由1相加组合而成的都只有一种可能； 我们可以把6 看作是（由1相加而成的一种可能性）+（5 的划分）；

import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner reader = new Scanner(System.in); while(reader.hasNext()){ int n= reader.nextInt(); System.out.println(q(n,n)); } } private static int q(int n, int m) { // TODO Auto-generated method stub if(n<1||m<1){ return 0;} if(n==m) { return 1+q(n,n-1);} if(n==1||m==1){ return 1;} if(m>n){ return q(n,n); } return q(n,m-1)+q(n-m,m); } }

四、二分法查找

多组数据输入，每组第一个数字为数组的长度n，然后输入n个整数，最后输入待查询的值。 输出待查询值所在的位置，如果没有找到，则返回-1。 例子 输入：3 1 2 3 2 4 0 1 3 4 2 输出：2 -1

import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner reader = new Scanner(System.in); while(reader.hasNextInt()){ int n= reader.nextInt(); int[] a = new int[n]; for(int i=0;i<n;i++){ a[i]=reader.nextInt(); } int x=reader.nextInt(); erfen(a,x,0,a.length-1); } } private static void erfen(int arr[],int n,int low,int high) { // TODO Auto-generated method stub int mid=(low+high)/2; if(low<=high){ if(n==arr[mid]){ System.out.println( mid+1);} if(n>arr[mid]){ erfen(arr,n,mid+1,high); } if(n<arr[mid]){ erfen(arr,n,low,mid-1); } }else{ System.out.println(-1);} } }