用栈来求解汉诺塔问题

# 递归求解
def hanoiProblem(num, left, mid, right):
    # num是需要移动的盘子数
    # left,mid,right是三座塔
    # 如果盘子数小于等于0
    if num < 1:
        # 移动步数是0
        return 0
    # 其它情况调用递归函数进行求解
    return process(num, left, mid, right, left, right)


# 汉诺塔递归求解函数
def process(num, left, mid, right, from_which, to):
    """
    :param num: 移动的盘子数
    :param left: 左塔
    :param mid: 中塔
    :param right: 右塔
    :param from_which: 盘子现在在哪座塔上
    :param to: 要移动到哪里
    :return: 最少移动步数
    """
    # 递归终止条件
    # 只剩一个盘子
    if num == 1:
        # 第一种情况
        # 从中塔到两端
        # 或者从两端到中塔
        if from_which == 'mid'&nbs***bsp;to == 'mid':
            print("Move 1 from {} to {}".format(from_which, to))
            return 1
        # 第二种情况
        # 从左塔到右塔
        # 或者从右塔到左塔
        else:
            print("Move 1 from {} to {}".format(from_which, mid))
            print("Move 1 from {} to {}".format(mid, to))
            return 2
    # 递归体
    # 第一种情况
    # 从中塔到两端
    # 或者从两端到中塔
    if from_which == 'mid'&nbs***bsp;to == 'mid':
        # 需要三步操作
        # 先将num-1个盘子从from_which移动到除了中塔的另外一座塔上
        another = right if (from_which == 'left'&nbs***bsp;to == 'left') else left
        part1 = process(num - 1, left, mid, right, from_which, another)
        # 将第num个盘子从from_which移动到to
        print("Move {} from {} to {}".format(num, from_which, to))
        part2 = 1
        # 将num-1个盘子从另外一座塔移动到to
        part3 = process(num - 1, left, mid, right, another, to)
        # 最少移动步数
        return part1 + part2 + part3
    # 第二种情况
    # 从左塔移动到右塔
    # 或者从右塔移动到中塔
    else:
        # 分为5步
        # 先将num-1个盘子从from_which移动到to
        part1 = process(num - 1, left, mid, right, from_which, to)
        # 将第num个盘子从from_which移动到中塔
        print("Move {} from {} to {}".format(num, from_which, mid))
        part2 = 1
        # 将num-1个盘子从to移动到from_which
        part3 = process(num - 1, left, mid, right, to, from_which)
        # 将第num个盘子从中塔移动到to
        print("Move {} from {} to {}".format(num, mid, to))
        part4 = 1
        # 最后将num-1个盘子从from_which移动到to
        part5 = process(num - 1, left, mid, right, from_which, to)
        # 最少移动步数
        return part1 + part2 + part3 + part4 + part5


# 移动的盘子数
n = int(input())
step = hanoiProblem(n, 'left', 'mid', 'right')
print("It will move {} steps.".format(step))

# 定义操作列表
# 分别是：
# 不做任何操作
# 左塔到中塔
# 中塔到左塔
# 中塔到右塔
# 右塔到中塔
action = ['No', 'LToM', 'MToL', 'MToR', 'RToM']


# 用栈求解汉诺塔问题
def hanoiProblem(num, left, mid, right):
    """
    :param num:移动的盘子数
    :param left:左塔
    :param mid:中塔
    :param right:右塔
    :return:最少移动步数
    """
    # 用列表模拟栈
    # 左塔
    ls = []
    # 中塔
    ms = []
    # 右塔
    rs = []
    # 将最大值加入栈中
    # 方便后面处理
    max_value = 10 ** 10
    ls.append(max_value)
    ms.append(max_value)
    rs.append(max_value)
    # 向右塔中加入num个盘子
    for i in range(num, 0, -1):
        ls.append(i)
    # 初始化操作序列记录
    record = [action[0]]
    # 初始化最少移动步数
    step = 0
    # 当num座塔没有完全被移动到右塔上时
    while len(rs) != num + 1:
        # 分别进行四种操作的试探
        step += fstackTotstack(record, action[2], action[1], ls, ms, left, mid)
        step += fstackTotstack(record, action[1], action[2], ms, ls, mid, left)
        step += fstackTotstack(record, action[4], action[3], ms, rs, mid, right)
        step += fstackTotstack(record, action[3], action[4], rs, ms, right, mid)
    return step


# 出栈、入栈操作
def fstackTotstack(record, pre_action, now_action, fstack, tstack, from_which, to):
    """
    :param record: 操作序列记录
    :param pre_action: 上个操作
    :param now_action:当前的操作
    :param fstack:出栈
    :param tstack:入栈
    :param from_which:出塔
    :param to:入塔
    :return:移动次数
    """
    # 如果满足操作条件
    if record[0] != pre_action and fstack[-1] < tstack[-1]:
        # 入栈
        tstack.append(fstack.pop())
        print("Move {} from {} to {}".format(tstack[-1], from_which, to))
        # 更新记录
        record[0] = now_action
        return 1
    return 0


n = int(input())
step = hanoiProblem(n, 'left', 'mid', 'right')
print("It will move {} steps.".format(step))

1. 将1~n-1从left柱借助right柱移动到mid柱；
2. 然后将n从left柱直接移动到right柱；
3. 最后再将1~n-1从mid柱借助left柱移动到right柱。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    private static int stages = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        hanoi(n, "left", "mid", "right");
        System.out.println("It will move "+ stages +" steps.");
    }
    
    private static void hanoi(int n, String left, String mid, String right) {
        if(n == 1){
            // 剩一个，借助mid柱把n从left移动到right
            move(n, left, mid);
            move(n, mid, right);
        }else{
            // 第一步，把1~n-1从left柱借助mid柱移动到right柱
            hanoi(n - 1, left, mid, right);
            // 第二步，把n从left柱借助mid柱移动到right柱
            move(n, left, mid);                // 先将n从left移动到mid
            hanoi(n - 1, right, mid, left);    // 再将mid上面的1~n-1移动借助mid到left上
            move(n, mid, right);               // 最后将n从mid移动到right上
            // 第三步，将1~n-1从left柱借助mid柱移动到right柱
            hanoi(n - 1, left, mid, right);
        }
    }
    
    // 将n从from移动到to
    private static void move(int n, String from, String to) {
        System.out.println("Move " + n + " from " + from + " to " + to);
        stages ++;
    }
}

#include <bits/stdc++.h>

using namespace std;

void hanoid(int n, string src, string mid, string dst, int &count){
    count ++;
    if (n==1){
        if (src=="mid" || dst=="mid")a
            cout << "Move " << n << " from " << src << " to " << dst <<endl;
        else{
            count ++;
            cout << "Move " << n << " from " << src << " to " << mid <<endl;
            cout << "Move " << n << " from " << mid << " to " << dst <<endl;
        }
        return;
    }
    // 退化为第一种情况
    if(src=="mid" || dst=="mid"){
        hanoid(n-1, src, dst, mid, count);
        cout << "Move " << n << " from " << src << " to " << dst <<endl;
        hanoid(n-1, mid, src, dst, count);
    }
    
    else{
        count ++;
        hanoid(n-1, src, mid, dst, count);
        cout << "Move " << n << " from " << src << " to " << mid <<endl;
        hanoid(n-1, dst, mid, src, count);
        cout << "Move " << n << " from " << mid << " to " << dst <<endl;
        hanoid(n-1, src, mid, dst, count);
    }
}


int main(){
    int n, count=0;
    cin >> n;
    string src="left", mid="mid", right="right";
    hanoid(n, src, mid, right, count);
    cout << "It will move " << count << " steps.";
    return 0;
}

import java.util.Scanner;
public class Hanota {

    public static void move(int n, String from, String to){
        System.out.println("将"+ n + "从" + from + "移动到" + to);
    }

    public static void hanota(int n, String A, String B, String C){
        if(n == 1){
            move(n, A, C);
        }else{
            hanota(n-1, A, C, B);
            move(n, A, C);
            hanota(n-1, B, A, C);
        }
    }


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        hanota(n, "A", "B", "C");
    }
}

import java.util.Scanner;
public class Main {
    static private int count=0;

    public static void move(int n, String from, String to){
        System.out.println("Move " + n + " from " + from + " to " + to);
        count++;
    }


    public static void hanota(int n, String A, String B, String C){
        if(n == 1){
            move(n, A, B);
            move(n, B, C);
            return;
        }else{
            hanota(n-1, A, B, C);
            move(n, A, B);
            hanota(n-1, C, B, A);
            move(n, B, C);
            hanota(n-1, A, B, C);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        hanota(n, "left", "mid", "right");
        System.out.println("It will move " + count + " steps.");
    }
}

#include "iostream"
#include "vector"
#include "string"

using namespace std;

vector<string> ump;
int count;

void dfs(int n,int src,int dest)
{
    if(n==1) {
        cout<<"Move 1 from "<<ump[src-1]<<" to mid"<<endl;
        cout<<"Move 1 from mid to "<<ump[dest-1]<<endl;
        count+=2;
        return;
    }
    dfs(n-1,src,dest);
    cout<<"Move "<<n<<" from "<<ump[src-1]<<" to mid"<<endl;
    count++;
    dfs(n-1,dest,src);
    cout<<"Move "<<n<<" from mid to "<<ump[dest-1]<<endl;
    count++;
    dfs(n-1,src,dest);
}

int main(){
    int n;
    cin>>n;
    count=0;
    ump={"left","mid","right"};
    dfs(n,1,3);
    cout<<"It will move "<<count<<" steps.";
    return 0;
}

# include <bits/stdc++.h>

using namespace std;

// count 得传引用
void move(int n, string from, string to, int& count){
    cout << "Move " << n << " from " << from << " to " << to << endl;
    count++;
}

void hanota(int n, string left, string mid, string right, int& count){
    if(n == 1){
        move(n, left, mid, count);
        move(n, mid, right, count);
        return;
    }
    else {
        // 将n-1个圆盘从A移动到C,借助B hanota(n-1, A, B, C) 
        hanota(n - 1, left, mid, right, count);
        // 将n从A移动到B
        move(n, left, mid, count);
        // 将n-1个圆盘从C移动到A,借助B hanota(n-1, C,B,A) 
        hanota(n - 1, right, mid, left, count);
        // 将n从B移动到C     
        move(n, mid, right, count);
        // 将n-1个圆盘从A移动到C,借助B hanota(n-1, A, B, C) 
        hanota(n - 1, left, mid, right, count);
    }
}

int main()
{
    int n;
    cin >> n;
    int count = 0;
    hanota(n, "left", "mid", "right", count);
    cout << "It will move " << count << " steps.";
}

1. 首先需要将n-1个塔从左侧移动到右侧，交给函数helper(n-1,true)处理。
2. 然后将第n个塔直接移动到中间，打印路径，统计步数。
3. 将n-1个塔从右侧移动到左侧，交给helper(n-1,false)处理。
4. 将第n个塔直接从中间移动到右侧，打印路径，统计步数。
5. 将n-1个塔从左侧移动到右侧。交给函数helper(n-1, true)处理。
   

import java.io.*;
public class Main {
    static int count = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(bf.readLine());
        bf.close();
        count = 0;
        System.out.print(helper(n, true));
        System.out.println("It will move "+count+" steps.");
    }

    public static StringBuilder helper(int n, boolean bool) {
        if (n == 0)
            return new StringBuilder();
        StringBuilder sb;
        sb = helper(n - 1, bool);
        if (bool) {
            sb.append("Move " + n + " from left to mid\n");
        } else {
            sb.append("Move " + n + " from right to mid\n");
        }
        sb.append(helper(n - 1, !bool));
        if (!bool) {
            sb.append("Move " + n + " from mid to left\n");
        }else{
            sb.append("Move " + n + " from mid to right\n");
        }         sb.append(helper(n - 1, bool));
        count += 2;          return sb;
    }
}

    public static StringBuilder helper(int n, boolean bool) {
        if (n == 0)
            return new StringBuilder();

        StringBuilder sb = new StringBuilder(), temp;
        int num = count;
        temp = helper(n - 1, bool);
        sb.append(temp);
        num = count - num;
        if (bool) {
            sb.append("Move " + n + " from left to mid\n");
        } else {
            sb.append("Move " + n + " from right to mid\n");
        }
        sb.append(helper(n - 1, !bool));
        if (!bool) {
            sb.append("Move " + n + " from mid to left\n");
        } else {
            sb.append("Move " + n + " from mid to right\n");
        }
        count += 2;
        sb.append(temp);
        count += num;
        
        return sb;
    }

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	reader := bufio.NewReader(os.Stdin)
	str, _ := reader.ReadString('\n')
	str = strings.ReplaceAll(str, "\n", "")
	n, err := strconv.Atoi(str)
	if err != nil {
		fmt.Println(err)
	}

	fmt.Println("It will move", hanoi(n, "left", "mid", "right"), "steps.")
}

func hanoi(n int, left, mid, right string) int {
	if n == 1 {
		fmt.Println("Move 1 from", left, "to", mid)
		fmt.Println("Move 1 from", mid, "to", right)
		return 2
	} else {
		res := hanoi(n-1, left, mid, right)
		fmt.Println("Move", n, "from", left, "to", mid)
		res += hanoi(n-1, right, mid, left)
		fmt.Println("Move", n, "from", mid, "to", right)
		res += hanoi(n-1, left, mid, right)
		return res + 2
	}
}