CHÀO MỪNG CÁC THẦY CÔ VỀ DỰ GIỜ
KIỂU MẢNG (TIẾT 3)
Ví dụ 2: Bài toán sắp xếp
Cho dãy A gồm N số nguyên a1, a2,..., aN. Sắp xếp dãy A trở thành dãy không giảm (tức là số hạng trước nhỏ hơn hoặc bằng số hạng sau).
* INPUT: Nhập số nguyên dương n (n? 250) và dãy n số nguyên dương a1,a2,...,an.
* OUTPUT: Dãy số A được sắp xếp theo trình tự không giảm.
KIỂU MẢNG (TIẾT 3)
1. Kiểu mảng một chiều:
a. Khai báo
b. Một số ví dụ
Ví dụ 2: Bài toán sắp xếp
Cho dãy A gồm N số nguyên a1, a2,..., aN. Sắp xếp dãy A trở thành dãy không giảm (tức là số hạng trước nhỏ hơn hoặc bằng số hạng sau).
Ý tưởng: + So sánh 2 số hạng liên tiếp nhau, nếu số trước lớn hơn số sau thì đổi chỗ chúng cho nhau.
+ Đổi để đưa số lớn nhất về vị trí cuối cùng.
+ Làm tương tự đối với những số còn lại cho đến khi không còn có sự đổi chỗ xảy ra nữa.

KIỂU MẢNG (TIẾT 3)
1. Kiểu mảng một chiều:
a. Khai báo
b. Một số ví dụ
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
Ví dụ 2: Bài toán sắp xếp
Cho dãy A gồm N số nguyên a1, a2,..., aN. Sắp xếp dãy A trở thành dãy không giảm (tức là số hạng trước nhỏ hơn hoặc bằng số hạng sau).
HS số 1 thực hiện NV1, HS số 2 thực hiện NV2, … HS số 6 thực hiện NV6, hoạt động cá nhân trong 3’.
Sau đó thực hiện PHT 2, hoạt động nhóm 7’ trình bày ra bảng phụ.
KIỂU MẢNG (TIẾT 3)
1. Kiểu mảng một chiều:
a. Khai báo
b. Một số ví dụ
Minh họa hoán đổi giá trị của hai phần tử, bằng cách dùng biến trung gian (TG).
TG := x (1)
x := y (2)
y := TG (3)
CT
Khai báo mảng A và các biến
Nhập N và các phần tử của mảng
Xử lí mảng bằng thuật toán sắp xếp tráo đổi
In mảng A đã sắp xếp ra màn hình
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
Tìm tòi khám phá
- Tìm hiểu các thuật toán sắp xếp khác: với thời gian thực hiện nhanh hơn thuật toán sắp xếp tráo đổi như: QuickSort(SX nhanh) và MergeSort(SX trộn trực tiếp)và chương trình Pascal tương ứng cho các thuật toán đó.
- Làm bài tập sau:
Bài 1: Viết chương trình tạo mảng A gồm n số nguyên (n<=100), mỗi số có giá trị tuyệt đối không vượt quá 300. Tính tổng các phần tử của mảng là bội số của một số nguyên dương k cho trước, với k nhập từ bàn phím. In tổng vừa tính ra màn hình.
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ưuớ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ưuợng của bọt nuướ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;