Một số bài toán cơ bản về mảng

7.1.6 Một số bài toán cơ bản về mảng

Tìm kiếm là một trong những bài toán cơ sở trong xử lý thông tin. Có nhiều bài toán tìm kiếm, tuy nhiên có thể quy về tìm kiếm trên mảng như sau: Cho mảng và phần tử x có kiểu dữ liệu cùng với kiểu dữ liệu của phần tử mảng. Hãy tìm xem có phần tử mảng nào có giá trị bằng x hay không.

Để giải quyết bài toán dạng này có thể sử dụng phương pháp tìm kiếm tuần tự hay tìm kiếm nhị phân.

Thủ tục tìm kiếm tuần tự là duyệt lần lượt các phần tử mảng, so sánh giá trị của nó với x. Việc tìm kiếm dừng khi tìm thấy hoặc đã hết mảng, tức là phát hiện ra là mảng không có giá trị khóa nào bằng x.

Có thể triển khai thủ tục tìm kiếm trên mảng bằng một vòng lặp while, dùng cờ báo là biến found kiểu Boolean.
Ví dụ 7.11: Viết chương trình nhập vào một dãy số thực có n phần tử và một số thực x. Kiểm tra xem x có xuất hiện trong dãy số đó không?
Program vidu_7_11;

Var A:array[1..100] of real;

i,n:integer;

x:real;

Begin

writeln(' Nhap tung phan tu cua day so:');

For i:=1 to n do

begin

end;

For i:=1 to n do

write(A[i]:7:2);

{Tim x trong day so A}

writeln;

found:=false;

For i:=1 to n do

if A[i]=x then

begin

found:=true;

end;

writeln(x:5:2,' co xuat hien trong day so')

else writeln(x:5:2,' khong xuat hien trong day so');

readln;

Sắp xếp cũng là một trong những bài toán cơ sở trong xử lý thông tin. Từ dãy dữ liệu ban đầu chưa có thứ tự, cần tiến hành sắp xếp để nhận được dãy kết quả có thứ tự tăng hoặc giảm dần theo một khóa cho trước nào đó. Bài toán quy về sắp xếp một mảng số nguyên.

Dưới đây sẽ trình bày phương pháp sắp xếp chọn trực tiếp hay còn được gọi là phương pháp nổi bọt. Không mất tính tổng quát ta xét bài toán sắp xếp tăng, cụ thể như sau:

Mô tả

- Chọn phần tử nhỏ nhất trong dãy nguồn, xếp nó vào vị trí đầu tiên trong dãy đích. Đây là phần tử thứ nhất và cũng là phần tử cuối cùng của dãy đích.

- Chọn phần tử nhỏ nhất trong dãy nguồn còn lại, đây là phần tử nhỏ thứ hai, xếp nó vào vị tri thứ hai và cũng là vị trí cuối của dãy đích vào lúc này.

- Lặp lại việc này cho đến khi hết dãy nguồn.

Để tiết kiệm chỗ, ta cũng xếp dãy đích và dãy nguồn liền nhau trong mảng. Do đó, ở bước thứ i, thao tác "xếp vào cuối dãy đích" chính là "đổi chỗ cho a[i]".

Minh hoạ:

Giả sử cần sắp xếp dãy số sau:

44 55 12 42 94 18 06 67

Sự thay đổi của dãy số qua từng bước sắp xếp như sau:

Xuất phát: 44 55 12 42 94 18 06 67

Bước 1: 06 / 55 12 42 94 18 44 67

Bước 2: 06 12 / 55 42 94 18 44 67

Bước 3: 06 12 18 / 42 94 55 44 67

Bước 4: 06 12 18 42 94 55 44 67

Bước 5: 06 12 18 42 44 / 55 94 67

Bước 6: 06 12 18 42 44 55 / 94 67

Bước 7: 06 12 18 42 44 55 67 / 94

Bước 8: 06 12 18 42 44 55 67 94
Thủ tục chi tiết

Var i,j,k: integer;

x: real;

Begin

for j:=i+1 to n do

if a[j]

“đổi chỗ a[i] và a[j] cho nhau”

End;
Ví dụ 7.12: Viết chương trình nhập vào một dãy số thực có n phần tử (1<=n<=100). Sắp xếp dãy số theo chiều tăng dần. In lên màn hình dãy số trước và sau khi sắp xếp.
Program vidu_7_12;

Type kieudayso = array[1..100] of real;

Var A: kieudayso;

i, j, n: integer;

tg: real;

Begin

For i:=1 to n do

begin

write('A[',i,']= ');readln(A[i]);

writeln('In day so vua nhap:');

For i:=1 to n do

write(A[i]:7:2);

For j:=i+1 to n do

If A[i]< A[j] then

Begin {hoán vị A[i] và A[j] cho nhau}

tg:=A[i];

A[i]:=A[j];

A[j]:=tg;

End;

For i:=1 to n do

write(A[i]:7:2);

readln;

7.1.7. Một số ví dụ khác

• 
  Ví dụ 7.13: Viết đoạn chương trình chèn một số vào dãy đã sắp tăng mà không thay đổi thứ tự sắp xếp của dãy:
  

Write('Nhap so can chen k =');

Readln(k);

i:=1;

While (k>a[i]) and (i<=n) do i:=i+1;

Writeln('Vi tri chen i=',i:2);

If i>n then

Begin

a[i]:=k; n:=n+1;

End

Else

Begin

For j:=n downto i do

a[j+1]:=a[j];

a[i]:=k;

n:=n+1;

End;

• 
  Ví dụ 7.14: Viết chương trình tính tổng các phần tử của ma trận, nhập vào hàng k và tính trung bình cộng các phần tử trên hàng k. Hiển thị ma trận nhập dạng bảng và các kết quả tính:
  

Program Vidu14;

Uses Crt;

Var i,j,m,n,k :integer;

a: array[1..10,1..10] of real;

S,Sk,TBC :real;

BEGIN

Clrscr;

Write('Cho so hang cua ma tran m= ');Readln(m);

Write('Cho so cot cua ma tran n= ');Readln(n);

Writeln('Nhap tri cac phan tu cua ma tran:');

For i:=1 to m do

For j:=1 to n do

Begin

Write('a[',i,',',j,']= ');

Readln(a[i,j]);

End;

Writeln('Ma tran nhap:');

For i:=1 to m do

Begin

For j:=1 to n do

Write(a[i,j]:7:2);

Writeln;

End;

S:=0;

For i:=1 to m do

For j:=1 to n do

S:=S+a[i,j];

Writeln('Tong cac pt cua ma tran S= ',S:6:2);

Write('Nhap hang k :');Readln(k);

Sk:=0;

For j:=1 to n do

Sk:=Sk+a[k,j];

TBC:=Sk/n;

Writeln('TBC cac phan tu hang',k:2,' la: ',TBC:6:2);

Readln;

END.

Каталог: images
images -> Hướng dẫn sử dụng Dropbox Để sử dụng được Dropbox
images -> BÀi thuyết trình cách xáC ĐỊnh và chế ĐỘ pháp lý CỦa các vùng biển theo công ưỚc của liên hiệp quốc về luật biển năM 19821
images -> Céng hßa x· héi chñ nghÜa viÖt nam Độc lập tự do hạnh phúc
images -> Lúa gạo Việt Nam Giới thiệu
images -> Trung Tâm kt tc-đl-cl
images -> Số: 105/2008/QĐ-ttg CỘng hòa xã HỘi chủ nghĩa việt nam độc lập Tự do Hạnh phúc
images -> ChuyêN ĐỀ ĐẠi số TỔ HỢP, XÁc suất kiến thức cơ bản Đại số tổ hợp
images -> BỘ giáo dục và ĐÀo tạo trưỜng đẠi học luật tp. HỒ chí minh dưƠng kim thế nguyên thủ TỤc phá SẢn các tổ chức tín dụng theo pháp luật việt nam
images -> Review of Condor, Sun Grid Engine and pbs

tải về 1.67 Mb.

Chia sẻ với bạn bè của bạn: