Bµi
13
Gi¸o ¸n ®iÖn tö tin häc líp 11

Bài 1. Tìm phần tử lớn nhất của dãy số nguyên
(với n 250 và A[i] 500
),
nếu dãy có nhiều phần tử cùng giá trị thì đ'a ra chỉ số của phần tử lớn nhất
đầu tiên.
Hãy xác định
Input, Output và
nêu thuật toán
tìm Max?
* INPUT: Nhập số nguyên dơng n và dãy n số
nguyên dơng a
1
,a
2
, ,a
n
.
* OUTPUT: Chỉ số và giá trị của phần tử lớn nhất
trong dãy.

Qu¶ nµy
lín nhÊt
Qu¶ nµy
míi lín
nhÊt
å! Qu¶

vµ chØ sè i => KÕt thóc;
4. NÕu a[i]>max th× max←a[i],
i ← i+1 => quay l¹i bíc 3.

Program Tim_Max;
Uses crt;
Type dayso = Array[1 250] of integer;
Var
A : dayso ;
i,n,max,csmax : integer;
BEGIN
Clrscr;
write(‘ Nhap vao so phan tu cua day so : ’) ;
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 := 1 to n do
If (A[i]>max) Then
begin
max := a[i];
csmax=i;
end;
Writeln(‘ Gia tri cua phan tu Max : ’,Max) ;
Writeln(‘ Chi so cua phan tu Max : ’, csmax) ;
Readln ;
END.

* OUTPUT: Dãy số đợc sắp xếp theo trình tự không giảm.

Các em hãy cho
biết để giải bài
toán trên, ở lớp 10
chúng ta dùng
thuật toán gì?
Là Thuật toán
tráo đổi kiểu
nổi bọt từ trên
xuống!

3
2
9
7
6
Cho dãy số sau: 3 2 9 7 6
Giả sử:
Mỗi phần tử đBợc xem nhB một bọt nBớc;
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 là 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

Các em hãy cho
biết trong Pascal
nhận xét 1 đBợc
thể hiện bằng
lệnh gì ?
1
For j := n downto 2 do
2
For i := 1 to j-1 do
IF A[i]>A[i+1] then
Tg := A[i];
A[i] := A[i+1];
A[i+1]:=Tg;
Begin
end;

Khai b¸o m¶ng 1 chiÒu
NhËp m¶ng 1 chiÒu
Xö lÝ m¶ng b»ng thuËt
to¸n næi bät
In kÕt qu¶
PROGRAM Sapxep;
Uses crt;
Type dayso = Array[1 250] of integer;
Var
i, j , n , tg : integer;
A : dayso;
BEGIN
Clrscr;
write(‘ Nhap vao so phan tu cua day so : ’);

và số nguyên k
* OUTPUT: Chỉ số i mà a
i
= k hoặc thông báo Không
tìm thấy nếu không có số hạng nào của
dãy A có giá trị bằng k.

Các em hãy
nêu các cách
để giải bài toán
trên ?
Lần lợt từ số hạng thứ nhất, so sánh giá trị số hạng
đang xét với k cho đến khi gặp đợc số hạng bằng k,
hoặc dãy đã đợc xét hết và không có số hạng nào
có giá trị bằng k.
Từ ý tBởng trên hãy
viết đoạn chBơng
trình bằng PASCAL
để tìm số hạng của
dãy có giá trị bằng
k?
For i := 1 to n do
IF A[i] = k then
Begin
Tim_thay:=true;
cs:=i;
break;
end;
Tim_thay := false;
IF tim_thay then writeln(Chi so tim duoc: ,i)

7
;
Lợt thứ ba: a
giữa
là a
6
= 21; 21= 21
Vậy chỉ số cần tìm là i = 6.
22
21
66
21

Dau:=1; Cuoi:=n; tim_thay:=false;
while ( Dau<= Cuoi) or NOT(tim_thay) do
Begin
Giua:= (Dau+Cuoi) div 2;
IF A[giua] = k then Tim_thay :=true
else
IF (A[Giua]>k) then Cuoi := Giua 1
else Dau := Giua +1;
end;
IF Tim_thay then Writeln( Chi so tim duoc la : ,Giua)
Else Writeln(Khong tim thay);
Vì dãy A là dãy tăng, ta thực hiện thu hẹp nhanh phạm vi tìm
kiếm bằng cách so sánh k với A[giua] và xét các trờng hợp:
- A[giua]=k tìm thấy chỉ số giữa và kết thúc;
- A[giua]>k Thu hẹp về phía bên trái (Cuối = Giữa -1);
- A[giua]<k Thu hẹp về phía bên phải (Đầu = Giữa +1);
Quá trình trên đợc lặp lại chừng nào còn cha tìm thấy