วิทย์ม.ต้น: รู้จัก Recursion,ใช้ Scratch คำนวณห.ร.ม., ตัวเลขเป็นจำนวนเฉพาะหรือไม่

วันนี้เด็กๆม.ต้นได้เรียนรู้เรื่อง Scratch  เพิ่มเติม ให้รู้จักการแปลงขบวนการคิดไปเป็นโปรแกรมครับ

เด็กม.3 ทำความรู้จักการหาห.ร.ม. (GCD, Greatest Common Divisor) โดยใช้วิธีของยูคลิด (Euclid’s algorithm)  ที่อาศัยว่าถ้าจำนวนเต็มบวก a, b มีตัวหารร่วมมาก d  ผลต่าง  a-b  หรือ b-a ก็หารด้วย d ลงตัวเช่นกัน เราจึงสามารถเปลี่ยนปัญหาการหา ห.ร.ม. ของ a และ b เป็นปัญหาที่เล็กลงคือหา ห.ร.ม. ของ a และ a-b ถ้า a มากกว่า b หรือหา ห.ร.ม. ของ a และ b-a ถ้า b มากกว่า a

จาก https://en.wikipedia.org/wiki/Greatest_common_divisor#Using_Euclid's_algorithm
จาก https://en.wikipedia.org/wiki/Greatest_common_divisor#Using_Euclid’s_algorithm

การลบหลายๆครั้งตามวิธีด้านบนก็เหมือนกันหารแล้วดูว่าเหลือเศษเท่าไร เราจึงเขียนได้อีกแบบโดยอาศัยวิธี a mod b ที่หาเศษจากการหาร a/b

จาก https://en.wikipedia.org/wiki/Greatest_common_divisor#Using_Euclid's_algorithm
จาก https://en.wikipedia.org/wiki/Greatest_common_divisor#Using_Euclid’s_algorithm

ตัว a mod b นี้สามารถให้ Scratch คำนวณให้ได้ (เช่น 19/5 = 3 เศษ 4 ดังนั้น 19 mod 5 ก็คือ 4) ผมจึงให้เด็กๆคิดว่าจะบอกให้ Scratch คำนวณห.ร.ม. ให้เราอย่างไร

19 mod 5 = 4
19 mod 5 = 4

เด็กๆได้รู้จัก Custom Block ใน Scratch ซึ่งทำหน้าที่เหมือนฟังก์ชั่นในภาษาโปรแกรมอื่นๆ และได้เห็นว่า Custom Block เรียกตัวเองได้ ก็คือได้รู้จัก Recursive function นั่นเอง

หน้าตาการหาห.ร.ม.แบบเรียกตัวเอง (recursion) จะออกมามีหน้าตาประมาณนี้ครับ:

หาห.ร.ม.แบบเรียกตัวเอง (recursive function)
หาห.ร.ม.แบบเรียกตัวเอง (recursive function)

นอกจากเขียนการหาห.ร.ม.แบบเรียกตัวเองแล้ว เรายังสามารถเขียนแบบให้เป็น loop หรือการวนซ้ำๆจนพบคำตอบแบบนี้ด้วยครับ การวนซ้ำๆจะเรียกว่าแบบ iterative ครับ:

การหาห.ร.ม.แบบวนซ้ำๆ (iterative)
การหาห.ร.ม.แบบวนซ้ำๆ (iterative)

สำหรับเด็กม.1-2 ผมแนะนำว่า  Operators ต่างๆของ Scratch ทำอะไรบ้าง หน้าตา Operators ก็เช่นพวกนี้ครับ:

ตัวอย่าง Operator ใน Scratch
ตัวอย่าง Operator ใน Scratch

จากนั้นผมให้เด็กๆสอนให้  Scratch บอกว่าตัวเลขจำนวนเต็มบวกที่เราป้อนเข้าไปเป็นจำนวนเฉพาะหรือไม่ ให้เด็กๆสังเกตว่าถ้าได้ตัวเลขมาหนึ่งตัว เราก็ลองไล่หาตัวเลขที่น้อยกว่ามันไปลองหารดูว่าลงตัวหรือไม่ เด็กๆได้สังเกตว่าเราควรตรวจดูก่อนว่าเลขคือ  1 หรือ 2 หรือไม่ ถ้าเป็น 1 ก็ไม่เป็นจำนวนเฉพาะ ถ้าเป็น 2 ก็เป็นจำนวนเฉพาะ สำหรับเลข N ที่มากกว่า 2 เราก็เอา 2, 3, 4, …, ไม่เกิน N ไปลองหาร N ดูว่ามีตัวไหนหารลงตัวไหม ถ้ามีเราก็บอกได้ว่า N ไม่ใช่จำนวนเฉพาะ ถ้าไม่มีตัวไหนหารลงตัวเลยเราก็รู้ว่า N  เป็นจำนวนเฉพาะ  นอกจากนี้เด็กๆยังได้เห็นว่าจริงๆเราหาตัวหารที่ไม่มากกว่ารูทที่ 2 ของ N ก็พอ เพราะถ้ามีตัวหารที่มากกว่ารูทที่ 2 ของ N เราก็จะต้องเจอตัวหารอีกตัวที่น้อยกว่ารูทที่ 2 ของ N ไปก่อนแล้วแน่นอน

เด็กๆไปนั่งหัดเขียนกันประมาณ 1 ชั่วโมงครับ ก็ได้โปรแกรมกันทุกคน ใครทำได้ก่อนก็ไปให้คำปรึกษาคนที่ยังติดอยู่ ผมบอกว่าไม่ให้บอกกันแต่ให้ถามๆและชี้ๆส่วนที่อาจเป็นบั๊กจนทุกคนเข้าใจและทำได้เองกันหมด หลายๆคนตื่นเต้นมากที่คอมพิวเตอร์ตอบคำถามว่าเลขไหนเป็นจำนวนเฉพาะอย่างรวดเร็วเพราะวิธีที่เด็กๆทำด้วยมือมันทำได้ช้าและใช้กับเลขน้อยๆเท่านั้น เด็กๆได้ทดลองตรวจสอบเลขใหญ่ๆเช่น 15,485,863 และ 32,452,843  (เลขจำนวนเฉพาะตัวที่ล้านและสองล้านตามลำดับ) และพบว่ามันเป็นจำนวนเฉพาะ

หน้าตาโปรแกรมจะเป็นทำนองนี้ครับ:

 

ตัวเลขเป็นจำนวนเฉพาะไหม?
ตัวเลขเป็นจำนวนเฉพาะไหม?

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.