Bài giảng Tin học đại cương - Bài 5: Mảng - Nguyễn Thanh Hùng

1TIN HỌC ĐẠI CƯƠNGPHẦN 2: LẬP TRÌNH BẰNG NGÔN NGỮ CBÀI 5: HÀMVIỆN CÔNG NGHỆ THÔNG TINSCHOOL OF INFORMATION COMMUNICATION TECHNOLOGY Ts. Nguyễn Thanh Hùng2BÀI 5: HÀM5.1. Khái niệm hàm5.2. Khai báo và sử dụng hàm5.3. Phạm vi biến5.4. Nguyên mẫu hàm5.5. Hàm đệ qui35.1. Khái niệm hàmCòn được gọi là chương trình conNhững đoạn chương trình lặp đi lặp lại nhiều lần ở những chỗ khác nhau: Viết thành hàm để khi cần chỉ cần gọi ra chứ không phải viết lại toàn bộ.Ví dụ:Các hàm toán học: sin(x), pow(x,y), sqrt(x),...Các hàm do người dùng viết ra.45.1. Khái niệm hàmGiải quyết một bài toán lớn thì chương trình của ta có thể rất lớn và dài  Chia thành các công việc nhỏ hơn được viết thành các hàm  Dễ viết, kiểm tra và sửa lỗi.Việc chia nhỏ một chương trình thành các chương trình con đảm nhận những công việc nhỏ khác nhau chính là tư tưởng chính cho phương pháp lập trình cấu trúc (structured programming). 5BÀI 5: HÀM5.1. Khái niệm hàm5.2. Khai báo và sử dụng hàm5.3. Phạm vi biến5.4. Nguyên mẫu hàm5.5. Hàm đệ qui65.2.1. Khai báo hàmCú pháp:[kieu_gia_tri_tra_ve] ([danh_sach_tham_so,]){//Than ham` bao gom://Cac khai bao...//Cac cau lenh}75.2.1. Khai báo hàm (tiếp)Ví dụ:long giai_thua(int a){ long ket_qua; int i; ket_qua = 1; for(i = 1;i#include int max(int x, int y, int z){ int max; max = x>y?x:y; max = max>z?max:z; return max;}void main(){ int a,b,c; clrscr(); printf("\n Nhap gia tri cho 3 so nguyen a, b, c: "); scanf("%d %d %d",&a,&b,&c); printf("\n Gia tri cac so vua nhap: "); printf(" a = %-5d b = %-5d c = %-5d“, a, b, c); printf("\n Gia tri lon nhat trong 3 so la %d",max(a,b,c)); getch();} 15Lưu ýTrong chương trình, khi gặp một lời gọi hàm thì hàm bắt đầu thực hiện bằng cách chuyển các lệnh thi hành đến hàm được gọi. Quá trình diễn ra như sau: Nếu hàm có tham số, trước tiên các tham số sẽ được gán giá trị thực tương ứng. Chương trình sẽ thực hiện tiếp các câu lệnh trong thân hàm bắt đầu từ lệnh đầu tiên đến câu lệnh cuối cùng.Khi gặp lệnh return hoặc dấu } cuối cùng trong thân hàm, chương trình sẽ thoát khỏi hàm để trở về chương trình gọi nó và thực hiện tiếp tục những câu lệnh của chương trình này.16#include #define KT 1000int nhap_so_pt(){ int n; do { printf("Nhap vao so phan tu cua mang: "); scanf("%d", &n); if (n KT) printf("Nhap sai\n"); } while (n KT); return n;}void hien_thi_mang(int *a, int n){ int i; for (i = 0; i #define KT 1000void nhap_mang(int *a, int *n){ int i; do { printf("Nhap so phan tu cua mang: "); scanf("%d", n); if (*n KT) printf("Nhap sai\n"); } while (*n KT); for (i = 0; i void main(){ { int a = 1; printf(“\n a = %d”,a); { int a = 2; printf(“\n a = %d”,a); } printf(“\n a = %d”,a); } { int a = 3; printf(“\n a = %d”,a); } getch();} 29Ví dụ 2#include #include int a, b, c;int tich(){ printf("\n Gia tri cac bien tong the a, b, c: "); printf(" a = %-5d b = %-5d c = %-5d“, a, b, c); return a*b*c;}void main(){ clrscr(); printf("\n Nhap gia tri cho 3 so nguyen a, b, c: "); scanf("%d %d %d",&a,&b,&c); printf("\n Tich cua 3 so la %d",tich()); getch();} 30Biến registerThanh ghi có tốc độ truy nhập nhanh hơn so với các loại bộ nhớ khác (RAM, bộ nhớ ngoài).Nếu một biến thường xuyên sử dụng được lưu vào trong thanh ghi thì tốc độ thực hiện của chương trình sẽ được tăng lên.Để làm điều này ta đặt từ khóa register trước khai báo của biến đó. Ví dụ: register int a;Số lượng và kích thước các thanh ghi có hạn  Số lượng biến khai báo register sẽ không nhiều và thường chỉ áp dụng với những biến có kích thước nhỏ như kiểu char, int. 31Biến staticMột biến cục bộ khi ra khỏi phạm vi của biến đó thì bộ nhớ dành để lưu trữ biến đó sẽ được giải phóng.Nếu cần lưu giá trị của các biến cục bộ này, cần khai báo biến với từ khóa static.Ví dụ: static int a;Biến static là biến tĩnh, nghĩa là nó sẽ được cấp phát một vùng nhớ thường xuyên từ lúc khai báo và chỉ giải phóng khi chương trình chính kết thúc.32Ví dụ# include # include void fct(){ static int count = 1; printf("\n Lan goi ham fct lan thu %2d",count++);}void main(){ int i; for(i=0; i#include int max(int, int, int); // khai bao nguyen mau hamvoid main(){ int a,b,c; clrscr(); printf("\n Nhap gia tri cho 3 so nguyen a, b, c: "); scanf("%d %d %d", &a, &b, &c); printf("\n Gia tri cac so vua nhap: "); printf(" a = %-5d b = %-5d c = %-5d“,a,b,c); printf("\n Gia tri lon nhat trong 3 so la %d",max(a,b,c)); getch();}int max(int x, int y, int z){ int max; max = x>y?x:y; max = max>z?max:z; return max;} 35Nguyên mẫu hàmNếu muốn đặt phần khai báo hàm nằm sau hàm main()  Cần khai báo nguyên mẫu của hàmĐể báo cho chương trình dịch biết có một hàm có dòng đầu hàm giống như trong phần nguyên mẫu này.Chương trình dịch có thể kiểm tra được là các lời gọi hàm trong chương trình chính có đúng hay khôngCó phù hợp về kiểu dữ liệu trả về hay khôngCác tham số thực có kiểu dữ liệu có phù hợp với kiểu dữ liệu đã khai báo hay không.Trong hàm nguyên mẫu có thể không cần nêu tên các tham số hình thức, nhưng trong phần khai báo hàm ta cần phải có các tham số hình thức. 36BÀI 5: HÀM5.1. Khái niệm hàm5.2. Khai báo và sử dụng hàm5.3. Phạm vi biến5.4. Nguyên mẫu hàm5.5. Hàm đệ qui375.5. Hàm đệ quy Khái niệm hàm đệ quy Hàm tự gọi chính mìnhKhi xây dựng hàm đệ quy cần:Xây dựng trường hợp cơ bảnNguyên lý đưa trường hợp tổng quát về trường hợp cơ bảnĐảm bảo tính dừng của giải thuật đệ quy - chắc chắn từ trường hợp tổng quát sẽ đến được trường hợp cơ bản385.5. Hàm đệ quy Ví dụ điển hình: tính giai thừa6! = 6 * 5 * 4 * 3 * 2 * 1Nguyên lý: 6! = 6 * 5!5! = 5 * 4! ...Kết luận là có thể tính giai thừa theo phương pháp đệ quyTrường hợp cơ bản: (1! = 0! = 1) được định nghĩa2! = 2 * 1! = 2 * 1 = 2;3! = 3 * 2! = 3 * 2 = 6;395.5. Hàm đệ quy (factorial 6)(6 * (factorial 5))(6 * (5 * (factorial 4)))(6 * (5 * (4 * (factorial 3))))(6 * (5 * (4 * (3 * (factorial 2)))))(6 * (5 * (4 * (3 * (2 * (factorial 1))))))(6 * (5 * (4 * (3 * (2 * 1)))))(6 * (5 * (4 * (3 * 2))))(6 * (5 * (4 * 6)))(6 * (5 * 24))(6 * 120)72040Ví dụ hàm đệ quy: tính giai thừa#include long factorial(long number);// khai bao kieu mau hamvoid main(){ int i; for (i = 0; i giá trị của phần tử đầu tiên và nhỏ hơn giá trị của phần tử trong mảng:So sánh phần tử giữa mảng với giá trị cần tìmNếu bằng, tìm thấy và kết thúcNếu giá trị cần tìm giá trị giữa, tìm trong nửa sau của mảngLặp lại cho tới khi tìm thấy hoặc đã duyệt qua hết các nửaMỗi lần như vậy ta loại bỏ được một nửa số phần tử đang xét - tìm kiếm nhị phân Giải thuật này sẽ thực hiện tìm kiếm rất nhanh44#include #define KT 20void main(){ int ds[KT] = {1, 4, 8, 9, 18, 27, 38, 49, 55, 59, 67,68, 69, 72, 75, 79, 87, 88, 97, 98}; int cs_min, cs_max; /* Bien luu chi so cua ptu dau va ptu cuoi trong mang */ int gtri_tim; // gia tri can tim kiem int cs; // chi so scanf( “Nhap gia tri can tim: %d”, & gtri_tim); minindex = 0; // Chi so cua phan tu dau tien maxindex = KT-1; // Chi so cua phan tu cuoi cung45 while (cs_min ds[cs]) // Khoang sau { cs_min = cs + 1; } else{ cs_max = cs - 1; } //Khoang truoc } if (cs_min == cs_max){ printf(“Chi so cua phan tu can tim la:%d”, cs); }}46Câu hỏi?