Leapyear.txt ------------ แบบฝึกหัดเรื่องปีอธิกสุรทินและเฉลยจาก Prac11 ตอนที่ ๑ : โจทย์ -------------- จงออกแบบขั้นตอนวิธีและเขียน shell script ตามข้อมูลรายละเอียดต่อไปนี้ :: ลักษณะของปัญหา :: ปีอธิกสุรทิน (Leap year) เป็นปีที่เดือนกุมภาพันธ์ตามปฏิทินสุริยคติ ตามระบบปฏิทินสากลที่เรียกว่า Gregorian calendar ตามชื่อของพระสันตปาปาเกรกอรีที่ 13 ผู้เริ่มต้นการใช้งานในเดือนกุมภาพันธ์ ค.ศ. 1582 พจนานุกรมฉบับราชบัณฑิตยสถานให้ความหมายของ อธิกสุรทิน ไว้ว่า "วันที่เพิ่มขึ้นในปีสุริยคติ คือในปีนั้นมีการเพิ่มวันเข้าไปในเดือนกุมภาพันธ์อีกวันหนึ่งเป็น 29 วัน" Gregorian calendar กำหนดไว้ว่าปีส่วนใหญ่ที่เป็นพหุคูณของ 4 เป็นปีอธิกสุรทิน (อธิก - เกิน, สุร - สุริยคติ, ทิน - วัน) ผู้คนโดยทั่วไปได้รับการสอนว่าระยะเวลา 1 ปีคือเวลาที่โลกโคจรรอบดวงอาทิตย์ครบหนึ่งรอบ เป็นเวลา 365 วัน เพื่อให้จำได้ง่าย และจำนวนวันต้องเป็นจำนวนเต็ม และต่อมาจึงรู้ว่าเวลาที่โลกโคจรรอบดวงอาทิตย์ใช้เวลา 365.25 วัน ดังนั้นทุกสี่ปีสี่ปีจึงต้องชดเชยเวลาที่เกินมา 1 วัน โดยกำหนดให้เดือนกุมภาพันธ์ในปีนั้นมีวันเพิ่มขึ้นเป็น 29 วัน เรึยกว่าปีอธิกสุรทิน หรือ leap year อย่างไรก็ดีเมื่อต้องทำงานหรือเขียนโปรแกรมที่เกี่ยวข้องกับเวลาจึงรู้ว่าเวลาที่โลกโคจรรอบดวงอาทิตย์ใช้เวลา 365.2425 วัน ทำให้เวลา 365.25 วันที่ใช้งานอยู่จึงเกินกว่าความเป็นจริงอยู่ประมาณ 3 วันทุกระยะเวลา 400 ปี (4 ศตวรรษ) ด้วยเหตุนี้ทุกรอบ 400 ปี จึงต้อง "งด" ชดเชยวันในเดือนกุมภาพันธ์ 3 ครั้ง คืองดในปีที่เป็นพหุคูณของ 100 แต่ไม่เป็นพหุคูณของ 400 เช่น ปี ค.ศ. 1700, 1800, 1900 "ไม่เป็น" ปีอธิกสุรทิน - หารด้วย 4 ลงตัว, หารด้วย 100 ลงตัว, แต่หารด้วย 400 ไม่ลงตัว ปี 2000 "เป็น" ปีอธิกสุรทิน - หารด้วย 4 ลงตัว, หารด้วย 100 ลงตัว, และหารด้วย 400 ลงตัว ปี 2100 "ไม่เป็น" ปีอธิกสุรทิน - หารด้วย 4 ลงตัว, หารด้วย 100 ลงตัว, แต่หารด้วย 400 ไม่ลงตัว :: ปฎิบัติการ :: จงออกแบบขั้นตอนวิธี (Algorithm) เพื่อตรวจสอบว่าปี ค.ศ. ที่ได้รับเป็นปีอธิกสุรทินหรือไม่ จากนั้นจึงเขียน shell script ชื่อ leapyear เพื่อรับค่าปี ค.ศ. ผ่าน command line argument ทำการตรวจสอบว่าปีที่ได้รับเป็นปีอธิกสุรทิน (Leap year) ตามขั้นตอน วิธีที่ออกแบบไว้ ในกรณีที่ผู้ใช้ไม่ได้กำหนดปีมาให้ ให้ดำเนินการกับปีปัจจุบัน (ปีที่อ่านได้จากระบบคอมพิวเตอร์โดยใช้คำสั่ง date) กำหนดการเรียกใช้งานและการแสดงผลดังนี้ $ leapyear 2016 2016 is a leap year, February has 29 days. $ leapyear 2014 2014 is NOT a leap year, February has 28 days. $ leapyear 2015 is NOT a leap year, February has 28 days. :: คำแนะนำ :: 1. การอ่านค่าปีปัจจุบันจากวันเวลาของระบบ ทำได้โดยใช้คำสั่ง date +%Y และเมื่อต้องการนำค่านี้ไปกำหนดให้กับตัวแปรทำได้โดยการทำ command substitution, $(date +%Y) เพื่อนำผลลัพธ์ของคำสั่งไปใช้งาน หรือ command substitution ดูรายละเอียดของคำสั่งได้ในแฟ้ม Unix03.txt 2. การคำนวณค่าของนิพจน์ทำได้โดยใช้ $((นิพจน์)) เช่น การหาเศษที่เหลือของการหาร (remainder) ของค่าในตัวแปร year ด้วย 4 ทำได้ดังนี้ $(($year % 4)) และสามารถนำไปใช้เป็นเงื่อนไขของโครงสร้าง if ดังนี้ if [ $(($year % 4)) = 0 ]; then ดูรายละเอียดของคำสั่ง test ได้จากแฟ้ม Unix03.txt ตอนที่ ๒: เฉลย ------------- :: การวิเคราะหฺ์งานและการออกแบบขั้นตอนวิธี :: ขั้นตอนวิธีส่วนที่สำคัญที่สุดคือ การทดสอบว่าปี ค.ศ. ที่กำหนดเป็นปีอธิกสุรทินหรือไม่? ซึ่งควรจะได้เริ่มพิจารณาก่อน ตัวหารมี 3 ตัวคือ 4, 100, และ 400 - ปีที่หารด้วย 4 ลงตัว "เกือบทั้งหมด" เป็นปีอธิกสุรทิน หรือ ปีที่หารด้วย 4 ลงตัว มีโอกาสเป็นปีอธิกสุรทินสูง คือมีโอกาส 97 ครั้งในระยะเวลา 400 ปี หรือมีความน่าจะเป็น 97/400 = 0.2425 - ปีที่หารด้วย 400 ลงตัว "ทั้งหมด" เป็นปีอธิกสุรทิน - ปีที่หารด้วย 100 ลงตัว "เกือบทั้งหมด" เป็นปีอธิกสุรทิน ยกเว้นเพียงกรณีเดียวคือปีที่หารด้วย 400 ไม่ลงตัว :: ความสัมพันธ์ระหว่างตัวหาร :: - 400 หารด้วย 100 ลงตัว และ 100 หารด้วย 4 ลงตัว ----> 400 หารด้วย 4 ลงตัว - ปีที่หารด้วย 4 ไม่ลงตัว หารด้วย 100 และ 400 ไม่ลงตัวเช่นเดียวกัน -- ปีที่หารด้วย 4 ไม่ลงตัว --> "ไม่เป็น" ปีอธิกสุรทินอย่างแน่นอน แยกออกก่อน เหลือเฉพาะปีที่หารด้วย 4 ลงตัว - 100 หาร 400 ลงตัว -- จึงควรแยกปีที่หารด้วย 400 ลงตัว ซึ่ง "เป็น" ปีอธิกสุรทินออกก่อน -- ส่วนที่เหลือนำมาแยกปีที่หารด้วย 100 ลงตัว ซึ่ง"ไม่เป็น" ปีอธิกสุรทินออก ปีที่เหลือทั้งหมดคือ ปีที่ "เป็น" ปีอธิกสุรทิน :: แนวความคิดแรก :: - แยกปีที่ไม่ใช่อย่างแน่นอนออกก่อน if ปีที่หารด้วย 4 ไม่ลงตัว then ไม่เป็นปีอธิกสุรทินอย่างแน่นอน else { เหลือเฉพาะปีที่หารด้วย 4 ลงตัว ซึ่งมีโอกาสที่จะเป็นปีอธิกสุรทิน } if ปีที่หารด้วย 400 ลงตัว then เป็นปีอธิกสุรทิน else if ปีที่หารด้วย 100 ลงตัว then ไม่เป็นปีอธิกสุรทิน else ปีที่เหลือทั้งหมดคือปีอธิกสุรทิน end end end กำหนดตัวแปรสำหรับใช้ในขั้นตอนวิธี ------------------------- year ปี ค.ศ. ที่ต้องการทดสอบ leapyear ตัวแปรชนิด flag สำหรับแสดงสถานะของปีอทิกสุรทิน - ตัวแปรชนิด boolean ขั้นตอนวิธีที่ปรับแล้ว --------------- if year mod 4 != 0 then { ปีที่หารด้วย 4 ไม่ลงตัวซึ่งไม่เป็นปีอธิกสุรทินออกก่อน } leapyear = false else if year mod 400 = 0 then { ปีที่หารด้วย 400 ลงตัว คือปีอธิกสุรทิน } leapyear = true else if year mod 100 = 0 then { ปีที่หารด้วย 100 ลงตัว ไม่เป็นปีอธิกสุรทิน } leapyear = false else leapyear = true { เมื่อแยกกรณีพิเศษออกหมดแล้ว ปีที่เหลือทั้งหมดคือปีอธิกสุรทิน } end end end จัดโครงสร้างใหม่ให้ดูง่ายขึ้นด้วย if-else if ... else -------------------------------------------- if year mod 4 != 0 then { ปีที่หารด้วย 4 ไม่ลงตัวซึ่งไม่เป็นปีอธิกสุรทินออกก่อน } leapyear = false else if year mod 400 = 0 then { เหลือเฉพาะปีที่หารด้วย 4 ลงตัว } leapyear = true { ปีที่หารด้วย 400 ลงตัว คือปีอธิกสุรทิน } else if year mod 100 = 0 then leapyear = false { ปีที่หารด้วย 100 ลงตัว ไม่เป็นปีอธิกสุรทิน } else leapyear = true { เมื่อแยกกรณีพิเศษออกหมดแล้ว ปีที่เหลือทั้งหมดคือปีอธิกสุรทิน } end ทำขั้นตอนวิธีให้สมบูรณ๋โดยการเพิ่ม input และ output ------------------------------------------- :: input :: ข้อมูลปี ค.ศ. ที่จะนำมาทดสอบปี อธิกสุรทิน มีสองกรณี ๑. ผู้ใช้กำหนดในบรรทัดคำสั่งเป็น formal parameter ตัวแรก หรือ positional parameter ตัวแรก การดำเนินการเป็นลักษณะเฉพาะของภาษาที่ใช้ในการเขียนโปรแกรม ๒. ผู้ใช้ไม่กำหนด แสดงว่าต้องการให้ทดสอบว่าปีปัจจุบันเป็นปีอธิกสุรทินหรือไม่? การอ่านวันเวลาของระบบคอมพิวเตอร์เป็นการดำเนินการที่ใช้คุณลักษณะเฉพาะของระบบปฏิบัติการ และภาษาที่ใช้ เขียนเป็นขั้นตอนวิธีได้เป็น if ผู้ใช้กำหนดปี ค.ศ. ในบรรทัดคำสั่ง then year = พารามิเตอร์ตัวแรก else year = ข้อมูลปี ค.ศ. ที่ได้จากการอ่านวันเวลาปัจจุบันของระบบ หมายเหตุ: ขั้นตอนวิธีส่วนนี้เป็นวิธีที่ขึ้นกับระบบและภาษาที่ใช้ (system specific) :: output :: การทดสอบตัวแปร leapyear และแสดงผล if leapyear = true then พิมพ์ " is a leap year, February has 29 days." else พิมพ์ " is NOT a leap year, February has 28 days." จากนั้นจึงรวมทุกอย่างเข้าด้วยกัน จาก input --> process --> output จะได้ขั้นตอนวิธีที่สมบูรณ์ Algorithm: ทดสอบว่าปี ค.ศ. ที่กำหนดเป็นปีอธิกสุรทินหรือไม่? input: ข้อมูลปี ค.ศ. จากบรรทัดคำสั่ง (command line argument) begin { การดำเนินการกับข้อมูล ปี ค.ศ. } if ผู้ใช้กำหนดปี ค.ศ. ในบรรทัดคำสั่ง then year = พารามิเตอร์ตัวแรก else year = ข้อมูลปี ค.ศ. ที่ได้จากการอ่านวันเวลาปัจจุบันของระบบ { การทดสอบว่าเป็นปีอธิกสุรทินหรือไม่ } if year mod 4 != 0 then leapyear = false else if year mod 400 = 0 then leapyear = true else if year mod 100 = 0 then leapyear = false else leapyear = true end { การแสดงผลตามที่ผู้ใช้กำหนด } if leapyear = true then พิมพ์ " is a leap year, February has 29 days." else พิมพ์ " is NOT a leap year, February has 28 days." end ข้อมูลทดสอบ (test set) --------------------- ปีที่ไม่ใช่ปีอธิกสุรทิน - 1700, 1800, 1900, 2013, 2014, 2015 ปีที่เป็นปีอธิกสุรทิน - 2000, 2012, 2016 เมื่อแน่ใจว่า Algorithm ถูกต้องสมบูรณ์แล้วจึงแปลเป็น shell script ที่เสร็จเรียบร้อยแล้วเป็นดังนี้ # year manipulation # ----------------- if [ $# = 0 ]; then year=`date +%Y` else year=$1 fi # test if 'year' is leap year if [ $(($year % 4)) -ne 0 ]; then leapyear=false elif [ $(($year % 400)) -eq 0 ]; then leapyear=true elif [ $(($year % 100)) -eq 0 ]; then leapyear=false else leapyear=true fi # display result echo "leapyear = $leapyear" if [ $leapyear = true ]; then echo "$year is a leap year, February has 29 days." else echo "$year is NOT a leap year, February has 28 days." fi การวิเคราะห์และปรับปรุง -------------------- เมื่อเขียนโปรแกรม และทำการทดสอบจนแน่ใจว่าโปรแกรมที่เขียนขึ้นทำงานถูกต้องทุกกรณีแล้ว หากมีเวลาควรได้วิเคราะห์โปรแกรมเพื่อหาวิธีการที่ดีกว่า ซึ่งสามารถวิเคราะห์ได้ทั้ง Algorithm และโปรแกรม โดยทั่วไปการวิเคราะห์จาก Algorithm ง่ายกว่า ขั้นตอนวิธีการตรวจสอบว่าปี ค.ศ. ที่กำหนดเป็นปีอธิกสุรทินหรือไม่ที่ดำเนินการมาแล้วคือ if year mod 4 != 0 then leapyear = false else if year mod 400 = 0 then leapyear = true else if year mod 100 = 0 then leapyear = false else leapyear = true end algorithm ดังกล่าวถึงแม้จะทำงานได้ถูกต้องสมบูรณ์ แต่ยังมีจุดที่สามารถปรับปรุงให้กระชับและกระทัดรัดได้อีกมาก --> ปี ค.ศ. ทั้งหมด มีโอกาสที่จะไม่ใช่ปีอธิกสุรทิน หรือมีความน่าจะเป็นที่จะเป็นปีปกติมากกว่า 0.75 ตั้งสมมมุติฐานว่า ปี ค.ศ. ที่ผู้ใข้กำหนด ไมใช่ปีอธิกสุรทิน โดยการกำหนดที่ flag leapyear = false --> จากนั้นจึงทำการพิสูจน์ว่าสมมุติฐานนั้นเป็นจริงหรือไม่ โดยรวมเงื่อนไข "ปีอธิกสุรทินคือปีที่หารด้วย 4 ลงตัว แต่หารด้วย 100 ไม่ลงตัว" และ "ปีอธิกสุรทินคือปีที่หารด้วย 400 ลงตัว" เข้าด้วยกันเป็น "ปีอธิกสุรทินคือปีที่หารด้วย 400 ลงตัว" --> หารด้วย 4 ลงตัว, หารด้วย 100 ไม่ลงตัว แต่หารด้วย 400 ลงตัว if (year mod 4 = 0 AND year mod 100 != 0) OR year mod 400 = 0 then leapyear = true เนื่องจาก logical AND มีลำดับความสำคัญ (precedence) สูงกว่า OR วงเล็บรอบเงื่อนไขแรกจึงไม่จำเป็นต้องใช้ ใส่ไว้เพื่อให้อ่านได้ง่ายและชัดเจน ทำการเปลี่ยนแทน algorithm เดิมด้วย leapyear = false if (year mod 4 = 0 AND year mod 100 != 0) OR year mod 400 = 0 then leapyear = true โปรแกรมทำงานได้ถูกต้องเช่นเดียวกัน คำถาม ----- 1. algorithm ใดทำงานได้ดีกว่า? algorithm ใดทำความเข้าใจได้ง่ายกว่า? 2. เมื่อต้องใช้งานจริงควรจะเลือกใช้ วิธีการใด เพราะเหตุใด? shell script ที่ใช้ Algorithm ใหม่ที่เสร็จเรียบร้อยแล้วเป็นดังนี้ # year manipulation # ----------------- if [ $# = 0 ]; then year=`date +%Y` else year=$1 fi # test if 'year' is leap year leapyear=false if [ $(($year % 4)) -eq 0 -a $(($year % 100)) -ne 0 -o $(($year % 400)) -eq 0 ]; then leapyear=true fi # display result echo "leapyear = $leapyear" if [ $leapyear = true ]; then echo "$year is a leap year, February has 29 days." else echo "$year is NOT a leap year, February has 28 days." fi