『递归』汉诺塔和全排列
1.问题 B: 汉诺塔
题目描述
使用递归编写一个程序实现汉诺塔问题，要求在输入圆盘数量之后，输出圆盘的移动步骤，输出格式示例如下：
第1步:1号盘从A柱移至B柱第2步:2号盘从A柱移至C柱
输入
多组测试用例，每组输入一个正整数n，n代表圆盘数量。
输出
每组输出之间有一行空行。
样例输入
3
样例输出
第1步:1号盘从A柱移至C柱
第2步:2号盘从A柱移至B柱
第3步:1号盘从C柱移至B柱
第4步:3号盘从A柱移至C柱
第5步:1号盘从B柱移至A柱
第6步:2号盘从B柱移至C柱
第7步:1号盘从A柱移至C柱
Java题解
移盘子很好理解，假如有两个盘子，我们直接把盘1移到b，把盘2移到c，再把盘1从b移到c
假如有三个盘子，我们把上面两个看作一个整体，想办法借助c盘，把上面两个移到b盘，这样就可以把最底下的盘移到c盘；再想办法，借助a盘把上面两个移到c盘
。。。
第一步：把上面的盘子看作一个整体，从from盘（起始盘）移到temp辅助盘，期间借助to盘（目标盘）
第二步：把最底下的盘从from盘移到要去的to目标盘
第三步：把移到了temp辅助盘的整体，借助起始盘from移到目标盘to
hanoi(n-1, from, to, temp);
move(count,n, from, to);
count++;
hanoi(n-1, temp, from, to);
其中count是全局变量用于计数，每移动一步就加1
importjava.util.Scanner;
publicclassMain {
staticintcount=1;
publicstaticvoidmain(String[] args) {
intn;
charfrom='A';chartemp='B';charto='C';
Scannerscanner=newScanner(System.in);
while(scanner.hasNext()) {
n=scanner.nextInt();
hanoi(n, from, temp, to);
count=1;
System.out.println();
}
scanner.close();
}
publicstaticvoidhanoi( intn,charfrom,chartemp,charto) {
if(n>0) {
hanoi(n-1, from, to, temp);
move(count,n, from, to);
count++;
hanoi(n-1, temp, from, to);
}
}
publicstaticvoidmove(intcount,intn,chara,charb) {
System.out.println("第"+count+"步:"+n+"号盘从"+a+"柱移至"+b+"柱");
}
}
2.问题 C: 汉诺塔II
题目描述
用1,2,...,n表示n个盘子，称为1号盘，2号盘,...。号数大盘子就大。经典的汉诺塔问题经常作为一个递归的经典例题存在。可能有人并不知道汉诺塔问题的典故。汉诺塔来源于印度传说的一个故事，上帝创造世界时作了三根金刚石柱子，在一根柱子上从下往上按大小顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一回只能移动一个圆盘。我们知道最少需要移动2^64-1次.在移动过程中发现，有的圆盘移动次数多，有的少 。 告之盘子总数和盘号，计算该盘子的移动次数.
输入
包含多组数据，首先输入T,表示有T组数据.每个数据一行，是盘子的数目N(1<=N<=60)和盘号k(1<=k<=N)。
输出
对于每组数据，输出一个数，到达目标时k号盘需要的最少移动数。
样例输入
2
601
31
样例输出
576460752303423488
4
Java题解
我们学了汉诺塔问题的时间复杂度为O(2n)，n个盘子一共需要移动（2n）-1次。
其中每个盘子的移动次数为20+21+22+……+2n-1
最底下的盘只需要移动20 次，最顶上的盘需要移动2n-1 次
importjava.util.Scanner;
publicclassMain {
publicstaticvoidmain(String[] args) {
intT;
Scannerscanner=newScanner(System.in);
T=scanner.nextInt();
intn,k;
while(T!=0) {
n=scanner.nextInt();
k=scanner.nextInt();
Longlong1=(long) Math.pow(2, n-k);
System.out.println(long1);
T--;
}
scanner.close();
}
}
3.问题 E: 字母全排列
题目描述
编写一个程序，使用递归算法输出一个一维字符数组中所有字符的全排列，假设字符都不一样。例如{'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个字母的全排列，且每组输出之间用空格隔开。
样例输入
1
2
样例输出
a
ab
ba
Java题解
上课的时候老师讲的我晕晕的，似懂非懂，后来自己推了一遍就明了了，果然算法还得自己动手实践。
关键代码短短三行，大概模板就是这样总结出来的吧
初值a[]={1,2,3}，start=0，end=3
这样分析就能明白递归实质的运行了，而后i继续加加，再次进入递归，打印”321“和”312“
public static void perm(char []a,int start ,int end) {
if(start==end) {
print(a);
System.out.println();
}else {
for(int i=start;i<end;++i) {
swap(a, start, i);
perm(a, start+1, end);
swap(a, start, i);
}
}
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int n;
Scanner scanner=new Scanner(System.in);
String string="abcdefghijklmnopqrstuvwxyz";
while(scanner.hasNext()) {
n=scanner.nextInt();
char a[]=string.substring(0, n).toCharArray();
perm(a, 0, n);
}
scanner.close();
}
public static void perm(char []a,int start ,int end) {
if(start==end) {
print(a);
System.out.println();
}else {
for(int i=start;i<end;++i) {
swap(a,start,i);
perm(a, start+1, end);
swap(a, start, i);
}
}
}
public static void swap(char []a,int i,int j) {
char temp=a[j];
a[j]=a[i];
a[i]=temp;
}
public static void print(char []a) {
for(char c:a) {
System.out.print(c);
}
}
}
4.问题 F: 九数组分数
题目描述
1, 2, 3...9 这九个数字组成一个分数，其值恰好为1/3，要求每个数字出现且只能出现一次，如何组合？编写程序输出所有的组合。
输入
无
输出
输出所有的结果，如果有多个，每条结果占一行。结果的格式 : xxxx/xxxxx ，按照分子从小到大的顺序输出。
Java题解
没有学全排列之前绝对想不到这道题要这么做。9位数要拆成x=3*y的形式，肯定x是5位数，y是4位数，这一点很容易发现，然后就是全排列的知识了
public class Main {
static int []ans=new int[5];
static int k=0;
public static void main(String[] args) {
int []a= {1,2,3,4,5,6,7,8,9};
perm(a,0,9);
}
public static void perm(int []a,int start,int end) {
if(start==end) {
int x=a[0]*10000+a[1]*1000+a[2]*100+a[3]*10+a[4];
int y=a[5]*1000+a[6]*100+a[7]*10+a[8];
if(x==y*3) {
System.out.printf("%d/%d",y,x);
System.out.println();
}
}else {
for(int i=start;i<end;++i) {
swap(a, start, i);
perm(a, start+1, end);
swap(a, start, i);
}
}
}
public static void swap(int []a,int i,int j) {
int temp=a[j];
a[j]=a[i];
a[i]=temp;
}
}
