BOJ 11729-ハノイタワー移動

11024 ワード
algorithm divide&conquer boj テキストリンク
Problem
https://www.acmicpc.net/problem/11729
3本の棒があり、大きさの異なる円板が棒に積み上げられている.
出力1番の棒に積まれた円盤を3番の棒に移動するのに必要な最小回数と手順.
  • 条件
  • は一度に1つの円板を別の塔に移動するしかありません.
  • に積まれた原版は、いつも上のほうが下のほうより小さいです.
    • Solution
    これはとても有名なハノイタワー問題です.
    もう一度口にして解決できる.
    n個の円板が存在する場合、n番の円板を3番に移動するには、
    (1)n-1個のディスクを2番に移動します.
    (2)n番のネガを3番に移動します.
    (3)n-1個のディスクを3番に移動する.
    として定義できます.
    このように一般化すると、中の小さな問題は自分で解決します.
    また,移動回数は一般項目を得ることができる.
    結論としては2^n - 1号です.この部分は検索して確認することをお勧めします!
    Code
    #include <bits/stdc++.h>
using namespace std;

void hanoi(int n, int from, int by, int to) {
    if (n == 0) return;
    hanoi(n - 1, from, to, by);
    //cout << n << "번 원판을 " << from << " 에서 " << to << " 로 옮긴다 \n";
   cout << from << ' ' << to << '\n';
    hanoi(n - 1, by, from, to);

    return;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    long long ans = 1;
    cin >> n;
    for (int i = 0; i < n; i++)
        ans *= 2;
    cout << ans - 1 << '\n';
    hanoi(n, 1, 2, 3);

    return 0;
}
    資料構造を学習する際、熱血資料構造で学習したことがあり、初期に回帰に関するハノイタワーの説明があった.不思議な記憶だった.
    上記の問題はby変数を用いず,始点と終点からのみコードを生成できる.
    #include <bits/stdc++.h>
using namespace std;

void hanoi(int n, int from, int to) {
    if (n == 0) return;
    hanoi(n - 1, from, 6 - from - to);
   cout << from << ' ' << to << '\n';
    hanoi(n - 1, 6-from-to,to);

    return;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    long long ans = 1;
    cin >> n;
    for (int i = 0; i < n; i++)
        ans *= 2;
    cout << ans - 1 << '\n';
    hanoi(n, 1, 3);

    return 0;
}
    ++最初はpow関数を用いて移動回数を出力し,float型に戻るため,上記のように簡単に繰り返し文を用いた.
    注:尹承佑の熱血資料構造、https://code.plus/course/43、分期征服(練習)
    マングース101:サブドキュメントの操作
    「買ってよかったもの」をまとめるWebサービスを作りました！【Rails + Vue.js】