汉诺塔问题

/**主要思想，汉诺塔的移动函数为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;
	        }
	    }
}

// 时间复杂度，空间复杂度皆为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;
}

#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;
}

#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;
}

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;
        }
    }
}