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¶

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.



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ử đ ợc xem nh một bọt n ớc;
Lợt1:

i chạy từ đầu dãy đến vị
trí[cuốidãy-1]

Khia[i]>a[i+1]tứclàbọtn
ớ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
ớcbêndớinổilên(tráo đổi
vị trí).

biết trong Pascal
nhận xét 1 đ ợ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 : ’);
readln(n);

* 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ừ ý t ởng trên hãy
viết đoạn ch ơ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)
else writeln(Khong tim thay);

;
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 ch a tìm thấy hoặc
Dau <= Cuoi.