首页 > 搜索 > DFS搜索 > hdu 2184 汉诺塔VIII-DFS-[解题报告]C++
2013
12-30

hdu 2184 汉诺塔VIII-DFS-[解题报告]C++

汉诺塔VIII

问题描述 :

1,2,…,n表示n个盘子.数字大盘子就大.n个盘子放在第1根柱子上.大盘不能放在小盘上.在第1根柱子上的盘子是a[1],a[2],…,a[n]. a[1]=n,a[2]=n-1,…,a[n]=1.即a[1]是最下面的盘子.把n个盘子移动到第3根柱子.每次只能移动1个盘子,且大盘不能放在小盘上.问移动m次后的状况.

输入:

第1行是整数T,表示有T组数据,下面有T行
每行2个整数n (1 ≤ n ≤ 63) ,m≤ 2^n-1

输出:

第1行是整数T,表示有T组数据,下面有T行
每行2个整数n (1 ≤ n ≤ 63) ,m≤ 2^n-1

样例输入:

3
3 2
4 5
39 183251937942

样例输出:

1 3
1 2
1 1
2 4 1
1 3
1 2
13 39 36 33 30 27 24 21 18 15 12 9 4 1
12 38 35 32 29 26 23 20 17 14 11 8 5
14 37 34 31 28 25 22 19 16 13 10 7 6 3 2

汉诺塔经典模型的一个问题,根本思想是基于汉诺塔递归模拟写法的剪枝统计,此题就是给你盘子的个数n,问你步数为m时,三个柱子上的盘子的分布情况?

解题思路:在汉诺塔递归的DFS中讨论剩下m的步数,然后选择进入不同的递归层数,并模拟盘子的移动,整体复杂度为:O(n^2)

递归代码写之纠结,详见代码:

/* 
 * File:   main.cpp
 * Author: hit-acm
 *
 * Created on 2012年8月27日, 下午7:40
 */

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
const int MAXN = 65;
int a[3][MAXN];
int size[3];
unsigned long long ans[MAXN];

void init() {
    ans[0] = 0;
    for (int i = 1; i < MAXN; i++) {
        ans[i] = 2 * ans[i - 1] + 1;
    }
}

void DFS(int n, unsigned long long m, int s, int e, int mid) {
    if (n <= 0) {
        return;
    }
    if (m < ans[n - 1]) {
        DFS(n - 1, m, s, mid, e);
    } else if (m == ans[n - 1]) {
        size[s] -= n - 1;
        for (int i = 1; i < n; i++) {
            a[mid][size[mid]++] = a[s][size[s] + i - 1];
        }
    } else {
        a[e][size[e]++] = n;
        size[s] -= n;
        for (int i = 1; i < n; i++) {
            a[mid][size[mid]++] = a[s][size[s] + i];
        }
        DFS(n - 1, m - ans[n - 1] - 1, mid, e, s);
    }
}

void get_result(int n, unsigned long long m) {
    for (int i = 0; i < 3; i++) {
        size[i] = 0;
    }
    size[0] = n;
    for (int i = 0; i < n; i++) {
        a[0][i] = n - i;
    }
    DFS(n, m, 0, 2, 1);
    for (int i = 0; i < 3; i++) {
        printf("%d", size[i]);
        for (int j = 0; j < size[i]; j++) {
            printf(" ");
            printf("%d", a[i][j]);
        }
        putchar('\n');
    }
}

int main() {
    int T;
    int n;
    unsigned long long m;
    init();
    scanf("%d", &T);
    while (T--) {
        scanf("%d%llu", &n, &m);
        get_result(n, m);
    }
    return 0;
}

解题转自:http://blog.csdn.net/cyb6100300115/article/details/7913798


  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  2. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n

  3. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?

  4. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。