Bài 13: Bài Tập Mảng Một Chiều.ppt (bài Giảng Tin Học 11) | Tải Miễn Phí

Trang chủ Tìm kiếm Trang chủ Tìm kiếm Bài giảng Tin học 11 - Bài 13: Bài tập mảng một chiều ppt 15 845 KB 1 103 4.1 ( 14 lượt) Xem tài liệu Nhấn vào bên dưới để tải tài liệu Tải về Đang chuẩn bị: 60 Bắt đầu tải xuống Để tải xuống xem đầy đủ hãy nhấn vào bên trên Chủ đề liên quan bài giảng tin học 11 Bài giảng Tin học 11 Bài 13 Bài 13 Bài tập mảng một chiều Bài giảng Bài tập mảng một chiều Thuật toán thể hiện bằng Pascal Chương trình Pascal

Nội dung

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. * INPUT: Nhập số nguyên dương n vàHãy dãy xác n số định nguyên dương a1,a2,...,an. Input, Output 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ÌM MAX Quả này mới lớn nhất Quả này lớn nhất MAX ồ!Tìm Quảranày quả lớn lớnnhất hơn rồi! 1. Nhập n và dãy a1,...,an; 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à chỉ số i => Kết thúc; For i :=2 to n do 4. Nếu a[i]>max thì maxa[i], i  i+1 => quay lại bước 3. IF a[i]>max then begin max:=a[i]; csmax:=i; end; 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. Chương trình chạy và cho kết quả như sau: Nhap vao so phan tu cua day so : Phan tu thu 1 = Phan tu thu 2 = Phan tu thu 3 = 15 Phan tu thu 4 = 25 Phan tu thu 5 = 18 Phan tu thu 6 = 12 Phan tu thu 7 = 19 20 16 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ình tự không giảm. * INPUT: Nhập số nguyên dương n và dãy n số nguyên dương a1,a2,...,an. * 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! 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 2: 1: 3 2 9 7 6 • i chạy từ từ đầu đầu dãy dãy đến đến vịvị trí trí [cuối dãy dãy -1] - 2] (bỏ qua phần tử cuối). • Khi a[i]>a[i+1] tức là bọt nước • Sau bên trên lượt nặng thứ hai hơn bọt bọtnước nướcbên có dưới => trọng lượng bọtlớnnước thứ trên hai nằm chìm xuống sát trênvàbọt bọtnước nướclớn bên nhất. dưới nổi đổi duyệt, vị trí). tráo đổi được • lên Quá(tráo trình lặp đi lặp lại cho đến khi chỉ còn • duyệt Sau lượt haithứ phần nhất, tử và bọtthu nước được có trọng dãy không lượng giảm. lớn nhất sẽ 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 em hãy cho biết trong Pascal nhận xét 1 được thể hiện 2 Tại mỗi lượt duyệt: bằng lệnh gì ? - Cho i chạy từ 1 đến số phần tử -1, nếu A[i]>A[i+1] thì tráo đổi vị trí A[i] và A[i+1] thông qua biến trung gian (Tg). 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; 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); For i := 1 to n do Begin write(‘ 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 so duoc sap xep ’); For i:=1 to n do Write(A[i]:5); Readln; 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ả Bài 3. Nhập vào một dãy A tăng gồm N (N  250) số nguyên dương khác nhau 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ương n, dãy n số nguyên dương a1,a2,...,an và số nguyên k * OUTPUT: Chỉ số i mà ai = 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ách 1: Tìm kiếm tuần tự 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. Các em hãy nêu Tim_thay := false; các cách để giải bài toánTừ trên ? trênFor ý tưởng hãyiviết := 1 to n do đoạn chương trình bằng PASCAL để tìm sốIFhạng A[i] = k then của dãy có giá trị bằng k? Begin Tim_thay:=true; 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ư sau: A 2 4 5 6 9 21 22 30 31 33 i 1 2 3 4 5 6 7 8 Lượt thứ nhất: agiữa là a5 = 9; 9 < 21  vùng tìm kiếm thu hẹp trong phạm vi từ a6 a10; Lượt thứ hai: agiữa là a8 = 30; 30 > 21  vùng tìm kiếm thu hẹp trong phạm vi từ a6 a7; Lượt thứ ba: agiữa là a6 = 21; 21= 21 Vậy chỉ số cần tìm là i = 6. 9 10 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]