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

Tin học 
Bài 4 : Bài toán và thuật toán 
Kiểm tra bài cũ 
Câu hỏi 1 : Kể tên các thiết bị vào ? 
Câu hỏi 2 : Kể tên các thiết bị ra ? 
1. Các thiết bị vào gồm : Bàn phím , chuột , máy quét , webcam. 
2 . Các thiết bị ra gồm : Máy in, máy chiếu , loa và tai nghe , modem. 
 Trong thực tế ta thấy có nhiều bài toán cần giải quyết . Chẳng hạn : Một công ty xây dựng nhận đư ợc một công trình giao thông với một số vốn nhất đ ịnh . Để hoàn thành công trình đảm bảo chất lượng và có lợi nhuận cho công ty th ì công ty này phải đề ra và thực hiện một loạt các khâu , biện pháp nh ư mua sắm trang thiết bị , vật liệu hợp lí , đ ẩy mạnh tiến độ thi công  
 Trong tin học cũng có những bài toán dạng nh ư vậy . Để giải quyết những bài toán này ta phải có những thuật toán . Bài hôm nay chúng ta sẽ tìm hiểu về vấn đề này . 
 Trở lại bài toán trong ví dụ trên ta thấy Công ty trên với số vốn và bản thiết kế muốn hoàn thành tốt công trình và có lợi nhuận cho công ty th ì câu hỏi đ ặt ra là phải làm thế nào ? 
1. Khái niệm bài toán 
 Bài toán là việc nào đ ó ta muốn máy thực hiện để từ thông tin đưa vào (INPUT) tìm đư ợc thông tin ra (OUTPUT ). 
 Trở lại lĩnh vực tin học th ì bài toán đư ợc hiểu nh ư thế nào ?  
Ví dụ 1: Tìm ư ớc số chung lớn nhất của hai số nguyên dương . 
Ví dụ 2: Bài toán kiểm tra tính nguyên tố . 
 Input: Hai số nguyên dương M và N. 
 Output: Ư ớc số chung lớn nhất của M và N. 
 Input : Số nguyên dương N. 
 Output : “ N là số nguyên tố ” hoặc “ N không là số nguyên tố ”. 
2. Khái niệm thuật toán 
Từ INPUT làm thế nào để tìm ra OUTPUT ? 
Các em cần tìm ra cách giải của bài toán . 
 Trở lại ví dụ thực tế : Từ một nguồn vốn nhất đ ịnh và bản thiết kế . Làm thế nào để đ ầu ra là công trình hoàn thành có chất lượng và có lợi nhuận ? Để làm đư ợc đ iều này đ òi hỏi công ty phải có một quy trình với một loạt các biện pháp đư ợc thực hiện nh ư mua sắm trang thiết bị , vật liệu hợp lí , đ ẩy mạnh tiến độ thi 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à b 
Bướ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>b 
Nhập a,b 
Max:=a, Min:=b 
Kế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án 
Tí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ản 
như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 : 
 P rogram 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 
 B egin 
 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 . 
3 
Ngườ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  a 1; 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  a i; 
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 
MAX 
Thuậ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 a 1 , a 2 , , a N ( a i với i: 1 N). 	  OUTPUT: Số lớn nhất (Max) của dãy số . 
ý tưởng : - Đ ặt gi á trị Max = a 1 .  - Lần lượt cho i chạy từ 2 đ ến N, so sánh  gi á trị a i với gi á trị Max, nếu a i > Max th ì Max nhận gi á trị mới là a i . 
Cách 1: Liệt kê các bước 
 B1: Nhập N và dãy a 1 ,, a N ; 
 B2: Max  a 1 ; 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 a i > Max th ì Max  a i ;	 Bước 4.2: i  i+1 rồi quay lại B3. 
Đ 
S 
Đ 
S 
Nhập N và dãy a1,, aN 
Max  a1 ; i  2 
i > N ? 
a i > Max ? 
 Max  a i 
i  i + 1 
Đưa ra Max rồi kết thúc 
 B1: Nhập N và dãy a 1 ,, a N ; 
 B2: Max  a 1 ; i  2; 
 B3: Nếu i > N th ì đưa ra gi á trị  Max rồi kết thúc ; 
 B4 : 4.1: Nếu a i > Max th ì Max  a i ; 
 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 
Đ 
S 
Nhập N và dãy a1,, aN 
Max  a1 ; i  2 
I > N ? 
a i > Max ? 
 Max  a i 
i  i+1 
Đưa ra Max rồi kết thúc 
Max 
i 
A 
7 
7 
5 
5 
5 
5 
4 
3 
2 
6 
7 
4 
1 
5 
N=5 ; A [ 5 1 4 7 6 ] 
Max  5 ; i  2 
2 > 5 ? 
1> 5 ? 
i  2+1 
3 > 5 ? 
4> 5 ? 
i 3+1 
4 > 5 ? 
7 > 5 ? 
 Max 7 
4 
i 4+1 
5 > 5 ? 
7 > 7 ? 
i 5+1 
6 > 5 ? 
Số lớn nhất của dãy là 7 
Mô phỏng 
thuật toán 
Với i = 2 
Với i = 3 
Với i = 4 
Với i = 5 
Đ 
S 
Đ 
S 
Nhập N và dãy a1,, aN 
Max  a1 ; i  2 
I > N ? 
a i > Max ? 
 Max  a i 
i  i+1 
Đưa ra Max rồi kết thúc 
Max 
i 
A 
7 
7 
5 
5 
5 
5 
4 
3 
2 
6 
7 
4 
1 
5 
N=5 ; A [ 5 1 4 7 6 ] 
Max  5 ; i  2 
2 > 5 ? 
1> 5 ? 
i  2+1 
3 > 5 ? 
4> 5 ? 
i 3+1 
4 > 5 ? 
7 > 5 ? 
 Max 7 
4 
i 4+1 
5 > 5 ? 
7 > 7 ? 
i 5+1 
6 > 5 ? 
Số lớn nhất của dãy là 7 
Hã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 a 
Hình b 
Thuật toán sắp xếp 
 Xác đ ịnh bài toán :  Input: Dãy A gồm N số nguyên a 1 , a 2 ,, a N . 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ước 
B1: Nhập N, các số hạng a 1 , a 2 ,, a N ; 
B2: M  N; 
B3: Nếu M < 2 th ì đưa ra dãy A đã sắp xếp rồi kết thúc ; 
B4: M  M – 1; i  0; 
B5: i  i +1; 
B6: Nếu i > M th ì quay lại B3; 
B7: Nếu a i > a i+1 th ì tráo đ ổi a i và a i+1 cho nhau ; 
B8: Quay lại B5. 
Nhập N và a 1 , a 2 ,..., a N 
M  N 
M < 2 ? 
M  M - 1; i  0 
i  i + 1 
i > M ? 
a i > a i+1 ? 
Tráo đ ổi 
a i và a i+1 
Đưa ra A đã sắp xếp 
rồi kết thúc 
Đ 
Đ 
Đ 
S 
S 
S 
Cá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 do 
Begin 
 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 : 
3 
5 
9 
8 
1 
7 
 Lượt thứ nhất : 
3 
5 
9 
8 
1 
7 
3 
5 
8 
9 
1 
7 
3 
5 
8 
1 
9 
7 
3 
5 
8 
1 
7 
9 
 Lượt thứ hai : 
3 
5 
8 
1 
7 
9 
3 
5 
1 
8 
7 
9 
3 
5 
1 
7 
8 
9 
 Lượt thứ ba : 
3 
5 
1 
7 
8 
9 
3 
1 
5 
7 
8 
9 
3 
1 
5 
7 
8 
9 
1 
3 
5 
7 
8 
9 
 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 a i > a j ( với 
a j = a i +1 ) bằng a i < a j ), Từ đ ó dễ dàng có thể đưa ra lời giải dưới đây: 
* Xác đ ịnh bài toán 
Input: Dãy A gồm n số nguyên a 1 ,a 2 ,...,a n . 
 Output: Dãy A đư ợc sắp xếp thành dãy không tăng 
 Bước 1: Nhập n, các số hạng a1,aư2,...,an; 
 Bước 2: In dãy số hạng a1,aư2,...,an; 
 Bước 3:: M  N; 
 Bước 4: Nếu M < 2 th ì đưa ra dãy A đã sắp xếp rồi kết thúc ; 
 Bước 5: M  M – 1; i  0; 
 Bước 6: i  i +1; 
 Bước 7: Nếu i > M th ì quay lại Bước 4; 
 Bước 8 : Nếu ai < ai +1 thì tráo đổi ai và ai +1 cho nhau; 
 Bước 9 : Quay lại bước 6. 
* Chương trình : Viết tương tự nh ư sắp xếp dãy tăng dần 
* Thuật toán : 
 Xác đ ịnh bài toán :  INPUT: Dãy A gồm N số nguyên a 1 , a 2 ,, a N đôi một khác nhau và số nguyên k. OUTPUT: Chỉ số i mà a i = k hoặc thông báo  không có số hạng nào của A bằng k . 
Thuật toán tìm kiếm tuần tự 
 Bài toán : Cho dãy A gồm n số nguyên a 1 ,a 2 ,...,a n . Nhập thêm một số nguyên k. Hãy kiểm tra xem k có trong dãy hay không ? 
ý tưởng : 	 
 Từ bước 3 đ ến bước n chúng ta tìm kiếm và kiểm tra đư ợc số nguyên k có ở trong mảng hay không ?. 
Bước 1 : Thực hiện công việc so sánh k với phần tử thứ nhất . 
Bước 2 : So sánh k với phần tử thứ hai . 
Cách 1: Liệt kê các bước 
 Bước 1: Nhập N, các số hạng a 1 , a 2 ,, a N  và gi á trị kho á k; 
 Bước 2: i  1; 
 Bước 3: Nếu a i = k th ì thông báo chỉ số i, rồi kết thúc ; 
 Bước 4: i  i+1; 
 Bước 5: Nếu i > 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, a 1 , a 2 ,..., a N 
 và k 
i  1 
a i = k ? 
Đưa ra i 
rồi kết thúc 
Đ 
S 
Đ 
i  i + 1 
i > 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úc 
S 
Cách 2 
Vẽ sơ đ ồ khối 
* Chương trình 
Program 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 <= n Then Tkiem :=i Else Tkiem :=0; 
 End; 
 BEGIN 
 nhap ; 
 write('day vao la'); 
 int ; 
 writeln ; 
 write('nhap k='); readln(k ); 
 If TKiem(k,n,a )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. 
5 
4 
3 
2 
1 
I 
51 
25 
11 
8 
9 
2 
4 
1 
7 
5 
A 
 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ó a 5 = 2 = k 
 Với k = 6 và dãy A gồm 10 số hạng nh ư sau : 
A 
5 
7 
1 
4 
2 
9 
8 
11 
25 
51 
I 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
 Với mọi i từ 1  10 không có a i có gi á trị bằng 6 
5 
The end