Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 4: Hàm con

42 trang hapham 1360

Download

Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 4: Hàm con", để 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:

bai_giang_cau_truc_du_lieu_va_giai_thuat_chuong_4_ham_con.pdf

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 4: Hàm con

4 / 3 / 2015 CHƯƠNG 4 HÀM CON 1 1
CẤU TRÚC CHƯƠNG TRÌNH Khai báo thư viện hàm Khai báo hàm Khai báo Khai báo hằng số Cài đặt tất cả những hàm con Cài đặt hàm đã được khai báo CHƯƠNG TRÌNH C TRÌNH CHƯƠNG Gọi thực hiện các hàm theo Hàm main() yêu cầu của bài toán 2
KHÁI NIỆM  Hàm là một đoạn chương trình độc lập thực hiện trọn vẹn một công việc nhất định sau đó trả về giá trị cho chương trình gọi nó, hay nói cách khác hàm là sự chia nhỏ của chương trình.  Mục đích sử dụng hàm:  Khi có một công việc giống nhau cần thực hiện ở nhiều vị trí.  Khi cần chia một chương trình lớn phức tạp thành các đơn thể nhỏ (hàm con) để chương trình được trong sáng, dễ hiểu trong việc xử lý, quản lý việc tính toán và giải quyết vấn đề. 3 3
Mẫu tổng quát của hàm TênHàm([ds các tham số]); Trong đó:  Kiểu dữ liệu trả về của hàm (kết quả của hàm/ đầu ra), gồm 2 loại – void: Không trả về giá trị – float / int / long / char */ kiểu cấu trúc / : Trả về giá trị kết quả có kiểu dữ liệu tương ứng với bài toán (chỉ trả về được 1 giá trị theo kiểu dữ liệu) 4
Ví dụ Tham số int Tong(int a, int b) { int s=a+b; return s; } void main() { Gọi hàm int kq = Tong (12, 3); Truyền đối số cout<<“Tong cua 12 va 3: “<<kq; } 5
 TênHàm: Đặt tên theo qui ước sao cho phản ánh đúng chức năng thực hiện của hàm  Danh sách các tham số (nếu có): đầu vào của hàm (trong một số trường hợp có thể là đầu vào và đầu ra của hàm nếu kết quả đầu ra có nhiều giá trị - Tham số này gọi là tham chiếu) 6
HÀM KHÔNG TRẢ VỀ GIÁ TRỊ Cài đặt void TênHàm([danh sách các tham số]) { Khai báo các biến cục bộ Các câu lệnh / khối lệnh hay lời gọi đến hàm khác. } Gọi hàm TênHàm(danh sách tên các đối số); Những phương thức loại này thường rơi vào những nhóm chức năng: Nhập / xuất dữ liệu , thống kê, sắp xếp, liệt kê 7
VÍ DỤ 1 Viết chương trình nhập số nguyên dương n và in ra màn hình các ước số của n Phân tích bài toán: Input: n (Để xác định tham số) Kiểu dữ liệu: số nguyên dương (int). Output: In ra các ước số của n (Để xác định kiểu dữ liệu trả về của hàm) Xuất ra màn hình Không trả về giá trị Kiểu dữ liệu của hàm là void . Xác định tên hàm: Hàm này dùng in ra các ước số của n nên có thể đặt là LietKeUocSo void LietKeUocSo(int n); 8
#include void LietKeUocSo(int n); Có dấu chấm phẩy void LietKeUocSo(int n) Không dấu chấm phẩy { for (int i = 1; i >n; cout<<"Cac uoc so cua “<<n<<“: “; LietKeUocSo(n); //gọi hàm } 9
Kết quả chương trình 10
HÀM TRẢ VỀ GIÁ TRỊ Cài đặt TênHàm([danh sách các tham số]) { kq; Khai báo các biến cục bộ Các câu lệnh / khối lệnh hay lời gọi đến hàm khác. return kq; } Gọi hàm Tên biến = TênHàm (danh sách tên các đối số); Những phương thức này thường rơi vào các nhóm: Tính tổng, tích, trung bình, đếm, kiểm tra, tìm kiếm 11
VÍ DỤ 2 Viết chương trình nhập số nguyên dương n và tính tổng Sn 1 2 3  n ;n 0  Phân tích bài toán: Input: n (Để xác định tham số)  Kiểu dữ liệu: số nguyên dương (int). Output: Tổng S (Để xác định kiểu dữ liệu phương thức)  Trả về giá trị của S.  S là tổng các số nguyên dương nên S cũng là số nguyên dương Kiểu trả về của hàm là int (hoặc long).  Xác định TênHàm: Dùng tính tổng S nên có thể đặt là TongS int TongS(int n); 12
#include int TongS(int n); int TongS(int n) { int kq = 0; for (int i = 1; i >n; S = TongS(n); //gọi hàm và gán kết quả cout<<"Tong tu 1 den n: " <<S; } 13
TẦM VỰC CỦA BIẾN Phạm vi khối Phạm vi hàm Phạm vi chương trình Phạm vi tập tin 14
PHẠM VI KHỐI Một khối được giới hạn bởi ngoặc {}. Biến khai báo trong khối đó có phạm vi khối, nghĩa là nó chỉ hoạt động trong khối đó mà thôi. Phạm vi này còn gọi là cục bộ, và biến đưọc gọi làbiến cục bộ. 15
PHẠM VI KHỐI (tt) void main() { int i=20; { int i=10; cout<<"Gia tri i ben trong khoi: "<<i<<endl; } cout<<"Gia tri i ben ngoai khoi: "<<i; } Kết quả Gia tri i ben trong khoi: 10 Gia tri i ben ngoai khoi: 20 16
PHẠM VI HÀM  Biến hoạt động từ đầu đến cuối một hàm, chỉ có tác dụng trong hàm void main() { int k; float m; double x; //Các lệnh khác // } 17
PHẠM VI CHƯƠNG TRÌNH  Biến được khai báo bên ngoài int a, b; các hàm – còn được gọi là void Nhap() biến toàn cục, có tác dụng cho { toàn bộ chương trình cout >a;  Biến toàn cục mặc dù được cout >b; toàn chương trình, nhưng } không nên khai báo sử dụng void main() { nhiều nếu không cần thiết, vì int c; nó sẽ gây trở ngại cho quá Nhap(); trình dò tìm lỗi khi debug c=a+b; chương trình cout<<"Tong = "<<c; } 18
PHẠM VI TẬP TIN  Biến được khai báo toàn cục và có kèm từ khóa static int x = 0; static int y = 0; static float z = 0.0; void main() { int i; //Các lệnh . . } 19
THAM SỐ LÀ THAM CHIẾU Tham số làm kết quả đầu ra Tham số vừa làm đầu vào và đầu ra Dùng dấu & phía trước tên tham số khi cài đặt hàm 20
VÍ DỤ Xét chương trình hoán vị 2 số nguyên a, b cho trước Viết chương trình với 2 trường hợp  Trường hợp không dùng tham chiếu  Trường hợp dùng tham chiếu 21
void HoanVi(int a, int b) TRƯỜNG HỢP 1 { int tam = a; a = b; b = tam; cout<<"Trong HoanVi: a = “<<a<<“ ;b = “<<b; } void main() { int a = 5, b = 21; cout<<"Truoc khi HoanVi: a = “<<a<<“ ; b = “<<b; HoanVi(a, b); cout<<"Sau khi goi HoanVi: a = “<<a<<“ ;b = “<<b; } 22
Kết quả 23
TRƯỜNG HỢP 2 void HoanVi(int &a, int &b) { int tam = a; a = b; b = tam; cout<<"Trong HoanVi: a = “<<a<<“ ;b = “<<b; } void main() { int a = 5, b = 21; cout<<"Truoc khi HoanVi: a = “<<a<<“ ; b = “<<b; HoanVi(a, b); cout<<"Sau khi goi HoanVi: a = “<<a<<“ ;b = “<<b; } 24
Kết quả 25
NGUYÊN TẮC XÂY DỰNG HÀM Trước khi xây dựng hàm phải trả lời những câu hỏi sau:  Hàm trả về gì? Xác định kiểu dữ liệu trả về của hàm  Hàm làm gì? Xác định tên hàm  Cần những thông tin gì để hàm xử lý? Xác định tham số Ứng với mỗi thông tin đã xác định, xác định xem đã có giá trị trước khi vào hàm chưa, - Nếu chưa có Biến ở dạng tham chiếu (dùng để nhập giá trị trong hàm) - Nếu có mà sau khi thực hiện xong hàm vẫn không thay đổi Biến ở dạng tham trị (không là tham chiếu) - Nếu có mà sau khi thực hiện xong hàm thì giá trị cũngbị thay đổi theo Biến ở dạng tham chiếu 26
GIỚI THIỆU HÀM ĐỆ QUI  Một hàm được gọi có tính đệ qui nếu trong thân của hàm đó có lệnh gọi lại chính nó một cách tường minh hay tiềm ẩn.  Phân loại đệ qui – Đệ qui tuyến tính. – Đệ qui nhị phân. – Đệ qui phi tuyến. – Đệ qui hỗ tương. 27
ĐỆ QUI TUYẾN TÍNH • Trong thân hàm có duy nhất một lời gọi hàm gọi lại chính nó một cách tường minh. TenHam ( ) { if (điều kiện dừng) { . . . //Trả về giá trị hay kết thúc công việc } //Thực hiện một sốcông việc (nếu có) . . . TenHam ( ); //Thực hiện một sốcông việc (nếu có) } 28
Ví dụ: Tính S(n) 1 2 3  n - Điều kiện dừng: S(0) = 0. - Qui tắc (công thức) tính: S(n) = S(n-1) + n. long TongS (int n) { if(n==0) return 0; return ( TongS(n-1) + n ); } 29
ĐỆ QUI NHỊ PHÂN Trong thân của hàm cóhai lời gọi hàm gọi lại chính nómộ t cách tường minh. TenHam ( ) { if (điều kiện dừng) { . . . //Trả về giá trịhay kết thúc công việc } //Thực hiện một số công việc (nếu có) . . .TenHam ( ); //Giải quyết vấn đề nhỏ hơn //Thực hiện một số công việc (nếu có) . . . TenHam ( ); //Giải quyết vấn đề còn lại //Thực hiện một số công việc (nếu có) } 30
Ví dụ: Tính số hạng thứ n của dãy Fibonaci được định nghĩa như sau: f1 = f0 =1 ; fn = fn-1 + fn-2 ; (n>1) Đ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); } 31
ĐỆ QUI PHI TUYẾN Trong thân của hàm có lời gọi hàm gọi lại chính nó được đặt bên trong vòng lặp. TenHam ( ) { for (int i = 1; i ); } } } 32
Ví dụ: Tính số hạng thứn của dãy {Xn} được định nghĩa như sau: X0 =1 ; 2 2 2 2 Xn = n X0 + (n-1) X1 + + (n-i) Xi + + 1 Xn-1 ; (n≥1) Điều kiện dừng:X(0) = 1. Phân tích : Với n = 3, biểu thức có dạng: 2 2 2 X3 = 3 X0 + 2 X1 + 1 X2; 2 2 X2 = 2 X0 + 1 X1; 2 X1 = 1 X0; X0 = 1; Kết quả : X3 = 18 33
long TinhXn (int n) { if(n==0) return 1; long s = 0; for (int i=1; i<=n; i++) s = s + i * i * TinhXn(n-i); return s; } 34
ĐỆ QUI HỖ TƯƠNG Trong thân của hàm này có lời gọi hàm đến hàm kia và trong thân của hàm kia có lời gọi hàm tới hàm này. g() f() f() f() g() h() 35
TenHam2 ( ); TenHam1 ( ) { //Thực hiện một sốcông việc (nếu có) TenHam2 ( ); //Thực hiện một sốcông việc (nếu có) } TenHam2 ( ) { //Thực hiện một sốcông việc (nếu có) TenHam1 ( ); //Thực hiện một sốcông việc (nếu có) } 36
Ví dụ: Tính số hạng thứ n của hai dãy {Xn}, {Yn} được định nghĩa như sau: X0 =Y0 =1 ; Xn = Xn-1 + Yn-1; (n>0) 2 Yn = n Xn-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); } 37
CÁCH HOẠT ĐỘNG HÀM ĐỆ QUI  Ví dụ tính n! với n=5 main() GiaiThua(5) GiaiThua(4) GiaiThua(3) GiaiThua(2) GiaiThua(1) 5 4 3 2 1 n 5 n 5 n 4 n 3 n 2 n 1 120 24 6 2 1 int giaithua(int n) { `if(n<=1) return 1; return giaithua(n-1)*n; } 38
BÀI TẬP 1 Xác định các khai báo hàm của các bài toán sau: 1.Viết chương trình tính diện tích và chu vi của hình chữ nhật với chiều dài và chiều rộng được nhập từ bàn phím. 2.Viết chương trình tính diện tích và chu vi hình tròn với bán kính được nhập từ bàn phím. 3.Nhập vào 3 số thực a, b, c và kiểm tra xem chúng có thành lập thành 3 cạnh của một tam giác hay không? Nếu có hãy tính diện tích, chiều dài mỗi đường cao của tam giác và in kết quả ra màn hình. 4.Viết chương trình nhập 2 số nguyên dương a, b. Tìm USCLN và BSCNN của hai số nguyên đó 39
BÀI TẬP 1 (tt) –Công thức tính diện tích s = sqrt(p*(p-a)*(p-b)*(p-c) ) với p là nửa chu vi của tam giác –Công thức tính các đường cao: ha = 2s/a, hb=2s/b, hc=2s/c. 40
BÀI TẬP 2 1. Viết chương trình tất cả các bài tập 1 2. Viết chương trình nhập số nguyên dương n, tính tổng các ước số dương của n. Ví dụ: Nhập n=6 Tổng các ước số từ 1 đến n: 1+2+3+6=12. 3. Nhập vào giờ, phút, giây. Kiểm tra xem giờ, phút, giây đó có hợp lệ hay không? In kết quả ra màn hình. 4. Viết chương trình nhập số nguyên dương n gồm k chữ số, đếm xem n có bao nhiêu chữ số là số nguyên tố. 41
5. Viết chương trình tính tiền thuê máy dịch vụ Internet và in ra màn hình kết quả. Với dữ liệu nhập vào là giờ bắt đầu thuê (GBD), giờ kết thúc thuê (GKT), số máy thuê (SoMay).  Điều kiện cho dữ liệu nhập: 6<=GBD<GKT<=21. Giờ là số nguyên.  Đơn giá: 2500đ cho mỗi giờ máy trước 17:30 và 3000đ cho mỗi giờ máy sau 17:30. 6. Viết chương trình tính tiền lương ngày cho công nhân, cho biết trước giờ vào ca, giờ ra ca của mỗi người. Giả sử rằng:  Tiền trả cho mỗi giờ trước 12 giờ là 6000đ và sau 12 giờ là 7500đ.  Giờ vào ca sớm nhất là 6 giờ sáng và giờ ra ca trễ nhất là 18 giờ (Giả sử giờ nhập vào nguyên). 42