›
›

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

pdf 30 trang ngocly 2730
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Kỹ thuật lập trình - Bài 2: Chương trình con và đệ quy - Ngô Hữu Dũng", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_ky_thuat_lap_trinh_bai_2_chuong_trinh_con_va_de_qu.pdf

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

  1. Kỹ thuật lập trình Bài 2 – Chương trình con và đệ quy Ngô Hữu Dũng 31 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
  2. Chương trình con 1. #include 2. int cong(int,int); // Khai báo prototype 3. void main() 4. { Input 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)); FUNCTION 9. } 10. int cong(int x, int y) // Hàm chi tiết 11. { 12. return x + y; Output 13. } 32 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
  3. Thành phần Main()  Kiểu trả về của hàm Function1()  Tên hàm  Tham số  Tham biến  Tham trị Function3()  Lệnh return trả về giá trị cho hàm Function2()  Khai báo prototype  Gọi hàm  Phạm vi của biến Function4() Return-type function-name(argument declarations) { declarations and statements } 33 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
  4. Kiểu trả về của hàm 1. int cong(int x, int y)  Hàm có thể trả về một giá trị 2. {  int 3. return x + y;  float 4. }  char  1. float nhan(int x, int y)  void: Không trả về giá trị 2. { 3. return x * y; 4. }  Khi kết thúc, hàm sẽ mang một giá trị trừ trường hợp hàm mang kiểu 1. void in(char line[]) void. 2. { 3. printf("%s",line); 4. } 34 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
  5. Tên hàm và tham số 1. int cong(int x, int y)  Tên hàm do người lập trình đặt 2. {  Không được trùng với từ khóa 3. return x + y;  Các ký tự liên tiếp nhau 4. }  Gồm ký tự, số, dấu gạch chân  Không gồm các ký tự đặc biệt 1. float nhan(int x, int y)  Có nghĩa, dễ hiểu 2. {  Tham số (đối số) 3. return x * y;  Một, nhiều hoặc không có tham số 4. }  Mỗi tham số đều có kiểu dữ liệu 1. void in(char line[])  Các tham số có thể được dùng như 2. { một biến cục bộ trong hàm. 3. printf("%s",line); 4. } 35 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
  6. Giá trị trả về 1. int cong(int x, int y)  Hàm return trả về giá trị cho hàm 2. {  Đồng thời kết thúc hàm 3. return x + y; 4. }  Cú pháp: return ; 1. float nhan(int x, int y) 2. {  Kiểu dữ liệu của phải 3. return x * y; trùng với kiểu trả về của hàm. 4. } 1. void in(char line[])  Hàm void không có giá trị trả về 2. {  Không dùng lệnh return (Ví dụ 3) 3. printf("%s",line); 4. } 36 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
  7. Khai báo prototype 1. int cong(int x, int y) 1. int cong(int, int); 2. { 2. float nhan(int, int); 3. return x + y; 3. void in(char); 4. } 1. float nhan(int x, int y)  Prototype: Khai báo các hàm dùng trong chương trình 2. {  Kiểu trả về 3. return x * y;  Tên hàm 4. }  Danh sách tham số (nếu có) 1. void in(char line[])  Dấu chấm phẩy ; 2. {  Đầu chương trình hoặc trong file 3. printf("%s",line); header (*.h) 4. } 37 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
  8. Gọi hàm  Lệnh gọi hàm 1. #include  Tên hàm 2. int cong(int, int);  Danh sách tham số (nếu có) 3. void main() 4. {  Theo thứ tự 5.  Cùng kiểu dữ liệu int a = 5, b, c; 6. b = cong(a, 3); 7. c = b + cong(a,b);  Hàm có thể trả về một giá trị có kiểu 8. printf("Tong: %d", c); của kiểu trả về của hàm. 9. } 10. int cong(int x, int y) 11. { 12. return x + y; 13. } 38 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
  9. Phạm vi của biến (1) 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. } 39 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
  10. Phạm vi của biến (2) 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. } 40 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
  11. Phạm vi của biến (3) 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. } 41 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
  12. Ví dụ - Số nguyên tố 1. int ngto(int a)  Các thành phần của hàm? 2. {  ? 3. int i;  ?  ? 4. for (i=2;i<a;i++)  ? 5. if (a%i==0) return 0;  Ý nghĩa của hàm và các câu 6. return 1; lệnh? 7. }  ?  ?  ? 42 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
  13. Ví dụ - Số nguyên tố (tt) 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. } 43 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
  14. Ví dụ - Sắp xếp chọn 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. } 44 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
  15. Ví dụ - Sắp xếp nổi bọt 1. void bubblesort(int a[], int n) 2. { 3. int i,j; 4. for (i=0;i a[j+1]) 9. swap(a[j], a[j+1]); 10. } 11. } 12. } 45 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
  16. Ví dụ - Sắp xếp chèn 1. void insertionsort(int a[], int n) 2. { 3. int i,j, value; 4. for (i=1; i 0 && value <a[j-1]; j ) 8. { 9. a[j] = a[j-1]; 10. } 11. a[j]= value; 12. } 13. } 46 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
  17. Ví dụ - Tìm kiếm tuần tự 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. } 47 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
  18. Ví dụ - Tìm kiếm nhị phân 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. } 48 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
  19. Quy nạp toán học  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. 49 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
  20. Lập trình đệ quy  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) 1. int S(int n) 2. {  Áp dụng vào lập trình: 3. if (n==1) return 1; 4. else return S(n-1) + (2*n – 1); 5. } 50 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
  21. Hàm đệ quy  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. } 51 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
  22. Hoạt động? 1. int S(int n)  Giả sử n = 5, hàm đệ quy chạy như sau: 2. { 3. if (n==1) return 1; S(5) = S(4) + 9 // Gọi hàm S(4) 4. else return S(n-1) + (2*n – 1); 5. } 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) 52 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
  23. Ví dụ vận dụng – Lũy thừa Exponent 53 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
  24. Ví dụ vận dụng – Lũy thừa (tt)  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 1. float E(float a, int n)  Bước cơ sở: E(0) = a0 = 1 2. {  Bước quy nạp: E(k+1) = a x E(k) 3. if (n==0) return 1; 4. else return a * E(a,n-1); 5. }  Hàm đệ quy: E(4) = 2*E(3)  Phần cơ sở: E(0) = 1 E(3) = 2*E(2)  Phần đệ quy: E(n) = a x E(n-1) E(2) = 2*E(1) E(1) = 2*E(0) E(0) = 1  Hoạt động: E(1) = 2 E(2) = 2*2  Giả sử a = 2, n = 4 E(3) = 2*2*2 E(4) = 2*2*2*2 = 24 54 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
  25. Ví dụ vận dụng – Giai thừa  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: ??? 55 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
  26. Ví dụ vận dụng – Giai thừa (tt)  Viết hàm đệ quy tính F(n) = 1 x 2 x 3 x x n = n!  Phép quy nạp 1. int F(int n)  Bước cơ sở: F(1) = 1 2. { 3.  Bước quy nạp: F(k+1) = (k+1) x F(k) if (n==1) return 1; 4. else return n * F(n-1);  Chứng minh: 5. }  Giả sử F(k) = k!  Ta có F(k+1) = (k+1) x k! = (k+1)! (Đúng!) F(4) = 4*F(3)  Hàm đệ quy F(3) = 3*F(2) F(2) = 2*F(1)  Phần cơ sở: F(1) = 1 F(1) = 1  Phần đệ quy: F(n) = n * F(n-1) E(2) = 2*1 E(3) = 3*2*1  Hoạt động: Cho n = 4 E(4) = 4*3*2*1 = 16 56 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
  27. Ví dụ vận dụng – Dãy số Fibonacci  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: ? 57 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
  28. Ví dụ vận dụng – Dãy số Fibonacci (tt) 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. } 58 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
  29. Bài toán Tháp Hanoi 59 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
  30. Hết bài 2  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 60 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng