Phương pháp lập trình - Tổng quan - Ngô Hữu Dũng

Phương pháp lập trình Tổng quan TS. Ngô Hữu Dũng TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP THÀNH PHỐ HỒ CHÍ MINH Bài 1 – Giới thiệu Phương pháp lập trình - Tổng quan Blog ngohuudung.blogspot.com Email ngohuudung@iuh.edu.vn 2 Nội dung  Các thành phần cơ bản  Nhập xuất dữ liệu và các thư viện  Các câu lệnh có cấu trúc  Vòng lặp  Thuật toán  Hàm – chương trình con  Kiểu dữ liệu mảng và chuỗi  Giải thuật đệ quy  Kiểu dữ liệu cấu trúc  Kiểu con trỏ, tập tin Phương pháp lập trình - Tổng quan3 Tài liệu Phương pháp lập trình - Tổng quan  Brian W. Kernighan and Dennis M. Ritchie. The C Programming Language (Second Edition). Prentice-Hall. Englewood Cliffs, New Jersey, 1988.  Slide, bài giảng  Bài tập thực hành  Bản dịch tiếng Việt: Giáo trình Ngôn ngữ lập trình C  Tham khảo thêm  Phạm Văn Ất. Kỹ thuật lập trình C. NXB Khoa học và Kỹ thuật, 1995  Randal E.Bryant and David R.O’Hallaron. Computer’s Perspective, 2001  Bjarne Stroustrup. The C++ Programming Language, AT&T Labs Murray Hill, New Jersey Addison-Wesley, 1997.  Andy Oram and Greg Wilson, Beautiful Code, 2007  cplusplus.com 4 Lịch trình Phương pháp lập trình - Tổng quan Tuần Nội dung Lý thuyết Thực hành Kiểm tra Tự học 1 Giới thiệu môn học 3 6 2 Các thành phần cơ bản của Ngôn ngữ C 3 6 Nhập xuất dữ liệu và các thư viện 6 3 Các câu lệnh có cấu trúc 3 3 7.5 5-6 Vòng lặp – thuật toán 6 6 TK 15 7-8 Hàm – chương trình con 6 6 GK 15 9-10 Mảng và chuỗi 6 6 15 11 Lập trình đệ quy 3 3 7.5 12 Kiểu cấu trúc 3 3 7.5 13 Kiểu con trỏ 3 3 TK 7.5 14 Kiểu tập tin 3 6 15 Ôn tập 3 CK 6 45 30 105 5 Kiểm tra đánh giá Phương pháp lập trình - Tổng quan  Lý thuyết  Kiểm tra thường kỳ  Thi cuối kỳ  Thực hành  Kiểm tra thường kỳ  Thi giữa kỳ  Kiểm tra cuối kỳ  Điểm liệt: <3  Số tín chỉ: 4  Lý thuyết: 45  Thực hành: 30  Tự học: 105 6 Thảo luận Phương pháp lập trình - Tổng quan7  Why?  What?  How?  Where?  When? Giới thiệu về môn học qua một số ví dụ Phương pháp lập trình - Tổng quan8  Nhập, tính toán, xuất  Đề bài: Viết chương trình nhập vào hai số nguyên, xuất ra màn hình tổng của hai số nguyên đó.  Các bước chính để giải bài toán:  Xác định rõ yêu cầu của bài toán  Lựa chọn các biến và cấu trúc dữ liệu  Xây dựng giải thuật (cách giải) cho bài toán  Xây dựng trình tự để giải bài toán  Viết chương trình (cài đặt) và biên dịch  Chạy thử và sửa lỗi  Hoàn thiện và tối ưu hóa Các bước giải bài toán Phương pháp lập trình - Tổng quan9  Xác định yêu cầu  Nhập 2 số nguyên, tính tổng, xuất ra tổng.  Lựa chọn các biến  2 biến số nguyên  1 biến tổng kiểu số nguyên  Xây dựng thuật toán và trình tự  Khai báo các biến  Nhập vào 2 số nguyên  Tính tổng  Xuất kết quả Tính tổng hai số nguyên 1. #include //Khai báo thư viện 2. int main() //Chương trình chính 3. { 4. int x, y, tong; //Khai báo biến 5. printf("Nhap x: "); 6. scanf("%d", &x); //Nhập x 7. printf("Nhap y: "); 8. scanf("%d", &y); //Nhập y 9. tong = x + y; //Biểu thức 10. printf("Tong la %d \n", tong); // Xuất 11. return 0; //Kết thúc 12. } Phương pháp lập trình - Tổng quan10 Nhận xét Phương pháp lập trình - Tổng quan11  Khai báo thư viện: Chứa các hàm cần dùng  #include  #include  #include  Chương trình chính: Nơi chương trình bắt đầu int main() { (nội dung chương trình) return 0; }  Khai báo biến: Lưu trữ dữ liệu  Kiểu , ;  int x, y, tong, hieu, tich;  float thuong;// Biến kiểu số thực Nhận xét (2) Phương pháp lập trình - Tổng quan12  Nhập: Nhập từ bàn phím giá trị cho biến  scanf("", &);  scanf("%d", &x);  scanf("%f", &z);  Biểu thức: Phép gán, tính toán  = ;  tong = x + y; tich = x * y;  thuong = (float)x/y;  Xuất: Xuất ra màn hình dòng chữ, giá trị của biến  printf("", ,);  printf("Tong la %d \n", tong);  printf("Thuong la %f \n", thuong); Tính tổng, hiệu, tích, thương Phương pháp lập trình - Tổng quan13  Đề bài: Viết chương trình nhập vào hai số nguyên, xuất ra màn hình tổng, hiệu, tích và thương của của số nguyên đó.  Gợi ý: #include /*Khai báo thư viện*/ int main() //Chương trình chính { . . . // Khai báo biến . . . // Nhập . . . // Biểu thức, tính toán . . . // Xuất return 0; //Kết thúc } Tính tổng, hiệu, tích, thương (tham khảo 1) Phương pháp lập trình - Tổng quan14 1. #include /*Khai báo thư viện*/ 2. int main() //Chương trình chính 3. { 4. int x, y, tong, hieu, tich; 5. float thuong; //Khai báo 6. printf("Nhap so nguyen x: "); 7. scanf("%d", &x); //Nhập x 8. printf("Nhap so nguyen y: "); 9. scanf("%d", &y); //Nhập y 10. tong = x + y; //Biểu thức tính tổng 11. hieu = x - y; //Biểu thức tính hiệu 12. tich = x * y; //Biểu thức tính tích 13. thuong = (float)x / y; //Biểu thức tính thương 14. printf("Tong la %d \n", tong); // Xuất tổng 15. printf("Hieu la %d \n", hieu); // Xuất hiệu 16. printf("Tich la %d \n", tich); // Xuất tích 17. printf("Thuong la %f \n", thuong); // Xuất thương 18. return 0; //Kết thúc 19. } Tính tổng, hiệu, tích, thương (tham khảo 2) Phương pháp lập trình - Tổng quan15 1. #include //Khai báo thư viện 2. int main() //Chương trình chính 3. { 4. int x, y, tong, hieu, tich; //Khai báo 5. float thuong; 6. printf("Nhap vao hai so nguyen: "); 7. scanf("%d%d", &x, &y); //Nhập x, y 8. tong = x + y; hieu = x - y; //Biểu thức 9. tich = x * y; thuong = (float)x / y; 10. printf("%d + %d = %d \n", x, y, tong);// Xuất 11. printf("%d - %d = %d \n", x, y, hieu); 12. printf("%d * %d = %d \n", x, y, tich); 13. printf("%d / %d = %f \n", x, y, thuong); 14. return 0; //Kết thúc 15. } Hình chữ nhật Phương pháp lập trình - Tổng quan16  Đề bài: Viết chương trình nhập vào hai cạnh của hình chữ nhật, xuất ra màn hình diện tích và chu vi của hình chữ nhật.  Gợi ý:  Khai báo thư viện  Chương trình chính  Khai báo biến  Nhập  Biểu thức  Xuất  Kết thúc a b DT = ? CV = ? Hình tròn Phương pháp lập trình - Tổng quan17  Đề bài: Viết chương trình nhập vào bán kính hình tròn, xuất ra màn hình diện tích và chu vi hình tròn.  Gợi ý:  Kiểu biến?  Hằng số? rDT = ? CV = ? Hình tròn (tham khảo) 1. #include 2. int main() 3. { 4. float r; // Bán kính 5. float DT, CV; // Diện tích, chu vi 6. printf("Nhap ban kinh hinh tron: "); 7. scanf("%f", &r); 8. DT = 3.14 * r * r; 9. CV = 2 * 3.14 * r; 10. printf("Dien tich hinh tron: %f\n", DT); 11. printf("Chu vi hinh tron: %f", CV); 12. return 0; 13. } Phương pháp lập trình - Tổng quan18 Hằng số 1. #include 2. #define PI 3.14 // PI là hằng số 3. int main() 4. { 5. float r; // Bán kính 6. float DT, CV; // Diện tích, chu vi 7. printf("Nhap ban kinh hinh tron: "); 8. scanf("%f", &r); 9. DT = PI * r * r; 10. CV = 2 * PI * r; 11. printf("Dien tich hinh tron: %.2f\n", DT); 12. printf("Chu vi hinh tron: %.2f", CV); 13. return 0; 14. } Phương pháp lập trình - Tổng quan19 Khoảng cách Phương pháp lập trình - Tổng quan20  Đề bài: Viết chương trình nhập vào tọa độ của hai điểm A(xA, yA) và B(xB, yB), xuất ra màn hình khoảng cách giữa hai điểm.  Gợi ý:  Thư viện math.h?  Hàm sqrt tính căn bậc hai  Hàm pow tính lũy thừa A(xA, yA) B(xB, yB) Khoảng cách (tham khảo) 1. #include 2. #include 3. int main() 4. { 5. float xA, yA; // A(xA, yA) 6. float xB, yB; // B(xB, yB) 7. float KC; // Khoảng cách 8. printf("Nhap A(xA, yA): "); 9. scanf("%f%f", &xA, &yA); 10. printf("Nhap B(xB, yB): "); 11. scanf("%f%f", &xB, &yB); 12. KC = sqrt(pow(xA-xB,2) + pow(yA-yB,2)); 13. printf("Khoang cach: %f\n", KC); 14. return 0; 15. } Phương pháp lập trình - Tổng quan21 Một số khái niệm Phương pháp lập trình - Tổng quan22  Thư viện  stdio.h, math.h  Chương trình chính  int main(){}  Kiểu biến  int, float  Tên biến  xA, xB  Chú thích  // Lời chú thích  Nhập  scanf(“%d”,&x);  Xuất  printf(“hello!”);  Biểu thức  tong = x + y;  Toán tử  +, -, *, /  Hằng số  #define PI 3.14  Hàm  sqrt, pow, scanf, printf Công cụ lập trình Phương pháp lập trình - Tổng quan23  C-Free Một số trình biên dịch khác  Codeblocks:  Dev-C++:  Visual studio: US/products/visual-studio-express-vs  TurboC: windows-7-windows-8-and-windows-xp/  Eclipse:  Netbeans: https://netbeans.org/downloads/index.html  Ideone: Biên dịch online, hỗ trợ nhiều ngôn ngữ lập trình https://ideone.com/ Phương pháp lập trình - Tổng quan24 Nội dung môn học Phương pháp lập trình - Tổng quan25  Thuật toán/giải thuật?  Cách giải bài toán  Lệnh cấu trúc?  if, else, switch, case  for, while, do while  Vòng lặp?  for, while, do while  Hàm?  Chương trình con  Mảng?  Dãy số  Chuỗi ký tự  Các thao tác cơ bản  Đếm, tìm kiếm, tính toán, thêm, xóa, sắp xếp  Đệ quy?  Hàm gọi lại chính nó  Kiểu cấu trúc?  Do người dùng định nghĩa  Kiểu con trỏ?  Biến lưu địa chỉ của biến  Kiểu tập tin?  Thao tác với tập tin Tìm hiểu sơ lược nội dung qua ví dụ Phương pháp lập trình - Tổng quan26  Thuật toán?  Toán tử ?  Luận lý?  Quan hệ?  Tăng giảm?  Trên bit?  Gán?  Lệnh rẽ nhánh?  if, else, else if  switch  Vòng lặp?  for  while  do while  Hàm?  Mảng?  Chuỗi?  Đệ quy?  Kiểu cấu trúc?  Kiểu con trỏ?  Kiểu tập tin? Thuật toán ? Phương pháp lập trình - Tổng quan27  Ví dụ: Viết chương trình hoán vị hai số nguyên. 1. #include 2. int main() 3. { 4. int x, y, temp; 5. x = 10; 6. y = 60; 7. printf("x=%d, y=%d.\n", x, y); 8. 9. // Hoán vị 10. temp = x; 11. x = y; 12. y = temp; 13. printf("x=%d, y=%d.", x, y); 14. return 0; 15. } Toán tử luận lý ? 1. if (a >= 10 && a < 100) 2. printf("a la so co 2 chu so.\n"); 3. if (a = 100) 4. printf("a khong la so co 2 chu so.\n"); 5. if (a >= 10 && a < 100) 6. printf("a la so co 2 chu so.\n"); 7. else 8. printf("a khong la so co 2 chu so.\n"); Phương pháp lập trình - Tổng quan28 10 100 Toán tử tăng, giảm ? 1. #include 2. int main() 3. { 4. int a, b = 10; 5. a = ++b; // Tăng trước 6. // Tương đương: b = b + 1; a = b; 7. a = b++; // Tăng sau 8. // Tương đương: a = b; b = b + 1; 9. a = --b * 2; // Giảm trước 10. // Tương đương: b = b - 1; a=b*2; 11. a = b-- * 2; // Giảm sau 12. // Tương đương: a=b*2; b = b - 1; 13. return 0; 14. } Phương pháp lập trình - Tổng quan29 Toán tử trên bit ? 1. #include 2. int main() 3. { 4. int a = 52; // 0011 0100 5. int b = 29; // 0001 1101 6. int c; 7. c = a & b; // Phép AND 0001 0100 8. printf("%d & %d = %d\n", a, b, c); 9. c = a | b; // Phép OR 0011 1101 10. printf("%d | %d = %d\n", a, b, c); 11. c = a ^ b; // Phép XOR 0010 1001 12. printf("%d ^ %d = %d\n", a, b, c); 13. c = ~a; // Phép NOT 1100 1011 14. printf("~%d = %d\n", a, c); 15. c = a << 2; // Dịch trái 1101 0000 16. printf("%d << 2 = %d\n", a, c); 17. c = a >> 2; // Dịch phải 0000 1101 18. printf("%d >> 2 = %d\n", a, c); 19. return 0; 20. } Phương pháp lập trình - Tổng quan30 Toán tử gán ? 1. #include 2. int main() 3. { 4. int a = 5, b; 5. b = a++; // b=a;a=a+1; 6. b += a; // b = b + a; 7. b -= a; // b = b – a; 8. b *= a; // b = b * a; 9. b /= a; // b = b / a; 10. b = 40; 11. b %= a; // b = b % a; 12. b &= a; // b = b & a; 13. b |= a; // b = b | a; 14. b ^= a; // b = b ^ a; 15. return 0; 16. } Phương pháp lập trình - Tổng quan31 Lệnh rẽ nhánh ? – if – else if - else Phương pháp lập trình - Tổng quan32  Ví dụ: Tìm giá trị lớn nhất giữa hai số nguyên A và B. 1. if (a>b) 2. printf("a lon nhat"); 3. else 4. printf("b lon nhat"); 1. if (a>b) 2. printf("a lon nhat"); 3. else if (a==b) 4. printf("a bang b"); 5. else 6. printf("b lon nhat");  Toán tử quan hệ  >  <  >=  <=  ==  !=  Toán tử luận lý  &&  || Lệnh switch ? – Lựa chọn các trường hợp 1. #include 2. #include 3. int main() 4. { 5. time_t t = time(NULL); 6. struct tm *time = localtime(&t); 7. int today = time->tm_wday; 8. printf("Hom nay la "); 9. switch (today) 10. { 11. case 1: printf("thu hai.");break; 12. case 2: printf("thu ba.");break; 13. case 3: printf("thu tu.");break; 14. case 4: printf("thu nam.");break; 15. case 5: printf("thu sau.");break; 16. default: printf("cuoi tuan."); 17. } 18. return 0; 19. } Phương pháp lập trình - Tổng quan33 Vòng lặp ? – for – while – do while Phương pháp lập trình - Tổng quan34  Đề bài: Xuất ra màn hình các số nguyên từ 0 đến 10. 1. int i; 2. for (i = 0; i <= 10; i++) 3. printf("%d ", i); 1. i = 0; 2. do{ 3. printf("%d ", i); 4. i++; 5. }while(i <= 10); 1. i = 0; 2. while(i <= 10) 3. { 4. printf("%d ", i); 5. i++; 6. } Hàm/Chương trình con ? 35 1. #include 2. int nhan(int x, int y) // Hàm nhan kiểu int 3. { 4. int z; // Biến z lưu giá trị phép nhân 5. z = x * y; // Thực hiện phép nhân 6. return z; // Trả về giá trị cho hàm nhan 7. } 8. void main() 9. { 10. int a, b, c; // Khai báo 11. a = b = 5; // Gán giá trị cho a và b 12. c = nhan(a, b); // c = giá trị hàm nhan 13. printf("%d x %d = %d",a,b,c);// Xuất 14. } Phương pháp lập trình - Tổng quan Mảng – dãy số ? 1. #include 2. int main() 3. { 4. int mang[5]; // Dãy số gồm 5 phần tử 5. int i; 6. mang[0] = 0; // Phần tử đầu tiên 7. mang[1] = 1; 8. mang[2] = mang[0] + mang[1]; 9. mang[3] = mang[1] + mang[2]; 10. i = 4; 11. mang[i] = mang[i-2] + mang[i-1]; 12. printf("%d",mang[i]); 13. return 0; 14. } mang[0] mang[1] mang[2] mang[3] mang[4] 0 ? ? ? ? Phương pháp lập trình - Tổng quan36 Chuỗi ký tự ? 1. #include 2. #include 3. int main() 4. { 5. char ten[30]; 6. char gioithieu[50] = "Toi ten la "; 7. char chao[6] = {'C','h','a','o','!','\0'}; 8. printf("Nhap ten cua ban: "); 9. scanf("%[^\n]s",&ten); 10. strcat(gioithieu,ten); 11. printf("%s \n%s \n", chao, gioithieu); 12. printf("Ten co %d ky tu.",strlen(ten)); 13. return 0; 14. } 'C' 'h' 'a' 'o' '!' '\0' Phương pháp lập trình - Tổng quan37 Đệ quy ? 38 1. #include 2. int factorial(int n) 3. { 4. if (n<=0) return 1; 5. return n * factorial(n-1); 6. } 7. void main() 8. { 9. int n; 10. do{ 11. scanf("%d",&n); 12. }while(n<0); 13. printf("Factorial(%d) = %d", n, factorial(n)); 14. } Phương pháp lập trình - Tổng quan Kiểu dữ liệu cấu trúc ? 39 1. #include 2. struct sinhvien // Khai báo kiểu struct 3. { 4. int ID; // Biến ID kiểu nguyên 5. float diem; // Biến điểm kiểu số thực 6. }; 7. void main() 8. { 9. struct sinhvien a; // Khai báo biến 10. a.ID = 123456; // Gán ID cho a.ID 11. a.diem = 5.5; // Gán điểm cho a.diem 12. printf("ID: %s\n", a.ID); // Xuất ID 13. printf("Diem: %d\n", a.diem); // Xuất diem 14. } Phương pháp lập trình - Tổng quan Kiểu con trỏ - pointer ? 40 1. #include 2. int main() 3. { 4. int x = 20; // Giá trị của biến x 5. int *p; // Biến con trỏ 6. p = &x; // Gán địa chỉ của biến x cho p 7. printf("Gia tri cua bien x: %d \n", x); 8. printf("Dia chi cua bien x: %p \n", &x); 9. printf("Dia chi luu trong bien p: %p \n", p); 10. printf("Gia tri cua *p: %d \n", *p); 11. p = NULL; // Gán giá trị rỗng 12. printf("Dia chi luu trong bien p: %p.", p); 13. return 0; 14. } Biến x p Địa chỉ 0073FB60 0073FB54 Giá trị 20 0073FB60 Phương pháp lập trình - Tổng quan Đọc tập tin ? 41 1. #include 2. void main() 3. { 4. FILE *f; // Khai báo biến kiểu FILE 5. char buffer[256]; // Kiểu chuỗi 6. f = fopen("input.txt", "r"); // Mở file 7. if (f == NULL) // Không có file này 8. printf("Lỗi khi mở file\n"); 9. else 10. { 11. while (fgets(buffer, 256, f) != NULL) 12. printf("%s",buffer); // Xuất 13. fclose(f); // Đóng file 14. } 15. } Phương pháp lập trình - Tổng quan Ghi vào tập tin ? 42 1. #include 2. void main() 3. { 4. FILE *f; // Khai báo biến kiểu FILE 5. char buffer[256]="Lap trinh C";// Kiểu chuỗi 6. f = fopen("output.txt", "w");// Mở file để ghi 7. if (f == NULL) // Không có file này 8. printf("Loi khi mo file\n"); 9. else 10. { 11. fputs(buffer, f); // Ghi chuỗi vào file 12. fclose(f); // Đóng file 13. } 14. } Phương pháp lập trình - Tổng quan Một số gợi ý Phương pháp lập trình - Tổng quan43  Bám sát các nội dung thực hành (quan trọng!)  Đọc tài liệu, slide trước khi đến lớp  In tài liệu, slide, bài tập  Tự đặt câu hỏi và trả lời  Tự làm bài tập ở nhà  Tóm tắt các nội dung chủ yếu  Vắng học? Hết bài 1 Phương pháp lập trình - Tổng quan  Giới thiệu  Nội dung  Tài liệu  Lịch trình  Kiểm tra  Nội dung môn học qua một số ví dụ 44 Nội dung tiếp theo (Yêu cầu tự học trước) Phương pháp lập trình - Tổng quan45  Thư viện  stdio.h, math.h, string.h  Chương trình chính  int main(){}  Kiểu biến  int, float  Tên biến  xA, xB  Chú thích  // Lời chú thích  Nhập  scanf(“%d”,&x);  Xuất  printf(“hello!”);  Biểu thức  tong = x + y;  Toán tử  +, -, *, /  Hằng số  #define PI 3.14  Hàm  sqrt, pow, scanf, printf