φυβλαςのβλογ
phyblasのブログ



แก้ปัญหาหอคอยฮานอยด้วย python
เขียนเมื่อ 2016/03/01 20:15
แก้ไขล่าสุด 2021/09/28 16:42
หอคอยฮานอย (Tours de Hanoï) เป็นปัญหาทางคณิตศาสตร์ที่คิดขึ้นโดยฟร็องซัว เอดูอาร์ อนาตอล ลูว์กา (François Édouard Anatole Lucas, ปี 1842 - 1891) นักคณิตศาสตร์ชาวฝรั่งเศส



รูปแบบและกติกา
เกมนี้เป็นเกมง่ายๆที่มีส่วนประกอบเป็นแค่แผ่นจานหลายๆอันซ้อนๆกัน โดยที่อันที่วางอยู่ด้านล่างสุดจะมีขนาดใหญ่สุด แล้วอันที่เรียงซ้อนขึ้นมาก็มีขนาดเล็กลดหลั่นกันลงมา

นอกจากนั้นก็อาจมีเสาสามแท่งเป็นหลักสำหรับเสียบแผ่นจาน เสาอาจมีหรือไม่มีก็ได้ เพียงแต่ต้องรู้ว่ามีหลักสำหรับวางแผ่นจานอยู่ ๓ ตำแหน่ง

กติกาการเล่นก็ง่ายๆคือให้ย้ายแผ่นจานทั้งหมดจากหลักหนึ่งไปยังอีกหลักหนึ่ง ถ้าย้ายได้หมดก็จบเกม

แต่มีข้อกำหนดว่า
- ย้ายแผ่นจานได้ทีละแผ่นเท่านั้น
- ห้ามย้ายออกไปที่อื่นนอกจากในหลัก ๓ ตำแหน่งนี้
- ไม่สามารถนำแผ่นจานที่ใหญ่กว่าทับแผ่นจานที่เล็กกว่าได้





วิเคราะห์ปัญหา
ถ้าได้ลองเล่นดูไปเรื่อยๆจะเริ่มจับหลักได้ว่าการจะจบเกมนี้ได้เร็วที่สุดนั้นจะต้องย้ายแผ่นจานด้วยหลักที่ตายตัวอย่างหนึ่ง

สมมุติมีจาน n ใบ ให้จานบนสุดเป็นจานใบที่ 1 และถัดมาเป็นใบที่ 2 และล่างสุดเป็นใบที่ n (ในภาพ n=5)

และให้หลักทั้ง ๓ ชื่อ ก. ข. ค. ไล่จากซ้ายไปขวา

หลักการคือ
- จานใบที่ 1 จะขยับทุก 2 ตา ใบที่ 2 ขยับทุก 2^2 = 4 ตา ใบที่ 3 ขยับทุก 2^3 = 8 ตา ใบที่ n ขยับทุก 2^n ตา
- ทิศทางการย้ายของแต่ละจานต้องมีความตายตัว คือ ก. -> ข. -> ค. -> ก. หรือ ก. -> ค. -> ข. -> ก. ตลอดเกม โดยจานที่ 1, 3, 5,... จะมีทิศทางเหมือนกัน ส่วน 2, 4, 6,... จะเป็นทิศตรงกันข้าม
- ใบที่ n จะขยับครั้งเดียวเท่านั้น และเป็นการขยับตอนกลางเกม และใบที่ n-1 จะขยับแค่ 2 ครั้ง ใบที่ n-2 ขยับ 2^2 = 4 ครั้ง ใบที่ 1 ขยับ 2^(n-1) ครั้ง
- จำนวนครั้งที่ขยับรวมทั้งหมดคือ (2^n)-1 ครั้ง





การเขียนโปรแกรมเพื่อแก้ปัญหา
เกมนี้มีชื่อเสียงในเรื่องที่ว่าสามารถแก้ปัญหาได้โดยง่ายด้วยการใช้ฟังก์ชันเวียนเกิด

เขียนโค้ดแก้ปัญหาด้วยภาษาไพธอน

t = 0 # ตั้งจำนวนตาเริ่มต้น
def hanoi(n,a,b,c): # นิยามฟังก์ชันฮานอย พารามิเตอร์คือจำนวนจาน ตามด้วยชื่อหลักทั้งสาม
    global t
    if(n>0): # จะมีการกระทำเกิดขึ้นตราบใดที่ n มากกว่า 0
        hanoi(n-1,a,c,b) # เรียกใช้ฟังก์ชันเดิมที่ n น้อยกว่าอยู่ 1 โดยสลับ b กับ c
        t += 1 # นับบวกจำนวนตา
        print('%d. ย้ายจานที่ %d จาก %s ไป %s'%(t,n,a,b)) # แสดงวิธีการย้าย
        hanoi(n-1,c,b,a) # เรียกใช้ฟังก์ชันเดิมที่ n น้อยกว่าอยู่ 1 โดยสลับ a กับ c
hanoi(5,'ก.','ข.','ค.') # เรียกใช้ฟังก์ชันเพื่อเล่นเกมที่มี 5 จาน

ผลลัพธ์
1. ย้ายจานที่ 1 จาก ก. ไป ข.
2. ย้ายจานที่ 2 จาก ก. ไป ค.
3. ย้ายจานที่ 1 จาก ข. ไป ค.
4. ย้ายจานที่ 3 จาก ก. ไป ข.
5. ย้ายจานที่ 1 จาก ค. ไป ก.
6. ย้ายจานที่ 2 จาก ค. ไป ข.
7. ย้ายจานที่ 1 จาก ก. ไป ข.
8. ย้ายจานที่ 4 จาก ก. ไป ค.
9. ย้ายจานที่ 1 จาก ข. ไป ค.
10. ย้ายจานที่ 2 จาก ข. ไป ก.
11. ย้ายจานที่ 1 จาก ค. ไป ก.
12. ย้ายจานที่ 3 จาก ข. ไป ค.
13. ย้ายจานที่ 1 จาก ก. ไป ข.
14. ย้ายจานที่ 2 จาก ก. ไป ค.
15. ย้ายจานที่ 1 จาก ข. ไป ค.
16. ย้ายจานที่ 5 จาก ก. ไป ข.
17. ย้ายจานที่ 1 จาก ค. ไป ก.
18. ย้ายจานที่ 2 จาก ค. ไป ข.
19. ย้ายจานที่ 1 จาก ก. ไป ข.
20. ย้ายจานที่ 3 จาก ค. ไป ก.
21. ย้ายจานที่ 1 จาก ข. ไป ค.
22. ย้ายจานที่ 2 จาก ข. ไป ก.
23. ย้ายจานที่ 1 จาก ค. ไป ก.
24. ย้ายจานที่ 4 จาก ค. ไป ข.
25. ย้ายจานที่ 1 จาก ก. ไป ข.
26. ย้ายจานที่ 2 จาก ก. ไป ค.
27. ย้ายจานที่ 1 จาก ข. ไป ค.
28. ย้ายจานที่ 3 จาก ก. ไป ข.
29. ย้ายจานที่ 1 จาก ค. ไป ก.
30. ย้ายจานที่ 2 จาก ค. ไป ข.
31. ย้ายจานที่ 1 จาก ก. ไป ข.


จะเห็นว่าจำนวนครั้งที่ย้ายคือ (2^5)-1 = 31 ครั้ง

ใช้โปรแกรมจำลองสามมิติเพื่อจำลองภาพการย้าย
เพื่อให้เห็นภาพชัดจึงลองสร้างภาพเคลื่อนไหวให้เห็นขั้นตอน

ในที้นี้ลองใช้โปรแกรมมายาซึ่งเขียนโค้ดเพื่อสร้างแผ่นจานและตั้งคีย์เฟรมด้วยภาษาไพธอน

เขียนโค้ดคล้ายเดิมแต่ต่างออกไปตรงที่เปลี่ยนจากการ print เป็นการตั้งคีย์เฟรมเพื่อย้ายตำแหน่งแผ่นจาน

t = 0 # เวลาเริ่มต้น
def hanoi(n,a,b,c):
    if(n>0):
        global t
        hanoi(n-1,a,c,b)
        mc.setKeyframe(chan[n-1],at='tx',v=a*15,t=t) # ตั้งคีย์เฟรมตำแหน่งจานก่อนย้าย
        mc.setKeyframe(chan[n-1],at='ty',v=ty[n-1],t=t) # ตั้งคีย์เฟรมความสูงจานก่อนย้าย
        mc.setKeyframe(chan[n-1],at='ty',v=6,t=t+11) # ตั้งคีย์เฟรมความสูงจานระหว่างย้าย
        mc.setKeyframe(chan[n-1],at='ty',v=6,t=t+14)
        ty[n-1] = d[b]+0.5 # กำหนดความสูงจานหลังย้าย
        d[b] += 1 # เพิ่มจำนวนจานหลัก b
        d[a] -= 1 # ลดจำนวนจานหลัก a
        mc.setKeyframe(chan[n-1],at='tx',v=b*15,t=t+25) # ตั้งคีย์เฟรมตำแหน่งจานหลังย้าย
        mc.setKeyframe(chan[n-1],at='ty',v=ty[n-1],t=t+25) # ตั้งคีย์เฟรมความสูงจานหลังย้าย
        t += 25 # บวกเวลาเพิ่ม 25 เฟรม = 1 วินาที
        hanoi(n-1,c,b,a)
chan = [] # ลิสต์เก็บชื่อจานบนหลัก
ty = [] # ลิสต์ของความสูงของจาน
d = [5,0,0] # ลิสต์แสดงจำนวนจานในแต่ละหลัก ประกอบด้วยหลัก 0, 1, 2 โดยเริ่มต้นแผ่นจานอยู่ที่หลัก 0
for i in range(1,6):
    chan += mc.polyCylinder(r=i+2,h=1,sx=20+i**2,ch=0) # สร้างแผ่นจาน พร้อมใส่ชื่อลงลิสต์
    ty += [5.5-i] # กำหนดความสูงเริ่มต้น โดยใส่ลงในลิสต์
hanoi(5,0,1,2) # เรียกใช้ฟังก์ชันฮานอยเพื่อเล่นเกมที่มี 5 จาน


คลิปแสดงภาพการย้ายแผ่นจาน ภาพในนี้มีการแต่งลายเพิ่มให้กับแผ่นจาน ภาพประกอบทั้งหมดมาจากตัวละครจากหนังสือสอนความรู้เรื่องโพรโทคอลอินเทอร์เน็ต รายละเอียดเกี่ยวกับหนังสือเขียนไว้แล้วใน https://phyblas.hinaboshi.com/20160229



อ้างอิง



-----------------------------------------

囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧

ดูสถิติของหน้านี้

หมวดหมู่

-- คอมพิวเตอร์ >> เขียนโปรแกรม >> python >> mayapython
-- คอมพิวเตอร์ >> 3D >> maya

ไม่อนุญาตให้นำเนื้อหาของบทความไปลงที่อื่นโดยไม่ได้ขออนุญาตโดยเด็ดขาด หากต้องการนำบางส่วนไปลงสามารถทำได้โดยต้องไม่ใช่การก๊อปแปะแต่ให้เปลี่ยนคำพูดเป็นของตัวเอง หรือไม่ก็เขียนในลักษณะการยกข้อความอ้างอิง และไม่ว่ากรณีไหนก็ตาม ต้องให้เครดิตพร้อมใส่ลิงก์ของทุกบทความที่มีการใช้เนื้อหาเสมอ

目次

日本による名言集
モジュール
-- numpy
-- matplotlib

-- pandas
-- manim
-- opencv
-- pyqt
-- pytorch
機械学習
-- ニューラル
     ネットワーク
javascript
モンゴル語
言語学
maya
確率論
日本での日記
中国での日記
-- 北京での日記
-- 香港での日記
-- 澳門での日記
台灣での日記
北欧での日記
他の国での日記
qiita
その他の記事

記事の類別



ติดตามอัปเดตของบล็อกได้ที่แฟนเพจ

  記事を検索

  おすすめの記事

ตัวอักษรกรีกและเปรียบเทียบการใช้งานในภาษากรีกโบราณและกรีกสมัยใหม่
ที่มาของอักษรไทยและความเกี่ยวพันกับอักษรอื่นๆในตระกูลอักษรพราหมี
การสร้างแบบจำลองสามมิติเป็นไฟล์ .obj วิธีการอย่างง่ายที่ไม่ว่าใครก็ลองทำได้ทันที
รวมรายชื่อนักร้องเพลงกวางตุ้ง
ภาษาจีนแบ่งเป็นสำเนียงอะไรบ้าง มีความแตกต่างกันมากแค่ไหน
ทำความเข้าใจระบอบประชาธิปไตยจากประวัติศาสตร์ความเป็นมา
เรียนรู้วิธีการใช้ regular expression (regex)
การใช้ unix shell เบื้องต้น ใน linux และ mac
g ในภาษาญี่ปุ่นออกเสียง "ก" หรือ "ง" กันแน่
ทำความรู้จักกับปัญญาประดิษฐ์และการเรียนรู้ของเครื่อง
ค้นพบระบบดาวเคราะห์ ๘ ดวง เบื้องหลังความสำเร็จคือปัญญาประดิษฐ์ (AI)
หอดูดาวโบราณปักกิ่ง ตอนที่ ๑: แท่นสังเกตการณ์และสวนดอกไม้
พิพิธภัณฑ์สถาปัตยกรรมโบราณปักกิ่ง
เที่ยวเมืองตานตง ล่องเรือในน่านน้ำเกาหลีเหนือ
ตระเวนเที่ยวตามรอยฉากของอนิเมะในญี่ปุ่น
เที่ยวชมหอดูดาวที่ฐานสังเกตการณ์ซิงหลง
ทำไมจึงไม่ควรเขียนวรรณยุกต์เวลาทับศัพท์ภาษาต่างประเทศ

ไทย

日本語

中文