Trang học tập môn Tin Học – Trần Hoàng Thạch
I.Cấu trúc điều khiển
1.Cấu trúc rẽ nhánh if…then
a.Dạng thiếu if <Điều kiện> then <Câu lệnh>;
*Hoạt động: Kiểm tra điều kiện, nếu điều kiện đúng thì thực hiện Câu lệnh
b.Dạng đủ If <Điều kiện> then <Câu lệnh 1>
Else <Câu lệnh 2>;
*Hoạt động: Kiểm tra điều kiện, nếu điều kiện đúng thì thực hiện Câu lệnh 1, điều kiện sai thì thực hiện Câu lệnh 2.
2.Câu lệnh rẽ nhánh Case…of
*Cú pháp: Case <Biểu thức số nguyên hoặc kí tự> of
<Danh sách 1>: Câu lệnh 1;
<Danh sách 2>: Câu lệnh 2;
…….
<Danh sách n>: Câu lệnh n
[Else Câu lệnh n+1];
End;
*Hoạt động: Khi gặp câu lệnh case…of máy tính tính giá trị biểu thức nếu trả về giá trị nào thì thực hiện câu lệnh tương ứng trong danh sách, nếu khác thì thực hiện câu lệnh n+1.
*Ví dụ: Nhập vào 2 số nguyên là tháng và năm. Cho biết tháng đó có bao nhiêu ngày?
Program vidu1;
Uses crt;
Var T,N,SN:integer;
Begin
Clrscr;
Write(‘Nhap thang va nam’); readln(T,N);
Case T of
4,6,9,11: SN:=30;
2: if (N mod 400=0) or ((N mod 100<>0) and (N mod 4=0)) then SN:=29
Else SN:=28;
Else SN:=31;
End;
Writeln(‘Thang ’,T, ‘ nam ’,N,’ Co so ngay ’,SN);
Readln
End.
3.Cấu trúc lặp For…do
*Cú pháp: For <Biến đếm>:=<Giá trị đầu> to <Giá trị cuối> do <Câu lệnh>;
For <Biến đếm>:=<Giá trị cuối> downto <Giá trị đầu> do <Câu lệnh>;
4.Cấu trúc While…do
*Cú pháp: While <điều kiện> do <câu lệnh>;
5.Cấu trúc lặp Repeat…until
*Cú pháp: Repeat
<Dãy câu lệnh>;
Until <Điều kiện>;
*Ví dụ: Kiểm tra số nguyên dương N nhập vào từ bàn phím có thỏa mãn điều kiện (0<=N<=1000)?
Repeat
Write(‘Nhap so nguyen N=’);
Readln(N);
Until (n>=0) and(n<=1000);
II.Kiểu dữ liệu có cấu trúc
1.Kiểu mảng một chiều
*Khái niệm: Mảng một chiều là một dãy hữu hạn các phần tử cùng kiểu có một tên chung, các phần tử này được đánh số gọi là chỉ số của các phần tử.
*Cú pháp khai báo: Var <Tên biến mảng>:array[n1..n2] of <Kiểu dữ liệu>;
2.Kiểu mảng 2 chiều
*Khai báo: Var <Tên biển mảng>:array[m1..m2,n1..n2] of <Kiểu dữ liệu>;
*Ví dụ: Chương trình sau tính và đưa ra màn hình bảng nhân
Program bangnhan;
Uses crt;
Var A:array[1..9,1..10] of integer;
i,j:integer;
begin
for i:=1 to 9 do
for j:=1 to 10 do
a[i,j]:=i*j;
for i:=1 to 9 do
begin
for j:=1 to 10 do
write(a[i,j]:4);
writeln;
end;
readln;
end.
*Bài tập về nhà:
Bài 1:Cho mảng 2 chiều m hàng, n cột. Hãy điền các số nguyên dương từ 1 đến m*n vào mảng 2 chiều sao cho mảng được sắp thứ tự theo hình vẽ: (ví dụ m=3, n=4 thì mảng có dạng sau:
1 2 3 4
8 7 6 5
9 10 11 12
Bài 2: Nhập vào số nguyên dương N (2<N<10000) và một dãy a1, a2,….an các phần tử nguyên dương. Cho biết dãy trên có bao nhiêu phần tử khác nhau.
Bài 3: Cho N gói kẹo (N<200) đánh số từ 1 đến N, gói kẹo thứ i có ai cái kẹo(ai<200). Hãy sắp các gói kẹo thành 2 phần sao cho độ chênh lệch nhau là ít nhất.
Nội Dung Chính
Gợi ý làm bài
Bài 1: Gợi ý dùng vòng for để điền các số vào mảng
Nếu chỉ số hàng lẻ thì ta điền theo chỉ số cột tăng
Nếu chỉ số hàng chẵn thì ta điền theo chỉ số cột giảm
Viết ra màn hình mảng vừa điền
T:=1;
For i:=1 to m do
Begin
If i mod 2<>0 then
For j:=1 to n do
Begin
A[I,j]:=T;
T:=T+1;
End
Else
For j:=N downto 1 do
Begin
A[I,j]:=T;
T:=T+1;
End
program zizac;
uses crt;
const nmax=10;
var A:array[1..nmax,1..nmax]of integer;
m,n,i,j:integer; T:longint;
begin
clrscr;
write(‘Nhap so hang so cot ‘); readln(m,n);
T:=1;
for i:=1 to m do
begin
if i mod 2 <> 0 then
begin
for j:=1 to n do
begin
a[i,j]:=T;
inc(T);
end;
end
else
for j:=n downto 1 do
begin
a[i,j]:=T;
inc(T);
end;
end;
for i:=1 to m do
begin
for j:=1 to n do
write(a[i,j]:4);
writeln;
end;
readln
end.
Bài 2: Để làm bài này ta dùng thuật toán “lùa bò vào chuồng”, Các phần tử bằng nhau sẽ nhốt chung một chuồng, có bao nhiêu chuồng thì có bấy nhiêu phần tử khác nhau trong dãy ban đầu.
Ta đóng dãy chuồng C, đánh số chuồng lần lượt từ 1,2….32000 ( ai là các số nguyên dương, ai<32000), ban đầu các chuồng đều trống) Duyệt mảng A ban đầu, phần tử ai sẽ được “nhốt” vào chuồng có số ai (tăng C[a[i]] lên một đơn vị).. Đếm số chuồng khác trống đó chính là số phần tử khác nhau của dãy ban đầu.
……..
Var C:array[0..32000] of integer;
……….
Ban đầu khởi tạo chuồng C trống
Fillchar(C,sizeof(C),0);
For i:=1 to N do inc(C[a[i]]);
D:=0;
For j:=0 to 32000 do if C[j]<>0 then inc(D);
Write(‘So phan tu khac nhau la’,D:4);
program sophantukhacnhau;
uses crt;
var A:array[1..10000] of integer;
C:array[0..maxint] of integer;
i,j,n,D:integer;
begin
clrscr; randomize;
write(‘Nhap so phan tu cua day ‘); readln(n);
for i:=1 to n do a[i]:=random(maxint)-random(100);
writeln(‘Day phan tu la ‘);
for i:=1 to n do write(a[i]:8);
fillchar(C,sizeof(C),0);
for i:=1 to N do inc(C[a[i]]);
D:=0;
for j:=0 to maxint do if c[j]<>0 then inc(D);
writeln(‘So phan tu khac nhau cua day la ‘,D:4);
readln
end.
Bài 3: Dùng một trục số với các điểm chia nguyên 0->40000 để đánh dấu tổng số kẹo có thể sinh ra khi xếp một số gói kẹo nào đó lại với nhau. Ta lần lượt xét từng gói kẹo từ a1->an
G/s bây giờ xét đến gói ai, để tạo ra các tổng mới, ta cộng ai vào từng tổng đã có (Cộng từ tổng lớn nhất về tổng nhỏ nhất là 0). Mỗi khi sinh ra tổng mới, cần ghi nhớ số hiệu vừa gộp vào để có tổng mới này.
…
Từ điểm X là điểm đánh dấu nửa tổng tất cả số kẹo (Nếu có) hoặc điểm đánh dấu gần x nhất (Nếu X không được đánh dấu) biết được gói cuối cùng thêm vào, trừ đi số kẹo của gói đó ta đến tổng mới, lại biết số kẹo nào vừa thêm vào để tạo ra tổng mới này….Quá trình tiếp tục khi ta về điểm đánh dấu 0.
Chương trình sau lay dl từ tệp chiakeo.int sau do ket qua ghi ở tệp chiakeo.out
program chiakeo;
uses crt;
const fi=’chiakeo.int’; fo=’chikeo.out’;
maxn=200; maxk=200; maxs=40000;
type m1=array[0..maxs] of byte;
m2=array[1..maxn] of byte;
var a:m2;
t:m1;
sum:word;
n:byte;
{———————————————————————–}
procedure nhap;
var f:text; i:byte;
begin
sum:=0;
assign(f,fi); reset(f);
readln(f,n); {so goi keo lan n}
for i:=1 to n do
begin
read(f,a[i]);
sum:=sum+a[i]; {sum la tong so keo}
end;
close(f);
end;
{———————————————————————–}
procedure danhdau;
var i:byte; max,j:word;
begin
fillchar(T, sizeof(T),0);
T[0]:=1; { danh dau tong =0 da duoc sinh ra}
Max:=0;
for i:=1 to n do
begin
for j:=max downto 0 do {Soat lai cac tong da co tu max ve 0}
if T[j]>0 then
if T[j+a[i]]=0 then T[j+a[i]]:=i; {danh dau tong j+a[i]
vua sinh ra goi i them vao}
max:=max+a[i];
end;
end;
{————————————————————————}
procedure timkq;
var i,tong:integer;
f:text; kq:m2;
begin
fillchar(kq,sizeof(kq),0);
assign(f,fo); rewrite(f);
tong:=sum div 2;
while T[tong]=0 do dec(tong);
writeln(f,sum-tong-tong);
repeat
kq[t[tong]]:=1;
tong:=tong-a[t[tong]]
until tong=0;
for i:=1 to n do
if kq[i]=1 then write(f,’Cac goi thuoc phan 1 ‘,i,’ ‘);
writeln(f);
for i:=1 to n do
if kq[i]=0 then write(f,’Cac goi thuoc phan 2 ‘,i,’ ‘);
close(f);
end;
{————————————————————————-}
Begin
clrscr;
nhap;
danhdau;
timkq;
end.
3.Kiểu xâu.
*Khai báo Var <biến xâu>:string[độ dài];
* Một số hàm và thủ tục liên quan đến xâu
-Length(S): Cho độ dài xâu S
-Upcase(ch): Cho kí tự in hoa ứng với ch
-Pos(s1,s2): Cho vị trí xuất hiện đầu tiên của S1 trong S2, nếu s1 không có trong s2 hàm cho giá trị 0.
-Insert(s1,s2,vt): Chèn xâu s1 vào xâu s2 tại vị trí vt
-Delete(s,vt,n): Xóa trong xâu s n kí tự từ vị trí vt
-Copy(s,vt,n): Sao chép trong xâu S n kí tự từ vị trí vt
-str(x,s): Biến đối số x thành 1 xâu kí tự biểu diễn số đó.
-Val(s,x,loi): Đổi xâu s thành số chứa trong x, nếu đổi thành công loi nhận giá trị 0, ngược lại loi nhận giá trị là vị trí kí tự sai trong s.
-Concat(s1,s2,…,sn): Ghép các xâu thành một xâu.Nếu tổng độ dài các xâu lớn hơn 255 thì máy tính báo lỗi.
….
Bài 1: Cho xâu S, kiểm tra xâu S có là xâu đối gương không?
Bài 2: Cho xâu S chỉ gồm các chữ cái. Cho biết xâu S có bao nhiêu chữ cái khác nhau. Mỗi chữ cái xuất hiện bao nhiêu lần.
Bài 3: Cho xâu S gồm các kí tự chữ số trong hệ thập phân biểu diễn 1 số nguyên dương có không quá 200 chữ số. Hãy tìm cách xóa đi k chữ số khỏi xâu S nói trên để xâu S thu được biểu diễn số có giá trị nhỏ nhất.
4.Kiểu dữ liệu tập hợp
Khi xử lí dữ liệu gồm các phần tử mà không cần lưu tâm đến quan hệ thứ tự giữa chúng, người ta có thể khai báo dữ liệu theo kiểu tập hợp.
*Khai báo: type <tên kiểu>=set of <kiểu cơ sở>;
Var <tên biến>:<tên kiểu>;
Hoặc var <tên biến>:set of <kiểu cơ sở>;
*Ví dụ: Khai báo biến b là tập hợp chứa các kí tự
Type ks=set of char;
Var b:ks;
*Người ta kí hiệu một tập hợp bằng cặp ngoặc vuông, bên trong chứa cá giá trị tập thuộc tập hợp đó: ví dụ A=[1,4,10]..
Một phần tử thuộc tập hợp đó kí hiệu là x in A
*Một số phép toán trên tập hợp
-Phép hợp: Kí hiệu A+B
-Phép giao: Kí hiệu A*B
-Phép hiệu: Kí hiệu A-B
-Phép thuộc: Kí hiệu A<=B
Bài tập áp dụng
Bài 1: Hai từ gọi là bạn bè nếu chúng được tạo nên cùng một số kí tự giống nhau: Ví dụ S1=’aabbbccccb’ và xâu S2=’aabccccaaaaa’ là bạn bè. Viết chương trình nhập 2 xâu từ bàn phím, kiểm tra 2 xâu có là bạn bè không?
Thuật toán: Ta đổi 2 xâu thành chữ in hoa, tạo 2 tập hợp t1, t2 rỗng. Duyệt xâu s1 kiểm tra từng kí tự nếu kí tự đang xét s1[i] chưa có trong tệp t1 thì thêm kí tự này vào tệp. Tương tự với xâu s2 và tập hợp t2. So sánh 2 tập hợp nếu chúng bằng nhau thì kết luận 2 xâu là bạn bè.
uses crt;
type kt=set of char;
var t1,t2:kt;
s1,s2:string;
i,n,m,j:byte;
begin
clrscr;
writeln(‘Nhap xau 1=’); readln(s1);
writeln(‘Nhap xau 2=’); readln(s2);
for i:=1 to length(s1) do s1[i]:=upcase(s1[i]);
for j:=1 to length(s2) do s2[j]:=upcase(s2[j]);
t1:=[]; t2:=[];
for i:=1 to length(s1) do if not(s1[i] in t1) then t1:=t1+[s1[i]];
for j:=1 to length(s2) do if not(s2[j] in t2) then t2:=t2+[s2[j]];
if t1=t2 then writeln(‘Hai xau la ban be ‘)
else writeln(‘Hai xa khong la ban be’);
readln
end.
Bài 2: Như các bạn đã biết dãy số Fibonaci là dãy 1, 1, 2, 3, 5, 8, …. Dãy này cho bởi công thức đệ qui sau:
F1 = 1, F2 =1, Fn = Fn-1 + Fn-2 với n > 2
Tính số hạng thứ n của dạy Fibonaci. Chương trình nhập n từ bàn phím và viết ra màn hình số hạng thứ N của dãy Fibonaci.
GV Hướng dẫn hs viết chương trình này
Ta khai báo một mảng lưu lại các số fibonaci tính được, viết ra màn hình số hạng thứ n
Var F:array[1..nmax] of longint;
F[1]:=1; F[2]:=2;
For i:=3 to n do F[i]:=F[i-1]+F[i-2];
Writeln(‘So hang thu n=’,F[n]);
Bài 3:Nhập vào một số nguyên không âm, kiểm tra xem nó có phải là số nguyên tố hay không?
Với bài này các em viết một hàm kiểm tra tính nguyên tố của một số dương n bất kỳ, hàm trả về giấ trị True nếu N nguyên tố, ngược lại hàm trả về giá trị False
Function NT(n:longint):Boolean;
Var i:longint; kq:boolean;
Begin
If (n=0) or (n=1) then kq:=falseElse
i:=1;
Repeat
i:= i+1;
Until (n mod i= 0) or (i*i>sqrt(n));
If i*i>sqrt(n) then kq:=true
Else kq:=false;
NT:=kq;
End.
Bài 4 In ra các số nguyên tố nhỏ hơn hoặc bằng N (N là số nguyên không âm được nhập từ bàn phím).
Với bài tập này các em sử dụng hàm ở trên để kiểm tra các số i<N, nếu NT(i)=true thì ta viết i ra màn hình.
program songuyenton;
uses crt;
var N,i:longint;
function NT(n:longint):boolean;
var i:longint; kq:boolean;
begin
if (n=0) or (n=1) then kq:=false
else begin
i:=1;
repeat
i:=i+1;
until (n mod i=0) or (i*i>n);
if i*i>n then kq:=true
else kq:=false;
end;
NT:=kq;
end;
begin
clrscr;
writeln(‘Nhap so n=’); readln(N);
if n<2 then writeln(‘Khong co so nt nao nho hon ‘,n)
else
for i:=2 to N do if NT(i) then write(i:4);
readln
end.
Thuật toán này dễ cài đặt nhưng có hạn chế là thời gian thực hiện lâu vì với mỗi số lại phải kiểm tra lần lượt các ước của nó do vậy thời gian thực hiện được tính là n2. Với n càng lớn thời gian thực hiện sẽ lâu. Có một thuật toán được xem là tốt hơn đó là thuật toán sàng các số nguyên tố.
Biểu diễn các só nguyên trên trục số bắt đầu từ số 2 đến N sau đó tìm cách xóa dần các điểm biểu diễn hợp số, các điểm còn lại trên trục số sẽ biểu diễn số nguyên tố. cụ thể:
-Ban đầu tất cả các điểm nguyên trên trục số chưa bị xóa;
-Số đầu tiên chưa bị xóa là số 2 (đó là số nguyên tố) , xóa các bội của 2
-Số đầu tiên chưa bị xóa là số 3 (Số nguyên tố), xóa các bội của 3
….quá trình cứ tiếp diễn với các số chưa bị xóa i mà i*i<N
Chương trình
uses crt;
var n,i,j:longint;
a:array[1..maxint] of 0..1;
begin
clrscr;
write(‘nhap so n=’); readln(n);
fillchar(a,sizeof(a),0);
i:=2;
while i*i<=n do
begin
j:=i+i;
while (j<=n) do
begin
a[j]:=1;
j:=j+i;
end;
inc(i);
while a[i]=1 do inc(i);
end;
for i:=2 to N do
if a[i]=0 then write(i:4);
readln
end.
Bài 5- Dãy số Fibonaci
Như các bạn đã biết dãy số Fibonaci là dãy 1, 1, 2, 3, 5, 8, …. Dãy này cho bởi công thức đệ qui sau:
F1 = 1, F2 =1, Fn = Fn-1 + Fn-2 với n > 2
- Chứng minh khẳng định sau:
Mọi số tự nhiên N đều có thể biểu diễn duy nhất dưới dạng tổng của một số số trong dãy số Fibonaci.
N = akFk + ak-1Fk-1 + …. a1F1
Với biểu diễn như trên ta nói N có biểu diễn Fibonaci là akak-1…a2a1.
- Cho trước số tự nhiên N, hãy tìm biểu diễn Fibonaci của số N.
Input:
Tệp văn bản P11.INP bao gồm nhiều dòng. Mỗi dòng ghi một số tự nhiên.
Output:
Tệp P11.OUT ghi kết quả của chương trình: trên mỗi dòng ghi lại biểu diễn Fibonaci của các số tự nhiên tương ứng trong tệp P11.INP.
{$R+}
const
Inp = ‘f11.int’;
Out = ‘f11.out’;
Ind = 46;
var
n: LongInt;
Fibo: array[1..Ind] of LongInt;
procedure Init;
var
i: Integer;
begin
Fibo[1] := 1; Fibo[2] := 1;
for i := 3 to Ind do Fibo[i] := Fibo[i – 1] + Fibo[i – 2];
end;
procedure Solution;
var
i: LongInt;
hfi, hfo: Text;
begin
Assign(hfi, Inp);
Reset(hfi);
Assign(hfo, Out);
Rewrite(hfo);
while not Eof(hfi) do
begin
Readln(hfi, n);
Write(hfo, n, ‘ = ‘);
i := Ind; while Fibo[i] > n do Dec(i);
Write(hfo, Fibo[i]);
Dec(n, Fibo[i]); { giảm n Fibo[i] đơn vị}
while n > 0 do
begin
Dec(i);
if n >= Fibo[i] then
begin
Write(hfo, ‘ + ‘, Fibo[i]);
Dec(n, Fibo[i]);
end;
end;
Writeln(hfo);
end;
Close(hfo);
Close(hfi);
end;
begin
Init;
Solution;
end.
Bài 6: Giai thừa (Đề thi HSG tỉnh năm 2010-2011)
Giai thừa của một số được cho bởi công thức sau: n!=1*2*…*n
Cho số N (N<=2.109) nguyên dương tính tổng giai thừa các chữ số chủa nó.
Trong bài các em viết 1 hàm tính giai thừa của số nguyên dương N. Sử dụng hàm này để tính tổng các chữ số của một số.
program tonggiai;
uses crt;
var SUM:longint;x,n,t:integer;
function GT(n:integer):Longint;
var i:integer;T:longint;
begin
if n=0 then T:=1
else
begin
T:=1;
for i:=1 to n do
T:=T*i;
end;
GT:=T;
end;
begin
clrscr;
write(‘Nhap n=’); readln(N);
sum:=0; t:=n;
while n>0 do
begin
x:=n mod 10;
SUM:=SUM+GT(x);
n:=n div 10;
end;
write(‘Giai thua cua ‘,t,’=’,sum);
readln
end.
Bài 7: (Đề thi HSG tỉnh năm 2010-2011) Dãy số Fibinaci
Cho số nguyên dương N (N<=2.109). Hãy kiểm tra xem n có là số thuộc dãy Fibinaci không? Nếu có thì là số bao nhiêu trong dãy?
Yêu cầu hs dựa vào chương trình bài 5 tự viết chương trình.
{$R+}
uses crt;
const
Ind = 46;
var
n: LongInt;
Fibo: array[1..Ind] of LongInt;
procedure Init;
var
i: LongInt;
begin
Fibo[1] := 1; Fibo[2] := 1;
for i := 3 to Ind do Fibo[i] := Fibo[i – 1] + Fibo[i – 2];
end;
procedure Solution;
var
i: LongInt;
begin
write(‘nhap n=’); readln(n);
i := 1;
repeat
inc(i);
until (Fibo[i]=n) or (i>=Ind);
if i=Ind then writeln(‘NO’)
else writeln(‘YES ‘,i);
readln
end;
begin
Init;
Solution;
end.
Bài 8: Số chữ số 0 tận cùng (Đề thi HSG tỉnh năm 2011-2012)
Tính chữ số 0 tận cùng của N!=1*2*….*N, với số nguyên dương N<=109. N nhập từ bàn phím, kết quả đưa ra màn hình gồm một số là số chữ số 0 tận cùng của N! tìm được.
Ví dụ N=12, kết quả đưa ra màn hình là 2.
program tonggiai;
uses crt;
var SUM:longint;t,i,n:integer;
s:string;
function GT(n:integer):Longint;
var i:integer;T:longint;
begin
if n=0 then T:=1
else
begin
T:=1;
for i:=1 to n do
T:=T*i;
end;
GT:=T;
end;
begin
write(‘Nhap n=’); readln(N);
SUM:=GT(n);
t:=0;
str(SUM,s); {Hàm str(SUM,s) đổi số SUM thành xâu S để đếm số 0 ở cuối xâu}
i:=length(s);
while s[i]=’0′ do
begin
inc(t);
dec(i);
end;
writeln(‘Cho so o tan cung cua ‘,N,’=’,t);
readln
end.
Buổi 5. Một số bài tập
Bài 1:
Bài tập tìm các số siêu nguyên tố có n chữ số
Bài này có thuật toán không đệ quy
Tạo các số siêu nguyên có i chữ số từ các số siêu nguyên tố có i-1 chữ số
Code
Khởi tạo a mảng chứa các số nguyên tố 1..9
Gs: có đem so trong a
For i:=2 to N do
Begin
For j:=1 to dem do
{tạo mảng b số siêu nguyên tố có i chữ số dựa vào i-1)
For k:=0 to 9 do
Begin
x:=a[j]*10+k;
if x nguyên tố then
Nap vào b
End;
{mảng b chứa các số nguyên tố cần tìm}
a:=b;
End;
Có thể sử dụng a,b là mảng a[1..2,1..max] thay vì gán mảng
program nt;
uses crt;
const nmax=100000;
var b,a:array[1..nmax] of longint;
i,j,dem,t,x,n,k:longint;
{————————————————————}
Function Prime(N: longint): boolean;
Var i: longint;
Begin
If (N=0) or (N=1) then
Prime:=false
Else
Begin
i:=2;
While (N mod i <> 0) and (i <= Sqrt(N)) do Inc(i);
If i > Sqrt(N) then
Prime:=true Else Prime:=false;
End;
End;
{————————————————————-}
begin
clrscr;
writeln(‘Nhap n=’); readln(n);
dem:=1;
a[1]:=0;
for i:=1 to N do
begin
t:=0;
for j:=1 to dem do
for k:=0 to 9 do
begin
x:=a[j]*10+k;
if Prime(x) then
begin
t:=t+1;
b[t]:=x;
end;
end;
a:=b;
dem:=t;
end;
for i:=1 to t do
begin
write(a[i],’ ‘);
if i mod 10=0 then writeln;
end;
writeln;
writeln(‘co ‘,t,’ so sieu nguyen to’);
readln
end.
Bài 2 (Đề thi HSG Tỉnh năm 2009-2010)
Dãy các số tự nhiên được viết ra thành một dãy vô hạn trên đường thẳng:
1234567891011121314….. (1)
Hỏi số ở vị trí thứ 1000 trong dãy trên là số nào?
Tổng quát lên ở vị trí thứ k?
Hãy làm bài này theo hai cách: Cách 1 dùng suy luận logic và cách 2 viết chương trình để tính toán và so sánh hai kết quả với nhau.
Đáp án: chữ số ở vị trí k = 1000 là số 3.
Cách 1: suy luận logic:
Ta có dãy số s = 123456789101112….
Gọi i là các số thành phần, i thuộc {1,2,3,4,…,10,11,….,100,101,102….,1000,10001 ….}
Khi i có 1 chữ số: có tối đa 9 số, số chữ số = 9×1 = 9;
Khi i có 2 chữ số: có tối đa 9 chữ số chục (1->9) x 10 chữ số đơn vị (0 ->9) = 9×10 = 90 số, số chữ số = 90×2 = 180;
Khi i có 3 chữ số: có tối đa 9x10x10 = 900 số, số chữ số tối đa = 900×3 = 2700;
….
Dựa vào đó ta có thể tính từ vị trí k bất kỳ:
k < 10 ta có chữ số chính là k
k>10: ví dụ k = 31, ta tính 31 – 9 = 22, 22/2 = 11 dư 0 nghĩa là chữ số thứ 2 của số thứ 11 tính từ 10, chính là 20 => kết quả = 0;
k>189: ví dụ k = 191, ta tính 191 – 189 = 2, 2/3 = 0 dư 2 nghĩa là chữ số thứ 2 của số thứ 1 tính từ 100, => kq = 0;
Trường hợp trên k = 1000, ta tính 1000 – 189 = 811, 811/3 = 270 dư 1 nghĩa là chữ số thứ 1 của số thứ 270 tính từ 100. Ta có từ 100 tới 299 có 200 số, 70 số còn lại rơi vào khoảng 300 -> 369, số thứ 270 chính là 369 vậy kết quả cần tìm là 3.
Chương trình
Const
fi=’num.inp’;
fo=’num.out’;
Var
cs:array[1..7] of longint = (9,180,2700,36000,450000,5400000,63000000);
n:longint;
f,g:text;
Function num(n:longint):char;
Var
k,so,mu:longint;
s:string;
Begin
k:=1;
mu:=1;
While (k<9) and (cs[k]<n) do
Begin
n:=n-cs[k];
inc(k);
mu:=mu*10;
End;
If mu=1 then
so:=n div k
Else
so:=n div k+mu+ord(n mod k>0)-1;
Str(so,s);
s:=s[k]+s;
num:=s[n mod k + 1];
End;
Begin
Assign(f,fi);
Reset(f);
Assign(g,fo);
Rewrite(g);
While not seekeof(f) do
Begin
Readln(f,n);
Writeln(g,num(n));
End;
Close(f);
Close(g);
End.
thuật toán rất đơn giản, căn bản là làm 2 bước sau:
b1. Xác định xem vị trí n nằm ở số nguyên nào trong dãy số “1234567891011121314…..”
vd: với k=14, thì số nguyên chứa chữ số ở vị trí thứ 14 chính là số 12
b2. Xác định chữ số cần tìm trong số nguyên vừa tìm ở bước 1
vd: với k=14, số nguyên tìm được là 12, thì chữ số cần tìm là số 1
– để làm được bước 1 thì ta dựa vào quy luật sau: ban đầu với các số nguyên có 1 chữ số thì ta sẽ có 9 chữ số, tiếp theo với các số nguyên có 2 chữ số ta sẽ có 180 chữ số, tiếp theo nữa là 2700 chữ số,….Ta gọi các số 9, 180, 2700,… này là d, và số d cần tìm phải là số lớn nhất và <=k, để tìm d ta dùng công thức :
d=9*i*10i-1 ( i là số chữ số của số nguyên)
– sau khi tìm được d, ta sẽ xác định số nguyên cần tìm là x=x+ d div i, và k=k-d là số dư còn lại
vd: với n=14, ta tìm được d là 9, x=9, số dư k=5
– với k còn dư, ta có x=x+(k div i)
– tiếp theo là làm bước 2, ta sẽ xác định vị trí chứa chữ số cần tìm trong số nguyên x :
nếu k mod i=0 thì vị trí đó chính là chữ số cuối của số nguyên vừa tìm, ngược lại thì vị trí đó sẽ là i = k mod i
– cuối cùng thì dùng hàm str(x,st) để chuyển số thành chuỗi và in chữ số st[i] ra màn hình
uses crt;
var st: string;
j,n,d,x: longint;
i: integer;
begin
clrscr;
write(‘Nhap n: ‘);readln(n);
i:=1;
j:=1;
d:=9;
x:=0;
while (n > d) do
begin
n:=n-d;
x:=x+d div i;
j:=j*10;
i:=i+1;
d:=j*9*i;
end;
x:=x+(n div i);
if n mod i>0 then
begin
x:=x+1;
i:=n mod i;
end;
str(x,st);
write(‘Ket qua: ‘,st[i]);
end.
Bài 3
Nhập một dãy A có N số tự nhiên (N<40) và 1 số K. Hãy xuất ra các phần tử có số lần xuất hiện trong dãy A từ K lần trở lên ( Mỗi số chỉ xuất 1 lần)
Dữ liệu nhập: file DAYSO.INP:
– Dòng 1: 2 số N, K giữa 2 số cách nhau 1 khỏang trắng
– Dòng 2: Dãy A
Kết quả: file DAYSO.OUT: xuất các số thỏa điều kiện trên, trường hợp không có số nào thỏa thì xuất số -1
es crt;var a,b:array[0..100] of integer; n,j,i,k:integer; f:text; Procedure docf; begin assign(f,’C:\DAYSO.INP’); reset(f); i:=0; read(f,n); readln(f,k); While not eof(f) do begin inc(i); read(f,a[i]); end; close(f); end; Procedure xuly; begin assign(f,’C:\DAYSO.OUT’); rewrite(f); FillChar(b,SizeOf(b),0); For i:=1 to n do inc(b[a[i]]); For i:=1 to n do if b[i]<>0 then if b[i]>=k then writeln(f,i,’ Xuat hien ‘,b[i], ‘ lan!’); close(f);end; BEGIN clrscr; docf; xuly; readln end.
Bài 4
Nhập dãy số thực a và số k. Xét xem trong dãy có k số dương đứng cạnh nhau hay không?
Dữ liệu nhập: DUNGCANH.INP: dãy a và số k
Dữ liệu xuất: DUNGCANH.OUT có xuất 1 , không có xuất 0.
es crt;var a:array[1..100] of real;k,n,j,i,s:integer;f:text;Procedure ghif; begin assign(f,’C:\DUNGCANH.INP’); reset(f); read(f,n); writeln(n); read(f,k); writeln(k); i:=0; While not eof(f) do begin inc(i); read(f,a[i]); writeln(a[i]); end; writeln; end; Procedure xuly;var d:integer; begin assign(f,’C:\DUNGCANH.OUT’); rewrite(f); For i:=1 to n do Begin d:=1; While (i<=n) and (a[i]>0) and (a[i+1]>0) do begin inc(d); inc(i);end; if d>=k then Begin s:=1; write(f,s); break; end; end; if s=0 then write(f,s); close(f); end; BEGIN clrscr; ghif; xuly; readln end.
Bài 5 – Số phản nguyên tố
Một số n gọi là số phản nguyên tố nếu số ước số của nó là nhiều nhất trong n số tự nhiên đầu tiên. Cho số K (K <= 2 tỷ). Hãy ghi ra số phản nguyên tố lớn nhất nhỏ hơn hoặc bằng K.
Dữ liệu vào trong file PNT.INP nội dung gồm:
– Dòng đầu tiên là số M (1 < M <= 100) – số các số cần tìm số phản nguyên tố lớn nhất của nó;
– M dòng tiếp theo lần lượt là các số K1, K2, K3, …, KM;
Dữ liệu ra trong file PNT.OUT gồm M dòng: dòng thứ i là số phản nguyên tố lớn nhất nhỏ hơn hoặc bằng Ki.
Ví dụ:
PNT.INP
1
1000
PNT.OUT
840
Bài 6
Một chuỗi kí tự thuần nhất được định nghĩa là chuổi chỉ bao gồm các kí tự ‘A’.. ‘Z’ hoặc ‘a’.. ‘z’. Một xâu thuần nhất có thể được viết thu gọn, bao gồm các ký tự kèm theo số lần xuất hiện liên tiếp của ký tự đó.
Ví dụ:
Chuỗi thuần nhất: AABBCDDEEF Chuỗi thu gọn: 2A2BC2D2EF
Chuỗi thu gọn: A5B3D2E Chuỗi thuần nhất: ABBBBBDDDEE
Yêu cầu: Viết chương trình nhập 1 chuỗi không quá 255 ký tự từ bàn phím là dạng thuần nhất hay dạng thu gọn, ghi chuổi vừa nhập vào tập tin INPUT.TXT
‒ Nếu là chuỗi thuần nhất thì hãy chuyển đổi nó về dạng thu gọn.
‒ Nếu là chuỗi thuộc dạng thu gọn thì hãy chuyển đổi nó trở lại dạng thuần nhất tương ứng.
‒ Kết quả lưu vào tập tin OUTPUT.TXT
sao nó ko
program Nen_giainen_chuoi;var s:string;i,k:integer;function Nen(s:string):string;var i,j,d:integer;c:string;begin for i:=1 to length(s)-1 do if s[i]=s[i+1] thenbegind:=2;for j:=i+1 to length(s) doif (s[i]=s[j+1]) and (j<length(s)) then d:=d+1elsebeginstr(d,c);insert(c,s,i);delete(s,i+1,d-1);break;end;end;nen:=s;end;function Giainen(s:string):string;var i,j,d,code:integer;c,x:string;beginfor i:=1 to length(s) doif s[i] in [‘0’..’9′] then c:=c+s[i] elsebeginval(c,d,code);for j:=1 to d do x:=x+s[i];c:=”; d:=0;end;giainen:=x;end;beginreadln(s);for i:=1 to length(s) doif s[i] in [‘0’..’9′] then begin k:=1; break; end;if k=1 then writeln(giainen(s)) else writeln(nen(s));readlnend For k:=1 to ka do
a[k]:=b[k]; end;
For k:=1 to ka do
Write(a[k]:10);
MỘT SỐ BÀI TẬP THAM KHẢO
BÀI 1: – Số siêu nguyên tố
Số siêu nguyên tố là số nguyên tố mà khi bỏ một số tuỳ ý các chữ số bên phải của nó thì phần còn lại vẫn tạo thành một số nguyên tố.
Ví dụ 7331 là một số siêu nguyên tố có 4 chữ số vì 733, 73, 7 cũng là các số nguyên tố.
Nhiệm vụ của bạn là viết chương trình nhập dữ liệu vào là một số nguyên N (0< N <10) và đưa ra kết quả là một số siêu nguyên tố có N chữ số cùng số lượng của chúng.
Ví dụ khi chạy chương trình:
Nhap so N: 4¿
Cac so sieu nguyen to có 4 chu so la: 2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393
Tat ca co 16 so_
Program Bai37;
{SuperPrime};
var a,b: array [1..100] of longint;
N,i,k,ka,kb,cs: byte;
Function Prime(N: longint): boolean;
Var i: longint;
Begin
If (N=0) or (N=1) then
Prime:=false
Else
Begin
i:=2;
While (N mod i <> 0) and (i <= Sqrt(N)) do Inc(i);
If i > Sqrt(N) then
Prime:=true Else Prime:=false;
End;
End;
BEGIN
Write (‘Nhap N: ‘);
Readln (N);
ka:=1; a[ka]:=0;
For i:=1 to N do
Begin
Kb:=0;
For k:=1 to ka do
For cs:=0 to 9 do
If Prime(a[k]*10+cs) then
Begin
Inc(kb);
b[kb]:=a[k]*10+cs;
end;
ka:=kb;
Writeln(‘Co tat ca’,ka,’so sieu nguyen to co’,N,’chu so.’);
Readln;
END.
Bài 2: Tam giác Pascal là gì? Quy luật của Tam giác Pascal rất đơn giản : bắt đầu từ hàng thứ ba, mỗi số bên trong là tổng của hai số ngay phía trên nó. Ví dụ : ở hàng 3, số 2 là tổng của 1 và 1 ; hàng 4, số 3 là tổng của 2 và 1 ; hàng 5, số 6 là tổng của 3 và 3. Căn cứ theo quy luật đó, Tam giác Pascal là kéo dài đến vô hạn.
Ví dụ:
1
2 3 2
3 4 5 4 3
4 5 6 7 6 5 4
5 6 7 8 9 8 7 6 5
Đoạn code sau sẽ in ra màn hình 10 dòng đầu của tam giác Pascal (được căn giữa).
uses crt;
const n=10;
var i,j:integer;
begin
for i:=1 to n do
begin
for j:=n downto i do
write(‘ ‘); { <- thêm dấu cách }
for j:=i to 2*i-1 do write(j:2); { <- đặt chỗ trống cho số}
for j:=2*i-2 downto i do write(j:2); { <- đặt chỗ trống cho số}
writeln;
end;
readln;
end.
Bài 3: Nhập ngày tháng năm. Hãy cho biết ngày tháng năm sau đó N ngày.
var d,m,y,n:integer;
Function Songay(thang,nam: Integer):Integer;
Var sn:Integer;
Begin
Case thang of
1,3,5,7,8,10,12 : sn:= 31;
4,9,11 : sn:= 30;
2: If (nam MOD 4 = 0) Then
sn:= 29
Else
sn:= 28;
End;
Songay:= sn;
End;
BEGIN
Writeln(‘Nhap ngay thang nam’);Readln(d,m,y);
Writeln(‘Nhap N’);Readln(N);
d:=d+N;
While d > Songay(m,y) Do
Begin
d:= d – Songay(m,y);
m:= m+1;
IF m > 12 Then
Begin
m:= 1;
y:= y + 1;
End;
End;
Writeln(‘Ket qua ‘,d,’/’,m,’/’,y);
Readln;
END.
Bài 4:Hai số m,n gọi là bạn của nhau nếu tổng các ước của m bằng n và ngược lại.Tìm tất cả các số là bạn của nhau và nhỏ hơn 10001.
Ý tưởng: Thay vì chạy 2 vòng lặp để xét m và n, ta có thể chỉ cần chạy 1 vòng lặp kiểm tra xem m và uoc(m) có là bạn của nhau không.
PROGRAM timban;
FUNCTION uoc(k:INTEGER):longint;
VAR i,tong:INTEGER;
BEGIN
tong:=0;
FOR i:=1 TO k DIV 2 DO
IF k MOD i =0 THEN tong:=tong+i;
uoc:=tong;
END;
VAR m:longint;
BEGIN
for m:= 1 to 10001 do
if uoc(uoc(m)) = m then writeln(m, ‘ va ‘, uoc(m),’ la ban cua nhau’);
readln
END
Bài 5:Nhập vào 1 số tự nhiên n* và nhập vào m, sau đó tính tổng m các số tận cùng của n.
vd: n = 365 m =2 tổng = 5+6=11.
Cách 1:
uses crt;
var n: longint;
m,tong,i: integer;
BEGIN
clrscr;
write(‘Nhap n: ‘); readln(n);
write(‘Nhap m: ‘); readln(m);
for i:=1 to m do
begin
tong:=tong+(n mod 10);
n:=n div 10;
end;
write(‘Tong ‘,m,’ chu so cuoi cua so vua nhap = ‘,tong);
readln;
END.
Cách 2: Sử dụng xâu: Xâu giúp lưu trữ thoải mái hơn kiểu số nguyên, nên ta có thể khái báo N có ở string thay vì Integer. Như vậy, ở những trường hợp lớn (vd N bao gồm 100 chữ số chẳng hạn) thuật toán vẫn có thể hoạt động bình thường.
uses crt;
var n: string;
m,i,a,tong: integer;
BEGIN
clrscr;
write(‘Nhap so n: ‘); readln(n);
write(‘Nhap m: ‘); readln(m);
for i:= length(n) downto length(n)-m+1 do
begin
val(n[i],a);
tong:=tong+a;
end;
write(tong);
readln;
END.
Như vậy, thay vì dùng lệnh mod như khi nhập N vào dưới dạng số nguyên, ta dùng thủ tục val của xâu (biến từ chữ thành số), các bạn có thể xem thêm tại bài Xâu – String.
Bài 6: Nhập vào n (1<=n<=30000), hãy in ra số chữ số 0 cuối cùng của n giai thừa.
Ý tưởng cách tìm: Xét tất cả các số chia hết cho 5. Giả sử mỗi số đó có thể chia hết cho Xi chữ số 5.
Cộng tất cả các Xi đó lại thì ta được số chữ số 0.
Giả sử 25! = 15511210043330985984000000 có 6 chữ số 0 tận cùng.
ta có
5 chia hết cho 1 chữ số 5
10 chia hết cho 1 chữ số 5
15 chia hết cho 1 chữ số 5
20 chia hết cho 1 chữ số 5
25 chia hết cho 2 chữ số 5
-> suy ra tổng là 6 (đúng với kết quả là có 6 chữ số 0).
var
n, i, j, count: longint;
begin
write(‘Nhap N (N>=1): ‘); readln(n);
for i:=1 to n do
begin
j:=i;
while j mod 5 = 0 do
begin
j:=j div 5;
count:=count+1;
end;
end;
write(‘ So chu so 0 cuoi cua ‘,n,’! la: ‘,count); readln;
end.
Bài 7: Cho một số ở hệ cơ số 10 đổi sang hệ nhị phận
Nguyên tắc của phương pháp chuyển đổi từ hệ cơ số 10 sang hệ cơ số 2 là lấy số cần chuyển đổi chia cho 2 (kết quả chỉ lấy phần nguyên), sau đó tiếp tục lấy kết quả chia 2 (và cũng chỉ lấy phần nguyên), kết quả số nhị phân thu được là tập hợp các số dư của các phép chia.
Program Doi_thap_phan_ra_nhi_phan;
Var
He10,N,Y:Word;
He2,Tam:String;
Begin
Writeln(‘DOI SO TU HE THAP PHAN SANG HE NHI PHAN’);
Writeln(‘ —————–‘);
Writeln;
Write(‘-Nhap so nguyen he thap phan: ‘);
Readln(He10);
N:=He10;
He2:=’ ‘;
Repeat
Y:=He10 Mod 2;
Str(Y, Tam);
He2:=Tam + He2;
He10:= He10 Div 2;
Until He10 = 0;
Writeln;
Writeln(‘+So he 10 la : ‘,N);
Writeln(‘+Doi sang he 2 la: ‘,He2);
Writeln;
Writeln(‘ Bam phim <Enter> de ket thuc’);
Readln
End.
Bài 8: Phân tích một số ra thừa số nguyên tố
Ví dụ: Phân tích 12=2*2*3. Ý tưởng: Thuật toán phân tích một số ra thừa số nguyên tố tương tự như thuật toán kiểm tra số nguyên tố. Điểm khác ở đây là khi kiểm tra số nguyên tố ta phải lần lượt kiểm tra các số nhỏ hơn sqrt(n) (căn bậc hai của n) có phải là ước của n hay không, còn khi phân tích ta chỉ việc chia n cho các số nguyên bắt đầu từ số nguyên tố nhỏ nhất là 2. Khi không chia được nữa thì ta tăng số chia lên 1 đơn vị, quá trình phân tích kết thúc khi n bằng 1.
VAR i,n :INTEGER;
BEGIN
Write (‘Nhap n:’);
Readln(n);
Write (n,’=’);
i:=2;
REPEAT
WHILE n MOD i <> 0 DO
i:=i+1;
Write(i);
n:=n DIV i;
IF n > 1 THEN
write (‘*’);
UNTIL n = 1;
readln;
END.
Bài 9:Viết chương trình nhập vào xâu, đưa ra xâu đảo theo từ. Ví dụ: đi xe đạp -> đạp xe đi.
uses crt;
var s:string;
x,y,z,t:byte;
begin
write(‘Nhap vao mot xau: ‘);
readln(s);
z:=length(s);
for y:=length(s) downto 1 do
begin
if ((s[y]=’ ‘)or(y=1)) then begin for t:=y to z do write(s[t]);z:=y end;
write(‘ ‘);
end;
readln;
end.
Bài 10: Dãy số tự nhiên a1 , a2 ,a3… ak được gọi là hạnh phúc nếu nó thoả mãn các điều kiện sau :
– Dãy trên là một dãy giảm dần .
– Với mọi i ( 1<=i <= k ) ai hoặc là số nguyên tố , hoặc phải là ước của một trong các số a1 , a2 , … , ai
VD : 18 17 13 11 9 7 6 5 3 2 là dãy hạnh phúc
Viết chương trình nhập 1 số tự nhiên N từ bàn phím và in ra màn hình một dãy số hạnh phúc càng dài càng tốt với số hạng đầu tiên là N.
Uses crt;
Const
max=37;
Var
a:array[1..max] of longint;
n,i:longint;
BEGIN
Clrscr;
a[1]:=1; a[2]:=1; a[3]:=2;
For i:=4 to max do
a[i]:=a[i-1]+a[i-2]+a[i-3];
Write(‘Nhap so n:’); readln(n);
i:=max;
While a[i]>n do i:=i-1;
Write(n,’=’,a[i]);
n:=n-a[i];
While n>0 do
Begin
i:=i-1;
If n>=a[i] then
Begin
Write(‘+’,a[i]);
n:=n-a[i];
End;
End;
Readln;
END.
Bài 11: Trước hết, chúng ta sẽ tìm hiểu khái niệm về số chính phương. Số chính phương là gì? Số chính phương là một số mà tự nó là căn bậc hai của một số tự nhiên khác, hay nói rõ hơn thì số chính phương là bình phương của một số tự nhiên.
Ví dụ: 289 là một số chính phương vì 289 = 17 bình phương.
Thuật toán Pascal dưới đây sẽ giúp tìm số chính phương trong mảng 1 chiều.
uses crt;
type ArrInt = array[1..250] of integer;
Var n,i,x : integer;
a: ArrInt;
BEGIN
clrscr;
write(‘Nhap so phan tu: ‘);
readln(n);
for i:=1 to n do
begin
write(‘Phan tu thu ‘,i,’= ‘);
readln(a[i]);
end;
writeln(‘Cac so chinh phuong co trong mang:’);
for i:=1 to n do
begin
x:=trunc(sqrt(a[i]));
if sqr(x)=a[i] then
write(a[i]:4);
end;
readln;
END.
Bài 12 Viết chương trình nhập mảng 1 chiều có N phần tử. In ra màn hình các phần tử có dạng 3k+2 (k=0,1,2,3…).
Ý tưởng: Viết hàm kiểm tra xem phần tử a[i] có dạng 3^k+2 hay không.
uses crt;
var b,j,i,x:integer;
a:array[1..100] of integer;
Function gt(k:integer):longint;
var j:integer;s:longint;
begin
s:=1;
for j:=1 to k do
s:=s*3;
gt:=s;
end;
{————————————-}
Function kt(x:integer):boolean;
var i,j,k:integer;s:longint;
begin
kt:=false;
s:=1;
k:=0;
Repeat
inc(k);
gt(k);
Until gt(k)>=x-2;
if gt(k)=x-2 then kt:=true;
end;
{———————————}
begin
clrscr;
Write(‘Nhap so phan tu= ‘);readln(x);
For i:=1 to x do begin
write(‘a[‘,i,’]= ‘);
readln(a[i]);
end;
For i:=1 to x do
if kt(a[i]) then write(a[i],’ ‘);writeln;
readln
end.
Một số thuật toán sắp xếp
Sắp xếp là thuật toán căn bản không chỉ trong ngôn ngữ lập trình Pascal mà còn trong nhiều lĩnh vực công nghệ khác. Bài viết sau sẽ để cập đến một số thuật toán sắp xếp bằng ngôn ngữ Pascal.
1. Bubble Sort (Sắp xếp nổi bọt)
Ý tưởng: Giả sử có mảng có n phần tử. Chúng ta sẽ tiến hành duyệt từ cuối lên đầu,so sánh 2 phần tử kề nhau, nếu chúng bị ngược thứ tự thì đổi vị trí, việc duyệt này bắt đầu từ cặp phần tử thứ n-1 và n. Tiếp theo là so sánh cặp phần tử thứ n-2 và n-1,… cho đến khi so sánh và đổi chỗ cặp phần tử thứ nhất và thứ hai. Sau bước này phần tử nhỏ nhất đã được nổi lên vi trí trên cùng (nó giống như hình ảnh của các “bọt” khí nhẹ hơn được nổi lên trên). Tiếp theo tiến hành với các phần tử từ thứ 2 đến thứ n.
Procedure bubblesort(var amang; Ninteger);
begin
var i,j integer;
for i=2 to N do
for j=N down to i do
if (a[j] a[j-1])
then
hoanvi(a[j-1],a[j]);
end;
- Selection Sort (Sắp xếp chọn)
Ý tưởng: Chọn phần tử nhỏ nhất trong n phần tử ban đầu, đưa phần tử này về vị trí đúng là đầu tiên của dãy hiện hành. Sau đó không quan tâm đến nó nữa, xem dãy hiện hành chỉ còn n-1 phần tử của dãy ban đầu, bắt đầu từ vị trí thứ 2. Lặp lại quá trình trên cho dãy hiện hành đến khi dãy hiện hành chỉ còn 1 phần tử. Dãy ban đầu có n phần tử, vậy tóm tắt ý tưởng thuật toán là thực hiện n-1 lượt việc đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đúng ở đầu dãy.
Các bước tiến hành như sau:
Bước 1: i=1
Bước 2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[n]
Bước 3: Hoán vị a[min] và a[i]
Bước 4: Nếu i<=n-1 thì i=i+1; Lặp lại bước 2
Ngược lại: Dừng. n-1 phần tử đã nằm đúng vị trí.
Procedure seletionsort(var a:mang; N:byte);
var i,j: byte; min: integer;
begin
for 1:=1 to N-1 do
if (a[j] < a[min] then min:=j;
if (min <> i) then hoanvi (a[min]; a[i];
end;
Procedure hoanvi(var x,y: integer);
var tam:integer
begin
tam:=x
x:=y
y:=tam
end;
-
Insert Sort
Procedure insertionsort(var a:mang, N:byte);
begin
var pos,i: byte; x:integer;
for i:=2 to N do
begin
x:=a[i]; pos:=i;
{sap xep tang dan}
while (pos>1 and a[pos-1]>x)do
begin
a[pos]:= a[pos-1]; dec(pos);
end;
a[pos]:= x;
end;
{sap xep giam dan}
while (pos>1)
begin
if(a[pos-1] > x)then
begin
a[pos]:= a[pos-1]; dec(pos);
end;
a[pos]:= x;4. QuickSort
procedure Quicksort ( Var A: Mang);
Procedure Sort( Left, Right: Integer);
Var
i, j, k: Integer;
Begin
i:= Left;
j:= Right;
k:= A[(Left + Right) Div 2];
Repeat
While A[i] < k Do Inc(i);
While k < A[j] Do Dec(j);
If i <> j Then
Begin
HoanVi(A[i],A[j]);
Inc(i);
Dec(j);
end;
Until i > j;
If Left < j Then Sort(Left,j);
If i < Right Then Sort(i,Right);
end;
Begin
Sort(Left; Right);
End;
Chia sẻ:
-
Thêm
Thích bài này:
Thích
Đang tải…
