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;

Writeln(‘ Day so sau khi sap xep la: ‘);

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

readln;

End.

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:
  

Readln(k);

i:=1;

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

If i>n then

Begin

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

Else

For j:=n downto i do

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

a[i]:=k;

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:
  

Uses Crt;

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

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

S,Sk,TBC :real;

BEGIN

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,']= ');

End;

For i:=1 to m do

Begin

For j:=1 to n do

Writeln;

S:=0;

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;

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

TBC:=Sk/n;

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

Readln;

END.

7.2. Kiểu chuỗi (xâu) ký tự

7.2.1 Khái niệm

• 
  Xâu ký tự là một kiểu dữ liệu nhận giá trị là dãy các ký tự trong bảng mã ASCII, dãy ký tự này được đặt trong một cặp dấu nháy đơn (‘ ’)
  

St1 = ‘NGON NGU PASCAL’

St2 = ‘Tin hoc nam 2002’

St3 = ‘123456’

St4 = ‘Truong Dai hoc Dien Luc’

- Độ dài của một xâu là số ký tự của xâu đó. Xét ví dụ 7.20:

độ dài của st1 là 15,

đồ dài của st2 là 16,

độ dài của st3 là 6,

độ dài của st4 là 23,

- Xâu rỗng là xâu không chứa ký tự nào, nó có độ dài là 0, được ký hiệu là ‘’. Xâu rỗng khác với xâu chứa ký tự trống ‘ ’. Xâu chỉ chứa 1 ký tự trống có độ dài là 1.

-

Số thứ tự

Độ dài N (=15) của biến St1 và ký tự trong byte 0 (ký hiệu là St[0]) liên quan với nhau như sau:

N = Ord ( St[0] )

St[0]= Chr( N )

7.2.2. Khai báo xâu ký tự

7.2.2.1. Khai báo kiểu dữ liệu xâu:

TYPE Tên_kiểu_xâu = string; {mặc định là xâu dài tối đa 256 ký tự}

Hoặc

TYPE Tên_kiểu_xâu = string[độ dài tối đa của xâu];

VAR biến_xâu : Tên_kiểu_xâu;
Trong đó độ dài tối đa của xâu là một số nguyên dương nằm trong đoạn [0..256].
Ví dụ 7.16: Khai báo kiểu họ tên là kiểu xâu ký tự có độ dài tối đa là 40 ký tự.

TYPE kieu_hoten = string[40];

VAR ht: kieu_hoten; {khai báo biến ht có kiểu là kieu_hoten}
*Chú ý: Khi một biến xâu được dùng làm đối số của hàm hay thủ tục thì nó cần phải được khai báo theo cách này ( trừ các biến xâu có kiểu String ).
7.2.2.2. Khai báo biến kiểu dữ liệu xâu:

VAR tên_biến_xâu: string;

Hoặc

VAR tên_biên_xâu: string[độ dài tối đa của xâu];
Ví dụ 7.17:

VAR st1: string; {khai báo biến xâu st mặc định có độ dài tối đa là 256}

st2: string[50]; {khai báo biến xâu st có độ dài tối đa là 50}

* Chú ý: Nếu xâu st có độ dài tối đa là N mà ta lại gán cho nó xâu có độ dài lớn hơn N thì xâu st chỉ nhận N ký tự đầu tiên.
Ví dụ 7.18:

- Var st: string[15];

Sau lệnh gán st:=’Truong Dai hoc Dien Luc’; thì st sẽ nhận giá trị là: ‘Truong Dai hoc ’

- Var st1: string[50];

st1 := ‘C5CNTD’
* Chú ý: Cần phân biệt độ dài với độ dài tối đa của biến xâu: độ dài tối đa được xác định ngay khi khai báo là khả năng có thể chứa của biến xâu, còn độ dài của xâu là số ký tự đang thực có trong xâu. Như ví dụ 7.23, xâu st1 có độ dài tối đa là 50 nhưng độ dài thực tế của xâu là 6.

Каталог: file -> downloadfile9
file -> CỘng hòa xã HỘi chủ nghĩa việt nam độc lập Tự do Hạnh phúc
file -> TIÊu chuẩn quốc gia tcvn 7790-5 : 2008 iso 2859-5 : 2005
file -> Qcvn 81: 2014/bgtvt
file -> UỶ ban nhân dân cộng hòa xã HỘi chủ nghĩa việt nam
file -> VIỆn chăn nuôi trịnh hồng sơn khả NĂng sản xuất và giá trị giống của dòng lợN ĐỰc vcn03 luậN Án tiến sĩ NÔng nghiệp hà NỘI 2014
downloadfile9 -> Môn: Sinh học lớp 11 Câu 1
downloadfile9 -> Đề cương ôn thi Olympic 30/4 môn Sinh Biên soạn: Nguyễn Hoàng Thiên Tân
downloadfile9 -> Họ và tên: Lớp: ĐỀ thi số 5 MÔN: dinh dưỠng học ngàNH: bqcbns
downloadfile9 -> Đề tài Tìm hiểu về lợi ích của alexa
downloadfile9 -> Em xin chân thành cảm ơn! Hải Dương, ngày 31tháng 5 năm 2012 Sinh viên Vũ Tiến Duy MỤc lụC

tải về 4.67 Mb.

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