Bài giảng Môn Tin học lớp 12 - Các thuật toán về số thuật toán kiểm tra số nguyên tố

f s[i-1]=' ' then s[i] := Upcase(s[i]) {Chuyển s[i] là kí tự đầu từ thành chữ hoa.}
         else
             if s[i] in ['A'..'Z'] then   {s[i] là kí tự chữ hoa không ở đầu một từ}
                s[i] := chr(ord(s[i]) + 32); {thì phải chuyển thành chữ thường}
end;
BEGIN
   write('Nhap vao 1 xau s:');
   readln(s);
   chuanhoa(s);
   writeln('Xau s sau khi chuan hoa:',s);
   readln;
END.
BÀI TẬP 2
Nhập vào một xâu x khác rỗng và thông báo xâu đó có phải là xâu đối xứng hay không?
HƯỚNG DẪN
Xâu đối xứng nếu nó bằng chính xâu đảo của nó. Vậy cách đơn giản nhất là ta sẽ xây dựng xâu đảo của x và kiểm tra xem nó có bằng x không. Để xây dựng xâu đảo của x, cách đơn giản nhất là cộng các kí tự của x theo thứ tự ngược (từ cuối về đầu).
Chương trình:
var x : string;
(************************************************)
function doixung(x : string) : boolean; {hàm kiểm tra xâu đối xứng}
var y : string;
    i : integer;
begin
     y := '';
{xây dựng y là xâu đảo của x, bằng cách cộng dần các kí tự của x vào y theo thứ tự ngược}
     for i := length(x) downto 1 do y := y + x[i];
{so sánh x và xâu đảo của nó}
     if x=y then doixung := true else doixung := false;
end;
BEGIN
     write('Nhap vao 1 xau:');
     readln(x);
     if doixung(x) then
        writeln('Xau doi xung!')
     else
        writeln('Xau khong doi xung!');
     readln;
END.
BÀI TẬP 3
Nhập vào một xâu s và đếm xem nó có bao nhiêu từ. Từ là một dãy các kí tự, cách nhau bởi dấu cách?
HƯỚNG DẪN
Cách đếm từ đơn giản nhất là đếm dấu cách: nếu s[i] là kí tự khác cách và s[i-1] là kí tự cách thì chứng tỏ s[i] là vị trí bắt đầu của một từ. Chú ý là từ đầu tiên của xâu không có dấu cách đứng trước.
Chương trình:
var s : string;
{Hàm đếm số từ của một xâu}
function sotu(s : string) : integer;
var i, dem : integer;
begin
{cộng thêm dấu cách phía trước xâu để đếm cả từ đầu tiên}
     s := ' ' + s; dem := 0;
     for i := 2 to length(s) do {s[i] là vị trí bắt đầu 1 từ}
         if (s[i-1]=' ') and (s[i]' ') then dem := dem + 1;
     sotu := dem;
end;
BEGIN
     write('Nhap vao 1 xau:');
     readln(s);
     writeln('So tu trong xau la:',sotu(s));
     readln;
END.
BÀI TẬP 4
Nhập vào một xâu s và in ra các từ của nó (Từ là một dãy các kí tự, cách nhau bởi dấu cách). Xâu có bao nhiêu từ là đối xứng?
HƯỚNG DẪN
Có nhiều cách để tách một xâu thành các từ. Cách đơn giản nhất tiến hành như sau:
1)      Bỏ qua các dấu cách cho đến khi gặp một kí tự khác cách (hoặc hết xâu).
2)      Ghi các kí tự tiếp theo vào xâu tạm cho đến khi gặp dấu cách hoặc hết xâu, khi đó ta được 1 từ.
3)      Nếu chưa hết xâu thì quay lại bước 1.
Mỗi khi tìm được một từ, ta ghi luôn nó ra màn hình, nếu từ đó là đối xứng thì tăng biến đếm. Ta cũng có thể lưu các từ tách được vào một mảng nếu bài tập yêu cầu dùng đến những từ đó trong các câu sau.
Chương trình:
var s : string;
    dem : integer;
{Hàm kiểm tra từ đối xứng}
function doixung(x : string) : boolean;
var y : string;
    i : integer;
begin
     y := '';
     for i := length(x) downto 1 do y := y + x[i];
     if x=y then doixung := true else doixung := false;
end;
{Thủ tục thực hiện tách từ}
procedure tach;
var i, len : integer;
    t : string;
begin
     writeln('Cac tu trong xau:');
     i := 1; len := length(s);
     repeat
{B1: bỏ qua các dấu cách cho đến khi hết xâu hoặc gặp 1 kí tự khác cách:}
           while (s[i]=' ') and (i<=len) do inc(i);
           if i>=len then break; {nếu hết xâu thì dừng}
           t := '';                             {t là biến tạm lưu từ đang tách}
{B2: lấy các kí tự khác cách đưa vào biến tạm cho đến khi hết xâu hoặc gặp 1 kí tự cách:}
           while (s[i]' ') and (i<=len) do begin
                 t := t + s[i];
                 inc(i);
           end;
{in ra từ vừa tách được và kiểm tra đối xứng}
           writeln(t);
           if doixung(t) then inc(dem);
     until i >= len;
     writeln('So tu doi xung trong xau:',dem);
end;
(************************************************)
BEGIN
     write('Nhap vao 1 xau:');
     readln(s);
     tach;
END.
BÀI TẬP 5
Một số nguyên gọi là palindrom nếu nó đọc từ trái sang cũng bằng đọc từ phải sang. Ví dụ 121 là một số palindrom. Nhập một dãy n phần tử nguyên dương từ bàn phím, 5<= n<=20 và các phần tử có 2 đến 4 chữ số. In ra các số là palindrom trong dãy.
HƯỚNG DẪN
Một số là palindrom thì xâu tương ứng của nó là xâu đối xứng. Ta sẽ xây dựng một hàm kiểm tra một số có phải là palindrom không bằng cách chuyển số đó thành xâu và kiểm tra xâu đó có đối xứng không?
Chương trình:
uses crt;
var  n : integer;
     a : array[1..20] of integer;
{Thủ tục nhập dữ liệu}
procedure nhap;
var i : integer;
begin
     clrscr;
     repeat
           write('n= '); readln(n);
           if (n=5) then break; {nếu đã thoả mãn thì thoát khỏi vòng lặp}
           writeln('Yeu cau 5<=n<=20. Nhap lai!');
     until false;
     for i := 1 to n do
          repeat
                write('A[',i,']='); readln(a[i]);
                if (a[i]=10) then break; {a[i] có 2 đến 4 chữ số}
                writeln('Yeu cau cac phan tu co 2 den 4 chu so. Nhap lai!');
          until false;
end;
{Hàm kiểm tra bằng các kiểm tra xâu đối xứng}
function palindrom(k : integer): boolean;
var x,y : string;
    i : integer;
begin
     str(k,x);        {chuyển k thành xâu x}
     y := '';
     for i := length(x) downto 1 do y := y + x[i];
{nếu x là đối xứng thì k là palindrom}
     if x=y then palindrom := true else palindrom := false;
end;
{In kết quả:}
procedure palin;
var i : integer;
begin
     writeln('Cac so la palindrom trong day:');
     for i := 1 to n do
         if palindrom(a[i]) then writeln(a[i]);
     readln;
end;
(* Chương trình chính *)
BEGIN
     nhap;
     palin;
END.
CÁC BÀI TẬP VỀ TỆP
BÀI TẬP 1
Nhập một mảng 2 chiều m dòng, n cột từ file BANGSO.TXT. Cấu trúc file như sau: dòng đầu là 2 số m và n, cách nhau bằng dấu cách, m dòng sau, mỗi dòng n số nguyên.
a)      Hãy in ra những số là số nguyên tố của mảng.
b)      Tìm vị trí phần tử lớn nhất trong mảng.
c)       Sắp xếp mỗi dòng của mảng tăng dần và in ra mảng dạng ma trận.
HƯỚNG DẪN
Ta khai báo một mảng 2 chiều và nhập dữ liệu từ file vào mảng. Quá trình nhập từ file văn bản giống như nhập từ bàn phím, không cần thực hiện kiểm tra dữ liệu.
Để sắp xếp mảng theo yêu cầu, ta thực hiện sắp xếp từng dòng của mảng bằng cách viết một thủ tục sắp xếp (kiểu đổi chỗ cho đơn giản) coi mỗi dòng của mảng như 1 mảng 1 chiều.
Chương trình:
var m,n : integer;
    a : array[1..100,1..100] of integer;
(* Nhập dữ liệu *)
procedure nhap;
var f : text;
    i,j : integer;
begin
     assign(f,'BANGSO.TXT'); reset(f);
     readln(f,m,n);
     for i := 1 to m do
         for j := 1 to n do read(f,a[i,j]);
     close(f);
end;
function ngto(k : integer): boolean;
var i : integer;
begin
     ngto := false;
     if k < 2 then exit;
     for i := 2 to round(sqrt(k)) do
         if k mod i = 0 then exit;
     ngto := true;
end;
procedure inngto;
var i,j : integer;
begin
     writeln('Cac phan tu nguyen to cua mang:');
     for i := 1 to m do
         for j := 1 to n do
             if ngto(a[i,j]) then write(a[i,j],' ');
     writeln;
end;
procedure timmax;
var max,i,j,im,jm : integer;
begin
     max := a[1,1]; im := 1; jm := 1; {im, jm lưu toạ độ phần tử đạt max}
     for i := 1 to m do
         for j := 1 to n do
             if max < a[i,j] then begin
                max := a[i,j];  {mỗi lần gán max thì gán toạ độ luôn}
                im := i; jm := j;
             end;
     writeln('Phan tu lon nhat bang la A[',im,',',jm,']=',max);
end;
{Thủ tục thực hiện sắp xếp tăng dần dòng thứ k. Các phần từ dòng k có dạng a[k,i]}
procedure xepdong(k: integer);
var i,j, tg : integer;
begin
     for i := 1 to n do
         for j := i+1 to n do
             if a[k,i] > a[k,j] then begin
                tg := a[k,i]; a[k,i] := a[k,j]; a[k,j] := tg;
             end;
end;
procedure sapxep;
var i,j : integer;
begin
     for i := 1 to m do xepdong(i); {sắp xếp từng dòng}
     writeln('Mang sau khi sap xep:');
     for i := 1 to m do begin                      {in dạng ma trận}
         for j := 1 to n do write(a[i,j] : 5); {in các phần tử trên 1 dòng}
         writeln;                {in hết 1 dòng thì xuống dòng}
     end;
end;
BEGIN
     nhap;
     inngto;
     timmax;
     sapxep;
END.
BÀI TẬP 2
Nhập 2 số m, n từ bàn phím, sau đó sinh ngẫu nhiên m´n số nguyên ngẫu nhiên có giá trị từ 15 đến 300 để ghi vào file BANG.TXT. Sau đó thực hiện các yêu cầu sau:
a)      In m´n số đã sinh dạng ma trận m dòng, n cột.
b)      In ra các số chính phương.
Yêu cầu: không được dùng mảng 2 chiều để lưu trữ dữ liệu.
HƯỚNG DẪN
Do yêu cầu không được dùng mảng 2 chiều để lưu trữ dữ liệu nên ta sẽ đọc file đến đâu, xử lí đến đấy.
-         Để sinh các số ngẫu nhiên từ a đến b, ta dùng biểu thức a + random(b-a+1).
-         Để kiểm tra số k có phải là số chính phương không, ta lấy căn bậc 2 của k, làm tròn rồi bình phương. Nếu kết quả bằng k thì k là số chính phương. Tức là kiểm tra sqr(round(sqrt(k))) = k.
Chương trình:
var m,n : integer;
    f : text;
procedure sinh;
var
    i,j : integer;
begin
     write('Nhap vao 2 so m,n: '); readln(m,n);
     assign(f,'BANG.TXT'); rewrite(f);
     writeln(f,m,' ',n);
     for i := 1 to m do begin
         for j := 1 to n do
             write(f,15 + random(300-15+1) : 6); {sinh số ngẫu nhiên từ 15 đến 300}
         writeln(f);
     end;
     close(f);
end;
{Hàm chính phương}
function cp(k : integer) : boolean;
begin
     if sqr(round(sqrt(k))) = k then cp := true
     else cp := false;
end;
procedure chinhphuong;
var
    i,j,k : integer;
begin
     assign(f,'BANG.TXT'); reset(f);
     readln(f,m,n);
     writeln('CAC SO CHINH PHUONG CUA BANG:');
     for i := 1 to m do begin
         for j := 1 to n do begin
             read(f,k);
             if cp(k) then write(k,' '); {vừa đọc vừa xử lí}
         end;
     end;
     close(f);
end;
procedure inbang;
var
    i,j,k : integer;
begin
     assign(f,'BANG.TXT'); reset(f); {mở lại để in dạng ma trận}
     readln(f,m,n);
     writeln(#10,'IN BANG DANG MA TRAN:');
     for i := 1 to m do begin
         for j := 1 to n do begin
             read(f,k);
             write(k : 6);      {đọc đến đâu in đến đó}
         end;
         writeln;
     end;
     close(f);
end;
BEGIN
     sinh;
     chinhphuong;
     inbang;
END.
CÁC BÀI TẬP VỀ BẢN GHI
BÀI TẬP 1
Viết chương trình quản lí sách. Mỗi cuốn sách gồm tên sách, tên nhà xuất bản, năm xuất bản, giá tiền, số lượng:
a)      Đưa ra danh sách các cuốn sách của nhà xuất bản Giáo dục.
b)      Tính tổng số tiền sách.
c)       Sắp xếp danh sách theo năm xuất bản giảm dần và ghi kết quả ra màn hình.
d)      In ra màn hình các cuốn sách có giá tiền<=10.000đ và xuất bản sau năm 2000.
HƯỚNG DẪN
Mô tả mỗi cuốn sách là một bản ghi, các thông tin về nó (tên sách, tên tác giả,…) là các trường. Danh sách cuốn sách sẽ là một mảng các bản ghi.
Khai báo kiểu dữ liệu mô tả sách như sau:
type
    sach = record
         ten : string[30];                 {tên sách}
         nxb  : string[20];               {tên Nhà xuất bản}
         namxb   : integer;  {năm xuất bản}
         soluong : integer;  {số lượng}
         gia : real;              {giá tiền}
    end;
Thông tin của tất cả các cuốn sách ta lưu trong một mảng các bản ghi kiểu sach:
var
   ds : array[1..100] of sach;
   n : integer;
Nhập dữ liệu: ta nhập tên sách trước. Nếu tên sách là xâu rỗng thì đừng nhập, ngược lại lần lượt nhập các thông tin khác:
   procedure nhap;
   var t : string;
   begin
        ClrScr;
        writeln('NHAP THONG TIN VE CAC CUON SACH');
        writeln('(nhap ten sach la xau rong neu muon dung)');
        repeat
              write('Ten sach:  ');
              readln(t);
              if t='' then break;
              n := n + 1;
              with ds[n] do begin
                 ten := t;
                 write('NXB:  ');readln(nxb);
                 write('Nam xuat ban:  ');readln(namxb);
                 write('So luong:  ');readln(soluong);
                 write('Gia tien:  ');readln(gia);
              end;
        until false;
   end;
Câu a: ta sẽ duyệt qua toàn bộ danh sách các cuốn sách, kiểm tra nếu tên nhà xuất bản là Giáo dục thì in ra tất cả các thông tin của cuốn sách tương ứng:
   procedure insach;
   var
      i   : integer;
   begin
        Clrscr;
        writeln('CAC CUON SACH CUA NXB GIAO DUC:');
        for i:=1 to n do
            with ds[i] do
                 if nxb='Giao duc' then begin
                    writeln('Ten:',ten);
                    writeln('Nam xuat ban:',namxb);
                    writeln('So luong:',soluong);
                    writeln('Gia tien:',gia);
                 end;
        readln;
   end;
Câu b: ta cũng duyệt qua toàn bộ các cuốn sách, nhân số lượng và giá tiền rồi cộng dồn vào một biến tổng. Sau đó in ra biến tổng đó:
procedure tinh;
var i : integer;
    tong : real;
begin
     tong := 0;
     for i := 1 to n do
         with ds[i] do tong := tong + gia * soluong;
     writeln('TONG GIA TRI CUA TAT CA CAC CUON SACH:', tong:0:3);
end;
Câu c: Sắp xếp danh sách giảm dần theo năm xuất bản bằng phương pháp nổi bọt (2 vòng for). Chú ý biến trung gian trong đổi chỗ phải có kiểu sach thì mới gán được.
procedure sxep;
var i,j : integer;
    tg : sach;
begin
     for i := 1 to n do
         for j := i + 1 to n do
             if ds[i].namxb < ds[j].namxb then begin
                tg := ds[i]; ds[i] := ds[j]; ds[j] := tg;
             end;
     for i:=1 to n do
        with ds[i] do begin
             writeln('Ten:',ten);
             writeln('Nam xuat ban:',namxb);
             writeln('So luong:',soluong);
             writeln('Gia tien:',gia);
        end;
     readln;
end;
Câu d: ta làm tương tự việc in danh sách các sách của NXB Giáo dục:
procedure inds;
var i : integer;
begin
     writeln('CAC CUON SACH GIA RE HON 10000 VA XUAT BAN TU NAM 2000:');
     for i := 1 to n do
         with ds[i] do
              if (gia = 2000) then writeln(ten);
end;
Chương trình chính: Lần lượt gọi các chương trình con theo thứ tự:
BEGIN
     nhap;
     insach;
     tinh;
     sxep;
     inds;
     readln;
END.
BÀI TẬP 2
Viết chương trình quản lí cán bộ. Thông tin về cán bộ gồm tên, tuổi, hệ số lương, phụ cấp, thu nhập.
a)      Nhập thông tin cán bộ từ file văn bản CANBO.TXT. Các thông tin gồm tên, tuổi, hệ số lương, phụ cấp, mỗi thông tin trên một dòng.
Tính thu nhập = hệ số lương ´ 350000đ + phụ cấp
b)      Đưa ra danh sách các bộ trẻ (tuổi <= 30), in đầy đủ các thông tin
c)       Sắp xếp tên cán bộ theo abc và ghi lên file truy cập trực tiếp SAPXEP.DAT.
d)      Đọc danh sách từ file SAPXEP.DAT, in ra màn hình các cán bộ có thu nhập từ 3 triệu trở lên.
HƯỚNG DẪN
Làm tương tự bài 1, chú ý là nhập dữ liệu từ file chứ không phải từ bàn phím. Do đó không cần ghi các thông tin yêu cầu nhập ra màn hình. Hơn nữa, phải tạo trước một file văn bản là CANBO.TXT để chương trình có thể chạy mà không báo lỗi.
Toàn văn chương trình:
uses crt;
type
    canbo = record
          ten : string[20];
          tuoi : byte;
          hsl, phucap, thunhap: real;
    end;
var
   ds : array[1..100] of canbo;
   n : integer;
(*********************************************)
procedure nhap;
var f : text;
begin
     assign(f,'CANBO.TXT'); reset(f);
     n := 0;
     while not eof(f) do begin
           n := n + 1;
           with ds[n] do begin
                readln(f,ten);
                readln(f,tuoi);
                readln(f,hsl);
                readln(f,phucap);
                thunhap := hsl * 350000 + phucap;
           end;
     end;
     close(f);
end;
(*********************************************)
procedure in30;
var i : integer;
begin
     writeln('DANH SACH CAC CAN BO TRE:');
     for i := 1 to n do
         with ds[i] do
              if tuoi <= 30 then begin
                 writeln('Ten:',ten);
                 writeln('Tuoi:',tuoi);
                 writeln('He so luong:',hsl :0 :3);
                 writeln('Phu cap:',phucap :0 :3);
                 writeln('Thu nhap:',thunhap :0 :3);
              end;
end;
(*********************************************)
procedure sxep;
var i,j : integer;
    tg : canbo;
begin
     for i := 1 to n do
         for j := i + 1 to n do
             if ds[i].ten > ds[j].ten then begin
                tg := ds[i]; ds[i] := ds[j]; ds[j] := tg;
             end;
end;
(*********************************************)
procedure ghitep;
var f : file of canbo;
    i : integer;
begin
     assign(f,'SAPXEP.DAT'); rewrite(f);
     for i := 1 to n do write(f,ds[i]);
     close(f);
end;
procedure doctep;
var f : file of canbo;
    i : integer;
begin
     assign(f,'SAPXEP.DAT'); reset(f);
     i := 0;
     while not eof(f) do begin
           i := i + 1;
           read(f,ds[i]);
     end;
     n := i;
     close(f);
end;
(*********************************************)
procedure in3M;
var i : integer;
begin
     writeln('DANH SACH CAC CAN BO CO THU NHAP CAO:');
     for i := 1 to n do
         with ds[i] do
              if thunhap >= 3000000 then begin
                 writeln('Ten:',ten);
                 writeln('Tuoi:',tuoi);
                 writeln('Thu nhap:',thunhap :0 :3);
              end;
end;
(*********************************************)
BEGIN
     nhap;
     in30;
     sxep;
     in3M;
     readln;
END.
THUAÄT TOAÙN( GIAÛI THUAÄT)
       I)Khaùi Nieäm Thuaät Toaùn:
1)giaûi thuaät cuûa moät baøi toaùn laø moät heä thoáng caùc quy taéc chaët cheõ vaø roõ raøng  chaèm xaùc ñònh moät daõy caùc thao taùc treân nhöõng döõ lieäu vaøo ( INPUT) , sao cho sau moät soá höõu haïn böôùc  thöïc hieän caùc thao taùc ta thu ñöôïc keát quaû( OUTPUT) cuûa baøi toaùn
2)Ví duï: cho hai soá nguyeân a,b . caàn xaây döïng giaûi thuaät ñeå tìm öôùc soá chung lôùn nhaát (USCLN) cuûa hai soá a vaø b. Döôùi ñaäy laø giaûi thuaät cuûa nhaø toaùn hoïc coå Hy Laïp Ôcliñeà xuaát cho baøi toaùn treân:
Giaûi thuaät Ôclid:
-         INPUT: a,b nguyeân
-         OUTPUT: USCLN cuûa a vaø b.
Böôùc 1: Chia a cho b tìm soá dö laø r
Böôùc 2: Neáu r=0 thì thoâng baùo keát quaû: USCLN laø b . Döøng giaûi thuaät
Böôùc 3: Neáu r ¹ 0 thì gaùn trò b cho a , gaùn trò r cho b roài quay veà böôùc 1
caùc thao taùc goàm:
-         Pheùp tìm dö: chia soá nnguyeân a cho soá nguyeân b ñeå tìm soá dö laø r
-         Pheùp gaùn trò: ñöa moät giaù trò cuï theå vaøo moät bieán naøo ñoù .
-         Pheùp chuyeån ñieàu khieån: cho pheùp thöïc hieän tieáp töø moät böôùc naøo ñoù ( neáu khoâng coù  gaëp pheùp chuyeån tieáp thì maùy seõ thöïc hieän tuaàn töï : sau böôùc i laø böôùc i+1)
Sau ñaây laø phaàn theå hieän giaûi thuaät Ôclid cuûa Ngoân ngöõ PASCAL thoâng qua moät chöông trình con laø Haøm.
{***************************************************}
 FUNCTION     USCLN( a,b:integer) :Integer;
                             var   r :integer;
                                Begin
                   While b0  do
begin
                             r:= a mod b;
                             a:=b;
                             b:=r;
end;
                                      USCLN:=a;
                             EN