Đề bài
Tháp Hà Nội là trò chơi bao gồm 3 cột ( 1 , 2 và 3) và có N đĩa có size khác nhau. Ban đầu, ở cột trái có tất cả N đĩa , được sắp xếp theo thứ tự tăng dần.
Nhiệm vụ của bạn là di chuyển tất cả các đĩa sang cột phải bằng cách dùng cột giữa. Mỗi bước, chúng ta chỉ được chọn một đĩa trên đầu của một cột sang cột khác. Và đĩa có diện tích nhỏ hơn luôn luôn nằm trên đĩa có diện tích lớn hơn.
Với cách chơi tối ưu, phải mất ít nhất bao nhiêu bước để chuyển hết được đĩa từ cột trái sang cột phải.
Dữ liệu:
- Dòng đầu tiên chứa số nguyên N : Số cái đĩa ( $1\leq N \leq 16$).
Kết quả:
- Dòng đầu tiên in số k đại diện cho số bước mà chúng ta cần di chuyển.
- Sau đó, k dòng tiếp theo in ra hai số a,b. Bạn chọn di chuyển từ cột a sang cột b.
Ví dụ:
Input
2
Output
3
1 2
1 3
2 3
Hướng dẫn
- Đây là một bài toán rất hay và khó. Thật không dể để có một lời giải dể hiểu cho bài toán này. Bài toán này ta sẽ dùng đệ quy để chuyển đĩa.
- Ý tưởng tổng quát là mình sẽ chuyển N-1 cái đĩa từ cột 1 sang cột 2 dùng cột 3. Sau đó mình sẽ di chuyển 1 đĩa từ cột 1 sang cột 3. Cuối cùng là di chuyển N-1 cột từ cột 2 sang cột 3 dùng cột 1.
- Ý tưởng rất là basic nhưng để hiểu và cài được lại là một chuyện khác =)). Admin mong khi có code tham khảo hãy chạy tay lại để hiểu rõ hơn bản chất bài toán.
Mã nguồn tham khảo
#include <bits/stdc++.h>
using namespace std;
#define task "test"
const int N = 1e5+1;
typedef pair<int,int> pi;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
int n;
void towerofhanoi(int n,int a,int b,int c){
if(n==0) return;
towerofhanoi(n-1,a,c,b);
cout << a << " " << c << '\n';
towerofhanoi(n-1,b,a,c);
}
void solve(){
cin >> n;
cout << (1<<n)-1 << '\n';
towerofhanoi(n,1,2,3);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if(fopen(task".inp","r")){
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
int t;
t=1;
while(t-->0){
solve();
}
}