预备练习（一）
字母的全排列问题：
1 package package1; 2 3 //对字母进行全排列 4 import java.util.*; 5 6 public class A1 { 7 8 static List f(String s) { 9 List lst = new Vector(); 10 11 // 出口 12 if (s.length() == 1) { 13 lst.add(s); 14 return lst; 15 } 16 17 // 下面是递归的相似性 18 /* Vector非常类似ArrayList，但是Vector是同步的。 */ 19 for (int i = 0; i < s.length(); i++) { 20 char x = s.charAt(i); 21 /* charAt() 方法用于返回指定索引处的字符。索引范围为从 0 到 length() - 1。 */ 22 // 开始递归（从去掉的i位置元素递归） 23 List t = f(s.substring(0, i) + s.substring(i + 1)); 24 25 /* 26 * str＝str.substring(int beginIndex);截取掉str从首字母起长度为beginIndex的字符串，将剩余字符串赋值给str； 27 * 28 * str＝str.substring(int beginIndex，int 29 * endIndex);截取str中从beginIndex开始至endIndex结束时的字符串，并将其赋值给str; 30 */ 31 for (int k = 0; k < t.size(); k++) { 32 lst.add("" + x + t.get(k)); 33 } 34 } 35 return lst; 36 37 } 38 39 public static void main(String[] args) { 40 List lst = f("ABC");// 传入一个串，将元素全部放在列表中 41 for (int i = 0; i < lst.size(); i++) { 42 System.out.println(lst.get(i)); 43 } 44 } 45 }
方法二：（数组）
1 package package1; 2 3 //对字母进行全排列 4 //方法二：数组 5 import java.util.*; 6 7 public class A1 { 8 //aa:待排数据 9 //k:考虑当前位置（数组下标） 10 static void f(char[] aa ,int k) { 11 12 //出口 13 if(k==aa.length-1) { 14 System.out.println(String.valueOf(aa)); 15 //把数组类型的aa强制转换成字符串类型,并输出 16 return ;//K达到上线，不能继续递归，程序返回 17 } 18 19 20 //递归相似性 21 //从第k个数开始，到数组中的最后一个数为止，依次进行交换（k从第一个数开始） 22 for(int i=k;i<aa.length;i++) {//i=k,即不能漏掉不交换的情况 23 {char t=aa[k];aa[k]=aa[i];aa[i]=t;}//试探 24 f(aa,k+1);//调用K+1；让后面的元素 25 {char t=aa[k];aa[k]=aa[i];aa[i]=t;}//回溯，再交换回来 26 //做试探，递归之后立即回溯 27 } 28 } 29 30 31 32 33 public static void main(String[] args) { 34 f("ABC".toCharArray(),0);//k从第0个开始 35 /*toCharArray()：将字符串转换成字符数组，便于对每一个字符进行单独操作*/ 36 } 37 38 }
题目一：
长100厘米的细长直杆子上有n只蚂蚁。它们的头有的朝左，有的朝右。
每只蚂蚁都只能沿着杆子向前爬，速度是1厘米/秒。
当两只蚂蚁碰面时，它们会同时掉头往相反的方向爬行。
这些蚂蚁中，有1只蚂蚁感冒了。并且在和其它蚂蚁碰面时，会把感冒传染给碰到的蚂蚁。
请你计算，当所有蚂蚁都爬离杆子时，有多少只蚂蚁患上了感冒。
【数据格式】
第一行输入一个整数n (1 < n < 50), 表示蚂蚁的总数。
接着的一行是n个用空格分开的整数 Xi (-100 < Xi < 100), Xi的绝对值，表示蚂蚁离开杆子左边端点的距离。正值表示头朝右，负值表示头朝左，数据中不会出现0值，也不会出现两只蚂蚁占用同一位置。其中，第一个数据代表的蚂蚁感冒了。
要求输出1个整数，表示最后感冒蚂蚁的数目。
例如，输入：
3
5 -2 8
程序应输出：
1
再例如，输入：
5
-10 8 -20 12 25
程序应输出：
3
题目（二）
小明最近喜欢搭数字积木。一共有10块积木，每个积木上有一个数字，0~9。
搭积木规则：
每个积木放到其它两个积木的上面，并且一定比下面的两个积木数字小。
最后搭成4层的金字塔形，必须用完所有的积木。
下面是两种合格的搭法：
0
1 2
3 4 5
6 7 8 9
0
3 1
7 5 2
9 8 6 4
请你计算这样的搭法一共有多少种？
解决方法：
1 package com.algorithm.java.blueBirdge; 2 3 //元素很小很少就直接写死，不用找规律 4 //企业需要可靠稳定易于维护 5 import java.util.*; 6 7 public class Inquiry { 8 static int N; 9 10 static void show (int[] a) { 11 System.out.println(" "+a[0]); 12 System.out.println(" "+a[1]+" "+a[2]); 13 System.out.println(" "+a[3]+" "+a[4]+" "+a[5]); 14 System.out.println(" "+a[6]+" "+a[7]+" "+a[8]+" "+a[9]); 15 System.out.println(); 16 17 } 18 19 static boolean near (int a ,int b) { 20 if(a+1==b || a==b+1) return true; 21 return false; 22 } 23 static void test(int [] a) { 24 if(a[1]<a[0]) return; 25 if(a[2]<a[0]) return; 26 if(a[3]<a[1]) return; 27 if(a[4]<a[1]) return; 28 if(a[4]<a[2]) return; 29 if(a[5]<a[2]) return; 30 if(a[6]<a[3]) return; 31 if(a[7]<a[3]) return; 32 if(a[7]<a[4]) return; 33 if(a[8]<a[4]) return; 34 if(a[8]<a[5]) return; 35 if(a[9]<a[5]) return; 36 //如果都未return 则show; 37 38 show(a); 39 N++;//N是静态数字，全局累计 40 } 41 42 //a:待排元素 43 //k:考虑当前位置（数组下标） 44 static void f(int[] a ,int k) { 45 46 //出口 47 if(k==a.length-1) { 48 test(a);//制造出一个全排列，用方法test判定 49 return ;//K达到上线，不能继续递归，程序返回 50 } 51 52 53 54 //递归相似性 55 //从第k个数开始，到数组中的最后一个数为止，依次进行交换（k从第一个数开始） 56 57 for(int i=k;i<a.length;i++) {//i=k,即不能漏掉不交换的情况 58 {int t=a[k];a[k]=a[k];a[i]=t;}//试探 59 f(a,k+1);//调用K+1；让后面的元素 60 {int t=a[k];a[k]=a[k];a[i]=t;}//回溯，再交换回来 61 //做试探，递归之后立即回溯 62 } 63 64 } 65 66 67 public static void main(String[] args) { 68 int [] a= {0,1,2,3,4,5,6,7,8,9}; 69 70 //show(a); 71 72 f(a,0); 73 System.out.println("N= "+N); 74 } 75 }
问题：此方法有误！
【未完待续】
题目（三）
X星球要派出一个5人组成的观察团前往W星。
其中：
A国最多可以派出4人。
B国最多可以派出2人。
C国最多可以派出2人。
D国最多可以派出1人。
E国最多可以派出1人。
F国最多可以派出3人。
那么最终派往W星的观察团会有多少种国别的不同组合呢？
题目（四）
已知不同字母构成的串，求它的全排列
题目（五）
有重复的字母中求取出m个所有组合
例如： "AAABBCCCCCCDD" 中取3个字母的所有组合
题目（六）
A A 2 2 3 3 4 4， 一共4对扑克牌。请你把它们排成一行。
要求：两个A中间有1张牌，两个2之间有2张牌，两个3之间有3张牌，两个4之间有4张牌。
请填写出所有符合要求的排列中，字典序最小的那个。
例如：22AA3344 比 A2A23344 字典序小。当然，它们都不是满足要求的答案。