Bài giảng Tin học Lớp 10 - Tiết 21: Một số ví dụ - Trường THPT Tam Giang

NHIỆT LIỆT CHÀO MỪNG QUÝ THẦY CÔ ĐẾN DỰ GIỜ THĂM LỚP	KIỂM TRA BÀI CŨPhát biểu khái niệm mảng một chiều, cú pháp khai báo mảng, cách thức để tham chiếu đến các phần tử trong mảng? bµi to¸n s¾p xÕp bµi to¸n t×m max, min SỞ GIÁO DỤC VÀ ĐÀO TẠOTHỪA THIÊN HUẾ1. T×M GI¸ TRÞ MAX.2. Sắp xếp.a. Bài toánb. Thuật toán1. Tìm giá trị max, min.c. Chương trìnhBài toán: Cho mảng A chứa các số nguyên dương như sau: 2, 7, 6, 9, 1, 4. Hãy tìm giá trị lớn nhất và vị trí xuất hiện của chúng trong mảng trên:276914A:123456a. Khái niệmb. Thuật toánc. Chương trìnhSỞ GIÁO DỤC VÀ ĐÀO TẠOTHỪA THIÊN HUẾ Thuật toán tìm max:276914A:1234561. T×M GI¸ TRÞ MAX.B1: Nhập mảng A cho trước; (n phần tử)B2: max  A1, i  1;B3: Nếu i>n thì thông báo max rồi kết thúc;B41: Nếu Ai > max thì max  Ai;B42: i  i+1 rồi quay lại B3; Đầu tiên gán giá trị của phần tử thứ nhất cho biến max, tiếp theo lần lượt so sánh giá trị của max với tất cả các phần tử còn lại, nếu giá trị của max nhỏ hơn giá trị của phần tử đang so sánh thì gán ngay giá trị đó cho max; như vậy đến lượt so sánh cuối cùng sẽ tìm được giá trị của max. 2. Sắp xếp.a. Bài toánb. Thuật toán1. Tìm giá trị max, min.c. Chương trìnha. Khái niệmb. Thuật toánc. Chương trìnhSỞ GIÁO DỤC VÀ ĐÀO TẠOTHỪA THIÊN HUẾ Minh họa thuật toán tìm max:26914A:123456TF7TFF279Max1. T×M GI¸ TRÞ MAX.2. Sắp xếp.a. Bài toánb. Thuật toán1. Tìm giá trị max, min.c. Chương trìnha. Khái niệmb. Thuật toánc. Chương trình THUẬT TOÁN	 THỂ HIỆN BẰNG PASCALB1. Nhập N và dãy a1aN;Write(‘nhap so luong phan tu cua mang:’);Readln(N);For i:=1 to N do Begin Write(‘phan tu thu’,i); Readln(a[i]); End;B2. Max← a[1], i ←1;Max:=a[1];	csMax:=1;B3. Nếu i>N thì đưa ra Max rồi KTB4. B41. Nếu a[i]>Max thì Max ←a[i] B42. i ←i+1 rồi quay lại B3For i:=2 to N do if a[i]>Max then 	begin	 Max:=a[i]; 	 csMax:=i; 	end;Writeln(‘GTLN la:’,Max,’Vi tri:’,csMax);Type arrInt=array[1..250] of integer;Var N, i , max, csmax : integer; a: arrInt;Program tim_max;Begin	Write(‘nhap so luong phan tu cua mang:’);	Readln(N);	For i:=1 to N do 	Begin 	Write(‘phan tu thu’,i); 	Readln(a[i]); 	End;max:=a[1]; csmax:=1;For i:=2 to N do if a[i]>max then 	begin	 max:=a[i]; 	 csmax:=i; 	end;	Write(‘Gia tri lon nhat la:’, max:4, ‘Vi tri dat max la:’, csmax:4);End.SỞ GIÁO DỤC VÀ ĐÀO TẠOTHỪA THIÊN HUẾ Minh họa thuật toán tìm min: (tương tự max)26914A:123456FF7FTF2Min11. T×M GI¸ TRÞ MIN.2. Sắp xếp.a. Bài toánb. Thuật toán1. Tìm giá trị max, min.c. Chương trìnha. Khái niệmb. Thuật toánc. Chương trìnhType arrInt=array[1..250] of integer;Var N, i , min, csmin : integer; a: arrInt;Program tim_min;Begin	Write(‘nhap so luong phan tu cua mang:’);	Readln(N);	For i:=1 to N do 	Begin 	Write(‘phan tu thu’,i); 	Readln(a[i]); 	End;min:=a[1]; csmin:=1;For i:=2 to N do if a[i]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.  Sơ đồ khối. M  NNhËp N vµ a1, a2,..., aNM  M – 1; i  0M M ? §óngSaiai > ai+1 ?i  i + 1 §­a ra A råi kÕt thóc§óngSaiSai§óngTr¸o ®æi ai vµ ai+1b. Thuật toán sắp xếp trao đổi:32976Giả sử:	Mỗi phần tử trong dãy được xem như là một bọt nước,	Trọng lượng của bọt nước thứ i là giá trị của A[i].Lượt 1 i chạy từ đầu dãy đến vị trí [cuối dãy -1] Khi a[i]>a[i+1] tức bọt nước bên trên nặng hơn bọt nước bên dưới, bọt nước trên chìm xuống và bọt nước bên dưới nổi lên (tráo đổi vị trí) Sau lượt 1 bọt nước nặng nhất sẽ chìm về cuối dãy.Lượt 2 i chạy từ đầu đến vị trí [cuối dãy -1] bỏ qua phần tử cuối cùng Sau lượt thứ 2 bọt nước nặng thứ 2 sẽ chìm về kế cận đáy. Quá trình duyệt, tráo đổi được lặp đi lặp lại cho đến khi duyệt chỉ còn 2 phần tử và dãy sẽ được sắp xếpCHO DÃY SỐ SAU:	3	2	9	7	6Nhận xét: Ta thấy rằng, sau mỗi lần đổi chỗ, giá trị lớn nhất của dãy A sẽ được chuyển dần về cuối dãy và sau lượt thứ nhất thì giá trị lớn nhất xếp đúng ở vị trí cuối dãy.	Tương tự: Sau lượt thứ hai, giá trị lớn thứ hai được xếp đúng ở vị trí sát cuối dãy, Có thể hình dung, sau mỗi lượt có ít nhất 1 số hạng đã được xếp đúng vị trí và không còn tham gia vào quá trình đổi chỗ nữa, giống như các bọt nước từ đáy hồ (đầu dãy) nổi dần và khi đã lên mặt nước (cuối dãy) rồi thì tan biến. Có thể vì thế mà sắp xếp bằng tráo đổi còn có tên gọi là sắp xếp nổi bọt (Bubble Sort).2. Sắp xếp.a. Bài toánb. Thuật toán1. Tìm giá trị max, min.c. Chương trìnha. Khái niệmb. Thuật toánc. Chương trìnhSỞ GIÁO DỤC VÀ ĐÀO TẠOTHỪA THIÊN HUẾNHẬN XÉT: ĐƯA RA ĐOẠN LỆNH SẮP XẾP1Số phần tử ở các lần duyệt (j) sẽ giảm từ n xuống 2 phần tửViệc giảm dần giá trị các lần duyệt cho phép loại ra các giá trị lớn nhất ở cuối dãy. Thể hiện bằng cấu trúc lệnh nào?for j:=N downto 2 do2ĐOẠN CHƯƠNG TRÌNH TRÁO ĐỔITại mỗi lần duyệt (ứng với mỗi lần duyệt của j)- Cho i chạy từ 1 đến số phần tử -1 Nếu A[i]>A[i+1] thì Tráo đổi A[i] với A[i+1] thông qua biến trung gian (tg) for i:=1 to j-1 do if A[i]>A[i+1] then begin	 tg:=A[i];	 A[i]:=A[i+1];	 A[i+1]:=A[i]; end;Type	arrInt=array[1..250] of integer;Var	N, i , j , tg : integer; A: arrInt;Begin	write(‘nhap so luong phan tu cua day, N= ’); readln(N); 	for i:=1 to N do	 begin	 write(‘Nhap phan tu thu’,i);	 readln(A[i]); 	 end;	for j:=N downto 2 do	 for i:=1 to j-1 do	if A[i] > A[i+1] then	 begin	tg:=A[i]; 	A[i]:=A[i+1]; 	A[i+1]:=tg;	 end;	writeln(‘Day duoc sap xep la:’);	for i:=1 to N do write(A[i]:4);	readln;End.Program sap_xep_mang;SỞ GIÁO DỤC VÀ ĐÀO TẠOTHỪA THIÊN HUẾ2. Sắp xếp.a. Bài toánb. Thuật toán1. Tìm giá trị max, min.c. Chương trìnha. Khái niệmb. Thuật toánc. Chương trìnhCỦNG CỐDẶN DÒ	 Kiểu mảng là một kiểu dữ liệu có cấu trúc được dùng nhiều trong lập trình. Những bài toán sắp xếp, tìm kiếm là các bài toán thường gặp và có ý nghĩa quan trọng, cần nắm kỹ thuật toán, cấu trúc dữ liệu để giải quyết các bài toán trên.	 Kiểu mảng một chiều thường được dùng trong những chương trình cần tổ chức dữ liệu như một dãy các phần tử cùng kiểu để giải quyết các bài toán đặt ra.	 Khi cần tổ chức dữ liệu có cấu trúc bảng, ta nghĩ đến việc dùng mảng hai chiều. (về nhà xem nội dung bài mảng hai chiều)