汉诺塔问题 II

爱被打了一巴掌 2023-07-05 10:24 34阅读 0赞

## 题目链接： [HDUoj 汉诺塔问题II][HDUoj _II]. ##

### 题目： ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]

### 分析： ###

##### [这是汉诺塔问题的一个变体][Link 1]. #####

原来的条件不变，把三根柱子换成四根柱子

对于该问题：

我们可以先找出上边连续的k个小盘，把他们放在一根柱子上，

剩下的大盘不能覆盖在小盘上，只能按照经典汉诺塔问题排列在目标柱上，

最后把小盘覆盖在大盘上

##### 即：F（n）=F(k)+ Math.pow(2, n-k) + F(k) #####

对于小盘的移动次数，我们可以根据已知移动次数求解

当小盘个数为1时，移动次数为1，  
当小盘个数为2时，移动次数为3，  
。。。逐步递推。。。  
F（n）=F(k)+ Math.pow(2, n-k) + F(k)

##### 最后列举出所有的k，对比出所有情况的最小值即为结果 #####

### 代码： ###

import java.util.Scanner;
    
    public class Main {
    	public static int arr[] = new int[65];
    
    	public static void f(int n) {
    		arr[1] = 1;
    		arr[2] = 3;
    		//对数组的每个位置的数据进行初始化
    		for (int i = 3; i < 65; i++) {
    			//定义汉诺塔的最小移动次数是一个非常大的数
    			int min = Integer.MAX_VALUE;
    			//将i层的汉诺塔分成两块进行动态规划处理
    			for (int j = 1; j < i; j++) {
    				//将前一部分小盘（j）移动到某一个特定的柱子上
    				//剩下的部分（i-j）按照正常的汉诺塔进行处理
    				//再把之前的小盘移动到目标柱
    				//对每次假设取最小值
    				min = (int) Math.min(2 * arr[j] + Math.pow(2.0, i - j) - 1,min);
    			}
    			arr[i] = min;
    		}
    	}
    
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		//初始化答案数组
    		f(64);
    		while (sc.hasNext()) {
    			int n = sc.nextInt();
    			System.out.println(arr[n]);
    		}
    	}
    }

[HDUoj _II]: http://acm.hdu.edu.cn/showproblem.php?pid=1207
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200214095744414.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3,size_16,color_FFFFFF,t_70
[Link 1]: https://blog.csdn.net/qq_43652327/article/details/104293220