CCI题目3-4:Hanoi Tower

By | 2012 年 11 月 20 日

这是一个经典问题,经典解法。要将n个盘子从stack0,移动到stack2,只需要做以下三步:
1.将n-1个盘子,从0移动到1,将stack1用作临时stack;
2.将最下面的第n个盘子,从0移动到2;
3.将刚才放到临时stack1的n-1个盘子,移动到stack2。

这是递归的办法,也可以将这个递归展开,只需要多用一个stack记录程序的状态。



题目
In the classic problem of the Towers of Hanoi, you have 3 rods and N disks of different sizes which can slide onto any tower. The puzzle starts with disks sorted in ascending order of size from top to bottom (e.g., each disk sits on top of an even larger one). You have the following constraints:
(A) Only one disk can be moved at a time.
(B) A disk is slid off the top of one rod onto the next rod.
(C) A disk can only be placed on top of a larger disk.
Write a program to move the disks from the first rod to the last using Stacks.



Code


//
//  main.cpp
//  CCI.3.4.Hanoi Tower
//
//  Created by Qiu Xiangyu on 12-11-20.
//  Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

#include 
#include 
using namespace std;

void move(stack stacks[], int count, int sourceIndex, int targetIndex, int tempIndex) {
    if (count == 0) {
        return;
    }
    //moving the top of plants to temporary stack, leaving the last one
    move(stacks,count - 1,sourceIndex,tempIndex,targetIndex);
    //moving the last plate to the target stack
    int plate = stacks[sourceIndex].top();
    cout<<"moving plate "< stacks[3];
    for (int i = 0; i < count; ++i) {
        stacks[0].push(count - i);
    }
    //solve it
    move(stacks,count,0,2,1);
}

int main(int argc, const char * argv[])
{
    // insert code here...
    std::cout << "Hello, World!\n";
    hanoi(10);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注