Tower of Hanoi समस्या

Tower of Hanoi pancakes के एक stack को एक plate से दूसरी में move करने जैसा है, एक समय में एक pancake, कभी एक बड़े pancake को एक छोटे पर नहीं रखते।

In this page:

Problem Idea
Recursive Rule
Base Case
Understanding the Process
Practice

Syntax

markup

def hanoi(n, source, target, auxiliary):
    if n == 1:
        print(source, '->', target)
        return
    hanoi(n - 1, source, auxiliary, target)
    print(source, '->', target)
    hanoi(n - 1, auxiliary, target, source)

Problem Idea

Tower of Hanoi एक classic puzzle है जहां आपको अलग-अलग sized disks का एक stack एक rod से दूसरी में move करना है, एक तीसरे rod को helper के रूप में उपयोग करते हुए, कभी एक बड़े disk को एक छोटे के ऊपर रखे बिना। यह एक favorite recursion teaching example है क्योंकि recursive solution moves directly plan करने की कोशिश से नाटकीय रूप से simpler है।

उदाहरण: Problem Idea

#include <iostream>
using namespace std;
int main() {
	cout << "Move 3 disks from rod A to rod C using rod B as helper";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Move 3 disks from rod A to rod C using rod B as helper");
	}
}

print("Move 3 disks from rod A to rod C using rod B as helper")

#include <stdio.h>
int main() {
	printf("Move 3 disks from rod A to rod C using rod B as helper");
	return 0;
}

Recursive Rule

Recursive insight top n-1 disks को एक group की तरह treat करना है: पूरे group को helper rod तक रास्ते से हटाएं, single largest disk को सीधे target तक move करें, फिर n-1 group को helper rod से इसके ऊपर move करें। उन दो n-1 moves में से हर एक उसी problem का बस एक छोटा version है।

उदाहरण: Recursive Rule

#include <iostream>
using namespace std;
void hanoi(int n, char from, char to, char via) {
	if (n == 0) return;
	hanoi(n - 1, from, via, to);
	cout << "Move disk " << n << " from " << from << " to " << to << endl;
	hanoi(n - 1, via, to, from);
}
int main() {
	hanoi(3, 'A', 'C', 'B');
	return 0;
}

public class Main {
	static void hanoi(int n, char from, char to, char via) {
		if (n == 0) return;
		hanoi(n - 1, from, via, to);
		System.out.println("Move disk " + n + " from " + from + " to " + to);
		hanoi(n - 1, via, to, from);
	}
	public static void main(String[] args) {
		hanoi(3, 'A', 'C', 'B');
	}
}

def hanoi(n, frm, to, via):
    if n == 0:
        return
    hanoi(n - 1, frm, via, to)
    print("Move disk", n, "from", frm, "to", to)
    hanoi(n - 1, via, to, frm)

hanoi(3, 'A', 'C', 'B')

#include <stdio.h>
void hanoi(int n, char from, char to, char via) {
	if (n == 0) return;
	hanoi(n - 1, from, via, to);
	printf("Move disk %d from %c to %c\n", n, from, to);
	hanoi(n - 1, via, to, from);
}
int main() {
	hanoi(3, 'A', 'C', 'B');
	return 0;
}

Base Case

Base case एक single disk है, जो बस एक step में अपनी current rod से target rod तक सीधे move होता है — किसी और recursion की ज़रूरत नहीं। इस stopping point के बिना, 'n-1 disks move करो' step हमेशा के लिए और भी छोटे groups move करने को कहता रहता।

उदाहरण: Base Case

#include <iostream>
using namespace std;
void hanoi(int n, char from, char to, char via) {
	if (n == 1) { cout << "Move disk 1 from " << from << " to " << to << endl; return; }
	hanoi(n - 1, from, via, to);
	cout << "Move disk " << n << " from " << from << " to " << to << endl;
	hanoi(n - 1, via, to, from);
}
int main() {
	hanoi(2, 'A', 'C', 'B');
	return 0;
}

public class Main {
	static void hanoi(int n, char from, char to, char via) {
		if (n == 1) { System.out.println("Move disk 1 from " + from + " to " + to); return; }
		hanoi(n - 1, from, via, to);
		System.out.println("Move disk " + n + " from " + from + " to " + to);
		hanoi(n - 1, via, to, from);
	}
	public static void main(String[] args) {
		hanoi(2, 'A', 'C', 'B');
	}
}

def hanoi(n, frm, to, via):
    if n == 1:
        print("Move disk 1 from", frm, "to", to)
        return
    hanoi(n - 1, frm, via, to)
    print("Move disk", n, "from", frm, "to", to)
    hanoi(n - 1, via, to, frm)

hanoi(2, 'A', 'C', 'B')

#include <stdio.h>
void hanoi(int n, char from, char to, char via) {
	if (n == 1) { printf("Move disk 1 from %c to %c\n", from, to); return; }
	hanoi(n - 1, from, via, to);
	printf("Move disk %d from %c to %c\n", n, from, to);
	hanoi(n - 1, via, to, from);
}
int main() {
	hanoi(2, 'A', 'C', 'B');
	return 0;
}

Understanding the Process

यह three-step pattern — छोटे group को हटाओ, बड़ा piece move करो, छोटे group को वापस ऊपर move करो — recursion के हर level पर repeat होता है, बस हर बार कम disks और swapped rod roles के साथ। 3 disks के लिए इसे हाथ से trace करना pattern को abstractly reason करने से पहले click करा देता है।

उदाहरण: Understanding the Process

#include <iostream>
using namespace std;
int moveCount = 0;
void hanoi(int n, char from, char to, char via) {
	if (n == 0) return;
	hanoi(n - 1, from, via, to);
	moveCount++;
	hanoi(n - 1, via, to, from);
}
int main() {
	hanoi(3, 'A', 'C', 'B');
	cout << "Total moves: " << moveCount;
	return 0;
}

public class Main {
	static int moveCount = 0;
	static void hanoi(int n, char from, char to, char via) {
		if (n == 0) return;
		hanoi(n - 1, from, via, to);
		moveCount++;
		hanoi(n - 1, via, to, from);
	}
	public static void main(String[] args) {
		hanoi(3, 'A', 'C', 'B');
		System.out.println("Total moves: " + moveCount);
	}
}

move_count = 0
def hanoi(n, frm, to, via):
    global move_count
    if n == 0:
        return
    hanoi(n - 1, frm, via, to)
    move_count += 1
    hanoi(n - 1, via, to, frm)

hanoi(3, 'A', 'C', 'B')
print("Total moves:", move_count)

#include <stdio.h>
int moveCount = 0;
void hanoi(int n, char from, char to, char via) {
	if (n == 0) return;
	hanoi(n - 1, from, via, to);
	moveCount++;
	hanoi(n - 1, via, to, from);
}
int main() {
	hanoi(3, 'A', 'C', 'B');
	printf("Total moves: %d", moveCount);
	return 0;
}

Practice

n disks solve करने में कम से कम 2^n - 1 moves लगते हैं, यही कारण है कि Tower of Hanoi यह illustrate करने के लिए भी उपयोग होता है कि exponential growth कितनी जल्दी impractical हो जाती है — अकेले 20 disks को एक million से ज़्यादा moves चाहिए।

उदाहरण: Practice

#include <iostream>
#include <cmath>
using namespace std;
int main() {
	int n = 4;
	cout << "Minimum moves for " << n << " disks: " << (int)pow(2, n) - 1;
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int n = 4;
		System.out.println("Minimum moves for " + n + " disks: " + ((int) Math.pow(2, n) - 1));
	}
}

n = 4
print("Minimum moves for", n, "disks:", 2 ** n - 1)

#include <stdio.h>
#include <math.h>
int main() {
	int n = 4;
	printf("Minimum moves for %d disks: %d", n, (int)pow(2, n) - 1);
	return 0;
}

Chapter Quiz — Complete all 7 topics to unlock

0/7 topics done

Complete these topics first:

← Previous Lesson Fibonacci and Factorial Next Lesson → Backtracking Introduction