Skip to main content

Tag: computing

Bubble Sort

Written by webmaster on . Posted in สื่อการสอน, เทคโนโลยีสารสนเทศและการสื่อสาร.

คำนำ

         การเรียงลำดับวิธีนี้จะกระทำโดยการเปรียบเทียบค่าข้อมูลที่อยู่ติดกันทีละคู่ไปเรื่อยๆ ในกรณีเรียง ลำดับข้อมูลจากน้อยไปมาก ถ้าค่าแรกมีค่ามากกว่าค่าสองก็จะทำการสลับที่กัน โดยวิธีการนี้ จะทำให้ ข้อมูลที่มีค่าน้อยกว่าลอยสูงขึ้นเรื่อยเหมือนฟองสบู่(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

Shortest Path

Written by webmaster on . Posted in สื่อการสอน, เทคโนโลยีสารสนเทศและการสื่อสาร.

คำนำ

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

 

วิธีการ

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

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

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

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

 

   

 

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

Binary Tree

Written by webmaster on . Posted in สื่อการสอน, เทคโนโลยีสารสนเทศและการสื่อสาร.

คำนำ

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

 

วิธีการ

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

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

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

 

 

 

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

Tower of Hanoi

Written by webmaster on . Posted in สื่อการสอน, เทคโนโลยีสารสนเทศและการสื่อสาร.

คำนำ

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

 

วิธีการ

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

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

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

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

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

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

 

 

 

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