bai Kieu xau

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (312.59 KB, 16 trang )

(1)<div class='page_container' data-page=1></div>
(2)<div class='page_container' data-page=2>

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.

</div>
(3)<div class='page_container' data-page=3>

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

</div>
(4)<div class='page_container' data-page=4>

1. Nhập n và d y a· 1,...,an;

2. Max  a1 ; i  1;

3. NÕu i>N ® a ra MAX vµ 
chØ sè i => KÕt thóc;

</div>
(5)<div class='page_container' data-page=5>

1. NhËp n vµ d y a· 1,...,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;

</div>
(6)<div class='page_container' data-page=6>

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 ;

</div>
(7)<div class='page_container' data-page=7>

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:

</div>
(8)<div class='page_container' data-page=8>

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.

</div>
(9)<div class='page_container' data-page=9>

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 chy 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.

</div>
(10)<div class='page_container' data-page=10>

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

</div>
(11)<div class='page_container' data-page=11>

Khai báo mảng 1 
chiều

Nhập m¶ng 1 chiỊu

Xử lí mảng bằng 
thuật tố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;

</div>
(12)<div class='page_container' data-page=12>

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

</div>
(13)<div class='page_container' data-page=13>

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.

For i := 1 to n do

IF A[i] = k then

Begin

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’);

</div>
(14)<div class='page_container' data-page=14>

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

</div>
(15)<div class='page_container' data-page=15>

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]<k Thu hẹp về phía bên phải (Đầu = Giữa +1);

</div>
(16)<div class='page_container' data-page=16></div>

bai Kieu xau

Bài 1

.

<i><b>Tìm phần tư lín nhÊt cđa d·y sè nguyªn (víi n </b></i>



<i><b> 250 vµ A[i] </b></i>



<i><b> 500), nÕu d·y cã nhiỊu phÇn tư cïng giá trị thì đ a ra chØ sè cđa </b></i>

phÇn tư lín nhất đầu tiên.

*

INPUT

:

thuËt toán tìm max

Ch ơng trình chạy và cho kết quả nh sau:

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

:

<b>3</b>

<b>2</b>

<b>9</b>

<b>7</b>

<b>6</b>

Cho d·y sè sau:

3 2 9 7 6

<b>Giả sử:</b>

<b> Mỗi số đ ợc xem nh một phần tử; </b>

<b>L ợt 1:</b>

<b> Phần tử thứ i là giá trị của A[i]. </b>

<b>L ợt 2:</b>

<b> Tại mỗi l ợt duyệt:</b>

<b> - </b>

1

<b>For</b>

<b> j := n </b>

<b>downto</b>

<b> 2 </b>

<b>do</b>

2

<b>For</b>

<b> i := 1 </b>

<b>to</b>

<b> j-1 </b>

<b>do </b>

<b>IF</b>

<b> A[i]>A[i+1] </b>

<b>then </b>

* INPUT:

<b>Lần l ợt</b>

<b> từ số hạng thứ nhất, so sánh giá trị số hạng </b>

<b>đang xét với k cho đến khi gặp đ ợc số hạng bằng k, </b>

<b>hoặc d y đ đ ợc xét hết và khơng có số hạng nào cú </b>

ó

ó

<b>giá trị bằng k.</b>

<b> Cách 2: Tìm kiếm nhị phân</b>

<b>10</b>

<b>9</b>

<b>8</b>

<b>7</b>

<b>6</b>

<b>5</b>

<b>4</b>

<b>3</b>

<b>2</b>

<b>1</b>

<b>i</b>

<b>33</b>

<b>31</b>

<b>30</b>

<b>22</b>

<b>21</b>

<b>9</b>

<b>6</b>

<b>5</b>

<b>4</b>

<b>2</b>

<b>A</b>