题解 | 61-递归和动态规划-汉诺塔II

#include <vector>
using namespace std;

class Hanoi {
public:
    int chkStep(vector<int> arr, int n) {
        if (n == 0) return -1; // 如果没有圆盘，返回 -1
        int i = n - 1, ans = 0; // 初始化索引和结果
        int left = 1, mid = 2, right = 3, temp = 2; // 定义柱子

        while (i >= 0) {
            // 检查当前圆盘的位置
            if (arr[i] != left && arr[i] != right) {
                return -1; // 如果圆盘不在有效位置，返回 -1
            } else if (arr[i] == left) {
                temp = right; // 更新临时变量
                right = mid; // 更新右柱
            } else {
                ans += 1 << i; // 计算当前状态的序号
                temp = left; // 更新临时变量
                left = mid; // 更新左柱
            }
            i--; // 移动到下一个圆盘
            mid = temp; // 更新中柱
        }
        return ans; // 返回计算得到的序号
    }
};

import java.util.*;

public class Hanoi {
    public int chkStep(int[] arr, int n) {
        if (n == 0) return -1; // 如果没有圆盘，返回 -1
        int i = n - 1, ans = 0; // 初始化索引和结果
        int left = 1, mid = 2, right = 3, temp = 2; // 定义柱子

        while (i >= 0) {
            // 检查当前圆盘的位置
            if (arr[i] != left && arr[i] != right) {
                return -1; // 如果圆盘不在有效位置，返回 -1
            } else if (arr[i] == left) {
                temp = right; // 更新临时变量
                right = mid; // 更新右柱
            } else {
                ans += 1 << i; // 计算当前状态的序号
                temp = left; // 更新临时变量
                left = mid; // 更新左柱
            }
            i--; // 移动到下一个圆盘
            mid = temp; // 更新中柱
        }
        return ans; // 返回计算得到的序号
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 读取圆盘数量
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt(); // 读取圆盘位置
        }
        Hanoi hanoi = new Hanoi();
        System.out.println(hanoi.chkStep(arr, n)); // 输出状态序号
    }
}

# -*- coding:utf-8 -*-

class Hanoi:
    def chkStep(self, arr, n):
        if n == 0:
            return -1  # 如果没有圆盘，返回 -1
        i = n - 1
        ans = 0  # 初始化结果
        left, mid, right = 1, 2, 3  # 定义柱子
        temp = 2

        while i >= 0:
            # 检查当前圆盘的位置
            if arr[i] != left and arr[i] != right:
                return -1  # 如果圆盘不在有效位置，返回 -1
            elif arr[i] == left:
                temp = right  # 更新临时变量
                right = mid  # 更新右柱
            else:
                ans += 1 << i  # 计算当前状态的序号
                temp = left  # 更新临时变量
                left = mid  # 更新左柱
            i -= 1  # 移动到下一个圆盘
            mid = temp  # 更新中柱

        return ans  # 返回计算得到的序号

# 示例用法
if __name__ == "__main__":
    n = int(raw_input("Enter the number of disks: "))  # 读取圆盘数量
    arr = map(int, raw_input("Enter the positions of disks: ").split())  # 读取圆盘位置
    hanoi = Hanoi()
    result = hanoi.chkStep(arr, n)  # 输出状态序号
    print "Result:", result  # 输出结果