Bài giảng Tin học 11 - Bài 13: Bài tập mảng một chiều

Bài 13 bài tập mảng một chiềuGiáo án điện tử tin học lớp 11Bà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 a1,a2,...,an.* 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ả này lớn hơn Tìm ra quả lớn nhất rồi! thuật toán tìm maxMAX1. 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; For i :=2 to n do IF a[i]>max then 	begin	 max:=a[i];	 csmax:=i;	end; 3. Nếu i>N đưa ra MAX 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.thuật toánthể hiện bằng pascalProgram 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.Nhap vao so phan tu cua day so :7Phan tu thu 1 = 15201625181219Gia tri cua phan tu Max : 25Chi so cua phan tu Max : 4 Chương trình chạy và cho kết quả như sau:Phan tu thu 2 = Phan tu thu 3 = Phan tu thu 4 = Phan tu thu 5 = Phan tu thu 6 = Phan tu thu 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! 32976Cho 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ượ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 (tráo đổi vị trí).Sau lượt thứ nhất, bọt nước có trọng lượng lớn nhất sẽ chìm xuống đáy. Trọng lượng của bọt nước thứ i là giá trị của A[i]. Lượt 2:i chạy từ đầu dãy đến vị trí [cuối dãy - 2] (bỏ qua phần tử cuối).Sau lượt thứ hai bọt nước có trọng lượng lớn thứ hai nằm sát trên bọt nước lớn nhất. Quá trình duyệt, tráo đổi được lặp đi lặp lại cho đến khi chỉ còn duyệt hai phần tử và thu được dãy không giảm.Nhận xét: Số phần tử ở các lượt duyệt (j) sẽ giảm từ n xuống hai phần tử. Tại mỗi lượt duyệt: - 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).Các em hãy cho biết trong Pascal nhận xét 1 được thể hiện bằng lệnh gì ? 1For j := n downto 2 do 2For 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ềuNhập mảng 1 chiềuXử lí mảng bằng thuật toán nổi bọtIn 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); 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.Chương trình pascalBà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á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 thenBegin 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’); Cách 1: Tìm kiếm tuần tự Cách 2: Tìm kiếm nhị phân	10987654321i333130222196542A Với k = 21 và dãy A gồm 10 số hạng như sau: 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 a7;Lượt thứ ba: agiữa là a6 = 21; 21= 21 	 Vậy chỉ số cần tìm là i = 6.22216621	Dau:=1; Cuoi:=n; tim_thay:=false;	while ( Dauk) 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.