عرض مصدر Algorithms/Towers of Hanoi

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

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

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

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

# تحريك القرص الأول من <code>'A'</code> إلى <code>'B'</code>.
# تحريك القرص الثاني من <code>'A'</code> إلى <code>'C'</code>.
# تحريك القرص الأول من <code>'B'</code> إلى <code>'C'</code>.

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

# تحريك الأقراص <code>n-1</code> من <code>'A'</code> إلى <code>'B'</code>.
# تحريك القرص الأخير من <code>'A'</code> إلى <code>'C'</code>.
# تحريك الأقراص <code>n-1</code> من <code>'B'</code> إلى <code>'C'</code>.

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

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

* C++‎:

<source lang="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; 
} 
</source>
* بايثون:

<source lang="python">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') 
</source>
* جافا:

<source lang="java">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'); // الحروف هي أسماء القضبان
	} 
} 
</source>
تعطي الشيفرات السابقة المخرجات التالية:

<source lang="text"> 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
</source>
يلاحظ من الأمثلة السابقة أن عدد الحركات الكلي هو <code>‎2<sup>n</sup>-1</code> إذ تمثّل <code>n</code> عدد الأقراص، وأنّ الدالة تستدعى <code>‎2<sup>(n-1)</sup>‎</code> مرة. 

== مصادر ==

* صفحة [https://www.geeksforgeeks.org/c-program-for-tower-of-hanoi/ Program for Tower of Hanoi] في توثيق الخوارزميات في موقع GeeksforGeeks.

[[تصنيف: الخوارزميات]]
[[تصنيف:التعاود]]