论坛: 编程破解 标题: 汉烙塔问题! 复制本贴地址    
作者: lqvewhop [lqvewhop]    论坛用户   登录
请问汉烙塔怎样用c++来编啊
在帮我解释一下

[此贴被 lqvewhop(lqvewhop) 在 12月26日20时44分 编辑过]

地主 发表时间: 04-12-26 00:57

回复: yuanrulai [yuanrulai]   论坛用户   登录
先把这个问题理解清楚再编

B1层 发表时间: 04-12-26 22:59

回复: kert_t8 [kert_t8]   论坛用户   登录
先收藏,有时间再来写吧

楼主也太..........



B2层 发表时间: 04-12-27 14:54

回复: kert_t8 [kert_t8]   论坛用户   登录
先分析一下这个问题

汉诺塔问题的约束条件是大盘子不能放到小盘子上,目标是把整堆的盘子从一个柱子转移到另一个柱子上去。假设我们考虑的是一个n个盘子的汉诺塔问题,我们可以发现,第n-1,n-2,n-3....2,1个盘子可以组成另外一个新的n-1的汉诺塔问题。这自然的就想到了递归求解。

(首先做变量声明:from,to表示堆的编号。堆的编号从一到三,初始状态:所有盘子在堆1。目标状态:所有盘子在堆3。)
考虑最简单的情况,一个盘子:直接从第from堆放到第to堆
其次简单的情况,两个盘子:先把最上面的盘子从from对放到另外一个不是to的堆上,然后把下面的盘子从from移到to上,然后把开始拿走的盘子放回to上
稍微复杂的情况,三个盘子:不考虑最底下的盘子(我们可以不考虑最底下的盘子是因为它不对其他的盘子的移动造成约束),把上面两个盘子从from移到非to堆上,在把最底下的盘子从from放到to上,然后把开始的两个盘子移回到to堆上
在复杂一点:(自己去想)

下面是使用 java 编写的源代码
代码:

public class hano {
final int[] plates;

public hano(int numOfPlates) {
plates = new int[numOfPlates];
for (int i=0;i<numOfPlates;i++)
plates[i]=1;
printState();
}

public void printState() {
System.out.println("\nHere is the state:");
for (int i=0;i<plates.length;i++) {
if (plates[i]==1)
System.out.print(plates[i]+"\t");
}
System.out.println();
for (int i=0;i<plates.length;i++) {
if (plates[i]==2)
System.out.print(plates[i]+"\t");
}
System.out.println();
for (int i=0;i<plates.length;i++) {
if (plates[i]==3)
System.out.print(plates[i]+"\t");
}
System.out.println();
}

public void movePlate(int plateNum, int toWhere) {
System.out.println(plateNum+":\tFrom "+plates[plateNum]+"\tTo "+toWhere);
plates[plateNum]=toWhere;
}

public void movePile(int plateNum, int toWhere) {
int nextPlate=9999;
for (int i=plateNum+1;i<plates.length;i++)
if (plates[i]==plates[plateNum]){
nextPlate=i;
break;
}

if (nextPlate==9999) {
movePlate(plateNum, toWhere);
return;
}

movePile(nextPlate, 6-plates[plateNum]-toWhere);

/*
We the sum of the pile number is 6. so plate[plateNum] is current pile number; toWhere is target
pile number; 6-plates[plateNum]-toWhere is the one rest. We leave the bottom of this pile there, move
the rest to the third pile. Next, we are going to move this plate(plateNum) to the target.
Then, we will move The rest of the pile to the target pile
*/

movePlate(plateNum, toWhere); // move the plate to the target
movePile(nextPlate, toWhere); // move the rest
}

public static void main(String arg[]) {
hano myHano =  new hano(3); // Change here to change the number of plates.
myHano.movePile(0,3);
}
}
��



之所以不用C++,是因为很长时间没有用,很多东西记不清楚了,编写效率较低。最近一段时间在打工,每天要工作13个小时,只有乘每天晚上这段时间写点东西,还得保证充足的睡眠以便第二天工作。所以不得不注意工作效率。这一点非常对不起楼主,请原谅。
不过我想Java写的程序面向对象体现的比较好,程序也就写的比较清楚,比较容易理解算法(找些借口打个圆场,找个台阶下

还有,我测试过2,3,4,是正确的,所以我推断后面的也不应该会错。不过忙乱之中,疏忽之处在所难免,如果有问题,望及时告知,并请谅解。谢谢

B3层 发表时间: 04-12-28 14:39

回复: ljsh012 [ljsh012]   论坛用户   登录
汉诺塔问题就是典型的递归问题。
此程序中递归算法是谭浩强的c教材中的。
上面月之御者的感觉有点繁琐。
故给出下面的java程序。
算法思想:
假设目标是把A上的n个碟放到C上,其中B可利用。
1,当A只有一个碟时,直接A------->C(表示步骤从A移到C,下面同理)
2,当有n个碟在A上时,所要做的是只要把A上的n-1个碟放到B上去,就可以把最大的碟子放到C上了。
3,完成上面两步后,现在要把B上的n-1个碟子放到C上,可以利用目前已经空闲的A。而这个方法跟上面的方法完全一样。仅仅变了顺序而也。而正因为这样,我们可以改变一下形参的位置。而我们的函数的算法始终是从某某借助某某移到某某。(写递归时把1和2的步骤换一下)在这个思想下可以有下面的主程序:
public static void move(char x,char y)
  {
  System.out.println(x+"----->"+y);
  }
public static void hano(int n,char one,char two,char three)
  {
  if(n==1)move(one,three);
  else
  {
  hano(n-1,one,three,two);//one 借助 three 把n-1个碟子移到 two
  move(one,three);//然后移动one上剩下的一个大碟子到three上
  hano(n-1,two,one,three);//把此时two上的n-1个碟子借助one移到three上
  }
  }
下面是完整的可以打印出结果的程序:(其中输入函数用了月之御者的程序,因为我对java的接收用户输入的方发还不知道,我目前仅是知道部分语法,而且程序可能一点都不好,仅是可以运行并得到正确结果)

import java.io.*;
class sq
{
public static void move(char x,char y)
  {
  System.out.println(x+"----->"+y);
  }
public static void hano(int n,char one,char two,char three)
  {
  if(n==1)move(one,three);
  else
  {
  hano(n-1,one,three,two);
  move(one,three);
  hano(n-1,two,one,three);
  }
  }
  public static String getString(InputStream in)
  {
  String retString;
  try
  {
  InputStreamReader streamRead = new InputStreamReader(in);
  BufferedReader stringReader= new BufferedReader(streamRead);
  retString = stringReader.readLine();
  }
  catch(IOException e)
    {
  System.out.println("String error");
  retString="ERROR";
  }
  return retString;
  }
  public static int getInt(InputStream in)
  {
  int retInt;
  Integer holdInt;
  try
  {
  String intStr =sq.getString(in);
  holdInt = Integer.valueOf(intStr);
  retInt = holdInt.intValue();
  }
  catch(NumberFormatException e)
  {
  System.out.println("WARNING:not valid integer");
  retInt = 0;
  }
  return retInt;
  }
  public static void main(String [] args)
  {
int m=0;
System.out.println("please intput the number m:");
try
{
m=sq.getInt(System.in);
}catch(Exception e){}
hano(m,'A','B','C');
System.out.println("there are "+m+" disk just you input");

  }
 

}


[此贴被 霜泉(ljsh012) 在 12月29日00时28分 编辑过]

B4层 发表时间: 04-12-29 00:17

回复: kert_t8 [kert_t8]   论坛用户   登录
确实是
这个,我还正儿八经整了几个盘子在那儿摆着,然后正儿八经的把它们换来换去的。但是如果不是这样写程序我还真不知道这个算法怎么做,以前学的东西早忘了。不过话又说回来,楼上的程序还真是写的精辟。中间两三行的代码我读了半天才读懂。程序居然可以这么写,阿弥陀佛,佩服佩服。
从我和霜泉的程序的区别可以看出来一个问题。这个算法的核心其实就是在于父问题转化成一个子问题加一个move的动作的时候,子问题和父问题状态其实和父问题是完全等价的。我之所以非要设计一个hano类,存储三个柱子现在的状态就是对这个条件认识不深刻。这个完全等价说起来简单,真正要利用起来不一定容易。我在做程序的时候就没有想到每一次确定一个子问题的时候(调用一次movePile方法,或者是霜泉里面的hano方法),子问题是一个完整的汉诺塔问题。也就是说我只想到要把这个盘子上面的每一个盘子都移到另外一个柱子上去,但是我不敢确定上面的这些盘子是不是都是连续的,也就是说,盘子的号码是不是连续的,会不会在n号盘子上面就是n-2或者n-3号盘子。事实上,这个担心也是不无道理的,但是在想通这个完全等价的条件以后,豁然开朗,从理论上证明了这种情况是不可能的。这也就是为什么霜泉可以不用存储汉诺塔状态的原因(我靠,这是不是个病句啊?读起来那么别扭)。
事实上,昨天我跟同学说起这个问题,他说他记得老师讲课的时候只用三四句话就完成了。现在想来,应该就是
代码:

void hano(int n, char one, char two, char three) {
        if (n==1)
                System.out.println(one + "-->" + three);
        else {
                hano(n-1,one,three,two);
                System.out.println(one + "-->" + three);
                hano(n-1,two,one,three);
        }
}



就是把霜泉的程序中move函数直接写到调用的地方(因为只有一句话)

现在我还有一个问题。我们给出了汉诺塔问题的一个解法,但是,这是不是最短解法呢?有没有人来回答一下?

B5层 发表时间: 04-12-29 13:37

回复: lqvewhop [lqvewhop]   论坛用户   登录
谢谢~~~~~~~``
    各位小弟的递归调用不行啊~~~~~~~~~
    请各位大哥帮我解释一下好吗?

B6层 发表时间: 05-01-01 18:09

回复: SysHu0teR [syshunter]   版主   登录
代码:

void hanoi(int n, char a,char b,char c) {
if(n>0) {
hanoi(n-1,a,c,b);
cout<<a<<" ----> "<<c<<endl;
hanoi(n-1,b,a,c);
}
}



按照思路,应该是最短解法

B7层 发表时间: 05-01-01 18:54

回复: lqvewhop [lqvewhop]   论坛用户   登录
没有什么 谢谢你对我的关心?
    不过我看不懂java的程序

B8层 发表时间: 05-03-01 21:17

回复: chenbin [chenbin]   论坛用户   登录
VB的我到是会一点点!
Option Explicit
Private Declare Sub Sleep Lib "kernel32" (ByVal dwMilliseconds As Long)

Const FromTower                          As Long = 1
Const ViaTower                          As Long = 2
Const ToTower                            As Long = 3

Dim NumDisks                            As Long
Dim TowerHeight(FromTower To ToTower)    As Long
Dim DiskNumber(FromTower To ToTower, 1 To 10)    As Long
Dim XPosn(FromTower To ToTower)          As Long
Dim YPosn                                As Long
Dim DiskHeight                          As Long
Dim NumMoves                            As Long
Dim CurrentDisk                          As Long
Dim Busy                                As Boolean
Dim StopRequested                        As Boolean

'  开始移动
Private Sub Command1_Click()
   
    If Not Busy Then
        Busy = True
        StopRequested = False
        Command2.Caption = "停止"
       
        NumDisks = 10
        Command1.Enabled = True
               
    '  每个塔的高度
        TowerHeight(FromTower) = NumDisks
        TowerHeight(ViaTower) = 0
        TowerHeight(ToTower) = 0
       
        '  将所有金盘放置在第一个根杆的位置
        For CurrentDisk = 1 To 10
            Disk(CurrentDisk).Move XPosn(FromTower) - Disk(CurrentDisk).Width \ 2, YPosn - CurrentDisk * DiskHeight
            DiskNumber(FromTower, CurrentDisk) = CurrentDisk
        Next CurrentDisk
        DoEvents
        NumMoves = 0
       
        On Error Resume Next
       
        '  开始移动金盘
        MoveAllDisks NumDisks, FromTower, ViaTower, ToTower
        '  如果移动结束则显示退出
        Busy = False
        Command2.Caption = "退出"
    End If
End Sub

'  移动金盘
Sub MoveAllDisks(ByVal NumDisks, ByVal FromTower, ByVal ViaTower, ByVal ToTower)
    Select Case NumDisks
      Case 1  ' 如果只有一块金盘则直接移动过去
        MoveOneDisk FromTower, ToTower
      Case Is > 1
        '  递归调用移动金盘
        MoveAllDisks NumDisks - 1, FromTower, ToTower, ViaTower

        '  只剩下最后一个金盘在第一根杆上,其他的在第二根杆上,
        '  第三根杆空的,可以直接将最后一个金盘移动过去
        MoveOneDisk FromTower, ToTower
       
        '  将空的杆作为临时杆,移动金盘
        MoveAllDisks NumDisks - 1, ViaTower, FromTower, ToTower
    End Select
End Sub

'  移动一块金盘从A杆到B杆
Sub MoveOneDisk(ByVal TowerA, ByVal TowerB)
    NumMoves = NumMoves + 1
    '  延迟
    Sleep 500
       
    '  确定当前移动的金盘是A杆中最上一块
    CurrentDisk = DiskNumber(TowerA, TowerHeight(TowerA))

    '  B杆中增加一块金盘
    TowerHeight(TowerB) = TowerHeight(TowerB) + 1

    '  在B杆中绘制这块金盘
    Disk(CurrentDisk).Move XPosn(TowerB) - Disk(CurrentDisk).Width \ 2, YPosn - TowerHeight(TowerB) * DiskHeight
    DiskNumber(TowerB, TowerHeight(TowerB)) = CurrentDisk

    '  A杆减少一块金盘
    TowerHeight(TowerA) = TowerHeight(TowerA) - 1
   
    DoEvents
   
    '  如果请求停止,则发送错误信息
    If StopRequested Then
        Err.Raise 1
    End If
End Sub

'  停止或退出
Private Sub Command2_Click()
    If Busy Then
        StopRequested = True
    Else
        Unload Me
    End If
End Sub

'  初始化
Private Sub Form_Load()
    XPosn(FromTower) = 100
    XPosn(ViaTower) = 250
    XPosn(ToTower) = 400
    YPosn = ScaleHeight - 70
   
    DiskHeight = Disk(1).Height - 1
   
    '  将所有金盘放置在第一个根杆的位置
    For CurrentDisk = 1 To 10
        Disk(CurrentDisk).Move XPosn(FromTower) - Disk(CurrentDisk).Width \ 2, YPosn - CurrentDisk * DiskHeight
        DiskNumber(FromTower, CurrentDisk) = CurrentDisk
    Next CurrentDisk
   
End Sub

'  绘制窗体中的杆
Private Sub Form_Paint()
    Dim i As Long
    FontBold = True
    For i = FromTower To ToTower
        CurrentX = XPosn(i) - 3 '
        CurrentY = YPosn + 1
        Print Mid$("ABC", i, 1);
    Next i
   
    Line1(FromTower).X1 = XPosn(FromTower)
    Line1(FromTower).X2 = XPosn(FromTower)
    Line1(ViaTower).X1 = XPosn(ViaTower)
    Line1(ViaTower).X2 = XPosn(ViaTower)
    Line1(ToTower).X1 = XPosn(ToTower)
    Line1(ToTower).X2 = XPosn(ToTower)
End Sub

Private Sub Form_Unload(Cancel As Integer)
    '  在移动过程中无法退出
    Cancel = Busy
End Sub



B9层 发表时间: 05-03-28 13:44

回复: liuluo [liuluo]   论坛用户   登录
VB的谢了

B10层 发表时间: 05-04-08 21:26

论坛: 编程破解

20CN网络安全小组版权所有
Copyright © 2000-2010 20CN Security Group. All Rights Reserved.
论坛程序编写:NetDemon

粤ICP备05087286号