intTypePromotion=1

Bài giảng Điện tử Tin học lớp 11: Bài 13

Chia sẻ: Le Ba Thanh | Ngày: | Loại File: PPT | Số trang:15

0
127
lượt xem
7
download

Bài giảng Điện tử Tin học lớp 11: Bài 13

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:
Lưu

Nội dung Text: Bài giảng Điện tử Tin học lớp 11: Bài 13

  1. Bµi 13 Gi¸o ¸n ®iÖn tö tin häc líp 11
  2. 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.
  3. 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
  4. 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;
  5. 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.
  6. 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
  7. 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
  8. 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 !
  9. 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.
  10. 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;
  11. 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.
  12. 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.
  13.  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’);
  14.  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 .
  15. 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]
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2