φυβλαςのβλογ
บล็อกของ phyblas



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



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

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

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

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





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

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

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

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


จะเห็นว่าจำนวนครั้งที่ย้ายคือ 25-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
ภาษา mongol
ภาษาศาสตร์
maya
ความน่าจะเป็น
บันทึกในญี่ปุ่น
บันทึกในจีน
-- บันทึกในปักกิ่ง
-- บันทึกในฮ่องกง
-- บันทึกในมาเก๊า
บันทึกในไต้หวัน
บันทึกในยุโรปเหนือ
บันทึกในประเทศอื่นๆ
qiita
บทความอื่นๆ

บทความแบ่งตามหมวด



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

  ค้นหาบทความ

  บทความแนะนำ

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

บทความแต่ละเดือน

2024年

1月 2月 3月 4月
5月 6月 7月 8月
9月 10月 11月 12月

2023年

1月 2月 3月 4月
5月 6月 7月 8月
9月 10月 11月 12月

2022年

1月 2月 3月 4月
5月 6月 7月 8月
9月 10月 11月 12月

2021年

1月 2月 3月 4月
5月 6月 7月 8月
9月 10月 11月 12月

2020年

1月 2月 3月 4月
5月 6月 7月 8月
9月 10月 11月 12月

ค้นบทความเก่ากว่านั้น

ไทย

日本語

中文