汉诺塔问题V

快来打我* 2023-07-05 10:27 38阅读 0赞

## 题目链接 [汉诺塔问题V][V]. ##

### 题目： ###

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

### 分析： ###

#### [同经典汉诺塔问题类似][Link 1]. ####

不同的是本题恰需要知道每个圆盘所移动的次数

添加一个二维数组用于记录不同圆盘数内各个圆盘的移动次数

设有n个圆盘：

当n==1时，仅仅需要移动一次

当n>1时，有三步操作

1.  把n-1个圆盘移动到中间盘
2.  把最大盘移动到目标盘
3.  把n-1个圆盘移动到目标盘

##### 可以得到递推公式 #####

if(盘的数目==当前盘的编号){
    	arr[盘的数目][当前盘的编号]=1；
    }else{
    	arr[盘的数目][当前盘的编号]=arr[盘的数目-1][当前盘的编号]*2;
    }

##### 可以用三目运算符 #####

arr[i][j]=j==i?1:arr[i-1][j]*2;

### AC代码： ###

import java.util.Scanner;
    
    public class 汉诺塔V {
    	public static long [][] arr=new long[61][61];
    	public static void f(int n){
    		arr[1][1]=1;
    		for(int i=2;i<=n;i++){
    			for(int j=1;j<=i;j++){
    				arr[i][j]=j==i?1:arr[i-1][j]*2;
    			}
    		}
    	}
    	public static void main(String[] args) {
    		Scanner sc=new Scanner(System.in);
    		int t=sc.nextInt();
    		f(60);
    		while(t-->0){
    			int n=sc.nextInt();
    			int k=sc.nextInt();
    			System.out.println(arr[n][k]);
    		}
    	}
    }

[V]: http://acm.hdu.edu.cn/showproblem.php?pid=1995
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200214113912889.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

发表评论取消回复

表情：

评论列表（有 0 条评论，38人围观）

还没有评论，来说两句吧...

相关阅读

相关汉诺塔问题V

题目链接 [汉诺塔问题V][V]. 题目： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_te

快来打我*/ 2023年07月05日 10:27/ 0 赞/ 39 阅读

相关汉诺塔问题

import java.util.Scanner; / 汉诺塔问题不考虑中转，只考虑起始柱子到目标柱子的移动记住始终一点：中间一个不管是啥柱

素颜马尾好姑娘i/ 2022年09月30日 00:32/ 0 赞/ 249 阅读

相关汉诺塔问题

1.汉诺塔问题：如果将n个盘子（由小到大）从a通过b，搬到c，搬运过程中不能出现小盘子在大盘子下面的情况。分析：这个一个递归问题。只要将n-1个盘子从a通过c（没有中间点肯

刺骨的言语ヽ痛彻心扉/ 2022年08月20日 10:14/ 0 赞/ 328 阅读

相关汉诺塔问题

“汉诺塔问题”的Java重写思路：典型的递归问题。 “汉诺塔问题”的Java重写代码： public class Hanoi {

不念不忘少年蓝@/ 2022年07月21日 05:42/ 0 赞/ 235 阅读

相关汉诺塔V

Problem Description n个盘子的汉诺塔问题的最少移动次数是2^n-1,即在移动过程中会产生2^n个系列。由于发生错移产生的系列就增加了，这种

小鱼儿/ 2022年05月28日 06:37/ 0 赞/ 113 阅读

相关汉诺塔问题

汉诺塔汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵

爱被打了一巴掌/ 2022年05月18日 00:40/ 0 赞/ 332 阅读

相关汉诺塔问题

问题描述：相传在[古印度][Link 1]圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺

向右看齐/ 2022年04月17日 05:12/ 0 赞/ 362 阅读

相关汉诺塔问题

汉诺塔问题是经典的递归问题，它的递归类型是：求解问题的方法是递归的。解题思路： 1. 首先将n-1个盘子从X借助Z移动到Y。 2. 将第n个盘子从X移动到Z。 3.

ゝ一世哀愁。/ 2022年03月15日 15:48/ 0 赞/ 306 阅读

相关汉诺塔问题

汉诺塔(Tower of Hanoi)源于印度传说中，大梵天创造世界时造了三根金钢石柱子，其中一根柱子自底向上叠着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新

梦里梦外;/ 2021年09月28日 17:06/ 0 赞/ 567 阅读

相关汉诺塔问题

汉诺塔问题 -------------------- 文章目录汉诺塔问题 1. 问题描述 2. 问题分析 3. 代

刺骨的言语ヽ痛彻心扉/ 2021年09月23日 23:26/ 0 赞/ 430 阅读