Bài giảng Nhắc lại kiến thức cơ bản trong pascal

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 ộ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 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; 2. 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; 3. 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;