Bài giảng Nhập môn lập trình - Bài 5: Hàm (Chương trình con)

Click to edit Master title style Click to edit Master text styles Second level Third level Fourth level Fifth level 31/01/2015 ‹#› 1 KỸ THUẬT LẬP TRÌNH Bài 5: HÀM ( CHƯƠNG TRÌNH CON ) 3 1. Cấu trúc và lý do sử dụng chương trình con 2. Tham số cho chương trình con 3. Chương trình đệ quy Một số bài toán đệ qui thông thường Truyền tham số cho chương trình: tham trị, tham biến 1.Cấu trúc hàm và lý do sử dụng hàm 1.1. Khái niệm Hàm là một khối lệnh thực hiện một công việc hoàn chỉnh (module), được đặt tên và được gọi thực thi nhiều lần tại nhiều vị trí trong chương trình. Hàm còn gọi là chương trình con (subroutine) 1.1. Khái niệm Hàm có thể được gọi từ chương trình chính (hàm main) hoặc từ 1 hàm khác. Hàm có giá trị trả về hoặc không. Nếu hàm không có giá trị trả về gọi là thủ tục (procedure) 1.1. Khái niệm Có hai lọai hàm: Hàm thư viện: là những hàm đã được xây dựng sẵn. Muốn sử dụng các hàm thư viện phải khai báo thư viện chứa nó trong phần khai báo #include. Hàm do người dùng định nghĩa. 1.2. Dạng tổng quát của hàm Dạng tổng quát của hàm do người dùng định nghĩa: returnType functionName(parameterList) { 	body of the function } Kiểu dữ liệu Tên hàm Tham số 1.2. Dạng tổng quát của hàm Gọi hàm Truyền đối số Tham số 1.2. Dạng tổng quát của hàm Vậy từ khóa return có tác dụng gì trong hàm? Khi một hàm muốn trả về một giá trị nào đó thì chúng ta dùng return . Bất kỳ kiểu dữ liệu nào của hàm cũng có thể sử dụng return NGOẠI TRỪ kiểu void Hàm có kiểu void đôi khi được gọi là Thủ Tục SAI 1.3. Gọi hàm Một hàm khi đã định nghĩa nhưng chúng vẫn chưa được thực thi, hàm chỉ được thực thi khi trong chương trình có một lời gọi đến hàm đó. Cú pháp gọi hàm: ([Danh sách các tham số]) 1.4. Nguyên tắc hoạt động của hàm void main() { 	int a, b, USC; 	cout>a>>b; 	USC = uscln(a,b); 	coutb) a-=b; 	else 	 b-=a; 	} 	return a;} 2. Tham số cho chương trình con 2.1. Tham số hình thức &tham số thực Khi hàm cần nhận đối số (arguments) để thực thi thì khi khai báo hàm cần khai báo danh sách các tham số để nhận giá trị từ chương trình gọi. Các tham số này được gọi là tham số hình thức. Ví dụ: 	int min(int a, int b) 	{ 	if(a// Khai báo thư viện iostream.h int max(int x, int y);// khai báo nguyên mẫu hàm max  void main()//hàm main (sẽ gọi các hàm thực hiện) { int a, b;// khai báo biến cout>a>>b; couty) ? x:y; } 3. Đệ qui Một hàm được gọi là đệ qui nếu một lệnh trong thân hàm gọi đến chính hàm đó. Đệ qui giúp giải quyết bài toán theo cách nghĩ thông thường một cách tự nhiên. Đệ qui phải xác định được điểm dừng. Nếu không xác định chính xác thì làm bài toán bị sai và có thể bị lặp vĩnh cửu (Stack Overhead) 3. Đệ qui Ví dụ: Định nghĩa giai thừa của một số nguyên dương n như sau: 5!=5*4! 4!=4*3! Tức là nếu ta biết được (n-1) giai thừa thì ta sẽ tính được n giai thừa, vì n!=n*(n-1)! Thấy n=0 hoặc n=1 thì giai thừa luôn = 1  chính là điểm dừng n!=1* 2 * 3 *…* (n-1) *n = (n-1)! *n (với 0!=1) 3. Đệ qui int giaiThua(int n) { if(n0) H10toH2(n/2); cout TenHam () { if (điều kiện dừng) { ... //Trả về giá trị hay kết thúc công việc } //Thực hiện một số công việc (nếu có) . . . TenHam (); //Thực hiện một số công việc (nếu có) } 3. Đệ qui tuyến tính Ví dụ: Tính S (n) = 1 + 2 + 3 + L + n - Điều kiện dừng: S(0) = 0. - Qui tắc (công thức) tính: S(n) = S(n-1) + n. long TongS (int n) { if(n==0) return 0; return ( TongS(n-1) + n ); } 3.2. Đệ qui nhị phân Trong thân của hàm có hai lời gọi hàm gọi lại chính nó một cách tường minh. TenHam () { 	if (điều kiện dừng) { ... //Trả về giá trị hay kết thúc công việc } //Thực hiện một số công việc (nếu có) . . .TenHam (); //Giải quyết vấn đề nhỏ hơn //Thực hiện một số công việc (nếu có) . . . TenHam (); //Giải quyết vấn đề còn lại //Thực hiện một số công việc (nếu có) } 3.2. Đệ qui nhị phân Ví dụ: Tính số hạng thứ n của dãy Fibonaci được định nghĩa như sau: f1 = f0 =1 ; fn = fn-1 + fn-2 ; Điều kiện dừng: f(0) = f(1) = 1.  long Fibonaci (int n) { if(n==0 || n==1) return 1; return Fibonaci(n-1) + Fibonaci(n-2); } (n>1) 3. 3. Đệ qui phi tuyến Trong thân của hàm có lời gọi hàm gọi lại chính nó được đặt bên trong vòng lặp. TenHam () { for (int i = 1; i); } } } 3. 3. Đệ qui phi tuyến Ví dụ: Tính số hạng thứ n của dãy {Xn} được định nghĩa như sau: X0 =1 ; Xn = n2X0 + (n-1)2X1 + … + 12Xn-1 ;  Điều kiện dừng:X(0) = 1.  long TinhXn (int n) { if(n==0) return 1; long s = 0; for (int i=1; i TenHam2 (); TenHam1 () { //Thực hiện một số công việc (nếu có) …TenHam2 (); //Thực hiện một số công việc (nếu có) } TenHam2 () { //Thực hiện một số công việc (nếu có) …TenHam1 (); //Thực hiện một số công việc (nếu có) } 3. 3. Đệ qui hỗ tương Ví dụ: Tính số hạng thứ n của hai dãy {Xn}, {Yn} được định nghĩa như sau: X0 =Y0 =1 ; Xn = Xn-1 + Yn-1;	(n>0) Yn = n2Xn-1 + Yn-1;	(n>0) - Điều kiện dừng:X(0) = Y(0) = 1. long TinhYn(int n); long TinhXn (int n) { if(n==0) return 1; return TinhXn(n-1) + TinhYn(n-1); } long TinhYn (int n) { if(n==0) return 1; return n*n*TinhXn(n-1) + TinhYn(n-1); } 3. 4. Cách hoạt động của hàm đệ qui Ví dụ tính n! với n=5