Kiểm tra bài cũ
Câu 1: Viết cách khai báo mảng một chiều (trực tiếp hoặc gián tiếp)? VD?
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.
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)
Tin học lớp 11
Bài 1: tìm phần tử lớn nhất của một 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: s? nguyờn duong n v� dóy n s? nguyờn duong 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.
ý tưu?ng:
- Đặt giá trị Max = a1.
- Lần lưu?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 bu?cư
B1: Nhập N và dãy a1,., aN;
B2: Max ? a1; i ? 2;
B3: Nếu i > N thì đưua ra giá trị Max rồi kết thúc;
B4:
Bu?c 4.1: Nếu ai > Max thì Max ? ai;
Bưu?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 đưua 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ưu?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. s?p x?p dóy s? nguyờn b?ng thu?t toỏn trỏo d?i.
* INPUT: Nh?p s? nguyờn duong n (n<= 250) v� dóy a1,a2,...,an, m?i s? d?u khụng vu?t quỏ 500.
* OUTPUT: dóy du?c s?p x?p th�nh dóy 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
Thuật toán sắp xếp
Hãy tìm cách sắp xếp học sinh đứng chào cờ (hình a) theo thứ tự thấp trưu?c cao sau (hình b).
Hình a
Hình b
Liệt kê các bu?c
B1: Nhập N, các số hạng a1, a2,., aN;
B2: M ? N;
B3: Nếu M < 2 thì đưa ra dãy A đã sắp xếp rồi kết thúc;
B4: M ? M - 1; i ? 0;
B5: i ? i +1;
B6: Nếu i > M thì quay lại B3;
B7: Nếu ai > ai+1 thì tráo đổi ai và ai+1 cho nhau;
B8: Quay lại B5.
3
2
9
7
6
Cho dãy số sau: 3 2 9 7 6
Giả sử:
? Mỗi phần tử đưu?c xem nhuư một bọt nưu?c;
Lần duyệ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ưu?c bên trên nặng hơn bọt nưu?c bên dưu?i => bọt nưu?c trên chìm xuống và bọt nưu?c bên dưu?i nổi lên (tráo đổi vị trí).
Sau lư?n duy?t thứ nhất, bọt nưu?c có trọng lưu?ng lớn nhất sẽ chìm xuống đáy.
? Trọng lưu?ng của bọt nưu?c thứ i là giá trị của A[i].
i chạy từ đầu dóy đến vị trí [cuối dóy - 2] (bỏ qua phần tử cuối).
Sau lư?n duy?t thứ hai bọt nưu?c có trọng lưu?ng lớn thứ hai nằm sát trên bọt nưu?c lớn nhất.
Quá trình duyệt, tráo đổi đưu?c lặp đi lặp lại cho đến khi khụng cũn s? trỏo d?i n�o x?y ra n?a và thu đưu?c dóy không giảm.
Lần duyệt 2
Nhận xét:
Số phần tử ở các lư?n duyệt (j) sẽ giảm từ n xuống hai phần tử.
Tại mỗi lư?n 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 đưu?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
Bài 1: Viết chương trình nhập vào từ bàn phím số nguyên dương N(N<=100), và dãy số . Tính tổng giá trị các phần tử trong mảng và hiển thị kết quả lên màn hình.
Var A : songuyen;
N, I, S: integer;
5. Begin
Clrscr;
Write(‘ Nhap vao so luong phan tu:’);
Readln(n);
6. For i:=1 to n do
begin
write(‘ Phan tu thu ’ ,i, ’ = ’);
readln(A[i]);
end;
2. Type songuyen = array [1..100] of integer;
9. S:=0; i:=0;
7. S:= S+ A[i];
Write(‘Tong S=‘, S:3);
3. readln;
4. end.
Sắp xếp lại các đoạn chương trình dưới đây thành ct hoàn chỉnh
8. For i :=1 to n do
10. Program tinh_tong;
Uses crt;
Chương trình sau khi sắp xếp
10. Program tinh_tong;
Uses crt;
2. Type songuyen = array [1..100] of integer;
1. Var A : songuyen;
N, I, S: integer;
5. Begin
Clrscr;
Write(‘ Nhap vao so luong phan tu:’);
Readln(n);
7. For i:=1 to n do
begin
write(‘ Phan tu thu ’ ,i, ’ = ’);
readln(A[i]);
end;
8. For i :=1 to n do write (A[i]:3);
9. S:=0; i:=0;
6. For i:= 1 to N do S:= S+ A[i];
Write(‘Tong S=‘, S:3);
3. readln;
4. End.
Chỉ ra lỗi ở đoạn chương trình ở bài toán 2 dưới đây
Bài 2: Viết chương trình nhập vào từ bàn phím số nguyên dương N(N<=100), và dãy số A1, A2, …. AN . Đếm các số chia hết cho 3 và hiển thị kết quả lên màn hình.
Var A: array [1..100] of char;
N,I,dem:integer;
Begin
Write(‘ Nhap vao so luong phan tu: N =’);
Readln(n);
For i:=1 to n do
begin
write(‘ Phan tu thu ’ ,i, ’ = ’);
readln(A[i])
end.
For i:=1 to N do write (A[i]:3)
dem:=10; i:=0;
For i :=1 to n do
If A[i] mod 3= 0 then dem:= dem - 1;
Write(‘so cac phan tu trong mang chia het cho 3 la:’, dem:3);
readln
End.
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)”
nguon VI OLET
