Bài 11. Kiểu mảng

Kiểm tra bài cũ
Câu 1: Nêu khái niệm mảng một chiều. Viết cách khai báo mảng một chiều (trực tiếp hoặc gián tiếp)?
Câu 2: Cho một dãy số nguyên gồm 20 số. Hãy viết khai báo dãy số trên bằng một trong hai cách?
Hướng dẫn trả lời
Câu 1.
Mảng một chiều là một dãy hữu hạn các phần tử có cùng kiểu.
Khai báo
Cách 1.
Var : Array[kiểu chỉ số] of ;
Cách 2 :
Type = Array [] of ;
Var : ;
Câu 2.
Khai báo
Cách 1.
Var a : Array[1..20] of integer ;
Cách 2:
Type songuyen = Array [1..20] of integer ;
Var a : songuyen ;
mảng một chiều (tiếp)
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 ?
* INPUT: Nhập số nguyên dương n và dãy n số nguyên dương a1,a2,...,an. (n ? 250, A[i] ? 500)
* 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 max
ý tưởng:
- Đặt giá trị Max = a1.
- Lần lượt cho i chạy từ 2 đến N, so sánh
giá trị ai với giá trị Max, nếu ai > Max thì
Max nhận giá trị mới là ai.
Liệt kê các bước
B1: Nhập N và dãy a1,., aN;
B2: Max ? a1; i ? 2;
B3: Nếu i > N thì đưa ra giá trị Max rồi kết thúc;
B4:
Bước 4.1: Nếu ai > Max thì Max ? ai;
Bước 4.2: i ? i+1 rồi quay lại B3.
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;
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án
thể hiện bằng pascal
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 luong phan tu: `) ;
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 := 2 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 luong phan tu :
7
Phan tu thu 1 =
15
20
16
25
18
12
19
Gia tri cua phan tu Max : 25
Chi 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.
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 s?p x?p tráo đổi hay thu?t toán n?i b?t
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ượ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).
Hãy cho 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);
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 pascal
Bài tập về nhà
Bài 1: Nhập vào một dãy số nguyên. Tính tổng các số chia hết cho 3
Bài 2: Nhập vào một dãy số nguyên.
Số lượng số chẵn và số lượng số lẻ có trong dãy
Số lượng số nguyên tố có trong dãy.
Củng cố - Dặn dò
Xem lại cách khai báo và các thao tác xử lí mảng một chiều. Ví dụ tìm giá trị lớn nhất và sắp xếp tráo đổi.
Làm bài tập về nhà
Chuẩn bị nội dung cho tiết thực hành: “Bài tập thực hành 3(tiết 1)”