Kỹ thuật lập trình - Bài 2: Chương trình con và đệ quy - Ngô Hữu Dũng

Kỹ thuật lập trình Bài 2 – Chương trình con và đệ quy Ngô Hữu Dũng Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-201731 Chương trình con Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201732 1. #include 2. int cong(int,int); // Khai báo prototype 3. void main() 4. { 5. int a = 5, b, c; 6. b = cong(a, 3); 7. c = cong(3,cong(a,b)); 8. printf("Tong la %d",cong(b,c)); 9. } 10. int cong(int x, int y) // Hàm chi tiết 11. { 12. return x + y; 13. } Ngô Hữu Dũng FUNCTION Input Output Thành phần Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201733  Kiểu trả về của hàm  Tên hàm  Tham số  Tham biến  Tham trị  Lệnh return trả về giá trị cho hàm  Khai báo prototype  Gọi hàm  Phạm vi của biến Return-type function-name(argument declarations) { declarations and statements } Ngô Hữu Dũng Main() Function1() Function2() Function3() Function4() Kiểu trả về của hàm Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201734  Hàm có thể trả về một giá trị  int  float  char   void: Không trả về giá trị  Khi kết thúc, hàm sẽ mang một giá trị trừ trường hợp hàm mang kiểu void. 1. int cong(int x, int y) 2. { 3. return x + y; 4. } 1. float nhan(int x, int y) 2. { 3. return x * y; 4. } 1. void in(char line[]) 2. { 3. printf("%s",line); 4. } Ngô Hữu Dũng Tên hàm và tham số Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201735  Tên hàm do người lập trình đặt  Không được trùng với từ khóa  Các ký tự liên tiếp nhau  Gồm ký tự, số, dấu gạch chân  Không gồm các ký tự đặc biệt  Có nghĩa, dễ hiểu  Tham số (đối số)  Một, nhiều hoặc không có tham số  Mỗi tham số đều có kiểu dữ liệu  Các tham số có thể được dùng như một biến cục bộ trong hàm. 1. int cong(int x, int y) 2. { 3. return x + y; 4. } 1. float nhan(int x, int y) 2. { 3. return x * y; 4. } 1. void in(char line[]) 2. { 3. printf("%s",line); 4. } Ngô Hữu Dũng Giá trị trả về Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201736  Hàm return trả về giá trị cho hàm  Đồng thời kết thúc hàm  Cú pháp: return ;  Kiểu dữ liệu của phải trùng với kiểu trả về của hàm.  Hàm void không có giá trị trả về  Không dùng lệnh return (Ví dụ 3) 1. int cong(int x, int y) 2. { 3. return x + y; 4. } 1. float nhan(int x, int y) 2. { 3. return x * y; 4. } 1. void in(char line[]) 2. { 3. printf("%s",line); 4. } Ngô Hữu Dũng Khai báo prototype Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201737  Prototype: Khai báo các hàm dùng trong chương trình  Kiểu trả về  Tên hàm  Danh sách tham số (nếu có)  Dấu chấm phẩy ;  Đầu chương trình hoặc trong file header (*.h) 1. int cong(int x, int y) 2. { 3. return x + y; 4. } 1. float nhan(int x, int y) 2. { 3. return x * y; 4. } 1. void in(char line[]) 2. { 3. printf("%s",line); 4. } 1. int cong(int, int); 2. float nhan(int, int); 3. void in(char); Ngô Hữu Dũng Gọi hàm Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201738  Lệnh gọi hàm  Tên hàm  Danh sách tham số (nếu có)  Theo thứ tự  Cùng kiểu dữ liệu  Hàm có thể trả về một giá trị có kiểu của kiểu trả về của hàm. 1. #include 2. int cong(int, int); 3. void main() 4. { 5. int a = 5, b, c; 6. b = cong(a, 3); 7. c = b + cong(a,b); 8. printf("Tong: %d", c); 9. } 10. int cong(int x, int y) 11. { 12. return x + y; 13. } Ngô Hữu Dũng Phạm vi của biến (1) 39 1. #include 2. float b = 9; // Biến toàn cục 3. void half(float a) 4. { 5. a = a / 2; // Biến cục bộ trong hàm half 6. b = b / 2; // Biến toàn cục 7. printf("a = %f, b = %f\n", a, b); 8. } 9. void main() 10. { 11. float a = 15; // Biến cục bộ 12. half(a); // Gọi hàm half 13. printf("a = %f, b = %f\n", a, b); 14. } Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng Phạm vi của biến (2) 40 1. #include 2. float x = 5, y = 6; // Biến toàn cục 3. void nhandoi(float x) 4. { 5. x = x * 2; // Biến cục bộ 6. y = y * 2; // Biến toàn cục 7. printf("x = %f, y = %f\n", x, y); 8. } 9. void main() 10. { 11. float y = 7; // Biến cục bộ 12. nhandoi(x); // Gọi hàm nhandoi 13. printf("x = %f, y = %f\n", x, y); 14. } Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng Phạm vi của biến (3) 41 1. #include 2. void main() 3. { 4. int x = 5; // Phạm vi hàm main 5. if (x) 6. { 7. int x = 10; // Phạm vi lệnh if 8. x++; 9. printf("x = %d\n",x); 10. } 11. x++; 12. printf("x = %d\n",x); 13. } Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng Ví dụ - Số nguyên tố Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201742 1. int ngto(int a) 2. { 3. int i; 4. for (i=2;i<a;i++) 5. if (a%i==0) return 0; 6. return 1; 7. }  Các thành phần của hàm?  ?  ?  ?  ?  Ý nghĩa của hàm và các câu lệnh?  ?  ?  ? Ngô Hữu Dũng Ví dụ - Số nguyên tố (tt) Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201743 1. #include 2. int ngto(int a) // Hàm kiểm tra số nguyên tố 3. { 4. int i; 5. for (i=2;i<a;i++) // Duyệt các số nhỏ hơn a 6. if (a%i==0) return 0; // Nếu chia chẵn 7. return 1; // Không có giá trị nào chia chẵn 8. } 9. void main() 10. { 11. int n; printf("Nhap n: "); scanf("%d",&n); 12. if (ngto(n)) // Nếu ngto(n) khác zero 13. printf("%d la so nguyen to.",n); 14. else // Nếu ngto(n) bằng zero 15. printf("%d khong phai la so nguyen to.",n); 16. } Ngô Hữu Dũng Ví dụ - Sắp xếp chọn 44 1. void selectionsort(int a[], int n) 2. { 3. int i, j, min; 4. for (i = 0; i<=n-1; i++) 5. { 6. min = i; 7. for (j = i+1; j <= n-1; j++) 8. if (a[j] < a[min]) 9. min = j; 10. hoanvi(&a[i], &a[min]); 11. } 12. } Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng Ví dụ - Sắp xếp nổi bọt 45 1. void bubblesort(int a[], int n) 2. { 3. int i,j; 4. for (i=0;i<=n-1;i++) 5. { 6. for (j=0;j<=n-2-i;j++) 7. { 8. if (a[j]>a[j+1]) 9. swap(a[j], a[j+1]); 10. } 11. } 12. } Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng Ví dụ - Sắp xếp chèn 46 1. void insertionsort(int a[], int n) 2. { 3. int i,j, value; 4. for (i=1; i<n, i++) 5. { 6. value = a[i]; 7. for (j=i; j>0 && value <a[j-1]; j--) 8. { 9. a[j] = a[j-1]; 10. } 11. a[j]= value; 12. } 13. } Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng Ví dụ - Tìm kiếm tuần tự 47 1. int search (int a[], int n, int key) 2. { 3. int i; 4. for (i=0; i<n; i++) 5. { 6. if (a[i] == key) 7. return i; 8. } 9. return -1; 10. } Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng Ví dụ - Tìm kiếm nhị phân 48 1. int bsearch(int a[], int low, int high, int key) 2. { 3. int mid; 4. if (low > high) 5. return -1; 6. mid = (low + high)/2; 7. if (key == a[mid]) 8. return mid; 9. else if (key < a[mid]) 10. return bsearch(a, low, mid-1, key); 11. else 12. return bsearch(a, mid+1, high, key); 13. } Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng Quy nạp toán học Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201749  Chứng minh hàm F(n) đúng với mọi số tự nhiên n ≥ N0.  Phương pháp quy nạp:  Bước cơ sở: Chỉ ra trường hợp ban đầu F(N0) đúng  Bước quy nạp: Chứng minh rằng giả sử F(k) đúng thì F(k+1) đúng.  Ví dụ: Chứng minh S(n): 1 + 3 + 5 + 7 + + (2n-1) = n2 (*), với n ≥ 1  Bước cơ sở: Trường hợp n = 1, (2n-1) = n2 = 1 là đúng hiển nhiên.  Bước quy nạp: Giả sử S(k) đúng, ta có 1 + 3 + 5 + ... + (2k – 1) = k2  Khi đó S(k+1): 1 + 3 + 5 + ... + (2k – 1) + [2(k+1) – 1] = k2 + (2k + 1) = (k + 1)2  Vậy S(k + 1) đúng S(n) đúng với mọi n ≥ 1. Ngô Hữu Dũng Lập trình đệ quy Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201750  Lập trình tính S(n) = 1 + 3 + 5 + + (2n – 1) = n2 với n bất kỳ, n ≥ 1.  Từ bài toán quy nạp ta có:  Bước cơ sở: S(1) = 1  Bước quy nạp: S(k+1) = S(k) + [2(k + 1) – 1]  Phương pháp lập trình đệ quy:  Phần cơ sở: S(1) = 1  Phần đệ quy: S(n) = S(n – 1) + (2n – 1)  Áp dụng vào lập trình: 1. int S(int n) 2. { 3. if (n==1) return 1; 4. else return S(n-1) + (2*n – 1); 5. } Ngô Hữu Dũng Hàm đệ quy Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201751  Là hàm có phép gọi lại chính nó  Áp dụng cho những bài toán có tính chất quy nạp  Gồm hai phần cơ bản  Phần cơ sở: Trường hợp ban đầu, hiển nhiên.  Phần đệ quy: Có phép gọi lại hàm. 1. int S(int n) 2. { 3. if (n==1) return 1; 4. else return S(n-1) + (2*n – 1); 5. } Ngô Hữu Dũng Hoạt động? Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201752  Giả sử n = 5, hàm đệ quy chạy như sau: S(5) = S(4) + 9 // Gọi hàm S(4) S(4) = S(3) + 7 // Gọi hàm S(3) S(3) = S(2) + 5 // Gọi hàm S(2) S(2) = S(1) + 3 // Gọi hàm S(1) S(1) = 1 // Return S(1) S(2) = 1 + 3 // Return S(2) S(3) = 1 + 3 + 5 // Return S(3) S(4) = 1 + 3 + 5 + 7 // Return S(4) S(5) = 1 + 3 + 5 + 7 + 9 = 25 // Return S(5) 1. int S(int n) 2. { 3. if (n==1) return 1; 4. else return S(n-1) + (2*n – 1); 5. } Ngô Hữu Dũng Ví dụ vận dụng – Lũy thừa Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201753 Exponent Ngô Hữu Dũng Ví dụ vận dụng – Lũy thừa (tt) Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201754  Viết hàm đệ quy tính E(n) = an với a  R, a ≠ 0, n  N và n ≥ 0.  Phép quy nạp  Bước cơ sở: E(0) = a0 = 1  Bước quy nạp: E(k+1) = a x E(k)  Hàm đệ quy:  Phần cơ sở: E(0) = 1  Phần đệ quy: E(n) = a x E(n-1)  Hoạt động:  Giả sử a = 2, n = 4 1. float E(float a, int n) 2. { 3. if (n==0) return 1; 4. else return a * E(a,n-1); 5. } E(4) = 2*E(3) E(3) = 2*E(2) E(2) = 2*E(1) E(1) = 2*E(0) E(0) = 1 E(1) = 2 E(2) = 2*2 E(3) = 2*2*2 E(4) = 2*2*2*2 = 24 Ngô Hữu Dũng Ví dụ vận dụng – Giai thừa Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201755  Viết hàm đệ quy tính F(n) = 1 x 2 x 3 x x n = n!  Phép quy nạp  Bước cơ sở: ???  Bước quy nạp: ???  Chứng minh: ???  Hàm đệ quy  Phần cơ sở: ???  Phần đệ quy: ???  Hoạt động: ??? Ngô Hữu Dũng Ví dụ vận dụng – Giai thừa (tt) Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201756  Viết hàm đệ quy tính F(n) = 1 x 2 x 3 x x n = n!  Phép quy nạp  Bước cơ sở: F(1) = 1  Bước quy nạp: F(k+1) = (k+1) x F(k)  Chứng minh:  Giả sử F(k) = k!  Ta có F(k+1) = (k+1) x k! = (k+1)! (Đúng!)  Hàm đệ quy  Phần cơ sở: F(1) = 1  Phần đệ quy: F(n) = n * F(n-1)  Hoạt động: Cho n = 4 1. int F(int n) 2. { 3. if (n==1) return 1; 4. else return n * F(n-1); 5. } F(4) = 4*F(3) F(3) = 3*F(2) F(2) = 2*F(1) F(1) = 1 E(2) = 2*1 E(3) = 3*2*1 E(4) = 4*3*2*1 = 16 Ngô Hữu Dũng Ví dụ vận dụng – Dãy số Fibonacci Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201757  Viết hàm đệ quy tính Fib(n) là phần tử thứ n của dãy số Fibonacci  Dãy Fibonaci: 1 1 2 3 5 8 13 21 34 55  Tính chất: Số sau bằng tổng hai số liền trước nó.  Quy nạp  Fib(1) = 1, Fib(2) = 1  Fib(k) = Fib(k-1) + Fib(k-2)  Hàm đệ quy ?  Phần cơ sở: ?  Phần đệ quy: ? Ngô Hữu Dũng Ví dụ vận dụng – Dãy số Fibonacci (tt) Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201758 1. // Fibonacci: 1 1 2 3 5 8 13 21 34 55... 2. #include 3. int fib(int n) // Tìm số Fibonacci thứ n 4. { 5. if (n==1 || n==2) return 1; // Phần cơ sở 6. return fib(n-1) + fib(n-2); // Phần đệ quy 7. } 8. void main() 9. { 10. int n; 11. do{ // Nhập n>=1 12. scanf("%d",&n); 13. }while(n<1); 14. printf("Fibinaci(%d) = %d.", n, fib(n)); 15. } Ngô Hữu Dũng Bài toán Tháp Hanoi Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201759 Ngô Hữu Dũng Hết bài 2 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201760  Chương trình con  Ví dụ vận dụng chương trình con  Phép quy nạp  Giải thuật đệ quy  Ví dụ vận dụng giải thuật đệ quy Ngô Hữu Dũng