您的位置:

java汉诺塔,java汉诺塔递归算法

本文目录一览:

用java实现汉诺塔的程序是啥呀?

其实不知道你到底是想要代码还是要什么

给你帖的示范代码吧:

汉诺塔问题的递归Java语言实现

public

class

Hanoi

{/**

*

*

@param

n

*

盘子的数目

*

@param

origin

*

源座

*

@param

assist

*

辅助座

*

@param

destination

*

目的座

*/

public

void

hanoi(int

n,

char

origin,

char

assist,

char

destination)

{

if

(n

==

1)

{

move(origin,

destination);

}

else

{

hanoi(n

-

1,

origin,

destination,

assist);

move(origin,

destination);

hanoi(n

-

1,

assist,

origin,

destination);

}

}

//

Print

the

route

of

the

movement

private

void

move(char

origin,

char

destination)

{

System.out.println("Direction:"

+

origin

+

"---"

+

destination);

}

public

static

void

main(String[]

args)

{

Hanoi

hanoi

=

new

Hanoi();

hanoi.hanoi(3,

'A',

'B',

'C');

}

}

java中汉诺塔的算法问题

class HanRuoTa {

static long s=0;

public static void main(String args[]) {

int n =3;

System.out.println("汉诺塔层数为" + n);

System.out.println("移动方案为:" );

hanoi(n, 'a', 'b', 'c');

System.out.println("需要移动次数:"+s);

}

static void hanoi(int n, char a, char b, char c) {

if (n 0) {

hanoi(n - 1, a, c, b);

move(a, b);

hanoi(n - 1, c, b, a);

s++;

}

}

static void move(char x, char y) {

System.out.println(x + "-" + y + "\t");

}

}

运行结果:

汉诺塔层数为3

移动方案为:

a-b

a-c

b-c

a-b

c-a

c-b

a-b

需要移动次数:7

用java编写hanoi塔的非递归算法。

这是个好问题,很少看到有人写汉诺塔的非递归...其实只要先写出递归,然后把递归的每一步要做的事情记录在一个栈里面就可以了

public class Test {

private static void emitStep(int source, int dest) {

System.out.println(source + " - " + dest);

}

static class Step {

Step(int n, int s, int d, int t) {

this.n = n;

source = s;

dest = d;

temp = t;

}

int n, source, dest, temp;

}

private static void hanoi(int n, int source, int dest, int temp) {

java.util.StackStep steps = new java.util.StackStep();

steps.add(new Step(n, source, dest, temp));

while (steps.empty() == false) {

Step step = steps.pop();

if (step.n == 1) {

emitStep(step.source, step.dest);

continue;

}

steps.push(new Step(step.n - 1, step.temp, step.dest, step.source));

steps.push(new Step(1, step.source, step.dest, 0));

steps.push(new Step(step.n - 1, step.source, step.temp, step.dest));

}

}

public static void main(String[] args) {

hanoi(3, 1, 3, 2);

}

}

汉诺塔问题?

汉诺塔(又称河内塔)问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒,第一根上面套着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');

}