Author: fortune

Tower of Hanoi

เป็นอุปกรณ์ที่ใช้ในการอธิบาย สมการเวียนบังเกิด (RECURSION) ซึ่งเป็นพื้นฐานการเขียนโปรแกรม แบบเรียนตัวเอง

Binary Tree

เป็นอุปกรณ์ใช้ในการอธิบาย การเรียงลำดับข้อมูลในรูปต้นไม้

Shortest  Path

เป็นอุปกรณ์ใช้ในการอธิบาย การคำนวณหาเส็นทางที่สั้นที่สุด

Bubble Sort

เป็นอุปกรณ์ใช้ในการอธิบาย การเรียงลำดับข้อมูลรูปแบบหนึ่ง

ติดต่อขอรับ เฉลยกิจกรรม ใบงาน แบบฝึกหัด ของหนังสือเรียน คณิตศาสตร์สำหรับคอมพิวเตอร์ ได้ที่นี้

Tower of Hanoi

คำนำ

           ตามตำนานเล่าว่าในอดีตกาล ณ ประเทศอินเดียพระที่อาศัยอยู่ในวัดแห่งหนึ่งจำเป็นจะต้องขนย้าย แผ่นอิฐซึ่งเป็นส่วนประกอบในการสร้างเจดีย์ จากที่หนึ่งไปอีกที่หนึ่ง โดยมีเงื่อนไขว่าขณะ ทำการขนย้าย จะยกอิฐได้ครั้งละ 1 แผ่น และไม่สามารถวางแผ่นอิฐใหญ่ทับบนแผ่นอิฐที่เล็กกว่าได้ ดังนั้นจึงจะ ต้องขน ย้ายอิฐบางส่วนมาพักไว้ก่อนที่จุดหนึ่ง  ก่อนที่จะนำไปวางในสถานที่ที่ต้องการ  ขั้นตอนวิธีของ "Tower of  Hanoi" นี้ ในภาษาไทยจะใช้คำว่า "หอคอยฮานอย"ซึ่งในบางแห่งมีความเชื่อว่าเป็น การ เคลื่อนย้าย หอคอยฮานอย

วิธีการ

ให้จุดที่จะขนย้ายแผ่นไม้มีอยู่ 3 จุด ( A, B และ C)

การย้ายแผ่นไม้ทั้งหมดจากจุด A ไปที่จุด C โดยมีเงื่อนไขว่า

สามารถใช้หลัก B ที่อยู่ตรงกลางช่วยในการวางแผ่นไม้ชั่วคราวได้

ต้องวางแผ่นไม้เล็กไว้ด้านบนเสมอ

หยิบแผ่นไม้ในการขนย้ายได้ครั้งละ 1 แผ่น

จำนวนครั้งในการเคลื่อนย้ายแผ่นไม้คำนวณจาก 2n – 1

ตัวอย่างการย้ายแผ่นไม้

Binary Tree

คำนำ

         ในการเรียงลำดับข้อมูลจะมีได้หลายวิธี ซึ่ง Binary Tree เป็นอีกวิธีการหนึ่ง มีลักษณะการจัดวาง ตำแหน่งของข้อมูลซึ่งรูปร่างคล้ายต้นไม้ หลักการของ Binary Tree คือ กำหนดให้ข้อมูลแต่ละชุดมีค่า เป็นโหนด และแต่ละโหนดจะมีลูกได้ 2 โหนด (ซ้ายและขวา)

วิธีการ

นำแท่งเหล็กแท่งแรกที่เลือกไว้ มาตั้ง ณ จุดเริ่มต้น

สุ่มเลือกแท่งเหล็กแท่งต่อไป นำมาเปรียบเทียบกับแท่งแรก หากมีขนาดสูงกว่าให้นำไปตั้ง ไว้ทางด้านขวา(โหนดขวา) หากมีขนาดเล็กกว่าให้นำไปตั้งไว้ทางด้านซ้าย(โหนดซ้าย)

สุ่มเลือกแท่งเหล็กต่อไป นำมาเปรียบเทียบกับแท่งเหล็กที่ตั้งไว้แล้ว ทำในลักษณะเดียวกับข้อ 2  และเปรียบเทียบไปเรื่อย ๆ  จนหมด เมื่อวางแท่งเหล็กครบหมดแล้ว ให้นำแท่งเหล็กที่อยู่ด้านซ้ายสุดลงมาวางด้านล่างตามลำดับ จะพบว่าแท่งเหล็กมีการเรียงลำดับตามขนาด

รูปอุปกรณ์ช่วยในการสอนเรื่อง Binary Tree

Shortest  Path

คำนำ

           SHORTEST PATH เป็นขั้นตอนที่เกี่ยวกับทฤษฎีกราฟเพื่อหาระยะทางที่สั้นที่สุด ในการเชื่อมจุด แต่ละจุด บนระนาบที่เราสนใจ ยกตัวอย่างให้เข้าใจง่ายๆ เช่น ถ้าต้องการตัดถนนผ่านเมือง 5 เมือง เราจะ ต้องหาเส้นทางในการตัดถนนที่มีค่าใช้จ่ายน้อยที่สุด คือ ต้องเริ่มต้นตัดถนนจากเมืองใด แล้วผ่านไปยัง เมืองใดเป็นเมืองที่ 2  3 4 และ 5 ตามลำดับและกลับมายังเมืองเดิม โดยให้ถนนที่ตัดเสร็จแล้วสั้นที่สุด เพื่อให้ใช้วัสดุและเวลาในการทำงานน้อยที่สุด

วิธีการ

ในแผงสาธิตจะมีแท่งเหล็ก 10 แท่งซึ่งแทนเมืองแต่ละเมือง

ในการสาธิตเราสามารถกำหนดได้ว่า เราต้องการตัดถนนผ่านเมืองใดบ้างและผ่านกี่เมือง

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

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

รูปอุปกรณ์ช่วยในการสอนเรื่อง Shortest  Path

Bubble Sort

คำนำ

         การเรียงลำดับวิธีนี้จะกระทำโดยการเปรียบเทียบค่าข้อมูลที่อยู่ติดกันทีละคู่ไปเรื่อยๆ ในกรณีเรียง ลำดับข้อมูลจากน้อยไปมาก ถ้าค่าแรกมีค่ามากกว่าค่าสองก็จะทำการสลับที่กัน โดยวิธีการนี้ จะทำให้ ข้อมูลที่มีค่าน้อยกว่าลอยสูงขึ้นเรื่อยเหมือนฟองสบู่(bubble) ที่ลอยขึ้นที่สูง และข้อมูลที่น้อยที่สุดก็จะ อยู่ในต่ำแหน่งบนสุดของชุดข้อมูลจึงเรื่อยการเรียงลำดับวิธีนี้ว่า BUBBLE  SORT

ขั้นตอนวิธีในการเรียงลำดับ (เรียงลำดับจากน้อยไปมาก)

1. ทำการเปรียบเทียบค่าข้อมูลตัวที่ 1 กับตัวที่ 2 ถ้าข้อมูลตัวที่ 2 มีค่าน้อยกว่าข้อมูลตัวที่ 1 ให้สลับที่ข้อมูลทั้ง 2
2. ทำการเปรียบเทียบข้อมูลตัวที่ 2 กับตัวที่ 3 และเปรียบเทียบข้อมูลไปเรื่อยๆจนหมดชุดข้อมูล เรียกการเปรียบเทียบข้อมูลตั้งแต่ตัวแรกถึงตัวสุดท้ายว่าเป็น  1 รอบของการทำงาน
3. ทุกครั้งที่หมดรอบของการทำงานต้องมีการตรวจสอบว่ารอบของการทำงานนั้นมีการสลับที่ของ ข้อมูลหรือไม่ ถ้ามีการสลับที่ในรอบนั้นจะต้องทำการเปรียบเทียบรอบใหม่ แต่ถ้ารอบใดก็ตาม ที่ไม่มีการสลับที่ แสดงว่าเมื่อจบการทำงานในรอบนั้น เราจะได้ข้อมูลที่มีการเรียงลำดับ เรียบร้อยแล้ว ซึ่งเป็นอันจบขั้นตอนการเรียงลำดับ

วิธีการ

1. สมมุติว่าแท่งเหล็กแต่ละแท่งเป็นข้อมูลที่มีค่าต่างกัน วางข้อมูลลงบนแผงวางข้อมูลโดยไม่ต้อง เรียงลำดับ

2. ผลักเม็ดพลาสติกสีแดงไปทางด้านขวาทั้งหมด เพื่อเริ่มรอบของการทำงาน

3. เปรียบเทียบข้อมูลตัวที่ 1 กับตัวที่ 2

          A. ถ้าตัวที่ 2 น้อยกว่าตัวที่ 1 (แท่งเหล็กแท่งที่ 2 สั้นกว่าแท่งที่ 1) ให้สลับที่ข้อมูลและเลื่อนเม็ดพลาสติกมาทางด้ายซ้าย 1 เม็ด แล้วไปทำข้อ 4

          B. ถ้าตัวที่ 2 มากกว่าตัวที่ 1 (แท่งเหล็กแท่งที่ 2 ยาวกว่าแท่งที่ 1) ไม่ต้องสลับที่ข้ามไปทำข้อ 4

4. ทำการเปรียบเทียบและสลับที่ข้อมูลไปเรื่อยๆโดยใช้หลักการในข้อ A และ B จนถึงตัวสุดท้าย

5. ตรวจสอบว่ามีเม็ดพลาสติกสีแดงถูกเลื่อนมาทางด้านซ้ายหรือไม่

          C. ถ้ามีแสดงว่ามีการสลับที่ของข้อมูลโดยจำนวนครั้งของการสลับที่เท่ากับจำนวนเม็ดพลาสติกที่อยู่ทางซ้าย ให้ย้อนกลับไปทำตั้งแต่ข้อที่ 2 ใหม่

          D. ถ้าไม่มีเม็ดพลาสติกอยู่ทางซ้ายแสดงว่าข้อมูลได้เรียงลำดับจากน้อยไปมากเรียบร้อยแล้ว และจบการทำงาน

รูปอุปกรณ์ช่วยในการสอนเรื่อง Bubble Sort