Bai Kieu xau

Bài 13
Bài tập mảng một chiều
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à 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 max
1. Nhập n và dãy a1,...,an;
2. Max ? a1 ; i ? 1;
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
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 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 :
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.
3
2
9
7
6
Cho dãy số sau: 3 2 9 7 6
Giả sử:
? Mỗi số được xem như một phần tử;
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à phần tử bên trên nặng hơn phần tử bên dưới => phần tử trên chìm xuống và phàn tử bên dưới nổi lên (tráo đổi vị trí).
Sau lượt thứ nhất, Phần tử có trọng lượng lớn nhất sẽ ở vị trí cuối cùng.
? Phần tử 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 phần tử có trọng lượng lớn thứ hai nằm sát trên phần tử 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).
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 Tráo đổi
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 3. Nhập vào một dãy A 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ó) ? Thông báo kết quả ra màn hình
* 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.
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ách 1: Tìm kiếm tuần tự
Cách 2: Tìm kiếm nhị phân
10
9
8
7
6
5
4
3
2
1
i
33
31
30
22
21
9
6
5
4
2
A
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? a10;
33
31
30
22
21
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.
22
21
6
6
21
Dau:=1; Cuoi:=n; tim_thay:=false;
while ( Dau<= Cuoi) or NOT(tim_thay) do
Begin
Giua:= (Dau+Cuoi) div 2;
IF A[giua] = k then Tim_thay :=true
else
IF (A[Giua]>k) 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] 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.