Kỹ thuật lập trình - Chương 5: Chương trình con (tiếp theo)

CHƯƠNG 5CHƯƠNG TRÌNH CON(TIẾP THEO)VI. PHẠM VI - THỜI GIAN SỐNG CỦA BIẾN (SCOPE & LIFE TIME)VII. HÀM ĐỆ QUIVI. PHẠM VI - THỜI GIAN SỐNG CỦA BIẾN (SCOPE & LIFE TIME)Định nghĩa phạm vi biến: Phạm vi của biến là phần chương trình trong đó việc tham khảo đến biến là hợp lệ. Gồm biến cục bộ và biến tòan cục.ĐN Thời gian sống của biến: Khi thực thi chương trình, biến được tạo ra và hủy đi. Thời gian sống là thời gian tồn tại của biến từ lúc được tạo ra đến lúc hủy đi. Thời gian sống phụ thuộc phạm vi và lớp lưu trữ.VI. PHẠM VI - THỜI GIAN SỐNG CỦA BIẾN (SCOPE & LIFE TIME)1. Biến tòan cục: Khai báo bên ngoài các hàm.Tự động khởi tạo giá trị 0 (không cho phép viết lệnh khai báo khởi tạo trị ).Có thời gian sống cùng với thời gian chạy chương trình. Nhắc lại: int n; //khai báo biến int a=5; //khai báo biến có khởi tạo trị. //không cho phép đ/v tòan cục VI. PHẠM VI - THỜI GIAN SỐNG CỦA BIẾN (SCOPE & LIFE TIME)2. Biến cục bộ:Khai báo bên trong hàm, trong khối lệnh.Không được tự động khởi tạo giá trị.Có phạm vi từ vị trí khai báo đến cuối hàm hoặc cuối khối lệnh. Thời gian sống từ lúc hàm được thực thi hoặc khối lệnh được thực thi đến lúc kết thúc hàm hoặc chạy xong khối lệnh. Xét ví dụ sau:int n1;void sub_fun();void main(){ int n2=2; int n3; coutint n1;void sub_fun();void main(){ int n1=10; cout#include void GiaiPhuongTrinh(float, float);void GiaiPhuongTrinh(float,float,float);void main(){ float m=2,n=3,p=-4; cout0) { cout#include void sub();void main(){ int i; for (i=0; i1) InDauSao(n-1); }VII. HÀM ĐỆ QUI2. Phân lọai: Đệ qui tuyến tính: Trong hàm chỉ có 1 lời gọi hàm đệ qui.Đệ qui phi tuyến: Có hơn 1 lời gọi hàm đệ qui. Đệ qui nhị phân là trường hợp đặc biệt của đệ qui phi tuyến. Đệ qui tương hỗ: Không đệ qui trực tiếp, không gọi lại chính mình. Ví dụ: A gọi B, B gọi C, C gọi AVII. HÀM ĐỆ QUI3. Sử dụng hàm đệ qui khi nào? Giải bài tóan có tính đệ qui giúp chương trình ngắn gọn.Là dạng tóan có thể qui về một bài tóan cùng dạng nhưng với số lượng phép tóan hay công việc giảm đi.Ví dụ:VII. HÀM ĐỆ QUI3. Sử dụng hàm đệ qui khi nào? Ví dụ: n! = n * (n-1)! USC(x,y)= USC(x-y,y) nếu x>y Số chữ số của x= 1 + số chữ số của x/10 fibonacci(n)=fibonacci(n-1)+fibonacci(n-2)VII. HÀM ĐỆ QUI4. Nguyên tắc viết hàm đệ qui: Hàm đệ qui cần thỏa 2 đk:Giải quyết được trong trường hợp riêng ứng với giá trị đặc biệt của tham số (tr/h suy biến).Trường hợp tổng quát, bài tóan được định nghĩa đệ qui với giá trị tham số thay đổi. Ví dụ: Tính n! Tổng quát: n!= n*(n-1)! Suy biến: Bằng 1 khi n=0||n=1VII. HÀM ĐỆ QUINhư vậy một hàm đệ qui sẽ có dạng ... hàmF (...) { if ( thông_số == trị_đặc_biệt ) return kết_quả; .... hàmF (...); .... }5. Quá trình thực thi hàm đệ qui:Ví dụ 1: Đếm số chữ số của một số nguyên n>0int DigitCount(int n){ if (n<10) return 1; else return 1+DigitCount(n/10);}Gọi hàm DigitCount(517) ta có quá trình thực thi sau:5. Quá trình thực thi hàm đệ qui:DigitCount(517)Thực thi DigitCount(517) Khởi tạo biến cục bộ và tham trị n=517{ if (n<10) //false return 1+DigitCount(51);}Thực thi DigitCount(51) Khởi tạo biến cục bộ và tham trị n=51{ if (n<10) //false return 1+ DigitCount(5);}Thực thi DigitCount(5) Khởi tạo biến cục bộ và tham trị n=5{ if (n<10) //true return 1;}1235. Quá trình thực thi hàm đệ qui:Ví dụ 2: Tìm ước số chung lớn nhất của 2 số nguyên dương.int USCLN(int u, int v){ if (v==0) return u; else return USCLN(v, u%v);}Gọi hàm USCLN(9,12) ta có quá trình thực thi sau:5. Quá trình thực thi hàm đệ qui:USCLN(9,6)Thực thi USCLN(9,6)Khởi tạo biến cục bộ và tham trị u=9, v=6{ if (v=0) //false return USCLN(6,3);}Thực thi USCLN(6,3) Khởi tạo biến cục bộ và tham trị u=6, v=3{ if (v==0) //false return USCLN(3,0);}Thực thi USCLN(3,0) Khởi tạo biến cục bộ và tham trị u=3, v=0{ if (v==0) //true return u;}33335. Quá trình thực thi hàm đệ qui:Kết luận:Mỗi lần gọi đệ qui tập các biến cục bộ, tham trị được tạo ra độc lập với tập các biến tạo ra cho lần gọi hàm trước.Mỗi lần thóat ra khỏi hàm của 1 lần gọi thì tập biến cục bộ tương ứng bị xóa.Lần gọi hàm sau cùng sẽ thóat ra đầu tiên.Hàm đệ qui thực thi cần nhiều không gian nhớ hơn hàm không đệ qui.6. Các ví dụ khácS= 1 + 2 + 3 + .... + nS= x + x3+ x5 + ... + x2n+1Tìm USCLN của 2 số bằng thuật tóan trừTính số Fibonacci thứ nBài tóan tháp hà nội