ADT Lecture 3 - 25/08/2014

Iteration​ (การวนซ้ำ)

  • Iteration ใช้ทำงานที่ซ้ำไปซ้ำมา
  • ในการเขียนโปรแกรมจะใช้คำสั่งลูป (while, do..while, for, for each, ฯลฯ) ในการเขียนอัลกอริธึมที่มีการวนซ้ำ

Recursion

  • เป็นการนิยามสิ่งหนึ่งโดยนิยามให้กล่าวถึงสิ่งนั้นเอง
  • เช่น ลิสต์มีได้สองแบบคือไม่มีข้อมูล กับมีข้อมูลหนึ่งแล้วตามด้วยลิสต์
  • สามารถใช้ในการวนซ้ำได้เหมือน iteration

  • เกี่ยวข้องกับการอุปนัย

  • Recursion สามารถเขียนด้วย iteration (loop) หรือกลับกันก็ได้

  • แต่บางครั้งการเขียนแบบใดแบบหนึ่งจะเข้าใจได้ง่ายกว่า

การพิสูจน์แบบอุปนัย

การจะพิสูจน์ว่า S(n) เป็นจริงทำดังนี้

  • กำหนดให้ S(n) เป็นจริง
  • ทดสอบว่า
  • กรณีเริ่มต้น: S(1) เป็นจริงหรือไม่?
  • อุปนัย: S(n) สามารถนำไปสู่ S(n+1) ได้หรือไม่?
  • ถ้าเป็นจริงทั้งคู่ สรุปได้ว่าประโยคนั้นเป็นจริง

ตัวอย่าง: S(n): 1 + 2 + 3 + ... + n = n(n+1)/2

  1. กำหนดให้ S(n) เป็นจริง
  2. S(1) เป็นจริงหรือไม่? S(1): 1 = 1(1+1)/2 = 1
  3. S(n) : 1 + 2 + 3 + ... + n = n(n+1)/2
  4. บวก (n+1) ทั้งสองข้าง: 1 + 2 + 3 + ... + n + (n+1) = n(n+1)/2 + (n+1)
  5. คูณด้วย 2/2: 1 + 2 + 3 + ... + n + (n+1) = n(n+1)/2 + 2(n+1)/2
  6. ดึงตัวร่วม (n+1): 1 + 2 + 3 + ... + n + (n+1) = (n+1)(n+2)/2
  7. S(n+1) : 1 + 2 + 3 + ... + (n+1) = (n+1)(n+2)/2
  8. ทั้งสองกรณีเท่ากัน แสดงว่า S(n) นำไปสู่ S(n+1)

การพิสูจน์นี้เกี่ยวข้องกับ recursion ตรงที่ recursion ใช้สมมุติฐานว่าปัญหาย่อยๆ สามารถแก้ได้ด้วยวิธีเดียวกับปัญหาใหญ่จนกว่าจะถึงกรณีเริ่มต้น (base case)

แบบฝึกหัด

1. คำนวณหา n!

เราต้องการหาค่าของ n! โดยวิธี recursive ใน Java แต่เราไม่ทราบว่าจะหา n! ได้อย่างไร แต่เรารู้วิธีการหา (n-1)! จะสามารถนำมาใช้เป็นประโยชน์ได้หรือไม่?

ได้ เนื่องจาก n! = (n-1)! * n

ส่วนกรณีเริ่มต้นของเราคือ 1! = 1

public static int factorial(int n){
    // Start with base case
    if(n == 1){
        return 1;
    }
    return factorial(n-1) * n;
}

2. ผลรวมของทุกหลักใน n

ตัวอย่าง กำหนดให้ n = 9,867 จะได้ผลรวมของทุกหลักคือ 9+8+6+7 = 30

หากเราไม่รู้วิธีการคำนวณผลรวมของหลักใน 9,867 แต่เราทราบวิธีหาผลรวมของ 986 สามารถหาผลรวมของ 9,867 ได้โดยบวก 7 เข้าไปในคำตอบของผลรวมของ 986

กรณีพื้นฐานคือเมื่อ n มีเพียงหลักเดียว ก็จะตอบ n ได้เลย

public static int sumDigits(int n){
    if(n < 10){
        return n;
    }
    // n%10 get the last digit
    // n/10 get rid of the last digit
    return n % 10 + sumDigits(n/10);
}

3. ข้อความนั้นเป็นพาลินโดรมหรือไม่

ตัวอย่าง a man a plan a canal panama สามารถอ่านจากซ้ายไปขวาหรือขวาไปซ้าย (กลับหน้ากลับหลัง) ก็จะได้ข้อความเดียวกัน

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

ถ้าเราทราบว่าข้อความที่อยู่ระหว่างตัวแรกกับตัวสุดท้ายนั้นเป็นพาลินโดรม เราสามารถตรวจสอบความเป็นพาลินโดรมของทั้งข้อความได้โดยตรวจสอบว่าตัวอักษรตัวแรกและตัวสุดท้ายเป็นตัวเดียวกัน

กรณีพื้นฐานคือเมื่อข้อความนั้นมีเพียงตัวอักษรเดียว ให้ถือว่าเป็นพาลินโดรม

public static boolean isPalindrome(String s){
    if(s.length() == 1) {
        return true;
    }
    if(!isPalindrome(s.substring(s, s.length() - 1))){
        return false;
    }
    return s.charAt(0) == s.charAt(s.length() - 1);
}