Algorithms/Towers of Hanoi

خوارزمية برج هانوي Tower of Hanoi هي مسألة رياضية يستخدم فيها ثلاثة قضبان و عدد معين (ليكن n) من الأقراص، والهدف هو تحريك كدس الأقراص من قضيب إلى آخر باتباع القواعد التالية:

1. يمكن لقرص واحد فقط أن يتحرك في كل مرة.
2. يؤخذ القرص العلوي من كدس الأقراص في كل حركة ويوضع فوق الكدس الآخر، بمعنى أنّه يسمح للقرص العلوي فقط بالحركة.
3. لا يسمح بوضع قرص فوق قرص أصغر منه.

لنفترض على سبيل المثال أنّ لدينا قرصان فقط، ولنفترض أن القضيب الأول = 'A' والثاني = 'B' والثالث 'C'.

يمكن حل المسألة باتباع الخطوات الثلاثة التالية:

1. تحريك القرص الأول من 'A' إلى 'B'.
2. تحريك القرص الثاني من 'A' إلى 'C'.
3. تحريك القرص الأول من 'B' إلى 'C'.

يلاحظ أن نمط الحركات هو:

1. تحريك الأقراص n-1 من 'A' إلى 'B'.
2. تحريك القرص الأخير من 'A' إلى 'C'.
3. تحريك الأقراص n-1 من 'B' إلى 'C'.

تنفيذ الخوارزمية

تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:

• C++‎:

#include <bits/stdc++.h> 
using namespace std; 

void towerOfHanoi(int n, char from_rod, 
					char to_rod, char aux_rod) 
{ 
	if (n == 1) 
	{ 
		cout << "Move disk 1 from rod " << from_rod << 
							" to rod " << to_rod<<endl; 
		return; 
	} 
	towerOfHanoi(n - 1, from_rod, aux_rod, to_rod); 
	cout << "Move disk " << n << " from rod " << from_rod << 
								" to rod " << to_rod << endl; 
	towerOfHanoi(n - 1, aux_rod, to_rod, from_rod); 
} 

// اختبار الدالة السابقة
int main() 
{ 
	int n = 4; // Number of disks 
	towerOfHanoi(n, 'A', 'C', 'B'); // الحروف هي أسماء القضبان
	return 0; 
}

• بايثون:

def TowerOfHanoi(n , from_rod, to_rod, aux_rod): 
	if n == 1: 
		print "Move disk 1 from rod",from_rod,"to rod",to_rod 
		return
	TowerOfHanoi(n-1, from_rod, aux_rod, to_rod) 
	print "Move disk",n,"from rod",from_rod,"to rod",to_rod 
	TowerOfHanoi(n-1, aux_rod, to_rod, from_rod) 
		
# اختبار الدالة السابقة
n = 4
# الحروف هي أسماء القضبان
TowerOfHanoi(n, 'A', 'C', 'B')

• جافا:

class GFG 
{ 
	static void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) 
	{ 
		if (n == 1) 
		{ 
			System.out.println("Move disk 1 from rod " + from_rod + " to rod " + to_rod); 
			return; 
		} 
		towerOfHanoi(n-1, from_rod, aux_rod, to_rod); 
		System.out.println("Move disk " + n + " from rod " + from_rod + " to rod " + to_rod); 
		towerOfHanoi(n-1, aux_rod, to_rod, from_rod); 
	} 
	
	// اختبار التابع السابق
	public static void main(String args[]) 
	{ 
		int n = 4; // عدد الأقراص
		towerOfHanoi(n, 'A', 'C', 'B'); // الحروف هي أسماء القضبان
	} 
}

تعطي الشيفرات السابقة المخرجات التالية:

 Move disk 1 from rod A to rod B
 Move disk 2 from rod A to rod C
 Move disk 1 from rod B to rod C
 Move disk 3 from rod A to rod B
 Move disk 1 from rod C to rod A
 Move disk 2 from rod C to rod B
 Move disk 1 from rod A to rod B
 Move disk 4 from rod A to rod C
 Move disk 1 from rod B to rod C
 Move disk 2 from rod B to rod A
 Move disk 1 from rod C to rod A
 Move disk 3 from rod B to rod C
 Move disk 1 from rod A to rod B
 Move disk 2 from rod A to rod C
 Move disk 1 from rod B to rod C

يلاحظ من الأمثلة السابقة أن عدد الحركات الكلي هو ‎2n-1 إذ تمثّل n عدد الأقراص، وأنّ الدالة تستدعى ‎2(n-1)‎ مرة.

مصادر

• صفحة Program for Tower of Hanoi في توثيق الخوارزميات في موقع GeeksforGeeks.