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
- กำหนดให้
S(n)
เป็นจริง S(1)
เป็นจริงหรือไม่?S(1)
: 1 = 1(1+1)/2 = 1S(n)
: 1 + 2 + 3 + ... + n = n(n+1)/2- บวก (n+1) ทั้งสองข้าง: 1 + 2 + 3 + ... + n + (n+1) = n(n+1)/2 + (n+1)
- คูณด้วย 2/2: 1 + 2 + 3 + ... + n + (n+1) = n(n+1)/2 + 2(n+1)/2
- ดึงตัวร่วม (n+1): 1 + 2 + 3 + ... + n + (n+1) = (n+1)(n+2)/2
S(n+1)
: 1 + 2 + 3 + ... + (n+1) = (n+1)(n+2)/2- ทั้งสองกรณีเท่ากัน แสดงว่า
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);
}