Bài giảng Điện tử Tin học lớp 11 - Bài 13: Bài tập mảng một chiều cung cấp cho các em một số bài tập về tìm phần tử lớn nhất của dãy số, thuật toán tìm max, tìm kiếm tuần tự, tìm kiếm nhị phân. Những bài tập này sẽ giúp các em ứng dụng giải toán nhanh trên máy tính.
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng Điện tử Tin học lớp 11: Bài 13
- Bµi 13
Gi¸o ¸n ®iÖn tö tin häc líp 11
- Bµi 1. T× phÇn tö lín nhÊt cña d·y sè nguyªn (v íi n ≤ 250 v µ A[i] ≤
m
500), nÕu d·y cã nhiÒu phÇn tö cïng gi¸ trÞ th× ® ra chØ sè cña
a
phÇn tö lín nhÊt ® tiªn.
Çu
* INPUT: NhËp sè nguyªn d¬ n H·y d·y n®Þnh
ng vµ x¸c sè nguyªn d¬ng
a1,a2,...,an. Inp ut, Outp ut v µ
nª u thuËt to ¸n
t×m Max?
* OUTPUT: ChØ sè vµ gi¸ trÞ cña phÇn tö lín nhÊt trong d·y.
- thuËt to¸n t× max
m
Qu¶ nµy
míi lín nhÊt å! Qu¶ nµy
T× ra qu¶
m
Qu¶ nµy lín lín nhÊt råi!
lín h¬n
nhÊt
MAX
- 1. NhËp n vµ d·y a 1,...,a n; Write(‘ Nhap vao so luong phan tu:’);
Readln(n);
For i:=1 to n do
begin
write(‘ Phan tu thu ’ ,i, ’ = ’);
readln(a[i])
end;
2. Max ← a1 ; i ← 1; Max:=a[1]; csmax:=1;
3. NÕu i>N ®a ra MAX vµ For i :=2 to n do
c hØ s è i => KÕt thó c ; IF a[i]>max then
begin
4. NÕu a[i]>max th× max←a[i],
max:=a[i];
i ← i+1 => quay l¹i bíc 3. csmax:=i;
end;
- Pro g ram Tim_Max;
Us e s c rt;
Type days o = Array[1..250] o f inte g e r;
Var
A : dayso ;
i,n,max,c s max : inte g e r;
BEGIN
Clrs c r;
write (‘ Nhap vao s o phan tu c ua day s o : ’) ;
re adln(n) ;
Fo r i := 1 to n do
Be g in
write (‘ Phan tu thu ‘,i,’ = ‘) ;
re adln(A[i]) ;
End;
Max := A[1[ ; c s max :=1 ;
Fo r i := 1 to n do
If (A[i]>max) The n
be g in
max := a[i];
c s max=i;
e nd;
Write ln(‘ Gia tri c ua phan tu Max : ’,Max) ;
Write ln(‘ Chi s o c ua phan tu Max : ’, c s max) ;
Re adln ;
END.
- Ch¬ tr× ch¹y vµ cho kÕt qu¶ nh
ng nh
sau:
Nhap vao so phan tu cua day so : 7
Phan tu thu 1 = 15
Phan tu thu 2 = 20
Phan tu thu 3 = 16
Phan tu thu 4 = 25
Phan tu thu 5 = 18
Phan tu thu 6 = 12
Phan tu thu 7 = 19
Gia tri cua phan tu Max : 25
Chi so cua phan tu Max : 4
- Bµi 2. NhËp vµo mét d·y sè nguyªn, s¾p xÕp d·y theo tr× tù kh«ng
nh
gi¶m.
* INPUT: NhËp sè nguyªn d¬ n vµ d·y n sè nguyªn d¬ a1,a2,...,an.
ng ng
* OUTPUT: D·y sè ® s¾p xÕp theo tr× tù kh«ng gi¶m.
îc nh
- C¸c e m h·y c ho
b iÕt ®Ó g i¶i b µi
to ¸n trª n, ë líp 10 Lµ ThuËt to ¸n
c hó ng ta d ïng tr¸o ®æ i kiÓu
thuËt to ¸n g ×? næ i b ät tõ trª n
xuè ng !
- 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;
Träng lîng c ña bät níc thø i lµ gi¸ trÞ cña A[i].
Lît 1:
2:
• i ch¹y tõ ®Çu d·y ®Õn vÞ trÝ
tõ ®Çu d·y ®Õn vÞ trÝ
3 [cuèi d·y 1] 2] (bá qua phÇn tö
d·y
cuèi).
• Khi a[i]>a[i+1] tøc lµ bät níc
2 • bªn trªnthø hai h¬n níc cã träng
Sau lît nÆng bät bät níc bªn
díi => bät níc trªn ch×m xuèng
lîng lín thø hai n»m s¸t trªn
9 vµ bät níc nhÊt.
bät níc lín bªn díi næi lªn (tr¸o
• ®æi vÞ trÝ). duyÖt, tr¸o ®æi ®îc
Qu¸ tr×nh
7 lÆp ®i lÆp l¹i cho ®Õn khi
• Sau cßn thø nhÊt, bät níc vµ
chØ lît duyÖt hai phÇn tö cã
6 thu ®îc d·y lín nhÊt sÏ
träng lîng kh«ng gi¶m. ch×m
xuèng ®¸y.
- 1 Sè phÇn tö ë c ¸c lît duyÖt (j) s Ï gi¶m tõ n xuè ng hai phÇn tö .
C¸c e m h·y c ho For j := n downto 2 do
b iÕt tro ng Pas c al
nhËn xÐt 1 ®îc
2 T¹i mçi lît duyÖt: For i := 1 to j-1 do
thÓ hiÖn b »ng
Cho ilÖnh g × 1 ®Õn s è phÇn tö 1,
c h¹y tõ ? IF A[i]>A[i+1] then
nÕu A[i]>A[i+1] th× Begin
tr¸o ®æ i vÞ trÝ A[i] vµ A[i+1] Tg := A[i];
th«ng qua biÕn trung g ian (Tg ). A[i] := A[i+1];
A[i+1]:=Tg;
end;
- PROGRAM Sapxep;
Uses crt;
Type dayso = Array[1..250] of integer;
Var Khai b ¸o m ¶ng 1
i, j , n , tg : integer; c hiÒu
A : dayso;
BEGIN
Clrscr;
write(‘ Nhap vao so phan tu cua day so : ’);
readln(n);
For i := 1 to n do
NhËp m ¶ng 1 c hiÒu
Begin
write(‘ Phan tu thu ‘,i,’ = ‘);
readln(A[i]);
end;
For j := n downto 2 do
For i:= 1 to j-1 do
Xö lÝ m ¶ng b »ng
If A[i]>A[i+1] Then
begin thuËt to ¸n næ i b ät
Tg := A[i];
A[i]:=A[i+1];
A[i+1]:=Tg;
end;
Writeln(‘ Day so duoc sap xep ’);
For i:=1 to n do Write(A[i]:5); In kÕt q u¶
Readln;
END.
- Bµi 3. NhËp vµo mét d·y A t¨ng gåm N (N ≤ 250) sè nguyªn d¬ kh¸c nhau
ng
vµ mét sè k. Cho biÕt vÞ trÝ cña sè h¹ng cã gi¸ trÞ b»ng k trong d·y (nÕu
cã) ?
* INPUT: NhËp sè nguyªn d¬ n, d·y n sè nguyªn d¬ a1,a2,...,an vµ
ng ng
sè nguyªn k
* OUTPUT: ChØ sè i mµ ai =k hoÆc th«ng b¸o “Kh«ng t× thÊy”
m
nÕu kh«ng cã sè h¹ng nµo cña d·y A cã gi¸ trÞ b»ng k.
- C¸ch 1: T×m kiÕm tuÇn tù
LÇn lît tõ s è h¹ng thø nhÊt, s o s ¸nh g i¸ trÞ s è h¹ng
®ang xÐt víi k c ho ®Õ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 ã
g i¸ trÞ b»ng k.
C¸c e m h·y nª u
c ¸c c ¸c h ®Ó Tim_thay := false;
g i¶i b µi to ¸ntë ng trª n i := 1 to n do
Tõ ý For h·y
trª n v iÕt ®o ¹n c h¬ng
?
tr×nh b »ng A[i] = k then
IF
PAS CAL ®Ó t×m s è Begin
h¹ng c ña d ·y c ã g i¸ Tim_thay:=true;
trÞ b »ng k? cs:=i;
break;
end;
IF tim_thay then writeln(‘Chi so tim duoc: ’,i)
else writeln(‘Khong tim thay’);
- C¸ch 2: T×m kiÕm nhÞ ph©n
Víi k = 21 vµ d·y A g åm 10 s è h¹ng nh s au:
A 2 4 5 6 9 21 22 30 31 33
i 1 2 3 4 5 6 7 8 9 10
Lît thø nhÊt: a g i÷a lµ a 5 = 9; 9 < 21
vïng t×m kiÕm thu hÑp tro ng ph¹m vi tõ a 6 a 10;
Lît thø hai: a g i÷a lµ a 8 = 30; 30 > 21
vïng t×m kiÕm thu hÑp tro ng ph¹m vi tõ a 6 a 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 .
- 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 ¸c h s o s ¸nh k víi A[g iua] vµ xÐt c ¸c trê ng hîp:
A[g iua]=k t×m thÊy c hØ s è g i÷a vµ kÕt thó c ;
A[g iua]>k Thu hÑp vÒ phÝa bªn tr¸i (Cuè i = Gi÷a 1);
A[g iua]
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
