Chương 7 Các lệnh có cấu trúc

Chương 7 CÁC LỆNH CÓ CẤU TRÚC Lý thuyết ngôn ngữ lập trình Nội dung Cấu trúc tuần tự Cấu trúc lựa chọn Cấu trúc lặp Giới thiệu thuật toán đệ quy Ngoại lệ và xử lý ngoại lệ Cấu trúc tuần tự Các công việc (các thao tác) được thực hiện một cách tuần tự, công việc này nối tiếp công việc kia Lưu đồ thuật toán tổng quát của cấu trúc tuần tự : Lệnh 1 Lệnh 2 … Lệnh n Cấu trúc tuần tự (tt) Một chương trình C sử dụng cấu trúc tuần tự. int main() { int a=5, b=6,c; float x=3.5, y=4.5,z; printf(“Day la chuong trinh chinh”); c= a + b; printf(“\n Tong cua %d va %d la %d”,a,b,c); z= x + y; printf(“\n Tong cua %f và %f là %f”, x,y,z); getch(); return 0; } Cấu trúc lựa chọn Lựa chọn một công việc để thực hiện căn cứ vào một điều kiện cho trước nào đó. Có một số dạng cấu trúc lựa chọn thông dụng như sau: Cấu trúc 1: Nếu (đúng) thì thực hiện . Trong ngôn ngữ lập trình C, cấu trúc này được thể hiện bằng lệnh if có cú pháp như sau : if () Cấu trúc lựa chọn (tt) Ví dụ : #include #include void main() { int a,b,c; print ( "\ nhập 2 số a,b : "); scanf(" %f %f ", &a, &b); if (a>b) c =a-b; printf (“c = %f \n”,c) } Cấu trúc lựa chọn (tt) Cấu trúc 2: Nếu (đúng) thì thực hiện <công việc 1>, ngược lại (điều kiện sai) thực hiện . Trong ngôn ngữ lập trình C, cấu trúc này được thể hiện bằng lệnh if ..else có cú pháp như sau : if () else Cấu trúc lựa chọn (tt) Ví dụ : #include #include void main() { int a,b,c; print ( "\ nhập 2 số a,b : "); scanf(" %f %f ", &a, &b); if (a>b) c =a-b; else c = b-a; printf (“c = %f \n”,c) } Cấu trúc lựa chọn (tt) chúng ta có thể sử dụng nhiều lệnh if .. else lồng nhau. Ví dụ : Chương trình C giải phương trình bậc nhất. #Include #Include void main ( void) {float a, b ; print ( "\ nhập 2 số a,b : "); scanf(" %f %f ", &a, &b); if ( a= = 0 ) if( b= =0 ) Printf (" Phương trình có vô số nghiệm ! \n " ); else Printf (" phương trình vô nghiệm \n "); else / * a khác 0 */ Printf (" phương trình có nghiệm là : x= %f \n ", -b/a); Printf( " ấn phím bất kỳ tiếp tục "); getch(); } Cấu trúc lựa chọn (tt) Cấu trúc 3: Trường hợp thực hiện . Trong ngôn ngữ lập trình C, cấu trúc này được thể hiện bằng lệnh switch có cú pháp như sau: switch () { case : // nếu = <biểu thức so sánh 1> ; break; case : // nếu = <biểu thức so sánh 2> ; break; … case : // nếu = <biểu thức so sánh n> ; break; default : // nếu không xảy ra tất cả các trường hợp trên } Cấu trúc lựa chọn (tt) Ví dụ : #Include #Include main( ) { Int so ; printf(" \n Nhập vào một số "); scanf(" %d ", &so); switch(so) { case 0 : printf(" \n Đây là số KHÔNG "); break; case 1 : printf( " \n Đây là số MỘT"); break; case 2 : printf(" \n Đây là số HAI");break; case 3 : printf (" \n Đây là số BA ");break; default : printf( " \n Đây là số từ BỐN trở lên hoặc là ký tự"); } } Cấu trúc lặp Thực hiện lặp đi lặp lại một công việc nhiều lần căn cứ vào một điều kiện nào đó. Cấu trúc này có hai dạng thông dụng như sau: Lặp xác định: Người lập trình đã xác định trước được sẽ lặp đi lặp lại công việc bao nhiêu lần khi viết chương trình. Cấu trúc lặp (tt) Trong ngôn ngữ lập trình C, cấu trúc này được thể hiện bằng vòng lặp for có cú pháp như sau: for (biểu thức 1; biểu thức 2;biểu thức 3) Trong đó: biểu thức1 thông thường là một phép gán để khởi tạo giá trị ban đầu cho biến điều khiển. biểu thức2 là một biểu thức kiểm tra điều kiện đúng sai để thoát khỏi vòng lặp. biểu thức3 thông thường là một phép gán để thay đổi biến điều khiển có thể là lệnh rỗng, một câu lệnh hoặc một khối lệnh. Cấu trúc lặp (tt) Ví dụ: Chương trình tìm phương án đổi tiền. #include #define TONGSOTIEN 300000 void main() { long i, j, k, l, m, count=0, soluong = 0; for (i=0; i<=TONGSOTIEN/1000; i++) for (j=0; j<=TONGSOTIEN/2000; j++) for (k=0; k<=TONGSOTIEN/5000; k++) for (l=0; l<=TONGSOTIEN/10000; l++) for (m=0; m<=TONGSOTIEN/20000; m++) Cấu trúc lặp (tt) {if ((i*1000 + j*2000 + k*5000 + l*10000 + m*20000) == TONGSOTIEN) printf("\n%5ld - %5ld%5ld%5ld%5ld%5ld", ++count, i, j, k, l, m); soluong++; } printf("so luong = %ld", soluong); getch(); } Cấu trúc lặp (tt) Lặp không xác định: Người lập trình không xác định được sẽ lặp đi lặp lại công việc bao nhiêu lần, mà số lần lặp đó chỉ xác định được khi thực thi chương trình. Cấu trúc lặp (tt) Trong ngôn ngữ lập trình C, cấu trúc này được thể hiện bằng vòng lặp while và vòng lặp do .. while có cú pháp như sau: + Vòng lặp while while () Trong đó biểu thức là một biểu thức kiểm tra điều kiện đúng sai để thoát khỏi vòng lặp và các lệnh có thể là lệnh rỗng, một câu lệnh hay khối lệnh Cấu trúc lặp (tt) Ví dụ : Chương trình in dãy số Fibonaci #include void main() { int n, i, fib1 = 1, fib2 = 1, fib = 2; printf("\nNhap gia tri N : "); scanf("%d", &n); printf("%d %d ", fib1, fib2); while (fib1+fib2 < n) { fib = fib1 + fib2; printf("%d ", fib); fib2 = fib1; fib1 = fib; } getch(); } Cấu trúc lặp (tt) + Vòng lặp do .. while: do while Tương tự như vòng lặp while, nhưng có điểm khác là các lệnh được thực hiện ít nhất một lần vì việc kiểm tra biểu thức điều kiện được thực hiện sau. Cấu trúc lặp (tt) Ví dụ : Chương trình cho biết mã ASCII của phím bất kỳ #include void main() { char c; printf("\nNhap vao mot phim muon biet ma cua no. ESC de thoat\n"); Cấu trúc lặp (tt) do { c = getch(); if (c == 0) { c = getch(); printf("\nMa mo rong : %d", c); } else printf("\nMa thuong : %d", c); } while (c != 27); } Giới thiệu thuật toán đệ quy Như đã biết, một thuật toán cần phải thỏa mãn ít nhất 3 tính chất : - Tính hữu hạn. - Tính xác định - Tính đúng đắn Tuy nhiên, có những bài toán mà việc xây dựng một thuật toán với đầy đủ ba tính chất trên rất khó khăn. Trong khi đó, nếu ta xây dựng một thuật toán vi phạm một vài tính chất trên thì cách giải lại trở nên đơn giản hơn nhiều và có thể chấp nhận được. Một trong những trường hợp đó là thuật toán đệ quy. Giới thiệu thuật toán đệ quy (tt) Tư tưởng giải bài toán bằng thuật toán đệ quy là đưa bài toán hiện tại về một bài toán cùng loại, cùng tính chất (đồng dạng) nhưng ở cấp độ thấp hơn (chẳng hạn : độ lớn dữ liệu nhập nhỏ hơn, giá trị cần tính toán nhỏ hơn, ....), và quá trình này tiếp tục cho đến lúc bài toán được đưa về một cấp độ mà tại đó có thể giải được. Từ kết quả ở cấp độ này, ta sẽ lần ngược để giải được bài toán ở cấp độ cao hơn cho đến lúc giải được bài toán ở cấp độ ban đầu. Trong toán học ta cũng thường gặp những định nghĩa về những đối tượng, những khái niệm dựa trên chính những đối tượng, khái niệm đó. Giới thiệu thuật toán đệ quy (tt) - Ðịnh nghĩa giai thừa Giai thừa của một số tự nhiên n, ký hiệu n! được định nghĩa là : 0! = 1 n! = (n-1)!n với mọi n>0 - Ðịnh nghĩa dãy số Fibonacci f0 = 1 f1 = 1 fn = fn-1 + fn-2 với mọi n>1 Theo toán học, những khái niệm được định nghĩa như vậy gọi là định nghĩa theo kiểu quy nạp. Chính vì vậy, đệ quy có sự liên hệ rất chặt chẽ với quy nạp toán học. Giới thiệu thuật toán đệ quy (tt) Ðệ quy mạnh ở điểm nó có thể định nghĩa một tập vô hạn các đối tượng chỉ bằng một số hữu hạn các mệnh đề. Tuy nhiên, đặc tính này của đệ quy lại vi phạm tính xác định của thuật toán. Về nguyên tắc, một bước trong thuật toán phải được xác định ngay tại thời điểm bước đó được thi hành, nhưng với thuật toán đệ quy, bước thứ n không được xác định ngay trong ngữ cảnh của nó mà phải xác định thông qua một bước thấp hơn. Giới thiệu thuật toán đệ quy (tt) Ưu thế của thuật toán đệ quy là ta chỉ cần giải bài toán tại một số trường hợp đặc biệt nào đó, còn gọi là trường hợp dừng. Sau đó, các trường hợp khác của bài toán sẽ được xác định thông qua trường hợp đặc biệt này. Ðối với việc tính dãy Fibonacci, trường hợp dừng chính là giá trị của f0 và f1. Giới thiệu thuật toán đệ quy (tt) Mọi thuật toán đệ quy đều gồm hai phần: - Phần cơ sở Là các trường hợp không cần thực hiện lại thuật toán (hay không có yêu cầu gọi đệ quy). Nếu thuật toán đệ quy không có phần này thì sẽ dẫn đến bị lặp vô hạn và sinh lỗi khi thi hành. Vì lý do này mà người ta đôi lúc còn gọi phần cơ sở là trường hợp dừng. - Phần đệ quy Là phần trong thuật toán có yêu cầu gọi đệ quy, tức là yêu cầu thực hiện lại thuật toán nhưng với một cấp độ dữ liệu thấp hơn. Giới thiệu thuật toán đệ quy (tt) - Chương trình không dùng thuật toán đệ quy được viết như sau: #include unsigned long giaithua(int n) { unsigned long ketqua = 1; int i; for (i=2; i<=n; i++) ketqua *= i; return ketqua; } Giới thiệu thuật toán đệ quy (tt) void main() { int n; printf("\nNhap vao gia tri N : "); scanf("%d", &n); printf("%d! = %lu", n, giaithua(n)); getch(); } Giới thiệu thuật toán đệ quy (tt) - Chương trình dùng thuật toán đệ quy được viết lại như sau: #include unsigned long giaithua(int n) { if (n==0||n==1) return 1; else return n*giaithua(n-1); } Giới thiệu thuật toán đệ quy (tt) void main() { int n; printf("\nNhap vao gia tri N : "); scanf("%d", &n); printf("%d! = %lu", n, giaithua(n)); getch(); } Ngoại lệ và xử lý ngoại lệ Khái niệm Trong quá trình thực hiện chương trình thường xảy ra một số sự kiện đặc biệt hoặc các lỗi như sự tràn số, truy xuất đến chỉ số mảng nằm ngoài tập chỉ số, thực hiện lệnh đọc một phần tử cuối tập tin ... Các sự kiện đó được gọi là ngoại lệ (exception). Thay vì tiếp tục thực hiện chương trình bình thường, một chương trình con sẽ được gọi để thực hiện một vài xử lý đặc biệt nào đó gọi là xử lý ngoại lệ. Hành động chú ý đến ngoại lệ, ngắt sự thực hiện chương trình và chuyển điều khiển đến xử lý ngoại lệ được gọi là đề xuất ngoại lệ (raising the exception). Ngoại lệ và xử lý ngoại lệ (tt) Xử lý ngoại lệ Thông thường các ngoại lệ đã được định nghĩa trước bởi ngôn ngữ, chẳng hạn như ZERO_DIVIDE chỉ sự kiện chia cho một số không, END_OF_FILE: hết tập tin , OVERFLOW: tràn số, hay tràn stack ... Xử lý ngoại lệ là một hành vi xử lý tương ứng khi một ngoại lệ có thể diễn ra. Ví dụ Ngoại lệ và xử lý ngoại lệ (tt) void example () { average = sum/total; ... return ; when zero_divide { average = 0; printf(“ error: cannot compute average, total is zero\n”); } ...... } /** function example **/ Ngoại lệ và xử lý ngoại lệ (tt) Sau khi đã hoàn thành việc xử lý một ngoại lệ và xử lý đó đã kết thúc thì có một vấn đề đặt ra là quyền điều khiển được chuyển tới chỗ nào? - Ðiều khiển nên được chuyển tới chỗ mà ngoại lệ được đề xuất? - Ðiều khiển nên chuyển về lệnh trong chương trình con chứa xử lý nơi mà ngoại lệ được đề xuất sau khi được truyền tới?Chương trình con chứa xử lý tự kết thúc một cách bình thường và nó xuất hiện tại chương trình gọi như là không có gì xẩy ra. - Ðây là những lựa chọn khi thiết kế ngôn ngữ. Ngoại lệ và xử lý ngoại lệ (tt) Đề xuất ngoại lệ Một ngoại lệ có thể bị đề xuất bằng phép toán nguyên thuỷ được định nghĩa bởi ngôn ngữ chẳng hạn phép cộng, phép nhân có thể đề xuất ngoại lệ OVERFLOW. Ngoài ra, một ngoại lệ có thể bị đề xuất một cách tường minh bởi người lập trình bằng cách dùng một lệnh được cung cấp cho mục đích đó. Lệnh này có thể được thực hiện trong một chương trình con sau khi xác định một biến riêng hoặc tập tin nhập chứa giá trị không đúng. Ngoại lệ và xử lý ngoại lệ (tt) Lan truyền ngoại lệ Thông thường, vị trí mà một ngoại lệ xuất hiện không phải là vị trí tốt nhất để xử lý nó. Khi một ngoại lệ được xử lý trong một chương trình con khác chứ không phải trong chương trình con mà nó được đề xuất thì ngoại lệ đó được gọi là được truyền (propagated) từ điểm mà tại đó nó được đề xuất đến điểm mà nó được xử lý. Ngoại lệ và xử lý ngoại lệ (tt) Quy tắc để xác định việc xử lý một ngoại lệ đặc thù thường được gọi là chuỗi động (dynamic chain) của các kích hoạt chương trình con hướng tới chương trình con mà nó đề xuất ngoại lệ. Ngoại lệ và xử lý ngoại lệ (tt) Khi một ngoại lệ P được đề xuất trong chương trình con C, thì P được xử lý bởi một xử lý được định nghĩa trong C nếu có một xử lý như thế. Nếu không có thì C kết thúc. Nếu chương trình con B gọi C thì ngoại lệ được truyền đến B và một lần nữa được đề xuất tại điểm trong B nơi mà B gọi C. Nếu B không cung cấp một xử lý cho P thì B bị kết thúc và ngoại lệ lại được truyền tới chương trình gọi B... Nếu các chương trình con và bản thân chương trình chính không có xử lý cho P thì toàn bộ chương trình kết thúc và xử lý chuẩn được định nghĩa bởi ngôn ngữ sẽ được gọi tới. Ngoại lệ và xử lý ngoại lệ (tt) Một hiệu quả quan trọng của quy tắc này đối với việc truyền các ngoại lệ là nó cho phép một chương trình con kế thừa (remain) như là một phép toán trừu tượng được định nghĩa bởi người lập trình ngay cả trong việc xử lý ngoại lệ. Ngoại lệ và xử lý ngoại lệ (tt) Một phép toán nguyên thuỷ có thể bất ngờ ngắt quá trình bình thường của nó và đề xuất một ngoại lệ. Tương tự, thông qua việc thực hiện lệnh RAISE, một chương trình con có thể bất ngờ ngắt quá trình bình thường của nó và đề xuất một ngoại lệ. Ðến chương trình gọi thì hiệu quả của đề xuất ngoại lệ của chương trình con cũng giống như hiệu quả đề xuất của phép toán nguyên thủy, nếu chương trình con tự nó không có một xử lý ngoại lệ. Nếu ngoại lệ được xử lý trong chương trình con thì chương trình con trở về một cách bình thường và chương trình gọi nó không bao giờ biết được rằng một ngoại lệ đã được đề xuất. CÂU HỎI ÔN TẬP CHƯƠNG 7 1. Khái niệm thuật toán đệ quy, ưu điểm và nhược điểm của đệ quy. 2. Viết chương trình để thực hiện các công việc sau: - In dãy số nguyên từ 1 đến 100 - Nhập vào một số nguyên n, tính tổng các số nguyên từ 1 đến n. - In ra dãy số 100 95 90 85 … 15 10 5 ra mà hình - Nhập vào một số nguyên n, tính tích các số lẻ từ 1 đến n. 3. Viết chương trình sử dụng thuật toán đệ quy in ra dãy số Fibonaci.