Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 3: Cấu trúc điều khiển

50 trang hapham 1080

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 3: Cấu trúc điều khiển", để 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_3_cau_truc_d.pdf

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 3: Cấu trúc điều khiển

CHƯƠNG 3 CẤU TRÚC ĐIỀU KHIỂN 1
CÁC CẤU TRÚC ĐIỀU KHIỂN TRONG CHƯƠNG TRÌNH Lệnh 1; Lệnh 2; TUẦN TỰ Lệnh 3; . RẼ NHÁNH CÓ if ĐIỀU KIỆN if else LỰA CHỌN switch case for LẶP while do while 2
CẤU TRÚC TUẦN TỰ Lệnh 1 Tuần tự thực thi tiến trình, mỗi lệnh được thực thi theo một chuỗi từ trên xuống, Lệnh 2 xong lệnh này rồi chuyển xuống lệnh kế tiếp. Lệnh 3 3
void main() { int a, b, tong, hieu, tich; float thuong; cout >a; cout >b; tong = a + b; hieu = a - b; tich = a * b; thuong = (float)a / b; //Ép kiểu cout<<"Tong: " <<tong; cout<<"Hieu: “<<hieu; cout<<"Tich: “<<tich; cout<<"Thuong: “<<thuong; } 4
CẤU TRÚC RẼ NHÁNH Cấu trúc rẽ nhánh chỉ cho máy tính chọn thực hiện một dãy lệnh nào đó dựa vào kết quả của một điều kiện (biểu thức quan hệ hay biểu thức so sánh) Gồm 2 dạng: Chỉ xét trường hợp đúng if (biểu thức điều kiện) { ; } Nếu biểu thức điều kiện cho kết quả true thì thực hiện khối lệnh bên trong if. 5
Ví dụ: Viết chương trình nhập vào một số nguyên từ 1 đến 10, nếu nhập sai thì thông báo void main() { int k; cout >k; if (k 10) { cout<<"So vua nhap khong hop le"; } } 6
Xét cả hai trường hợp đúng và sai: if (biểu thức điều kiện) { ; } else { ; } Nếu biểu thức điều kiện cho kết quả true thì thực hiện khối lệnh 1, ngược lại thì cho thực hiện khối lệnh thứ 2 7
Ví dụ 1: Nhập vào số nguyên a và b, nếu a là bội số của b thì in thông báo “a là bội số của b”, ngược lại in “a khong la boi so cua b” cout >a; cout >b; if(a%b==0) else { { cout<<“a la boi so cua b“; cout<<“a khong la boi so cua b“; } 8 }
Cài đặt: void main() { int a, b; cout >a; cout >b; if(a%b= =0) { cout<<“a la boi so cua b”; } else { cout<<“a khong la boi so cua b”; } 9 }
Ví dụ 2: Giải và biện luận phương trình: ax+b=0 10
void main() { float a, b; cout >a; cout >b; if (a == 0) { if (b == 0) cout<<"Phuong trinh vo so nghiem”; else cout<<"Phuong trinh vo nghiem”; } else { cout<<"Phuong trinh co nghiem x = “<< -b / a; } } 11
BÀI TẬP – CHO BIẾT KẾT QUẢ int a=9, b=6; a++; a=a+b ; a=a+( b); if(a%2==0) cout<<"Gia tri cua a la chan”; cout<<"Tong cua a va b la: " <<(a + b); 12
int a=7, b=8; a++; a=a+b ; b; a ; a = ( a)+( b); if(a%2 != 0) cout<<"a la so le”; else cout<<"a la so chan”; cout<<"Gia tri cua a: " <<a; 13
BÀI TẬP VIẾT CHƯƠNG TRÌNH 1. Nhập vào hai số nguyên a, b. In ra màn hình giá trị lớn nhất. 2. Cho ba số a, b, c đọc vào từ bàn phím. Hãy tìm giá trị lớn nhất của ba số trên và in ra kết quả. 3. Cho ba số a, b, c đọc vào từ bàn phím. Hãy in ra màn hình theo thứ tự tăng dần các số. (Chỉ được dùng thêm hai biến phụ). 4. Viết chương trình nhập vào một số nguyên n gồm ba chữ số. Xuất ra màn hình chữ số lớn nhất ở vị trí nào? Ví dụ: n=291. Chữ số lớn nhất nằm ở hàng chục (chữ số 9). 14
5. Viết chương trình nhập vào số nguyên n gồm ba chữ số. Xuất ra màn hình theo thứ tự tăng dần của các chữ số. Ví dụ: n=291. Xuất ra 129. 6. Nhập vào ngày, tháng, năm. Kiểm tra xem ngày, tháng, năm đó có hợp lệ hay không? In kết quả ra màn hình. 7. Nhập vào giờ, phút, giây. Kiểm tra xem giờ, phút, giây đó có hợp lệ hay không? In kết quả ra màn hình. 8. Viết chương trình nhập vào ngày, tháng, năm hợp lệ. Cho biết năm này có phải là năm nhuận hay không? In kết quả ra màn hình. 9. Viết chương trình tính diện tích và chu vi các hình: tam giác, hình vuông, hình chữ nhật và hình tròn với những thông tin cần được nhập từ bàn phí15 m.
10. Viết chương trình tính tiền cước TAXI. Biết rằng: km đầu tiên là 13000đ. Mỗi km tiếp theo là 12000đ. Nếu lớn hơn 30km thì mỗi km thêm sẽ là 11000đ. Hãy nhập số km sau đó in ra số tiền phải trả. 11. Nhập vào 3 số nguyên dương. Kiểm tra xem 3 số đó có lập thành tam giác không? Nếu có hãy cho biết tam giác đó thuộc loại nào? (Cân, vuông, đều, ). 12. Viết chương trình nhập vào số nguyên dương n. Kiểm tra xem n có phải là số chính phương hay không? (số chính phương là số khi lấy căn bậc 2 có kết quả là nguyên). 16
CẤU TRÚC LỰA CHỌN switch (biểu thức) case n1: các câu lệnh ; Trường hợp giá trị biểu thức bằng n1 break ; case n2: các câu lệnh ; Trường hợp giá trị biểu break ; thức bằng n2 case nk: Trường hợp giá trị biểu ; thức bằng nk break ; [default: các câu lệnh]  Các trường hợp còn lại 17
Với: ni là các hằng số nguyên hoặc ký tự. Phụ thuộc vào giá trị của biểu thức viết sau switch, nếu: –Giá trị này = ni thì thực hiện câu lệnh sau case ni. –Khi giá trị biểu thức không thỏa tất cả các ni thì thực hiện câu lệnh sau default nếu có, hoặc thoát khỏi câu lệnh switch. –Khi chương trình đã thực hiện xong câu lệnh của case ni nào đó thì nó sẽ thực hiện luôn các lệnh thuộc case bên dưới nó mà không xét lại điều kiện (do các ni được xem như các nhãn) Vì vậy, để chương trình thoát khỏi lệnh switch sau khi thực hiện xong một trường hợp, ta dùng lệnh break. 18
Ví dụ: Nhập vào số nguyên n có giá trị từ 1 đến 5. In cách đọc của số đó ra màn hình. void main() { int n; cout >n; switch (n) { case 1: cout<<"So mot”; break; case 2: cout<<"So hai"; break; case 3: cout<<"So ba”; break; case 4: cout<<"So bon”; break; case 5: cout<<"So nam”; break; default : cout<<"Khong doc duoc"; } 19 }
BÀI TẬP VIẾT CHƯƠNG TRÌNH 13. Viết chương trình nhập vào số điểm và xếp hạng như sau:  Điểm1 -4: Kém  Điểm5 : Trung bình  Điểm6 : Trung bình khá  Điểm7 : Khá  Điểm8 -9: Giỏi  Điểm10 : Xuất sắc 14. Viết chương trình nhập vào ngày tháng năm, kiểm tra xem ngày tháng năm có hợp lệ không? In kết quả kiểm tra ra màn hình – Gợi ý: if ((Nam % 400 == 0) || ((Nam % 100 != 0) && (Nam % 4 == 0))); 20
CẤU TRÚC LẶP Điều kiện Yes lặp No Lệnh / Khối lệnh 21
VÒNG LẶP FOR 1 2 4 for ( ; ; ) { ; 3 }  Khởi gán: Dùng để khởi gán giá trị ban đầu cho vòng lặp  Điều kiện lặp: Dùng để kiểm tra điều kiện trước khi thực hiện vòng lặp  Cập nhật: Dùng để cập nhật vòng lặp (tăng hoặc giảm chỉ số lặp) Bất kỳ biểu thức nào trong 3 biểu thức nói trên đều có thể vắng nhưng phải giữ dấu chấm phẩy (;) 22
SƠ ĐỒ HOẠT ĐỘNG Khởi gán Điều kiện lặp Yes Lệnh / Khối lệnh Cập nhật vòng lặp 23
 Bước 1: Khởi gán  Bước 2: Kiểm tra điều kiện ― Nếu điều kiện bằng true thì cho thực hiện các lệnh của vòng lặp, thực hiện cập nhật vòng lặp. Quay trở lại bước 2. ― Ngược lại thoát khỏi lặp. 24
Ví dụ: In ra màn hình 10 dòng chữ “ABC” dong = 1 dong <= 10 Yes “ABC” End line dong = dong + 1 25
void main() { for (int dong = 1; dong <= 10; dong++) cout<<“ABC“<<endl; } 26
 Ví dụ: Tính tổng: S 1 2 3  n , với n>0 n S = 0 i = 1 i <= n Yes S = S + i “Tổng = “ S i = i + 1 27
VÒNG LẶP while 1 2 while ( ) lệnh/ khối lệnh; 3 4   Lưu ý: Cách hoạt động của while giống for 28
Ví dụ: In ra màn hình 10 dòng chữ “Xin chao” void main() { int dong = 1; while(dong <= 10) { cout<<"Xin chao“<<endl; dong++; } } 29
VÒNG LẶP do while Khởi gán do Lệnh / Khối lệnh { ; Cập nhật vòng lặp ; } while (điều kiện); Điều kiện lặp Yes 30
VÒNG LẶP do while  Thực hiện khối lệnh cho đến khi biểu thức có giá trị bằng false. Cấu trúc lặp do while thường dùng cho trường hợp nhập có kiểm tra điều kiện  Ngược lại với cấu trúc lặp for và while (kiểm tra điều kiện trước khi thực hiện lặp), vòng lặp do while thực hiện lệnh lặp rồi mới kiểm tra điều kiện. Do đó vòng lặp do while thực hiện lệnh ít nhất một lần. 31
Ví dụ: Nhập vào một số nguyên dương, nếu nhập sai thì thông báo lỗi và yêu cầu nhập lại. void main() { int n; do{ cout >n; if (n <= 0) cout<<"Nhap sai, hay nhap lai!“<<endl; } while (n <= 0); cout<<"Ban da nhap dung, ket thuc chuong trinh”; } 32
LỆNH break và return  Lệnh break: thoát khỏi các cấu trúc switch, while, for, do while chứa nó gần nhất (đang chứa break) tại thời điểm break được gọi thi hành mà không cần kiểm tra kết quả của biểu thức điều kiện.  Tuy nhiên, cần phân biệt với lệnh return là lệnh trả về từ hàm, nghĩa là thoát khỏi hàm đang thi hành, nên cũng giúp thoát luôn khỏi tất cả các vòng lặp. 33
LỆNH continue Lệnh continue: được sử dụng trong các vòng lặp như while, for, do while. Khi lệnh continue được gọi thì chương trình sẽ quay trở về đầu vòng lặp để bắt đầu lần lặp mới (có kiểm tra điều kiện lặp để xác định có lặp tiếp hay không). Nếu có các lệnh còn lại (cùng trong vòng lặp) đặt sau continue sẽ không được thực hiện. Nói tóm lại, lệnh continue dùng để bỏ qua một lần lặp nào đó nếu thỏa điều kiện. 34
Ví dụ: Cho phép người dùng nhập liên tục số nguyên dương, nếu nhập số nguyên âm thì dừng void main() { int n; while (true) { cout >n; if (n <= 0) { cout<<"Ket thuc vong lap”; break; } } 35 }
Ví dụ: In ra màn hình giá trị từ 10 đến 20 trừ đi số 13 và số 17. void main() { for (int k = 10; k <= 20; k++) { if (k == 13 || k == 17) continue; cout<<k<<“\t"; } } 36
XÁC ĐỊNH KẾT QUẢ int a=18; for(int i = 1; i <= a; i++) if(a%i == 0) cout<<i <<“\t”; for(int i = 0; i < 5; i++) { for(int j = 0; j <= i; j++) cout<<j<<“\t”; cout<<endl; } 37
int i = 10, s = 0; while(i > 0) { if(i%2 == 0) s+=i; else if(i > 5) s+=2*i; i ; } cout<<“s = ” <<s; 38
int a = 18, i = 1; do{ if(a%i == 0) cout<<i<<“\t”; i++; } while(i <= a); 39
int a = 11, b = 16, i = a; while( i < b ) { if(i%2 == 0) { cout<<i<<"\t"; break; } i++; } 40
int a = 10, s = 0, i = 0; while( i < a ) { i++; if (i % 2 == 0) continue; else s=s+i; } cout<<"s = " <<s; 41
int i = 1, s = 0; while(true) { s = s + i++; if (i % 2) i = i + 2; else i = i + 1; if (i > 20) break; } cout<<"s = " <<s; 42
15. Viết chương trình nhập số nguyên dương n. Liệt kê n số nguyên tố đầu tiên. 16. Viết chương trình nhập vào hai số nguyên dương a và b. Tìm ước số chung lớn nhất và bội số chung nhỏ nhất của a và b. 17. Viết chương trình nhập vào một số nguyên n gồm tối đa 10 chữ số (4 bytes). In ra màn hình giá trị nhị phân của số trên. (Hướng dẫn: chia lấy dư cho 2 và xuất theo thứ tự ngược lại). 18. Viết chương trình đếm số ước số của số nguyên dương N. Ví dụ: N=12 số ước số của 12 là 6 43
19. Một số hoàn thiện là một số có tổng các ước số của nó (không kể nó) bằng chính nó. Hãy liệt kê các số hoàn thiện nhỏ hơn 30000. Ví dụ: số 6 là số hòan thiện vì tổng các ước số là 1+2+3 = 6. 20. Nhập vào ngày, tháng, năm. Cho biết đó là ngày thứ mấy trong năm. 21. In ra dãy số Fibonaci f1 = f0 =1; fn = fn-1 + fn-2; (n>1) 44
XÁC ĐỊNH KẾT QUẢ CHƯƠNG TRÌNH  Xác định xem chương trình có sử dụng những biến nào;  Giá trị ban đầu của mỗi biến;  Những biến nào sẽ bị thay đổi trong quá trình chạy chương trình thì lập thành bảng có dạng sau: Bước (hoặc lần Kết quả trả về lặp hoặc dòng Biến 1 Biến 2 Biến k (hoặc in ra lệnh thực hiện) màn hình) 0 Giá trị 0 Giá trị 0 Giá trị 0 1 Giá trị 1 Giá trị 1 Giá trị 1 2 Giá trị 2 Giá trị 2 Giá trị 2  Lưu ý từng lệnh và xét kỹ giá trị của biểu thức điều kiện 45 trong đoạn chương trình
DÙNG CÔNG CỤ DEBUG XÁC ĐỊNH LỖI/ KẾT QUẢ CHƯƠNG TRÌNH Dùng để xác định lỗi logic (lỗi giải thuật) trong chương trình. Mặc dù chương trình không còn lỗi nhưng khi chạy chương trình vẫn ra kết quả sai, những lỗi đó có thể là: Dùng chấm phẩy sau: if, else, for, while mà chưa thực hiện lệnh; Không dùng cặp dấu ngoặc ({}) để bao khối lệnh; Khai báo sai kiểu dữ liệu, không ép kiểu dữ liệu; Chia cho 0; Không có điều kiện dừng (điều kiện dừng sai); Phân tích giải thuật thiếu (chưa vét hết các trường hợp) hoặc sai; 46
 Bước 1: Đặt dấu nháy vào vị trí bắt đầu cần kiểm tra lỗi 47
 Bước 2: Nhấn phím Ctrl + F10 48
Quan sát vị trí dấu mũi tên trên cửa sổ viết code để xác định dòng lệnh đang thực hiện. Cửa sổ Locals (View\ Debug Windows\ Variables hoặc nhấn phím Alt+4) sẽ thể hiện tên (name), giá trị (value) và kiểu (type) của các biến cục bộ trong đoạn chương trình. Cửa sổ Watch (View\ Debug Windows\ Watch hoặc nhấn Alt+3) cũng có thể quan sát chi tiết biến tương tự như cửa sổ Locals, nhưng chỉ thể hiện những biến nào mà ta nhập tên biến tương ứng vào cửa sổ này. 49
 Bước 3: Nhấn phím F10 để thực hiện lệnh kế tiếp (hoặc hàm kế tiếp). Nếu muốn xem lệnh thực hiện bên trong của hàm thì nhấn phím F11 (nếu lệnh là lời gọi thực hiện hàm – lưu ý: không nên nhấn phím F11 khi thực hiện các hàm thư viện (ví dụ: cin, cout) 50