「java汉诺塔递归」java用递归实现汉诺塔
本篇文章给大家谈谈java汉诺塔递归，以及java用递归实现汉诺塔对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。
本文目录一览：
汉诺塔递归算法是什么？
hanot (n-1,b,a,c);（解释：在把B塔上的(n-1))个借助A塔移动到C塔）
为了实现 n个盘从 借助c 从a 移动到 b
思路如下：
首先考虑极限当只有一个盘的时候，盘直接从 a - b即可。
当有2个盘的时候，把1号盘从a - c 然后 把2号盘 a-b 再 把 2好盘从 c - b。
当有n个盘的时候，把 n-1个 盘 借助 b 移动到 c 然后将 n号盘从 a - b。
这时候只要将 n-1想办法从c移动到 b 借助 a 那么就可以先把 n-2个盘借助b移动到a。
递归，就是在运行的过程中调用自己。
构成递归需具备的条件：
1，子问题须与原始问题为同样的事，且更为简单；
2，不能无限制地调用本身，须有个出口，化简为非递归状况处理。
在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。
以上内容参考：百度百科-递归公式
汉诺塔的算法
算法介绍：当盘子的个数为n时，移动的次数应等于2^n_1。后来一位美国学者发现一种出人意料的简单方法，只要轮流进行两步操作就可以了。首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放A、B、C；
若n为奇数，按顺时针方向依次摆放A、C、B。
所以结果非常简单，就是按照移动规则向一个方向移动金片：如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C
汉诺塔问题也是程序设计中的经典递归问题。
扩展资料
由来：
法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。
不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。
不管这个传说的可信度有多大，如果考虑一下把64片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。这需要多少次移动呢?这里需要递归的方法。假设有n片，移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7，且f(k+1)=2*f(k)+1。此后不难证明f(n)=2^n-1。n=64时，
假如每秒钟一次，共需多长时间呢？一个平年365天有31536000 秒，闰年366天有31622400秒，平均每年31556952秒，计算一下：18446744073709551615秒。
这表明移完这些金片需要5845.54亿年以上，而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5845.54亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。
参考资料来源：百度百科-汉诺塔
汉诺塔问题？
汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。解答结果请自己运行计算，程序见尾部。面对庞大的数字(移动圆片的次数)18446744073709551615，看来，众僧们耗尽毕生精力也不可能完成金片的移动。
后来，这个传说就演变为汉诺塔游戏:
1.有三根杆子A,B,C。A杆上有若干碟子
2.每次移动一块碟子,小的只能叠在大的上面
3.把所有碟子从A杆全部移到C杆上
经过研究发现，汉诺塔的破解很简单，就是按照移动规则向一个方向移动金片：
如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C
此外，汉诺塔问题也是程序设计中的经典递归问题。
算法思路：
1.如果只有一个金片，则把该金片从源移动到目标棒，结束。
2.如果有n个金片，则把前n-1个金片移动到辅助的棒，然后把自己移动到目标棒，最后再把前n-1个移动到目标棒
(非专业人士可以忽略以下内容)
补充：汉诺塔的算法实现（c++）
#include
#include
using namespace std;
ofstream fout("out.txt");
void Move(int n,char x,char y)
{
fout"把"n"号从"x"挪动到"yendl;
}
void Hannoi(int n,char a,char b,char c)
{
if(n==1)
Move(1,a,c);
else
{
Hannoi(n-1,a,c,b);
Move(n,a,c);
Hannoi(n-1,b,a,c);
}
}
int main()
{
fout"以下是7层汉诺塔的解法:"endl;
Hannoi(7,'a','b','c');
fout.close();
cout"输出完毕！"endl;
return 0;
}
C语言精简算法
/* Copyrighter by SS7E */
#include /* Copyrighter by SS7E */
void hanoi(int n,char A,char B,char C) /* Copyrighter by SS7E */
{
if(n==1)
{
printf("Move disk %d from %c to %c\n",n,A,C);
}
else
{
hanoi(n-1,A,C,B); /* Copyrighter by SS7E */
printf("Move disk %d from %c to %c\n",n,A,C);
hanoi(n-1,B,A,C); /* Copyrighter by SS7E */
}
}
main() /* Copyrighter by SS7E */
{
int n;
printf("请输入数字n以解决n阶汉诺塔问题：\n");
scanf("%d",n);
hanoi(n,'A','B','C');
}/* Copyrighter by SS7E */
PHP算法：
?php
function hanoi($n,$x,$y,$z){
if($n==1){
move($x,1,$z);
}else{
hanoi($n-1,$x,$z,$y);
move($x,$n,$z);
hanoi($n-1,$y,$x,$z);
}
}
function move($x,$n,$z){
echo 'move disk '.$n.' from '.$x.' to '.$z.'
';
}
hanoi(10,'x','y','z');
?
JAVA算法：
public class Haniojava
{
public static void main(String args[])
{
byte n=2;
char a='A',b='B',c='C';
hanio(n,a,b,c);
}
public static void hanio(byte n,char a,char b,char c)
{
if(n==1)
System.out.println("move "+a+" to "+b);
else
{
hanio((byte)(n-1),a,c,b);
System.out.println("move "+a+" to "+b);
hanio((byte)(n-1),c,b,a);
}
}
}
#include
void move(char ch1, char ch2) {
coutch1"ch2' ';
}
void hanoi(int n, char a, char b, char c) {
if (n==1)
move (a,c);
else {
hanoi (n-1,a,c,b);
move (a,c);
hanoi (n-1,b,a,c);
}
}
void main() {
int m;
cout"Enter the number of disk to move:\n";
cinm;
cout"The step to moving "m" disk:\n";
hanoi (m,'A','B','C');
cinm;
}
用不了这么复杂
，设A上有n个盘子。
如果n=1，则将圆盘从A直接移动到C。
如果n=2，则：
1.将A上的n-1(等于1)个圆盘移到B上；
2.再将A上的一个圆盘移到C上；
3.最后将B上的n-1(等于1)个圆盘移到C上。
如果n=3，则：
A. 将A上的n-1(等于2，令其为n`)个圆盘移到B(借助于C)，步骤如下：
(1)将A上的n`-1(等于1)个圆盘移到C上。
(2)将A上的一个圆盘移到B。
(3)将C上的n`-1(等于1)个圆盘移到B。
B. 将A上的一个圆盘移到C。
C. 将B上的n-1(等于2，令其为n`)个圆盘移到C(借助A)，步骤如下：
(1)将B上的n`-1(等于1)个圆盘移到A。
(2)将B上的一个盘子移到C。
(3)将A上的n`-1(等于1)个圆盘移到C。
到此，完成了三个圆盘的移动过程。
从上面分析可以看出，当n大于等于2时，移动的过程可分解为三个步骤：
第一步 把A上的n-1个圆盘移到B上；
第二步 把A上的一个圆盘移到C上；
第三步 把B上的n-1个圆盘移到C上；其中第一步和第三步是类同的。
当n=3时，第一步和第三步又分解为类同的三步，即把n`-1个圆盘从一个针移到另一个针上，这里的n`=n-1。 显然这是一个递归过程，据此算法可编程如下：
move(int n,int x,int y,int z)
{
if(n==1)
printf("%c--%c\n",x,z);
else
{
move(n-1,x,z,y);
printf("%c--%c\n",x,z);
move(n-1,y,x,z);
}
}
main()
{
int h;
printf("\ninput number:\n");
scanf("%d",h);
printf("the step to moving %2d diskes:\n",h);
move(h,'a','b','c');
}
java中递归的作用是什么？为什么要用到递归？
你的两个问题其实是一个问题，对吧。
递归的作用：递归算法可以解决一些通过递归定义的题目。
首先需要明白什么是递归定义的题目，通俗一点来说就是一个大问题中蕴含着小问题，而小问题同时又与大问题的结构相同，只是规模更小。
比如n阶乘的定义可以理解为：
n！= n*(n-1)!
从上面不难看出 (n-1)! 就是比n! 规模更小的问题，按照此方法不断分解下去，就能得到最初的一些基本的已知的数据。然后反过来就可以求出最终的结果了。
n的阶乘算法如下：
private static int jieCheng(int n) {
if(n == 1)
return 1;
else {
return n*jieCheng(n-1);
}
}
还有就是数据结构中二叉树的定义，也是递归定义的。因此二叉树的好多操作都是通过递归实现的。
用递归会使程序相当简洁。
求java版汉诺塔的演示程序
源代码：
/**
*本程序完成的功能是利用汉递规算法实现汉诺塔的动态演示程序
*/
import javax.swing.*;
import java.awt.geom.*;
import java.awt.event.*;
import java.awt.*;
public class Hanio extends JApplet implements ActionListener, Runnable
{
/**
*diskNum是盘子的数量
*/
private int diskNum ;
/**
*各个组件的句柄
*/
private JButton begin, stop;
private JLabel lDiskNum;
private JTextField text;
JPanel pane;
/**
*定义一个线程句柄
*/
private Thread animate;
/**
*定义a,b,c三个柱子上是否有盘子，有哪些盘子
*/
private int adisk[];
private int bdisk[];
private int cdisk[];
public void init()
{
Container content = getContentPane();
content.setLayout(new BorderLayout());
lDiskNum = new JLabel(盘子的数目);
text = new JTextField(8);
begin = new JButton(开始);
begin.addActionListener(this);
stop = new JButton(停止);
stop.addActionListener(this);
pane = new JPanel();
pane.setLayout(new FlowLayout());
pane.add(lDiskNum);
pane.add(text);
pane.add(begin);
pane.add(stop);
content.add(pane, BorderLayout.SOUTH);
}
public void paint(Graphics g)
{
Graphics2D g2D = (Graphics2D)g;
Ellipse2D.Double ellipse;
g2D.setPaint(getBackground());
if(adisk != null)
{
/**
*消除以前画的盘子
*/
for(int j=adisk.length, i=0; --j=0; i++ )
{
ellipse = new Ellipse2D.Double(20+i*5, 180-i*10, 180-i*10, 20);
g2D.fill(ellipse);
ellipse = new Ellipse2D.Double(220+i*5, 180-i*10, 180-i*10, 20);
g2D.fill(ellipse);
ellipse = new Ellipse2D.Double(420+i*5, 180-i*10, 180-i*10, 20);
g2D.fill(ellipse);
}
drawEllipse(g, 20, adisk);//画A组盘子
drawEllipse(g, 220, bdisk);//画B组盘子
drawEllipse(g, 420, cdisk);//画C组盘子
}
pane.repaint();
}
public void update(Graphics g)
{
paint(g);
}
/**画出椭圆代表盘子，g是图形环境，x是最下面的盘子的横坐标，
*arr是柱子数组
*/
public void drawEllipse(Graphics g,int x,int arr[])
{
Graphics2D g2D = (Graphics2D)g;
Ellipse2D.Double ellipse;
g2D.setPaint(Color.gray);
g2D.draw(new Line2D.Double(x+90, 10, x+90, 180));
for(int j=arr.length, i=0; --j=0; i++ )
if(arr[j] != 0)
{
if(i%2 == 0)
g2D.setPaint(Color.blue);
else
g2D.setPaint(Color.red);
ellipse = new Ellipse2D.Double(x+i*5, 180-i*10, 180-i*10, 20);
g2D.fill(ellipse);
}
}
public void actionPerformed(ActionEvent e)
{
String command = e.getActionCommand();
if(command.equals(开始))
{
/**
*进行初始化，开始的时候只有a柱子上有盘子，其他柱子都没有
*/
diskNum = Integer.parseInt(text.getText());
adisk = new int[diskNum];
for(int i=0; iadisk.length; i++)
adisk[i] = 1;
bdisk = new int[diskNum];
for(int k=0; kbdisk.length; k++)
bdisk[k] = 0;
cdisk = new int[diskNum];
for(int i=0; icdisk.length; i++)
cdisk[i] = 0;
repaint();
if(animate == null || !animate.isAlive())//创建一个线程
{
animate = new Thread(this);
animate.start();
}
}
if(command.equals(停止))
{
for(int k=0; kbdisk.length; k++)
bdisk[k] = 0;
for(int i=0; icdisk.length; i++)
cdisk[i] = 0;
repaint();
text.setText();
animate = null;
}
}
/**
*线程方法，在此调用汉诺塔执行移动盘子操作
*/
public void run()
{
hanio(diskNum, 'A', 'B', 'C');
repaint();
}
/**
*汉诺塔递规调用程序，n是盘子的数量，A，B，C分别代表三个柱子
*/
public void hanio(int n, char A, char B, char C)
{
if(n 1)
{
hanio(n-1, A, C, B);
pause();//停顿几秒在执行
switch(A)
{
case 'A':adisk[n-1] = 0;break;
case 'B':bdisk[n-1] = 0;break;
case 'C':cdisk[n-1] = 0;break;
default:break;
}
switch(C)
{
case 'A':adisk[n-1] = 1;break;
case 'B':bdisk[n-1] = 1;break;
case 'C':cdisk[n-1] = 1;break;
default:break;
}
repaint();
hanio(n-1, B, A, C);
}
pause();
switch(A)
{
case 'A':adisk[n-1] = 0;break;
case 'B':bdisk[n-1] = 0;break;
case 'C':cdisk[n-1] = 0;break;
default:break;
}
switch(C)
{
case 'A':adisk[n-1] = 1;break;
case 'B':bdisk[n-1] = 1;break;
case 'C':cdisk[n-1] = 1;break;
default:break;
}
repaint();
}
/**
*每隔半妙钟移动一个盘子
*/
public void pause()
{
try{
Thread.sleep(500);//可以修改此值加快盘子移动的速度
}catch(InterruptedException e){}
}
}
java递归算法的例子。
阶乘：
要求：给定一个数值，计算出它的阶乘值，例如5的阶乘为5*4*3*2*1
实现：
[html] view plaincopy
span style="font-size:12px;" // 利用递归实现一个数的阶乘值 private static BigDecimal getNum(BigDecimal inNum) { if (inNum.compareTo(BigDecimal.ONE) == 0) { return inNum; } return inNum.multiply(getNum(inNum.subtract(BigDecimal.ONE))); }/span
（2）Fibonacci数列：1，1，2，3，5，8，13……
要求：找出数列中指定index位置的数值
实现：
[html] view plaincopy
span style="font-size:12px;" // 利用递归实现了Fibonacci数列 private static int fab(int index) { if (index == 1 || index == 2) { return 1; } else { return fab(index - 1) + fab(index - 2); } }/span
（3）汉诺塔
要求：汉诺塔挪动
实现：
[html] view plaincopy
span style="font-size:12px;" span style="white-space:pre;" /spanprivate static final String DISK_B = "diskB"; span style="white-space:pre;" /spanprivate static final String DISK_C = "diskC"; span style="white-space:pre;" /spanprivate static final String DISK_A = "diskA"; span style="white-space:pre;" /spanstatic String from=DISK_A; span style="white-space:pre;" /span static String to=DISK_C; span style="white-space:pre;" /span static String mid=DISK_B; span style="white-space:pre;" /span public static void main(String[] args) { span style="white-space:pre;" /span String input=JOptionPane.showInputDialog("please input the number of the disks you want me move."); span style="white-space:pre;" /span int num=Integer.parseInt(input); span style="white-space:pre;" /span move(num,from,mid,to); span style="white-space:pre;" /span }/span
[html] view plaincopy
span style="font-size:12px;" // 利用递归实现汉诺塔 private static void move(int num, String from2, String mid2, String to2) { if (num == 1) { System.out.println("move disk 1 from " + from2 + " to " + to2); } else { move(num - 1, from2, to2, mid2); System.out.println("move disk " + num + " from " + from2 + " to " + to2); move(num - 1, mid2, from2, to2); } }/span
（4）排列组合
要求：将输入的一个字符串中的所有元素进行排序并输出，例如：你给出的参数是"abc"，
则程序会输出
abc
acb
bac
bca
cab
cba
实现：
[html] view plaincopy
span style="font-size:12px;"span style="white-space:pre;" /spanpublic static void permute(String str) { span style="white-space:pre;" /span char[] strArray = str.toCharArray(); span style="white-space:pre;" /span permute(strArray, 0, strArray.length - 1); span style="white-space:pre;" /span}/span
[html] view plaincopy
span style="font-size:12px;" // 利用递归实现，将输入的一个字符串中的所有元素进行排序并输出 public static void permute(char[] list, int low, int high) { int i; if (low == high) { String cout = ""; for (i = 0; i = high; i++) { cout += list[i]; } System.out.println(cout); } else { for (i = low; i = high; i++) { char temp = list[low]; list[low] = list[i]; list[i] = temp; permute(list, low + 1, high); temp = list[low];
java汉诺塔递归的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于java用递归实现汉诺塔、java汉诺塔递归的信息别忘了在本站进行查找喔。