Nhằm mục đích khuyến khích các bạn học sinh phổ thông nắm bắt rõ về các phương pháp tìm kiếm sắp xếp cơ bản trong lập trình. Cũng như chuẩn bị kiến thức cho các kì thi học kì, kiểm tra. Tôi sẽ làm một bài mẫu về tìm kiếm sắp xếp với phong cách code dễ hiểu nhất dành cho những bạn học chương trình cơ bản, nhất là học sinh lớp 11.
1. Đề bài Tìm kiếm sắp xếp cơ bản
Cho mảng A, N phần tử và một số nguyên K. Hãy thực hiện các công việc sau:
-In ra các vị trí mà K xuất hiện trong A.
-Tìm các phần tử chính phương của dãy A.
-Tìm các phần tử là số nguyên tố của dãy A.
-In ra dãy đã dược sắp xếp giảm dần.
Input
-2 số nguyên N và K (N,K<=1000).
-N phần tử của A mỗi phần tử cách nhau ít nhất một dấu cách.
Output
-Các vị trí mà K xuất hiện trong A.
-Các phần tử chính phương của A.
-Các phần tử nguyên tố của A.
-Dãy A đã được sắp xếp giảm dần.
Ví dụ
INPUT:
5 1
1 2 3 4 5
OUTPUT:
1
1 4
2 3 5
5 4 3 2 1
2. Thuật toán
Ở đây chúng ta dùng những thuật toán cơ bản nhất đó là tìm kiếm tuần tuần tự và sắp xếp nổi bọt. Còn tìm số nguyên tố và chính phương thì chắc các bạn đã được luyện tập nhiều nên có lẽ không cần nói tới. Đây chưa phải là cách tối ưu nhất nhưng đây là cách dễ hiểu nhất.
3. Code tham khảo
const fi='';
fo='';
type ma = array[1..1000] of longint;
var a: ma;
i,j,k,n: longint;
f: text;
procedure init; //Đọc dữ liệu
begin
assign(f,fi);
reset(f);
readln(f,n,k);
for i:=1 to n do read(f,a[i]);
close(f);
end;
procedure sort; //Sắp xếp mảng giảm dần
var tam: longint;
begin
for i:=1 to n-1 do
for j:=i+1 to n do
if (a[j]>a[i]) then
begin
tam:=a[j];
a[j]:=a[i];
a[i]:=tam;
end;
end;
procedure search(x: longint); //Tìm các vị trí mà K xuất hiện trong A
begin
for i:=1 to n do
if a[i]=x then write(f,i,' ');
end;
function nt(x: longint): boolean; //Hàm kiểm tra số nguyên tố
begin
if x<2 then exit(false);
for j:=2 to trunc(sqrt(a[i])) do
if x mod j = 0 then exit(false);
nt:=true;
end;
procedure cp_nt; //Thủ tục tìm phần tử nguyên tố chính phương
begin
for i:=1 to n do
if frac(sqrt(a[i]))=0 then write(f,a[i],' ');
writeln(f);
for i:=1 to n do
if nt(a[i]) then write(f,a[i],' ');
end;
BEGIN //Chương trình chính
init;
assign(f,fo); rewrite(f);
search(k);
writeln(f);
cp_nt;
writeln(f);
sort;
for i:=1 to n do write(f,a[i],' ');
close(f);
END.
Mọi thắc mắc vui lòng comment bên dưới!
