อัลกอริทึมของหอคอยแห่งฮานอย: Python, C++ รหัส

หอคอยแห่งฮานอยคืออะไร?

หอคอยแห่งฮานอยเป็นปริศนาทางคณิตศาสตร์ที่ประกอบด้วยแท่งสามแท่งและแผ่นจานจำนวนมากวางซ้อนกัน มีชื่อเรียกอีกอย่างว่า Tower of Brahma หรือหอคอย Lucas ตามที่นักคณิตศาสตร์ชาวฝรั่งเศส Edouard Lucas แนะนำให้รู้จักในปี 1883 ปริศนานี้มีพื้นฐานมาจากตำนานเกี่ยวกับการเคลื่อนย้ายแผ่นทองคำระหว่างแท่งสามแท่ง

ปริศนานี้มีแท่งสามแท่งและดิสก์ซ้อนกันหลายจำนวน แท่งเหล่านั้นได้รับการออกแบบให้เป็นหอคอยแบบวงกลม ดังนั้นดิสก์ที่มีเส้นผ่านศูนย์กลางใหญ่กว่าจะเรียงซ้อนกันที่ด้านล่าง และดิสก์ขนาดเล็กกว่าจะซ้อนกันอยู่ด้านบน

เริ่มแรกเราได้รับหมุดหรือไม้เท้าสามอัน และหนึ่งในนั้น (A ดังแสดงในตัวอย่าง) มีดิสก์ทั้งหมดซ้อนกัน เรามุ่งหวังที่จะย้ายดิสก์ทั้งหมดจากแท่งหนึ่ง (A) ไปยังอีกแท่งหนึ่ง (C) โดยปฏิบัติตามกฎเฉพาะบางประการ

นี่คือการตั้งค่าเริ่มต้นของปริศนา -

และนี่คือเป้าหมายสุดท้าย-

กฎของหอคอยฮานอย

ต่อไปนี้เป็นกฎสำคัญบางประการสำหรับหอคอยฮานอย:

• สถานะเริ่มต้นของปริศนานี้ ดิสก์ทั้งหมดจะซ้อนกันเป็นแกนหนึ่ง
• สถานะสุดท้ายคือดิสก์ทั้งหมดจากก้านที่หนึ่งจะถูกซ้อนกันบนก้านที่สองหรือก้านที่สาม
• เราสามารถย้ายออนดิสก์จากแท่งหนึ่งไปยังอีกแท่งหนึ่งได้ตลอดเวลา
• เราสามารถย้ายได้เฉพาะดิสก์บนสุดจากแกนเท่านั้น
• ไม่สามารถวางดิสก์ไว้บนดิสก์อื่นซึ่งมีขนาดเล็กกว่าได้

ตำนานดั้งเดิมนั้นเกี่ยวกับการเคลื่อนย้ายแผ่นดิสก์ 64 แผ่น โดยนักบวชสามารถเคลื่อนย้ายแผ่นดิสก์ได้ครั้งละแผ่นตามกฎ ตามตำนานนั้น มีคำทำนายว่าโลกจะล่มสลายหากพวกเขาสามารถทำภารกิจนี้ได้สำเร็จ ในส่วนของความซับซ้อนของเวลา เราจะแสดงให้เห็นว่าการตั้งค่า Tower of Hanoi ที่มีแผ่นดิสก์ n แผ่นจะมีค่าใช้จ่ายในการเคลื่อนที่ 2^n – 1 ครั้ง

ดังนั้น หากบาทหลวงต้องการเวลา 1 วินาทีในการเคลื่อนย้ายแผ่นดิสก์ เวลาทั้งหมดที่พวกเขาต้องใช้ในการแก้ปริศนาจะเป็น 2^64 – 1 วินาที หรือ 584,942,417,356 ปี 26 วัน 7 ชั่วโมง และ 15 วินาที

อัลกอริทึมสำหรับหอคอยแห่งฮานอย

วิธีทั่วไปวิธีหนึ่งในการแก้ปัญหาหอคอยฮานอยคืออัลกอริธึมแบบเรียกซ้ำ อันดับแรก เราต้องตัดสินใจว่าจะใช้ไม้เท้าหรือหมุดสองอันเป็นแหล่งที่มาและปลายทาง และหมุดสำรองจะเป็นอุปกรณ์ช่วยหรืออุปกรณ์ช่วย

ต่อไปนี้เป็นขั้นตอนในการไขปริศนาหอคอยแห่งฮานอย:

• ย้ายดิสก์ n-1 ด้านบนจากหมุดต้นทางไปยังหมุดตัวช่วย
• หลังจากนั้น ย้ายดิสก์ที่ n จากหมุดต้นทางไปยังหมุดปลายทาง
• สุดท้าย ให้ย้ายดิสก์ n-1 ที่เหลือจากหมุดตัวช่วยไปยังหมุดปลายทาง

หมายเหตุ: หากเรามีดิสก์แผ่นเดียว เราก็สามารถย้ายจากต้นทางไปยังปลายทางได้โดยตรง

วิธีแก้ปริศนาหอคอยแห่งฮานอย

มาแสดงอัลกอริทึมสำหรับดิสก์สามแผ่นและพิจารณา peg A เป็นแหล่งที่มา peg B เป็นตัวช่วย และ peg C เป็นปลายทาง

ขั้นตอน 1) เริ่มแรก ดิสก์ทั้งหมดจะซ้อนกันบนหมุด A

ที่เวทีนี้:

ที่มา = Peg A
จุดหมาย = หมุดซี
ผู้ช่วย = เพ็ก บี

ตอนนี้ เราต้องย้ายดิสก์ n-1 อันดับแรกจากแหล่งที่มาไปยังตัวช่วยเหลือ

หมายเหตุ แม้ว่าเราจะสามารถย้ายดิสก์ได้ครั้งละหนึ่งดิสก์เท่านั้น แต่มันก็แบ่งปัญหาของเราจากปัญหา 3 ดิสก์ไปเป็นปัญหา 2 ดิสก์ ซึ่งเป็นการเรียกซ้ำ

ขั้นตอน 2) เมื่อเราเรียกการโทรซ้ำจากหมุด A และปลายทางคือหมุด B เราจะใช้หมุด C เป็นตัวช่วย

โปรดสังเกตว่าเราอยู่ในขั้นตอนหนึ่งอีกครั้งสำหรับปัญหาหอคอยฮานอยเดียวกันสำหรับดิสก์สองแผ่น

ตอนนี้เราจำเป็นต้องย้าย n-1 หรือดิสก์หนึ่งแผ่นจากต้นทางไปยังตัวช่วยเหลือ โดยย้ายดิสก์ที่เล็กที่สุดจากหมุด A ไปยังหมุด C

ที่เวทีนี้:

ที่มา = หมุด A
จุดหมาย = หมุดบี
ตัวช่วย = หมุด C

ขั้นตอน 3) จากนั้น ตามอัลกอริทึมของเรา ความต้องการดิสก์ลำดับที่ n หรือ 2 ควรถูกถ่ายโอนไปยังปลายทางหรือหมุด B

ที่เวทีนี้:

ที่มา = หมุด A
จุดหมาย = หมุดบี
ตัวช่วย = หมุด C

ขั้นตอน 4) ตอนนี้ เราจะย้ายดิสก์ n-1 หรือดิสก์หนึ่งจากตัวช่วยหรือหมุด C ไปยังปลายทางหรือหมุด B ตามขั้นตอนที่สามของอัลกอริทึมของเรา

ที่เวทีนี้:

ที่มา = หมุด A
จุดหมาย = หมุดบี
ตัวช่วย = หมุด C

ขั้นตอน 5) หลังจากเสร็จสิ้นการเรียกซ้ำ เราจะกลับสู่การตั้งค่าก่อนหน้าของเราเมื่อถึงขั้นตอนแรกของอัลกอริทึม

ขั้นตอน 6) ตอนนี้ ในขั้นตอนที่สอง เราจะย้ายแหล่งที่มาไปยังปลายทาง ซึ่งก็คือการย้ายดิสก์ 3 ไปยังหมุด C จากหมุด A

ที่เวทีนี้:

ที่มา = หมุด A
จุดหมาย = หมุดซี
ตัวช่วย = หมุดบี

ขั้นตอน 7) ตอนนี้เราเห็นแล้วว่า

d คือการย้ายดิสก์ที่เหลือจากตัวช่วย (peg B) ไปยังปลายทาง (peg C) เราจะใช้แหล่งที่มาเริ่มต้นหรือหมุด A เป็นตัวช่วยในกรณีนี้

ขั้นตอน 8) เนื่องจากเราไม่สามารถย้ายดิสก์ 1 แผ่นพร้อมกันได้ เราจะเรียกการเรียกซ้ำสำหรับดิสก์ XNUMX ตามขั้นตอนสุดท้ายและของเรา ขั้นตอนวิธีปลายทางในขั้นตอนนี้คือหมุด A

ที่เวทีนี้:

ที่มา = หมุด B
จุดหมาย = หมุด ก
ตัวช่วย = หมุด C

ขั้นตอน 9) การโทรซ้ำของเราเสร็จสิ้นแล้ว จากนั้นเราจะย้ายดิสก์ 2 จากต้นทางไปยังปลายทาง

ที่เวทีนี้:

ที่มา = หมุด B
จุดหมาย = หมุดซี
ตัวช่วย = หมุด A

ขั้นตอน 10) จากนั้นเราจะย้าย n-1 หรือดิสก์ 1 ที่เหลือจากตัวช่วยไปยังปลายทาง

ที่เวทีนี้:

ที่มา = หมุด A
จุดหมาย = หมุดซี
ตัวช่วย = หมุดบี

รหัสหลอกสำหรับหอคอยแห่งฮานอย

START
Procedure Tower_Of_Hanoi(disk, source, dest, helper)
  		IF disk == 1, THEN
      			move disk from source to dest             
   		ELSE
     			Tower_Of_Hanoi (disk - 1, source, helper, dest)     
      			move disk from source to dest          
      			Tower_Of_Hanoi (disk - 1, helper, dest, source)     
   		END IF   
END Procedure

รหัสโปรแกรมเข้า C++

#include <bits/stdc++.h>
using namespace std;
void tower_of_hanoi(int num, string source, string dest, string helper) {
  if (num == 1) {
    cout << " Move disk 1 from tower " << source << " to tower " << dest << endl;
    return;
  }
  tower_of_hanoi(num - 1, source, helper, dest);
  cout << " Move disk " << num << " from tower " << source << " to tower " << dest << endl;
  tower_of_hanoi(num - 1, helper, dest, source);
}
int main() {
  int num;
  cin >> num;
  printf("The sequence of moves :\n");
  tower_of_hanoi(num, "I", "III", "II");
  return 0;
}

เอาท์พุต

3
The sequence of moves :
Move disk 1 from tower I to tower III
Move disk 2 from tower I to tower II
Move disk 1 from tower III to tower II
Move disk 3 from tower I to tower III
Move disk 1 from tower II to tower I
Move disk 2 from tower II to tower III
Move disk 1 from tower I to tower III

รหัสโปรแกรมเข้า Python

def tower_of_hanoi(n, source, destination, helper):
	if n==1:
		print ("Move disk 1 from peg", source," to peg", destination)
		return
	tower_of_hanoi(n-1, source, helper, destination)
	print ("Move disk",n," from peg", source," to peg", destination)
	tower_of_hanoi(n-1, helper, destination, source)		
# n = number of disks
n = 3
tower_of_hanoi(n,' A','B','C')

Output:

Move disk 1 from peg A to peg B
Move disk 2 from peg A to peg C
Move disk 1 from peg B to peg C
Move disk 3 from peg A to peg B
Move disk 1 from peg C to peg A
Move disk 2 from peg C to peg B
Move disk 1 from peg A to peg B

ความซับซ้อนของหอคอยแห่งฮานอย

นี่คือความซับซ้อนของเวลาและพื้นที่ของหอคอยแห่งฮานอย:

1) ความซับซ้อนของเวลา:

หากเรามองย้อนกลับไปที่อัลกอริทึมของเรา เราจะเห็นว่าเรากำลังแนะนำการเรียกซ้ำสำหรับดิสก์ (n-1) สองครั้ง การเรียกซ้ำสำหรับดิสก์ (n-1) สามารถแบ่งออกเป็น ((n-1)-1) อื่น ๆ และต่อ ๆ ไปจนกว่าเราจะย้ายดิสก์ได้เพียงดิสก์เดียว

สำหรับสามดิสก์-

• ดิสก์ 3 เรียกใช้ฟังก์ชันแบบเรียกซ้ำสำหรับดิสก์สองสองครั้ง
• ดิสก์ 2 เรียกใช้ฟังก์ชันแบบเรียกซ้ำสำหรับดิสก์หนึ่งสองครั้ง
• ดิสก์ 1 สามารถเคลื่อนที่ได้ภายในเวลาคงที่ และเวลาในการแก้ไขสำหรับดิสก์ XNUMX แผ่น

= 2*(เวลาในการแก้สำหรับดิสก์สองแผ่น) + เวลาคงที่ในการย้ายดิสก์ 3

= 2*(2*เวลาในการแก้สำหรับดิสก์หนึ่งแผ่น + เวลาคงที่ในการย้ายดิสก์ 2) + ค่าคงที่ เวลาในการย้ายดิสก์ 3

= (2*2) (เวลาคงที่ในการย้ายดิสก์ 1) + 2*เวลาคงที่ในการย้ายดิสก์ 2 + เวลาคงที่ในการย้ายดิสก์ 3

สำหรับดิสก์ n สามารถเขียนเป็น –

(2^n-1 * เวลาคงที่ในการย้ายดิสก์ 1 + 2^n-2 * เวลาคงที่ในการย้ายดิสก์ 2 + ….

ความก้าวหน้าทางเรขาคณิตนี้จะส่งผลให้ O(2^n-1) หรือ โอ(2ⁿ), ซึ่งเป็นเลขชี้กำลัง

2) ความซับซ้อนของพื้นที่

ความซับซ้อนของพื้นที่ของหอคอยแห่งฮานอยคือ 0(n) นั่นเป็นเพราะเราจำเป็นต้องจัดเก็บลำดับของแผ่น เมื่อเราใช้การเรียกซ้ำ จะใช้สแต็ก และขนาดสูงสุดของสแต็กสามารถเป็น "n" ได้ นั่นคือเหตุผลที่ความซับซ้อนของพื้นที่จึงกลายเป็น O(n)