Bài giảng Tin học Lớp 10 - Bài 4: Bài toán và thuật toán

hi công Vậy để giải được bài toán ,tìm ra được Output thì phải có thuật toán để giải bài toán đó. Vậy thuật toán là gì ? Thuật toán để giải một bài toán là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự xác định sao cho sau khi thực hiện dãy thao tác ấy , từ input của bài toán , ta nhận được Output cần tìm. Có 2 cách thể hiện thuật toán : + Liệt kê dãy các thao tác + Sơ đồ khối + Ngôn ngữ giả pascal* Ví dụ như sau:	Tìm max, min của hai số nguyên.	- Nếu viết chương trình theo đề bài của bài toán thì sẽ tốn rất nhiều thời gian cho việc suy nghĩ để lập trình nên một chương trình. Vậy ta phải làm thế nào? Vậy muốn viết chương trình một bài toán có hiệu quả hơn thì trước hết chúng ta cần xác định bài toán, mô tả thuật toán rồi mới viết chương trình. Từ ví dụ trên chúng ta cần thực hiện như sau:* Xác định bài toán:Input: Hai số nguyên a và b	 Output: Giá trị lớn nhất max và nhỏ nhất min. * Thuật toán:Bước 1: Nhập a và bBước 2: Nếu a > b thì max  a; min  b; chuyển tới bước 4 Bước 3: Ngược lại, max  b; min  a;Bước 4: Thông báo kết quả. Biểu diễn thuật toán bằng sơ đồ khối Thể hiện phép so sánh Thể hiện các phép tính toán Thể hiện thao tác nhập, xuất Dliệu Quy định trình tự thực hiện các thao tác a>bNhập a,bMax:=a, Min:=bKết quảMax:=a, Min:=b* Chương trình: Program Tim_max_min; Var	a, b, max, min: Integer; BEGIN Clrscr; Write(‘Nhap vao gia tri cua a’ ); Readln (a); Write(‘Nhập vào giá trị của b’); Readln (b); If a > b then Begin Max := a; Min := b; End;	 Else	 Begin Max :=b; Min := a; End; Writeln (‘ max = ‘, max ); Writeln (‘ min = ‘, min ); END.Tính đúng đắn: Sau khi thuật toán kết thúc, ta phải nhận được Output cần tìm.Các đặc trưng chính của thuật toánTính dừng: Thuật toán phải kết thúc sau một số hữu hạn lần thực hiện các thao tác;Tính xác định: Sau khi thực hiện một thao tác thì hoặc là thuật toán kết thúc hoặc là có đúng một thao tác xác định để được thực hiện tiếp theo;3. Một số ví dụ về bài toán và thuật toán . Ví dụ 1: Tính tổng n số nguyên đầu tiên và đưa kết quả ra màn hình . Việc sử dụng lệnh có cấu trúc là để hợp lý hoá, tiết kiệm công sức lập trình, giản lược bớt các quá trình cả bài toán khi gặp bài toán phức tạp, xử lý việc lặp đi lặp lại nhiều lần một công việc chỉ bằng một câu lệnh hay một khối lệnh. Hơn nữa, lệnh có cấu trúc cũng giúp cho người lập trình dễ khoanh vùng và kiểm tra lỗi cho bài toán. Đây là một bài toán có thể sử dụng cấu trúc vòng lặp. Bởi vì cấu trúc vòng lặp cho phép lặp lại nhiều lần một công việc (được thể hiện bằng một câu lệnh hay một khối lệnh) nào đó cho đến khi thoả mãn một điều kiện cụ thể. Nếu chỉ sử dụng câu lệnh thông thường thì chúng ta sẽ mất rất nhiều thời gian để lặp lại việc tính tổng, nếu số n nhập và nhỏ thì đơn giảnnhưng nếu gia trị n được nhập vào lớn một chút thì sẽ gặp khó khăn trong việc tính toán.	Cụ thể bài toán ta có thể sử dụng vòng lặp For cho phép lặp lại công việc cho đến khi điều kiện sai.* Xác định bài toán: - Input: Dãy N số tự nhiên 	 - Output: Giá trị của tổng* Thuật toán:Bước 1: nhập số nguyên N , a[i];Bước 2: T 0 Bước 3: i  i + 1; Bước 4: Nếu i  N, thì T  T + a[i] và quay lại bước 3. Bước 5: Thông báo kết quả và kết thúc thuật toán.* Chương trình được viết như sau: Program tinhtong; Uses wincrt; Var i , n , T: integer; a:array [1..100] of integer; BEGIN Write ('nhap vao so n = '); readln(n); for i:=1 to n do Begin write('[a',i,']='); readln(a[i]); end; write('day n la:'); for i:=1 to n do Begin write(a[i]:3); end; writeln; T:=0; For i:=1 to n do Begin T:=T+a[i] end; Writeln('Tong cua day la:',T); END. - Giải thích : Nếu chúng ta nhập vào số 9 và nhấn enter thi kết quả hiển thị ra màn hình sẽ như sau: Nhap vao so nguyen duong n = 4 Nhập các a[i] là : a[1] = 3 , a[2] = 8 , a[3] = 12 , a[4] = 20.	 Tổng của dãy là: 43 Như vậy, ở đây ta chỉ dùng một câu lệnh lặp For mà ta có thể tối ưu hoá được số bước lặp đi lặp lại nhiều lần của một công việc tính tổng.3Người ta đặt 5 quả bóng có kích thước khác nhau trong hộp đã được đậy nắp như hình bên. Chỉ dùng tay hãy tìm ra quả bóng có kích thước lớn nhất .Thuật toán tìm max Các khái niệm : - Bài toán là một việc nào đó ta muốn máy tính thực hiện . - Thuật toán để giải một bài toán là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự xác định sao cho sau khi thực hiện dãy thao tác ấy, từ Input của bài toán, ta nhận được Output cần tìm.Xác định bài toán và mô tả thuật toán: * Xác định bài toán:- Input: Số nguyên dương N và dãy N số nguyên a1 ..., aN.- Output: Giá trị lớn nhất Max của dãy số.* Mô tả thuật toán: Bước 1: Nhập N và dãy a1, ..., aN;Bước 2: Max  a1; i  2;Bước 3: Nếu i > N thì đưa ra giá trị Max rồi kết thúc; Bước 4. Nếu ai > Max thì Max  ai;Bước 5. i  i + 1 rồi quay lại bước 3;Quả này lớn nhất Quả này mới lớn nhất ồ! Quả này lớn hơn Tìm ra quả lớn nhất rồi! Cùng tìm thuật toán MAXThuật toán tìm số lớn nhất trong một dãy số nguyên Xác định bài toán:INPUT: Số nguyên dương N và dãy N số 	nguyên a1, a2, , aN (ai với i: 1N).	OUTPUT: Số lớn nhất (Max) của dãy số.ý tưởng: - Đặt giá trị Max = a1. - Lần lượt cho i chạy từ 2 đến N, so sánh giá trị ai với giá trị Max, nếu ai > Max thì Max nhận giá trị mới là ai.Cách 1: Liệt kê các bước B1: Nhập N và dãy a1,, aN; B2: Max  a1; i  2; B3: Nếu i > N thì đưa ra giá trị Max rồi kết thúc; B4:	Bước 4.1: Nếu ai > Max thì Max  ai;	Bước 4.2: i  i+1 rồi quay lại B3.ĐSĐSNhập N và dãy a1,,aNMax  a1 ; i  2i > N ?ai > Max ? Max  aii  i + 1Đưa ra Max rồi kết thúc B1: Nhập N và dãy a1,,aN; B2: Max  a1; i  2; B3: Nếu i > N thì đưa ra giá trị  Max rồi kết thúc; B4 : 4.1: Nếu ai > Max thì Max  ai; 4.2: i  i + 1 rồi quay lại B3.Cách 2: Sơ đồ khối* Chương trình của bài toán: Program max1; uses wincrt; var i,n,max:integer; a : array [1..100]of integer; BEGIN write('Nhap n=');readln(n); for i:=1 to n do begin write('a[',i,']=');readln(a[i]); end; Write('Day cac so la:'); For i:=1 to n do Begin write(a[i]:3); end; Max:=a[1]; For i:=1 to n do Begin if (a[i]>max) then max:=a[i]; end; writeln; write('Gia tri Max=',max); END.ĐSĐSNhập N và dãy a1,,aNMax  a1 ; i  2I > N ?ai> Max ? Max aii  i+1Đưa ra Max rồi kết thúcMaxiA77555543267415N=5 ; A [ 5 1 4 7 6 ]Max  5 ; i  22 > 5 ?1> 5 ?i  2+13 > 5 ?4> 5 ?i 3+14 > 5 ?7 > 5 ? Max 74i 4+15 > 5 ?7 > 7 ?i 5+16 > 5 ?Số lớn nhất của dãy là 7Mô phỏng thuật toán Với i = 2Với i = 3Với i = 4Với i = 5ĐSĐSNhập N và dãy a1,,aNMax  a1 ; i  2I > N ?ai> Max ? Max aii  i+1Đưa ra Max rồi kết thúcMaxiA77555543267415N=5 ; A [ 5 1 4 7 6 ]Max  5 ; i  22 > 5 ?1> 5 ?i  2+13 > 5 ?4> 5 ?i 3+14 > 5 ?7 > 5 ? Max 74i 4+15 > 5 ?7 > 7 ?i 5+16 > 5 ?Số lớn nhất của dãy là 7Hãy tìm cách sắp xếp học sinh đứng chào cờ (hình a) theo thứ tự thấp trước cao sau (hình b).Hình aHình bThuật toán sắp xếp Xác định bài toán: Input: Dãy A gồm N số nguyên a1, a2,, aN. Output: Dãy A được sắp xếp thành dãy không giảm. Khi lập trình với những câu lệnh được lặp đi lặp lại nhiều lần ta có thể sử dụng chương trình con để tiện lợi cho việc sửa chữa, khoa học hơn, tiện lợi hơn cho việc lập trình . Với thuật toán này  ý tưởng: Với mỗi cặp số hạng đứng liền kề trong dãy, nếu số trước lớn hơn số sau ta đổi vị trí chúng cho nhau. Việc đó được lặp lại cho đến khi không có sự đổi chỗ nào xảy ra nữa. Cách 1: Liệt kê các bướcB1: Nhập N, các số hạng a1, a2,, aN; B2: M  N;B3: Nếu M M thì quay lại B3;B7: Nếu ai > ai+1 thì tráo đổi ai và ai+1 cho nhau;B8: Quay lại B5.Nhập N và a1, a2,..., aN M  NM M ?ai > ai+1 ?Tráo đổi ai và ai+1Đưa ra A đã sắp xếprồi kết thúcĐĐĐSSSCách 2 Vẽ sơ đồ khối Program sapxep; Uses wincrt; Var tg ,i ,j ,n ,max :integer; a : array [1..100]of integer; Procedure nhap; Begin write('Nhap n=');readln(n); for i:=1 to n do Begin write('a[',i,']=');readln(a[i]); End; End;Procedure int; Begin For i:=1 to n doBegin write(a[i]:3); End; End; Procedure sxep; Begin For i:=1 to n-1 do for j:=i+1 to n do Begin if a[i]>a[j] then Begin tg:=a[i]; a[i]:=a[j]; a[j]:=tg; EEnd; End; Writeln; Write('Day cac so SX la:'); Int; End; {***************} BEGIN nhap; Write('Day cac so la:'); int; sxep; END. Với N = 6 và dãy A gồm 6 số hạng như sau : 359817 Lượt thứ nhất: 359817358917358197358179 Lượt thứ hai: 358179351879351789 Lượt thứ ba: 351789315789315789135789 Lượt thứ tư: Mô phỏng thuật toán sắp xếp bằng tráo đổi Trong chương trình trên có nhiều câu lệnh được lặp lại nhiều lần như nhóm lệnh in dãy. Nhờ việc tạo chương trình con ta giảm bớt được số lần lệnh, nhìn vào cấu trúc lập trình ta thấy khoa học ,tiện lợi hơn . Để hiểu rõ thuật toán sắp xếp vấn đề ngược lại là làm thế nào để viết được thuật toán sắp xếp dãy A theo chiều giảm dần (sắp xếp không tăng). Muốn viết thuật toán cho dãy A giảm dần thì chỉ cần thay đổi thao tác so sánh trong thuật toán (cụ thể là thay ai>aj (với aj = ai +1 )bằng ai M thì quay lại Bước 4; Bước 8 : Nếu ai N thì thông báo dãy A không có số hạng nào có giá trị bằng k, rồi kết thúc; Bước 6: Quay lại B3.Nhập N, a1, a2,..., aN và ki  1ai = k ?Đưa ra irồi kết thúcĐSĐi i + 1i > N ?Thông báo dãy A không có số hạng có giá trị bằng k, rồi kết thúcSCách 2 Vẽ sơ đồ khối* Chương trìnhProgram timkiem; Uses wincrt; Type Mang = ARRAY[1..50] Of Integer; Var tg,i,k,j,n,max:integer; a :mang; Procedure nhap; Begin write('Nhap n=');readln(n); for i:=1 to n do Begin write('a[',i,']=');readln(a[i]); end; end; {*******************} Procedure int; Begin For i:=1 to n do Begin write(a[i]:3); end; End; {********************} Function TKiem(k, n:integer; a:mang):Integer; Var i:Integer; Begin i:=1; While (i a[i]) do i:=i+1; If i 0 Then Writeln('Vi tri cua', k:3,' trong mang la:', TKiem(k,n,a):3) Else Writeln(k,' khong co trong day.'); Readln; END.54321I5125118924175A Mô phỏng thuật toán tìm kiếm tuần tự  Với k = 2 và dãy A gồm 10 số hạng như sau: Tại vị trí i = 5 có a5 = 2 = k Với k = 6 và dãy A gồm 10 số hạng như sau: A5714298112551I1234567891011 Với mọi i từ 1 10 không có ai có giá trị bằng 6 5The end