锐客网

  1. 首页 > 生活百科 > it技术 > >

汉诺塔递归代码java 汉诺塔递归python

递归IT技术

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;" /spanstatic String to=DISK_C;span style="white-space:pre;" /spanstatic String mid=DISK_B;span style="white-space:pre;" /spanpublic static void main(String[] args) {span style="white-space:pre;" /spanString input=JOptionPane.showInputDialog("please input the number of the disks you want me move.");span style="white-space:pre;" /spanint num=Integer.parseInt(input);span style="white-space:pre;" /spanmove(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;"/spanchar[] 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, low1, high);temp = list[low];
如何用java实现汉诺塔中的递归public class Hannuota {
private int n;//储存盘子个数
public Hannuota(int n){
this.n = n;
}
public void function(){
//初始化三个柱子，A是开始堆满盘子的柱子，C是目标柱子
Pillar a = new Pillar(n,n,"A");
Pillar b = new Pillar(n,"B");
Pillar c = new Pillar(n,"C");
//把三个柱子按顺序排好 ， 详见后面的算法那里的解释
Pillar[] pillars = new Pillar[3];
pillars[0] = a;
if(n%2==0){
pillars[1] = b;
pillars[2] = c;
}else{
pillars[1] = c;
pillars[2] = b;
}
//开始移动，k用来计数，移动次数为2^n-1,至于为什么，我不太清楚，
//反正有人证明过 。i是用来保存最小那个盘子正在哪跟柱子上的 。
int i=0;
for(int k=0;k(int)Math.pow(2, n)-1;){
int min;
//将最小的盘子顺时针移动一个柱子
min = pillars[i%3].Pop();
pillars[(i 1)%3].Push(min);
System.out.println(pillars[i%3] "-" pillars[(i 1)%3]);
k;
i;
//这个IF好像可以不要，当时写的 ， 后面忘了删除 。
if(k(int)Math.pow(2, n)-1){
//如果，剩下两根柱子中，某一根为空，则一定是非空那根中最上面个盘子
//移动到空的那个柱子上 。若两根都不为空 ， 则把编号小的一个盘子
//移动到另外跟柱子上
if(!pillars[(i-1)%3].isEmpty()(pillars[(i 1)%3].isEmpty()||pillars[(i 1)%3].Top()pillars[(i-1)%3].Top())){
min=pillars[(i-1)%3].Pop();
pillars[(i 1)%3].Push(min);
System.out.println(pillars[(i-1)%3] "-" pillars[(i 1)%3]);
}else{
min=pillars[(i 1)%3].Pop();
pillars[(i-1)%3].Push(min);
System.out.println(pillars[(i 1)%3] "-" pillars[(i-1)%3]);
}
k;
}
}
}
//主函数 ， 用来测试的 。3表示3个盘子 。
public static void main(String args[]){
new Hannuota(3).function();
}
}
class Pillar{//构造一个新类，表示柱子，实际是当一个栈在用
private int[] s;
private int top;
private String name;
public String toString(){
return name;
}
//这个构造函数用来构造BC两个柱子，下面那个用来构造柱子A 。其实也可以写成一个构造函数 。
public Pillar(int max,String name){
s = new int[max];
top = -1;
this.name = name;
for(int i=0;imax;i){
s[i] = max 1;
}
}
public Pillar(int n,int max,String name){
s = new int[max];
top = n-1;
this.name = name;
for(int i=0;imax;i){
s[i] = max - i;
}
}
//这后面这些就是栈的基本方法了，不用介绍了吧
public boolean isEmpty(){
return top==-1?true:false;
}
public int Top (){
return s[top];
}
public int Pop(){
return s[top--];
}
public void Push(int x){
s[top] = x;
}
}
算法是这个
首先容易证明，当盘子的个数为n时 ， 移动的次数应等于2^n - 1 。
首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上 。
根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放 A B C；
若n为奇数，按顺时针方向依次摆放 A C B 。
（1）按顺时针方向把圆盘1从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘1在柱子A ， 则把它移动到B；
若圆盘1在柱子B，则把它移动到C；若圆盘1在柱子C，则把它移动到A 。
（2）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上 。
即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时 ， 移动较小的圆盘
这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的 。
（3）反复进行（1）（2）操作，最后就能按规定完成汉诺塔的移动 。
这玩意要非递归真麻烦 。需不需要加点注释？
其实我不明白干嘛非要非递归 。。。
怎么用递归法编写简单的汉诺塔java程序package Hanoi;
import java.awt.*;
import java.io.*;
import java.awt.event.*;
public class Hanoi {
public static void main(String args[]) throws IOException {
Hanoi aa = new Hanoi();
aa.go();
}
public void go() throws IOException {
int n;
BufferedReader buf;
buf = new BufferedReader(new InputStreamReader(System.in));
System.out.print("请输入盘数：");
n = Integer.parseInt(buf.readLine());
Hanoi hanoi = new Hanoi();
hanoi.move(n, 'A', 'B', 'C');
}
public void move(int n, char a, char b, char c) {
if (n == 1) {
System.out.println("盘 "n" 由 "a" 移至 "c);
} else {
move(n - 1, a, c, b);
System.out.println("盘 "n" 由 "a" 移至 "c);
move(n - 1, b, a, c);
}
}
}
求java版汉诺塔的演示程序源代码汉诺塔递归代码java：
/**
*本程序完成汉诺塔递归代码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三个柱子上是否有盘子汉诺塔递归代码java，有哪些盘子
*/
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);
}
/**画出椭圆代表盘子汉诺塔递归代码java，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柱子上有盘子 ， 其汉诺塔递归代码java他柱子都没有
*/
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分别代表三个柱子
*/
publicvoid hanio(int n, char A, char B, char C)
{
if(n1)
{
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 汉诺塔递归python】汉诺塔递归代码java的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于汉诺塔递归python、汉诺塔递归代码java的信息别忘了在本站进行查找喔 。

    推荐阅读


    上一篇：phpsqlserver类的简单介绍

    下一篇：ice异常服务器拒绝连接 ice服务器怎么解决