Intro data structure

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

          

           ให้เครื่องหมาย   =     หมายถึงการกำหนดค่า และก่อนเริ่มทำงาน กำหนดให้ค่า

                            x              =     5 มีความหมายคือ ให้ตัวแปร x เก็บค่า 5

                            y              =     2 มีความหมายคือ ให้ตัวแปร y เก็บค่า 2

Program 1

        

          ต้องการสลับค่า x และ y โดยให้ x เก็บค่า 2 และ y เก็บค่า 5

• ขั้นตอนที่ 1 :                      x = y
• ขั้นตอนที่ 2 :                      y = x
• ขั้นตอนที่ 3 :                      stop

Program 2

        

          วิธีคิด : หาที่ฝากข้อมูลเก่า เพื่อเก็บไว้ก่อน

• ขั้นตอนที่ 1 :          xold = x
• ขั้นตอนที่ 2 :          yold = y
• ขั้นตอนที่ 3 :          y = xold
• ขั้นตอนที่ 4 :           x = yold
• ขั้นตอนที่ 5 :           stop

Program 3

     

          วิธีคิด : ถ้าไม่ใช้หน่วยความจำเพิ่ม จะทำอย่างไร

• ขั้นตอนที่ 1 :          x = x + y
• ขั้นตอนที่ 2 :          y = y - x
• ขั้นตอนที่ 3 :          x = x + y
• ขั้นตอนที่ 4 :          y = -y
• ขั้นตอนที่ 5 :          stop

Program 4

         วิธีคิด : ปรับจากโปรแกรม 2 เล็กน้อย

• ขั้นตอนที่ 1 :          z = x
• ขั้นตอนที่ 2 :          x = y
• ขั้นตอนที่ 3 :          y = z
• ขั้นตอนที่ 4 :          stop

จำนวนครั้ง VS การใช้หน่วยความจำ

              ถ้าเปรียบเทียบความสำคัญของจำนวนขั้นตอนเทียบกับเนื้อที่ในหน่วยความจำที่ใช้แล้ว จำนวนขั้นตอนที่น้อยจะมีความสำคัญกว่าการใช้หน่วยความจำ เพราะการมีขั้นตอนน้อยจะทำให้การทำงานของโปรแกรมเร็วขึ้น

Algorithm

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

นิยามอัลกอริทึม

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

            อัลกอริทึม (Algorithm) หมายถึง ลำดับขั้นตอนวิธีในการทำงานของโปรแกรม เพื่อแก้ปัญหาหนึ่ง ซึ่งถ้าปฏิบัติตามขั้นตอนอย่างถูกต้องแล้ว จะต้องสามารถช่วยแก้ปัญหาหรือประมวลผลตามความต้องการได้สำเร็จ สำหรับในการเขียนอธิบายอัลกอริทึมนั้น เราสามารถคิดอัลกอริทึมเพื่อมาแก้ปัญหาได้หลายแบบ

ตัวอย่างอัลกอริทึม (algorithm)

          การต้มไข่ไก่

          วัตถุดิบ : ไข่ไก่            ผลลัพธ์ : ไข่ต้มสุก

Algorithm 1 VS Algorithm 2

           ผลที่ได้เหมือนกัน คือ ไข่ต้ม
           ผลลัพธ์ Algorithm 1 สามารถทานได้เลย ส่วน Algorithm 2 ต้องปอกก่อนทาน
          สรุปคือ เราได้ผลลัพธ์ตามโจทย์ต้องการ คือ ไข่ต้ม
          Algorithm 3 : คุณยังไม่ได้ไข่ต้ม เนื่องจาก คุณยังไม่ได้ใส่ไข่ต้มลงไปนั่นเอง

การวิเคราะห์ปัญหา

การพิจารณา

•          ขั้นตอนการทำงานเป็นการนำเข้าป้อนเข้าระบบ ถือเป็น Input
•          ขั้นตอนเกี่ยวกับการกระทำ (กริยา) ถือเป็น Process
•          ขั้นตอนการนำข้อมูลออกจากระบบ แสดงผล ถือเป็น Output

วิเคราะห์ขั้นตอนการต้มไข่

        ต้มน้ำให้เดือน à การกระทำ (Process)

       ใส่ไข่ à การป้อนข้อมูล (input)

       รอ 10 นาที à การกระทำ (Process)

       ดับไฟ à การกระทำ (Process)

       ปอกไข่ à การกระทำ (Process)

       ผลลัพธ์ à ไข่ต้มสุก (output)

ตัวอย่าง : ต้องการคำนวณหาพื้นที่ของสามเหลี่ยมรูปหนึ่ง

1. วิเคราะห์ผลลัพธ์ : พื้นที่สามเหลี่ยม

           กำหนดวัตถุประสงค์ การคำนวณหาพื้นที่สามเหลี่ยม

           รูปแบบผลลัพธ์ (Output)

                   พื้นที่สามเหลี่ยม = ……………………..

2. กำหนดข้อมูลเข้า (Input)

            ความยาวฐาน

            ความสูง

3. ขั้นตอนการประมวลผล

            ขั้นตอนที่ 1 ป้อนความยาวฐาน

            ขั้นตอนที่ 2 ป้อนความสูง

            ขั้นตอนที่ 3 คำนวณพื้นที่สามเหลี่ยม จากสูตร

ตัวอย่าง : อัลกอริทึมเพื่อทำการบวกราคาโดยใช้เครื่องคิดเลข

1. วิเคราะห์ผลลัพธ์ : ยอดรวมราคา

2. กำหนดข้อมูลเข้า (Input) : ยอดเงิน

3. ขั้นตอนการประมวลผล

            

            ขั้นตอนที่ 1 พิมพ์ยอดเงิน

            ขั้นตอนที่ 2 กดเครื่องหมาย

            ขั้นตอนที่ 3 วนการทำงาน

            ขั้นตอนที่ 4 กดเครื่องหมาย =

            ขั้นตอนที่ 5 คำนวณยอดรวมราคา

การออกแบบอัลกอริทึม

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

ประสิทธิภาพของอัลกอริทึม

           อัลกอริทึมของใครใช้เวลาในการประมวลผลและหน่วยความจำน้อยกว่า ถือว่าอัลกอริทึมนั้นฉลาดกว่าอีกอัลกอริทึมหนึ่ง   การพิจารณาประสิทธิภาพของอัลกอริทึมนั้น มี 2 ส่วนหลัก ดังนี้

          1.            หน่วยความจำ (Memory) ที่จะต้องใช้ในการประมวลผล

          2.            เวลา (Time) ที่ใช้ในการประมวลผล

คุณสมบัติของอัลกอริทึมที่ดี

         

         1.            อัลกอริทึมที่ดีต้องมีความถูกต้อง (Correctness)

         2.            อัลกอริทึมที่ดีต้องง่ายต่อการอ่าน (Readability)

         3.            อัลกอริทึมที่ดีต้องสามารถปรับปรุงได้ง่ายต่ออนาคต (Ease of Modification)

         4.            อัลกอริทึมที่ดีสามารถนำกลับมาใช้ใหม่ได้ (Reusability)

         5.            อัลกอริทึมที่ดีต้องมีประสิทธิภาพ (Efficiency)

การควบคุมการทำงานของโปรแกรม

            เครื่องมือที่ผู้พัฒนาโปรแกรมใช้ในการแสดงลำดับการทำงานของโปรแกรมหรือใช้อธิบายอัลกอริทึม ให้เป็นระบบและง่ายต่อความเข้าใจ โดยโครงสร้างอาจจะอยู่ในรูปแบบ ดังนี้คือ

1.            ผังงาน (Flowchart) ใช้อธิบายขั้นตอนการทำงานของโปรแกรมในลักษณะรูปภาพ

2.            รหัสเทียม (Pseudo code) จะมีลักษณะคล้ายกับภาษาอังกฤษ ก้ำกึ่งระหว่างภาษาอังกฤษกับภาษาคอมพิวเตอร์ ใช้ในการอธิบายลักษณะโครงสร้างของข้อมูล และการทำงานของอัลกอริทึมที่เราเขียนขึ้น

ประโยชน์ของผังงาน

1.            ลำดับขั้นตอนการทำงานของโปรแกรมและสามารถเขียนโปรแกรมได้โดยไม่สับสน

2.            ตรวจสอบความถูกต้องและแก้ไขโปรแกรมได้ง่าย เมื่อเกิดข้อผิดพลาด

3.            การปรับปรุง เปลี่ยนแปลง แก้ไข ทำได้อย่างสะดวกและรวดเร็ว

4.            ทำให้ผู้อื่นสามารถศึกษาการทำงานของโปรแกรมได้อย่างง่ายและรวดเร็วมากขึ้น