การระบุข้อมูลเข้าข้อมูลออกและเงื่อนไขของปัญหา
การแก้ปัญหาด้วยคอมพิวเตอร์นั่น
ก่อนที่ระบุขั้นตอนวิธีที่ชัดเจนได้
จะต้องวิเคราะห์และทำความเข้าใจกับปัญหาเพื่อให้ทราบว่ามีข้อมูลอะไรบ้างที่สามารถใช้ในการประมวลผลได้
มัเงื่อนไขต่างๆ อย่างไร ผลลัพธ์ที่ต้องการคืออะไร โดยจะแบ่งข้อมูลที่เกี่ยวข้องกับการทำงานออกเป็นสองส่วนคือ
1. ข้อมูลเข้า ( input ) เป็นข้อมูลที่ใช้เพื่อประมวลผล
2. ข้อมูลออก ( output ) เป็นข้อมูลผลลัพธ์ที่ต้องการ
จากการวิเคราะห์ข้อมูลทั่งสอนส่วนนี้ นอกจากจะระว่าคืออะไรแล้ว
ยังอาจระบุเงื่อนไขเพิ่มเติมได้ เช่น ข้อมูลอาจการระบุขอบเขตหรือเงื่อนไข
หรือข้อมูลออกอาจมีการระบุคุณสมบัติที่ต้องการ
การวิเคราะห์นี้เป็นการระบุข้อกำหนดต่างๆ ที่เกี่ยวข้องกับปัญหาให้ชัดเจน
ซึ่งจำเป็นต่อการออกแบบขั้นตอนวิธีที่ถูกต้อง
ตัวอย่าง 2.1
ปัญหาการหา ห.ร.ม
พิจารณาตัวอย่างปัญหาการหา
ห.ร.ม จากหัวข้อที่ 1.2 ในบทที่ 1 นักเรียนสามารถระบุข้อมูลเข้า
ข้อมูลออก รวมทั่งเงื่อนไขได้ดังนี้
- ข้อมูลเข้า
: จำนวนเต็มบวกหนึ่งจำนวน a และ b
- ข้อมูลออก
: จำนวนเต็มบวกหนึ่งจำนวน c ที่มีคุณสมบัติดังนี้
ตัวอย่างที่ 2.2 คะแนนสอบ
พิจารณาสถานการณ์สมมติต่อไปนี้
ครูได้ตรวจข้อสอบของนักเรียน40คน และได้ประกาศคะแนนไว้หนน้าห้อง หากต้องการหาคะแนนสูงสุด และต่ำสุด
และคำนวณคะแนนเฉลี่ยของนักเรียนทุกคน ในกรณีนี้ระบุข้อมูลออกได้ดังนี้
- ข้อมูลเข้า
: รายการคะแนนสอบของนักเรียน 40
คน
- ข้อมูลออก
: คะแนนสูงสุด คะแนนต่ำสุด คะแนนเฉลี่ย
แม้ว่าในหลานๆ กรณี การระบุข้อมูลเข้าและข้อมูลออกนั่นอาจตะไม่สามารถทำได้อย่างชัดเจน
แต่ความพยายามในการระบุข้อมูลทั่งสองมักเป็นเงื่อนไขให้ต้องทำความเข้าใจกับปัญหามากขึ้น
ลองพิจารณาตัวอย่างต่อไปนี้
ตัวอย่าง ที่ 2.3 แบ่งกลุ่มการทำงาน
นักเรียนในห้องต้องการจัดกิจกรรมวันภาษาไทย จากการประชุมมีงานที่ต้องทำดังนี้
1. จัดบอร์ดหน้าห้องเกี่ยวกับภาษาไทย
2. จัดเตรียมงานโต้วาที
3. เป็นกลุ่มผู้โต้วาที โดนมาสองกลุ่ม กลุ่มละ 3 คน
4. อ่านกลอนทำน้องเสนาะ
5. ร้องเพลงไทยสมัยใหม่
เพื่อให้ทุกคนได้ทำงานที่ต้องการทำหรืออย่างน้องเป็นงานที่ยินดีทำ
จึงได้ให้นักเรียนทุกคนกรอกข้อมูลว่าสมมารถทำงานใดได้บ้าง
และมีงานใดบ้างที่ต้องการทำเป็นพิเศษ โดยมีเงื่อนไขว่า
ให้นักเรียนหนึ่งคนไม่ควรทำงานเกิน 2 อย่าง และผู้โต้วาทีไม่ควนเป็นคนจัดเตรียมงานโต้วาที
จากจ้อมูลดังกล่าว ต้องการจัดกลุ่มว่านักเรียนคนใดจะทำงานใดบ้าง
สามารถระบุข้อมูลเข้าและข้อมูลออกได้ดังนี้
- ข้อมูลเข้า : รายการของงาทั่งหมด
ข้อมูลนักเรียนแต่ละคนที่ระบุว่าสามารถทำงานใดได้บ้างและต้องการทำงานใดเป็นพิเศษบ้าง
- ข้อมูลออก : ข้อมูลที่ระบุว่านักเรียนคนใดทำงานอะไร
โดยมีเงื่อนไขดังนี้
จากการวิเคราะห์ข้อมูลข้างต้น
นักเรียนอาจจะพบปัญหาเมื่อเริ่มดำเนินการ เช่น
ถ้ามีนักเรียนบางคนไม่ระบุงานที่สามารถทำได้ ก็จะทำให้ไม่สามารถจัดกลุ่มได้
สักเกตว่าการระบุข้องมูลที่ชัดเจนทำให้สามารถวิเคราะห์สถานการณ์ได้ชัดเจนยิ่งขึ้น
และจะช่วยปรับปรุงกระบวนการต่างๆ ได้ดีกว่าเดิมในกรณีนี้เพื่อให้สามารถจัดกลุ่มได้
อาจะเพิ่มเงื่อนไขให้นักเรียนทุกคนต้องเลือกงานที่สามาทำได้อย่างน้อยหนึ่งอย่าง
ตัวอย่างที่ 2.4 อุปกรณ์รดน้ำต้นไม้อัตโนมัติ
ตัวอย่างนี้จะพิจารณาการสร้างอุปการณ์เพื่อตรวจสอบความชื่นของดิน
ถ้าดินแห้งจะสั่งให้รถน้ำต้นไม้โดยอัตโนมัติ ระบบดังกล่าวแสดงดังรูป 2.3
ระบบการรดน้ำต้นไม้อัตโนมัตินี้มีการรับและส่งงานระหว่างคอมพิวเตอร์
และอุปกรณ์อื่นๆ เช่น ตัวตรวจจับ ( sensor ) เพื่อใช่อ่านข้อมูลจากสภาพแวดล้อมหรือจากสิ่งที่สนใจโดยข้อมูลเข้า
คือ ระดับความชื่นของดินที่อ่านจากตัวตรวจจับ และเครื่องคอมพิวเตอร์จะประมวลผลเพื่อสั่งงานไปยังอุปกรณ์ควบคุมการเปิดปิดน้ำ
ดังนั่นข้อมูลออกในกรณีนี้คือสัญญาณควบคุมอุปกรณ์เปิดปิดน้ำโดนสรุป
สามารถระบุจ้อมูลเข้าและข้อมูลออกได้ดังนี้
- ข้อมูลเข้า
: ระดับความชื้นของดิน
(ผ่านทางตัวตรวจจับ)
- ข้อมูลออก
: สัญญาณควยคุมการเปิดปิดน้ำ
กิจกรรมที่ 2.3
ข้อมูลเข้าและข้อมูลออก
ให้ระบุข้อมูลเข้า และข้อมูลออก ของรถยนต์อัตโนมัติ และระบบแปลภาษา
2.3 การออกแบบขั้นตอนวิธี
ทักษะการคิดเชิงคำนวณ
เช่น การแยกส่วนประกอบและการย้อยปัญหา การหารูปแบบ และการคิดเชิงนามธรรม
สามารถรำมาใช้ในการออกแบบขั้นตอนวิธีเพื่อแก้ปัญหาต่างๆ การออกแบบนี้ไม่มีขั้นตอนที่ตายตัว
จำเป็นต้องอาศัยประสบการณ์และการฝึกฝนจำเป็นสิ่งที่ท้าทายซึ่งจะเป็นประโยชน์กับนักเรียนในอนาคต
2.3.1 ตัวอย่างการออกแบบขั้นตอนวิธี
ตัวอย่างที่ 2.5
การตัดสินใจรดน้ำต้นไม้ของระบบรดน้ำต้นไม้อัตโนมัติ
การตัดสินใจรดน้ำต้นไม้ในขั้นตอนวิธีของระบบรดน้ำต้นไม้อัตโนมัติ
ระบบจะต้องอ่านข้อมูลความชื้นของดินแล้วเปรียบเที่ยวกับค่าที่กำหนดไว้ (
สมมติค่าความชื้นกำหนดเป็น 0.1 หน่วย)
หากค่าความชื้นต่ำกว่าค่าที่กำหนด ให้ระบบส่งสัญญาณเปิดน้ำ
และหากมีค่าความชื้นเกินกว่าหรือเท่ากับค่าที่กำหนดไว้ให้ระบบส่งสัญญาณปิดน้ำ
ในส่วนการทำงานหลักของขั้นตอนวิธี คือ การตัดสิ้นใจรดน้ำต้นไม้
มีการทำงานตามลำดับดังนี้
1. อ่านค่าความชื้นของดิน
2. ให้ H แทนค่าความชื้น
3. ถ้า H <
0.1 แล้ว
3.1 ส่งสัญญาณเปิดน้ำ
ถ้าเงื่อนไขไม่เป็นจริง
3.2 ส่งสัญญาณปิดน้ำ
ส่วนของขั้นตอนวิธีดังกล่าวเป็นการตัดสินใจเพียงครั้งเดียว
ดังนั่นเพื่อความสมบูรณ์ขั้นตอนวิธีที่จะทำให้ระบบรดน้ำต้นไม้มีการอ่านค่าและส่งสัญญาณควบคุมจะต้องทำสม่ำเสมอ
จึงต้องให้ขั้นตอนวิธีด้านบนทำซ้ำๆ ต่อเนื่องกับไป ดังนี้
- ขั้นตอนวิธี
: ควบคุมการเปิดปิดน้ำของเครื่องรดน้ำต้นไม้
- ข้อมูลเข้า
: ค่าความชื้นของดิน
- ข้อมูลออก
: สัญญาณเปิด ปิดน้ำ
1. ทำซ้ำทุกๆ 1วินาที
1.1 อ่านค่าความชื้นของดิน
1.2 ให้ H แทนค่าความชื้นดังกล่าว
1.3 ถ้า H <
0.1 แล้ว
1.3.1 ส่งสัญญาณเปิดน้ำ
ถ้าเงื่อนไขไม่เป็นจริง
1.3.2 ส่งสัญญาณปิดน้ำ
ขั้นตอนวิธีดังกล่าวเขียนเป็นผังงานได้ดังรูป 2.4
ตัวอย่างที่ 2.6 การคำนวณคะแนนข้อสอบ
พิจารณาสถานการณ์จากตัวอย่างที่
2.2 ต้องการคำนวณคะแนนสูงสุด คะแนนต่ำสุด และคะแนนเฉลี่ย
ของนักเรียนในห้อง โดยมีข้อมูลเข้าและข้อมูลออก ดังนี้
- ข้อมูลเข้า
: รายการคะแนนสอบของนักเรียน 40
คน
- ข้อมูลออก
: คะแนนสูงสุด คะแนนต่ำสุด คะแนนเฉลี่ย
ชวนคิด
นักเรียนคิดว่าปัญหาการคำนวณคะแนนสอบมีลักษณะคล้ายคลึงกับปัญหาใดต่อไปนี้มากที่สุด
1 ปัญหาการวางแผนการเดินทางเพื่อไปให้ครบทุกที่
2 ปัญหาการหา ห.ร.ม
3 ปัญหาการเลือกรายการอาหารที่เหมาะสมที่สุด
ปัญหานี้สามารถแบ่งได้เป็นสามส่วน คือ การหาคะแนนสูงสุด
การหาคะแนนต่ำสุด และการหาคะแนนเฉลี่ย
จะเริ่มพิจารณาจากปัญหาการหาคะแนนสูงที่สุดก่อน
ในการออกแบบนั่นจะเริ่มโดยสังเกตวิธีการที่นักเรียนใช้ในการหาค่าสูงสุดของข้อมูล
พิจารณาตัวอย่างจำนวนเต็ม สิบจำนวนโดยที่ห้าจำนวนแรกดังรูป2.5 และอีกห้าจำนวนอยู่หน้า 57
รูป 2.7
โดยทั่วไปแล้ว ถ้ามีจำนวนข้อมูลน้อย
นักเรียนสามารถหาค่าสูงสุดได้ทันที อย่างไรก็ตามถ้าข้อมูลอยู่คนละหน้า
จะพบว่าระหว่างที่พลิกหาหน้าไปพิจารณาข้อมูลชุดที่สองนั่น
นักเรียนจะต้องจำค่าสูงสุดที่พบจากข้อมูลชุดแรก
สังเกตว่าการตัดสินใจดังกล่าวจะเกินขึ้นระหว่างการพิจารณาข้อมูลไปทีละจำนวนด้วย
นักเรียนสามารถใช้แนวคิดนี้ในการเขียนขั้นตอนวิธีได้โดยในการจดจำ จะใช้ตัวแปรชื่อ MAX แทนค่าสูงสุดที่พบ
ขั้นตอนวิธีดังกล่าวแสดงได้ดังนี้
- ขั้นตอนวิธี
: หาค่าสูงที่สุดของข้อมูลในรายการ
- ข้อมูลเข้า
: รายการข้อมูล
- ข้อมูลออก
: ค่าสูงสุดของข้อมูล
1. พิจารณาข้อมูลตัวแรกให้ MAX มีค่าเป็นข้อมูลดังกล่าว
2. พิจารณาข้อมูลตัวถัดไป
ทีละจำนวน
2.1 เรียกข้อมูลที่กำลังพิจารณาว่า
X
2.2 ถ้า X >
MAX ให้ MAX ← X
3. ตอบว่าค่าที่สูงที่สุดคือ
MAX
กิจกรรมที่ 2.4
ค่าต่ำสุด
เนื่องจากคะแนนเฉลี่ยคือคะแนนรวมหารด้วยจำนวนนักเรียนในห้องซึ่งในที่นี้
มีค่าเท่ากับ 40 คน
ดังนั้นในการคำนวณคะแนนเฉลี่ยจะสนใจเฉพาะคะแนนรวม
นักเรียนสามารถคำนวณคะแนนรวมด้วยวิธีการใกล้เคียงกับการหาคะแนนสูงสุด
โดยจะใช้ตัวแปร Total เก็บค่าผลรวมของคะแนนทั่งหมด
เมื่อเริ่มต้นจะให้ Total มีค่าเป็น 0 ขั้นตอนวิธีดังกล่าวแสดงได้ดังนี้
- ขั้นตอนวิธี
: หาค่าเฉลี่ยของข้อมูลในรายการ
- ข้อมูลเข้า
: รายการข้อมูล
- ข้อมูลออก
: ผลรวมของข้อมูล
1. ให้ Total มีค่าเป็น 0
2. พิจารณาข้อมูล
ทีละจำนวนจนครบทุกจำนวน
2.1 เรียกข้อมูลตัวที่กำลังพิจารณาว่า
X
2.2 ให้ Total ← Total + X
3. ตอบว่าผลรวมคือ Total
เมื่อคำนวณผลรวมได้แล้ว ค่าเฉลี่ยจะมีค่าเท่ากับ Total 40
การหาค่าเฉลี่ยโดยรวมด้วย
40 นั้น ใช้ได้กับกรณีที่มีข้อมูลจำนวน 40 จำนวนเท่านั้น เราสามารถแก้ไขขั้นตอนวิธีให้ทำงานได้ครอบคลุมมากขึ้น
โดยนับจำนวนข้อมูลไปพร้อมๆ กับการหาผลรวมขั้นตอนวิธีแก้ไชแล้วเป็นดังนี้
- ขั้นตอนวิธี
: หาค่าเฉลี่ยของจ้อมูลในรายการ
- ข้อมูลเข้า
: รายการข้อมูล
- ข้อมูลออก
: ค่าเฉลี่ยของข้อมูล
1. ให้ Total มีค่าเป็น 0
2. ให้ Count มีค่าเป็น 0
3. พิจารณาข้อมูล ทีละจำนวน
1. เรียกข้อมูลตัวที่กำลังพิจารณาว่า X
2. ให้ Total ← Total + X
3. ให้ Count ← Count + X
4. ตอบว่าค่าเฉลี่ยคือ Total Count
ขั้นตอนในจ้อ 3.2
และ 3.3 มีการกำหยดให้ Total และมีการกำหยดให้ Count มีค่าเป็น Count + 1 เพื่อเพิ่มค่าให้ตัวแปร Count การเขียนลักษณะนี้จะพบได้บ่อยครั้งในการเขียนโปรแกรม
ซึ่งแตกต่างจากการเขียนสมการทางคณิตศาสตร์
2.3.2 การออกแบบและพิจารณาเงื่อนไข
1. การสร้างเงื่อนไขอย่างง่าย
การออกแบบเงื่อนไขที่ถูกต้องและชัดเจนจะเป็นปัจจัยสำคัญของการออกแบบขั้นตอนวิธี
ซึ่งเงื่อนไขที่กำหนดอาจจะเป็นเงื่อนไขอย่างง่าย มักจะเป็นการเปรียบเทียบ มากกว่า
น้อยกว่า หรือไม่เท่ากัน เช่น การหาค่าสูงสุด มีการใช้เงื่อนไข
ถ้า x > Max แล้วให้ Max ← x
ขั้นตอนวิธีดังกล่าว
มีการกำหนดให้การทำงานขึ้นกับเงื่อนไข “x > Max” ซึ่งเป็นรูปแบบที่ง่ายที่สุดโดยเปรียบเทียบกับค่าของตัวแปร
x และค่าของตัวแปร Max
เกร็ดน่ารู้
ในทางตรรกศาสตร์
“ประพจน์” (proposition) คือข้อความที่สามารถบอกค่าความจริงได้
ซึ่งจะมีค่าเป็นจริงหรือเท็จเท่านั่น
ในการกำหนดเงื่อนไขในขั้นตอนวิธีมักจะเขียนในรูปแบบของประโยคเปิดซึ่งเป็นรูปประโยคที่มีตัวแปร
เช่น x>max และเมื่อแทนค่าตัวแปรแล้ว
ประโยคเปิดจะกลายเป็นประพจน์ เพราะสามารถบอกค่าความจริงได้
ตัวอย่างที่ 2.7 ตรวจสอบพิกัด
แผนที่ฉบับหนึ่ง
มีอัตราส่วน 1 เซนติเมตร ต่อ 1กิโลเมตร
และมีกี่ตีตารางพิกัดทุกๆ หนึ่งเซนติเมตร ถ้าพิกัดของโรงเรียนอยู่ที่ตำแหน่ง (2.3)
พิกัดของร้านอาหารอยู่ที่ตำแหน่ง (x,y) ในแผนที่
ถ้าต้องการตรวจสอบว่าร้านอาหารมีระยะห่างจากโรงเรียนไม่เกิน 1 กิโลเมตรหรือไม่ จะระบุเงื่อนไขได้ดังนี้
- เงื่อนไข
: จุด (x,y) ห่างจากจุด (2,3)
ในแผนที่ไม่เกิน 1 เซนติเมตร
ในการตรวจสอบเงื่อนไขดังกล่าว อาจต้องใช้ไม้บรรทัดวัดระยะห่างในแผนที่
หรือใช้ทฤษฎีบทพีทาโกรัส คำนวณระยะห่างของพิกัดของร้านอาหาร (x,y)กับจัด (2.3) ได้เท่ากับ
- เงื่อนไข
:
ให้เขียนเงื่อนไขต่อไปนี้ให้ชัดเจน
2. การสร้างเงื่อนไขด้วยตัวดำเนินการตรรกะ
เงื่อนไขบางเงื่อนไข เช่น “รถประจำทางถึงโรงเรียนแล้ว” หรือ
“รถยนต์มีความเร็วที่เหมาะสม” เป็นเงื่อนไขที่ระบุด้วยประโยคที่ชัดเจน
ในการออกแบบขั้นตอนวิธีเราสามารถใช้เงื่อนไขเช่นนี้ได้ อย่างไรก็ตามระหว่างที่เราวิเคราะห์บางครั้งจะพบว่าเงื่อนไขที่ระบุด้วยประโยคลักษณะนี้
ถ้าพิจารณาด้วยแนวคิดการแยกส่วยประกอบและการย่อยปัญหาอาจจะประกอบด้วยเงื่อนไขย่อยๆ
อีกก็ได้เช่น เงื่อนไข “รถยนต์มีความเร็วที่เหมาะสม” อาจมีความหมายว่า
รถยนต์มีความเร็วมากกว่า 40 กิโลเมตรต่อชั่วโมง และไม่เกิน 90
กิโลเมตรต่อชั่วโมง
สังเกตว่าเงื่อนไขนี้ประกอบด้วยเงื่อนไขย่อยสองเงื่อนไข
และเชื่อมกันด้วยตัวดำเนินการตรรกะ “และ” (AND) นอกจากตัวดำเนินการ
“และ” แล้วตัวดำเนินการที่พบบ่อยในการออกแบบขั้นตอนวิธี คือ “หรือ” (OR) และ “นิเสธ” (NOT) ดังตารางที่ 2.3 แสดงตารางค่าความจริงของเงื่อนไขที่ใช้ตัวดำเนินการตรรกะทั่งสามแบบ
ตัวอย่างที่ 2.8 ตรวจสอบพิกัดโรงเรียน
จากตัวอย่างที่ 2.7
สมมติว่าพื้นที่โรงเรียนเป็นรูปสี่เหลี่ยมมุมฉากที่มีด้วยขนานกับแกนตั้งและแกนนอน
โดยมีพิกัดมุมล่างซ้ายอยู่ที่ตำแหน่ง (1,1) และมุมบนขวาในแผนที่อยู่ที่
(4,3) นักเรียนคนหนึ่งอยู่ที่ตำแหน่ง (X,Y) เงื่อนไขที่ระบุว่านักเรียนสามารถเขียนได้หลานแบบ เช่น
ที่มาhttp://www.168training.com/elearning_new/tc_co_m4_1/lesson2/content2/more/teachercontent1.p hp
ไม่มีความคิดเห็น:
แสดงความคิดเห็น