首页 > 试题广场 > 汉诺塔问题
[编程题]汉诺塔问题
  • 热度指数:2511 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个整数n,代表汉诺塔游戏中从小到大放置n个圆盘,假设开始所有圆盘都在左边的柱子上,那么用最优的办法把所有圆盘都移动到右边的柱子上的过程,就称为最优移动轨迹。给定一个整型数组arr, 其中只含有1、2和3,代表所有圆盘目前的状态,1代表左柱,2代表中柱,3代表右柱,a[i]的值代表第i+1个圆盘的位置(a[i]下标从0开始)。比如,arr=[3,3,2,1], 代表第1个圆盘在右柱上、第2个圆盘在右柱上、第3个圆盘在中柱上、第4个圆盘在左柱上。如果arr代表的状态是最优移动轨迹过程中出现的状态,输出arr这种状态是最优移动轨迹中的第几个状态(由于答案可能较大,请输出对取模后的答案)。如果arr代表的状态不是最优移动轨迹过程中出现的状态,则输出-1。


输入描述:
输入包括两行,第一行一个整数n,表示圆盘的个数,第二行n个正整数,且均为1或2或3,第i个整数表示第i个圆盘位置。


输出描述:
输出一个整数,表示这种状态是第几个最优移动状态(输出对取模后的答案),无解输出-1。
示例1

输入

2
1 1

输出

0
示例2

输入

2
3 3

输出

3

备注:
时间复杂度,空间复杂度
经典汉诺塔问题的最优解可以抽象成三步:
  1. 1~i-1号圆盘从left柱移动到mid柱;
  2. i号圆盘从left柱移动到right柱;
  3. 最后将1~i-1号圆盘从mid柱移动到right柱。
假设有个函数F(N)表示移动N个汉诺塔,当只有一个盘的时候F(1)=1,则根据以上的分析就可以得到递推公式如下:          
因此有如下三种情况:
  1. 如果i号圆盘在left柱上,说明步骤1还没有完成,我们需要递归看看步骤1走到哪了
  2. 如果i号圆盘在right柱上,说明步骤2已经完成了,我们需要递归看看步骤3走到哪了,而步骤一和二一共走了F(i-1)-1+1=2i-1步;
  3. 如果i号圆盘在mid柱上,则说明这不是最优移动中的任何一步,因为不存在i号圆盘在mid柱上的步骤。
递归版本代码很好写,但是AC不了
// 递归版本
import java.lang.String;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] strArr = br.readLine().split(" ");
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) arr[i] = Integer.parseInt(strArr[i]);
        System.out.println(getStepNum(arr, arr.length - 1, 1, 2, 3));
    }
    
    public static int getStepNum(int[] arr, int i, int left, int mid, int right) {
        if(i == -1) return 0;
        if(arr[i] == mid) return -1;
        if(arr[i] == left){
            return getStepNum(arr, i - 1, left, right, mid);        // i圆盘在left柱上,看第一步进行到什么程度
        }else{
            int rest = getStepNum(arr, i - 1, mid, left, right);    // i圆盘在right柱上,看第三步进行到什么程度
            return rest != -1? ((1 << i) + rest) % 1000000007: -1;
        }
    }
}
由于数据大得离谱,用递归会触发StackOverflowError的错误,因此要将递归思路改成迭代实现。本以为可以AC了,然而发现提交之后仍然还有坑(怪不得题目说空间复杂度O(N)),在计算2的幂次时也可能溢出,因此在计算指数时也需要取模。
import java.lang.String;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] strArr = br.readLine().split(" ");
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) arr[i] = Integer.parseInt(strArr[i]);
        System.out.println(getStepNum(arr, arr.length - 1, 1, 2, 3));
    }
    
    public static int getStepNum(int[] arr, int i, int left, int mid, int right) {
        int steps = 0;
        int cache = 0;
        int[] cacheRes = new int[arr.length];
        int temp = 1;
        for(int k = 0; k < arr.length; k++){
            cacheRes[k] = temp;
            temp = (temp << 1) % 1000000007;
        }
        while(i >= 0){
            if(arr[i] == mid) return -1;
            if(arr[i] == right){
                // i圆盘在right柱上,看第3步进行到什么程度
                steps = (steps + cacheRes[i]) % 1000000007;;
                // 第3步交换left和mid
                cache = left;
                left = mid;
                mid = cache;
            }else{
                // i圆盘在left柱上,看第1步进行到什么程度
                // 第一步交换right和mid
                cache = right;
                right = mid;
                mid = cache;
            }
            i--;
        }
        return steps;
    }
}

编辑于 2021-12-08 16:22:54 回复(0)
思路和 Yeahoffer 一致,用循环解决,详情见注释

#include<iostream>
#include<vector>

using namespace std;

int main() {
    int n;
    cin >> n;
	vector<int> state(n);
    for(int index=0;index<n;index++){
        cin >> state[index];
    }
	vector<bool> flag(n, false);
	int src=1,help=2,target=3;
    //从后往前检测状态
	for(int index=n-1;index>=0;index--){
        //注意更新 原位、辅助位、目标位 的真实柱编号
        //如果当前盘子已经被放到目标位置,则至少经过了2^n步(将其上的n-1个盘子移动到辅助位需要2^n-1步,将其移至目标位需要一步)
		if(state[index] == target){
            //接下来要将辅助位递归的转移到目标位;即原来的原位变成了辅助位,辅助位是原位
			flag[index] = true;
			int tmp = src;
			src = help;
			help = tmp;
		}
        //如果当前盘子还在原位,则无需处理
		else if(state[index] == src){
            //要先把其上的盘子转移到辅助位,才能取出最底下的盘子;即将辅助位改为目标,目标位暂时辅助
			int tmp = help;
			help = target;
			target = tmp;
		}
        //不可能把当前盘放到辅助位,这是浪费步骤的做法,非最优解,即导致无解
		else{
			cout << -1 << endl;
			return 0;
		}
	}
	int result = 0;
    //为了以O(n)计算2的次方,先用flag数组保存了状态,再循环累加所需次数
	for(int index=0,base=1;index<n;index++,base=(base<<1)%1000000007){
		if(flag[index]) result = (result+base)%1000000007;
	}
	cout << result << endl;
}


发表于 2020-07-30 16:41:08 回复(1)

/**主要思想,汉诺塔的移动函数为Hanoi(n),从left,借助mid移动到right需要几步,递归可知,Hanoi(n)=2Hanoi(n)+1,简单点儿,可以利用位运算移位来完成,即:Hanoi(n)=1<<n-1;
1.在移动的时候对于Hanoi(n)来说,进行完Hanoi(n-1)的辅助之后,是直接把n放到目标上的,所以不会出现n在mid上的情况。
2.所以从大到小对圆盘进行考察,若是它在left上,则是正在进行Hanoi(n-1)的操作,即正在借助right转移到mid上。还未全部完成,不需要计算。(其部分完成的交给递归来计算)
3.若是n已经在right上了,说明已经完成了目标,当前正在进行借助left从mid到right的操作,则将其结果加起来就是答案

import java.util.*;
public class Main {
    public static void main(String[] args) {
	    Scanner scanner = new Scanner(System.in);
	     int n = scanner.nextInt();
	    int[] arr = new int[n];
	    for(int i=0; i<n; i++){
	    arr[i] = scanner.nextInt();
	    System.out.println(hanoi1(arr, n-1, 1, 2, 3));	    
                                        }
                    }
    public static int hanoi1(int[]arr,int n,int left,int mid,int right){
	     // 所有的盘子递归结束
	   if(n == -1){
	       return 0;
	         }
	  //1.如果当前盘子在中间,不是最优解;
	   if(arr[n] == mid)
	   {return -1;}
    //2.当前盘子在左边,说明对第n盘子没有进行任何操作(如果是最优解),只需要递归求解前n-1个盘子的操作次数
	  if(arr[n] == left){
	     return hanoi1(arr, n-1, left, right, mid);
                            }
     //3.当前盘子在右边,说明数组已经完成了Hanoi的前两步
  //第一步将前n-1移动到中间步数为2^(n-1)-1,然后最后一个n移动到右边步数为1,总共为2^(n-1);
	  else {
	     int rest = hanoi1(arr, n-1, mid, left ,right);
	    // 如果rest个盘子不是最优解
	   if(rest == -1) {
	     return -1;}
	 //是最优解时返回取模的结果
          return ((1<<n) + rest)%1000000007;
	        }
	    }
}


编辑于 2020-07-16 18:27:47 回复(3)
// 时间复杂度,空间复杂度皆为O(n)解法
#include <iostream>
#include <vector>
using namespace std;

int main() {
	int n = 0;
	cin >> n;
	vector<int> arr(n);
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	int res = 0;
	int from = 1;
	int mid = 2;
	int to = 3;
	vector<int> arrhelper(n);
	int last = 1;
	for (int i = 0; i < n; i++) {
		arrhelper[i] = last;
		last = (last << 1) % 1000000007;
	}
	for (int i = n - 1; i >= 0; i--) {
		if (arr[i] == mid) {
			std::cout << -1 << std::endl;
			return 0;
		}
		else if (arr[i] == from) {
			int temp = to;
			to = mid;
			mid = temp;
		}
		else {
			res = (res + arrhelper[i]) % 1000000007;
			int temp = from;
			from = mid;
			mid = temp;
		}
	}
	std::cout << res << std::endl;
	return 0;
}

发表于 2019-08-21 15:01:38 回复(6)
#include 
#include 
#define MOD 1000000007
int main(void) {
    int n, *arr;
    scanf("%d", &n);
    if (n == 0) return -1;
    arr = (int *) malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        scanf("%d", arr + i);
    }
    int from = 1, mid = 2, to = 3;
    int i = n - 1, res = 0, tmp;
    // 记录2的i次幂
    int *pow2 = (int *) malloc(sizeof(int) * n);
    pow2[0] = 1;
    for (int i = 1; i < n; i++) {
        // 取模防止溢出
        pow2[i] = (pow2[i-1] << 1) % MOD;
    }
    while (i >= 0) {
        if (arr[i] != from && arr[i] != to) {
            res = -1;
            break;
        }
        if (arr[i] == from) {
            tmp = to;
            to = mid;
        } else {
            res = (res + pow2[i]) % MOD;
            tmp = from;
            from = mid;
        }
        mid = tmp;
        i--;
    }
    printf("%d\n", res);
    free(arr);
    free(pow2);
    return 0;
}
发表于 2022-01-24 17:49:38 回复(0)
#include<bits/stdc++.h>
using namespace std;
//第n个盘子要么在左边(需要先把上面n-1个放到辅助盘上才能移动n),要么在最右边(在把上面的n-1个移动到fuzhu盘之后,可以把n放在最右边),
//不会出现第n个盘子在辅助盘上的情况
int mod=1e9+7;
//递归实现和非递归均可ac
// int hannuo(int n,vector<int>& arr,int from,int fuzhu,int to,vector<int>& rec){//递归写法
//     if(n==0) return 0;//已经检测完
//     if(arr[n-1]==fuzhu) return -1;//不会出现第n个盘子在中间的情况,此时非法
//     else if(arr[n-1]==from) return hannuo(n-1,arr,from,to,fuzhu,rec);
//     else if(arr[n-1]==to){
//         int temp=hannuo(n-1,arr,fuzhu,from,to,rec);
//         if(temp==-1) return -1;
//         return (rec[n-1]+temp)%mod;
//     }
// }

int hannuo(int n,vector<int>& arr,int from,int fuzhu,int to,vector<int>& rec){//非递归写法
    int ans=0;
    while(n>0){
        if(arr[n-1]==fuzhu){
            return -1;
        }
        int newfrom,newfuzhu,newto;
        if(arr[n-1]==from){
            newfrom=from;
            newfuzhu=to;
            newto=fuzhu;
        }
        else if(arr[n-1]==to){
            ans=(ans+rec[n-1])%mod;
            newfrom=fuzhu;
            newfuzhu=from;
            newto=to;
        }
        n--;
        from=newfrom;
        fuzhu=newfuzhu;
        to=newto;
    }
    return ans;
}

int main(){
    int n;
    while(cin>>n){
        vector<int> arr(n);
        for(int i=0;i<n;i++){
            cin>>arr[i];
        }
        vector<int> rec(n);
        //2^n次方可能会超过1e9+7,因此需要用rec[i]存储2的i的次方(注意需要取mod)
        rec[0]=1;
        for(int i=1;i<n;i++){
            rec[i]=(rec[i-1]*2)%mod;
        }
        int from=1;
        int fuzhu=2;
        int to=3;
        cout<<hannuo(n,arr,from,fuzhu,to,rec)<<endl;
    }
    return 0;
}

发表于 2021-09-01 20:57:08 回复(0)
import java.io.*;
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int count = scanner.nextInt();
        int[] inputs = new int[count];
        for(int i=0; i<count; i++)
            inputs[i] = scanner.nextInt();
        System.out.println(helper(inputs, count-1, 1, 2, 3));
    }
    public static int helper(int[]arr, int i, int from, int mid, int to){
        if(i == -1)
            return 0;
        if(arr[i] != from && arr[i] != to)
            return -1;
        if(arr[i] == from)
            return helper(arr, i-1, from, to, mid);
        else {
            int rest = helper(arr, i-1, mid, from ,to);
            if(rest == -1)
                return -1;
            return (1<<i) + rest;
        }
    }
}
请检查是否存在数组越界等非法访问情况点击对比用例标准输出与你的输出
case通过率为70.59%。
不去管通过率。我没有去计算mod,也不管大数位运算导致溢出。这些问题应该不会和数组越界非法访问扯上关系把。当然已经看了别人的代码。
我比较关心到底是什么让程序判断数组越界或者非法访问?遇到很多次这种情况,“点击对比用例标准输出与你的输出”屁都没有。
有没有网友知道的,请告诉我。
发表于 2020-06-05 20:18:21 回复(1)