Îðãàíèçàöèÿ è ôóíêöèîíèðîâàíèå êîìïüþòåðîâ

         

÷åì àíàëèçèðîâàòü ïðèíöèïû


Ïðåæäå, ÷åì àíàëèçèðîâàòü ïðèíöèïû è ïðèåìû ñîñòâëåíèÿ àëãîðèò­ìîâ, ïðèâåäåì íåñêîëüêî ïðèìåðîâ.
Ïðèìåð 1. Âû÷èñëåíèå ðàññòîÿíèÿ ìåæäó äâóìÿ òî÷êàìè íà ïëîñêîñòè.
à). Áëîê-ñõåìà àëãîðèòìà.              
á).Ïðîãðàììà íà Ïàñêàëå.
program  length;
var       x1,x2,y1,y2,r: real;
begin  readln (x1,y1,x2,y2);
             r := (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
             r := sqrt (r);
             writeln (r)
end.
Ïðèìåð 2.   Âû÷èñëèòü ÷àñòíóþ ñóììó ðÿäà 

à). Áëîê-ñõåìà àëãîðèòìà ñ ïðåäóñëîâèåì.
                k=1; s=0                         k£n         äà               s=s+1/k2; k=k+1                                          ðåçóëüòàò â s
                                                               íåò


á). Áëîê-ñõåìà àëãîðèòìà ñ ïîñòóñëîâèåì.
                                                                                                                                                    äà
                k=0; s=0                         k=k+1                       s=s+1/k2                                         k£n         íåò           ðåçóëüòàò â s
â). Ïðîãðàììà íà Ïàñêàëå ñ ïðåäóñëîâèåì è áåçóñëîâíûì ïåðåõîäîì.
program  summa;
var          k,n: integer;  s: real;
label      m1,m2;
begin     readln (n);
                s := 0;  k := 1;
   m1:      if  k>n  then  goto  m2;
                s := s + 1/(k*k);               k := k+1;                goto  m1;
   m2:      writeln (s)
end.
ã). Ïðîãðàììà íà Ïàñêàëå ñ ïîñòóñëîâèåì è áåçóñëîâíûì ïåðåõîäîì.
program  summa;
var          k,n: integer;  s: real;
label      m1;
begin     readln (n);
                s := 0;
                k := 0;
   m1:      k := k+1;
                s := s + 1/(k*k);
                if  k<=n  then  goto  m1;
                writeln (s)
end..
ä). Ïðîãðàììà íà Ïàñêàëå ñ îïåðàòîðîì öèêëà ñ ïðåäóñëîâèåì, ýêâèâàëåíò­íàÿ ïðîãðàììå ïóíêòà â).
program  summa;
var       k,n: integer;  s: real;
begin  readln (n);


             s := 0;
             k := 1;
             while  k<=n  do
             begin  s := s + 1/(k*k);
                         k := k+1;
                   end;
             writeln (s)
end.
å). Ïðîãðàììà íà Ïàñêàëå ñ îïåðàòîðîì öèêëà ñ ïîñòóñëîâèåì, ýêâèâàëåíòíàÿ ïðîãðàììå ïóíêòà ã).
program  summa;
var       k,n: integer;  s: real;
begin  readln (n);
             s := 0;
             k := 0;
      repeat    k := k+1;
                      s := s + 1/(k*k);
             until  k>n;          
             writeln (s)
end.
æ). Ïðîãðàììà íà Ïàñêàëå ñ îïåðàòîðîì öèêëà ñî ñ÷åò÷èêîì.
program  summa;
var   k,n: integer;  s: real;
begin  readln (n);
             for  k := 1  to  n  do      s := s + 1/(k*k);
             writeln (s)
end.
Ç). Äðóãîé âàðèàíò öèêëà:
program  summa;
var   k,n: integer;  s: real;
begin  readln (n);
             for  k := n  downto 1 do s := s + 1/(k*k);
             writeln (s)
end.

Ïðèìåð 3. Ïîèñê çíà÷åíèÿ x â ìàññèâå a.
à). Áëîê-ñõåìà àëãîðèòìà (äëèíà ìàññèâà ðàâíà 100).
                                                                                                                           íåò
             n=0                  n=n+1                          n>100       íåò             a[n]=x          äà            Ýëåìåíò èìååò â ìàññèâå íîìåð n             
                                                                                     äà
                                                    Ýëåìåíò â ìàññèâå îòñóòñòâóåò
á). Ôðàãìåíò ïðîãðàììû íà Ïàñêàëå.
var       n,x: integer;
             a: array [1..100] of integer;
label   m1 ;
begin  {Çàïîëíèòü ìàññèâ a}
             readln (x);
             for  n:=1  to  100  do
                if  a[n] = x  then  goto  m1;
             n := 0;
             m1:            ...;
end.
Ïðèìåð 4. Îïðåäåëåíèå íîìåðà äíÿ â íåâèñîêîñíîì ãîäó ïî ÷èñëó è ìåñÿöó (ïðîãðàììà íà Ïàñêàëå).
function  numerday (d,m: integer): integer;  {d- äåíü, m


- ìåñÿö}
const   a: array [1..12] of
integer = (31,28,31,30,31,30,31,31,30,31,30,31);
             b: array [1..12] of integer = (0,31,59,90,120,151,181,212,243,273,304,334);
begin  if  (m>=1) and
(m<=12) and (d>=1) and (d<=a[m] )
                then  numerday := b[m]+d
                else   numerday := 0
end;
Ïðèìåð 5. Îïðåäåëåíèå äíÿ è ìåñÿöà â íåâèñîêîñíîì ãîäó ïî íîìåðó äíÿ.
à). Ïðîöåäóðà íà Ïàñêàëå.
procedure  date (n: integer; var  d,m: integer);
const   b: array [1..12] of
integer = (0,31,59,90,120,151,181,212,243,273,304,334);
var       n: integer;
label   m1;
begin  for  m:=1  to  11  do
                if  n<=b[m+1]  then  goto  m1;
             if  n<=365
                then     m := 12
                else      m := 0;
   m1:   if  m>0
                then     d := n - b[m]
                else      d := 0
end;
Ïðèìåð 6.   Óñòàíîâèòü, ÿâëÿåòñÿ ëè äàííîå öåëîå ÷èñëî  n  ïðîñòûì.
à). Ñëîâåñíûé àëãîðèòì. Íàäî ïåðåáðàòü âñå íàòóðàëüíûå ÷èñëà  k, ìåíüøèå êâàäðàòíîãî êîðíÿ èç çàäàííîãî ÷èñëà  n.  Åñëè äëÿ êàêîãî-òî k  ÷èñëî  n  äåëèòñÿ íà  k  íàöåëî, òî  n  ñîñòàâíîå, â ïðîòèâíîì ñëó÷àå îíî ïðîñòîå.
á). Ôóíêöèÿ íà Ïàñêàëå.
function  simple (n: integer): boolean;
var       k,m: longint;  b: boolean;
label   m1;
begin  b := true;
             m := trunc (sqrt (n) );
             for  k:=2  to  m  do
                   if  (n mod k)=0  then
                         begin  b := false;
                                      goto  m1
                         end;
   m1:   simple := b
end;
Ïðèìåð 7.   Îïðåäåëèòü êîëè÷åñòâî ïðîñòûõ äåëèòåëåé â ïîëíîì ðàçëîæåíèè çàäàííîãî ÷èñëà  n.
à). Ñëîâåñíûé àëãîðèòì. Ïåðåáîðîì â âîçðàñòàþùåì ïîðÿäêå íàéäåì íàèìåíüøåå ÷èñëî  k,  íà êîòîðîå äåëèòñÿ äàííîå ÷èñëî  n. Åñëè  k=n, çíà÷èò ÷èñëî  n  ïðîñòîå è ñîñòîèò èç îäíîãî ïðîñòîãî ìíîæèòåëÿ. Åñëè  k<n, êîëè÷åñòâî ïðîñòûõ ñîìíîæèòåëåé ÷èñëà  n  íà åäèíèöó áîëüøå êîëè÷åñòâà ïðîñòûõ ñîìíîæèòåëåé ÷èñëà  n/k.


Ýòî ìîæíî âûðàçèòü òàê íàçûâàåìîé ðåêóððåíòíîé ôîðìóëîé:  f(n)=1+f(n/k).  ýòîé ôîðìóëå ôóíêöèÿ fn âûðàæàåòñÿ ÷åðåç ñàìó ñåáÿ, íî îò ìåíüøåãî çíà÷åíèÿ àðãóìåíòà.
á). Ðåêóðñèâíàÿ ôóíêöèÿ íà Ïàñêàëå (ôóíêöèÿ, â êîòîðîé îäèí èç îïåðàòîðîâ ïðåäñòàâëÿåò ñîáîé âûçîâ ñåáÿ ñàìîé).
function  fn (n: longint): integer;
var       k,m: longint;  p: integer;
label   m1;
begin  p := 1;
             m := trunc (sqrt (n) );
             for  k:=1  to  m  do
                if  (n mod k)=0  then
                   begin  p := 1+fn (n div k);
                               goto  m1
                   end;
   m1:   fn := p
end;
Ïðèìåð 8. Îïèñàòü ñîáûòèå: “Êàðòà Ê1  áüåò êàðòó Ê2, âêëþ÷àÿ ó÷åò êîçûðíîé ìàñòè”.
à). Ôóíêöèÿ íà Ïàñêàëå.
type
   suit = (spades, clubs, diamonds, hearts);
   value = (c7,c8,c9,c10,jack,queen,king,ace);
   card = record  s: suit;  v: value  end;
function  beat (sc: suit; c1,c2: card): boolean;
begin
   if  c1.s=sc
      then beat := ( (c2.s <> sc) or ( (c2.s = sc) and (c1.v > c2.v) ) )
      else  beat := ( (c1.s=c2.s) and (c1.v > c2.v) )
end;
Ïðèìåð 9. Îïðåäåëåíèå êîëè÷åñòâà ïðîñòûõ ÷èñåë, ìåíüøèõ èëè ðàâíûõ äàííîìó ÷èñëó n.
à). Àëãîðèòì (ðåøåòî Ýðàòîñôåíà).
Ñíà÷àëà âñå ÷èñëà îò 2 äî n ñ÷èòàþòñÿ ïðîñòûìè. Çàòåì, íà÷èíàÿ ñ 2, äëÿ êàæäîãî ÷èñëà k, äëÿ êîòîðîãî óæå óñòàíîâëåíî, ÷òî îíî ïðîñòîå, ïðîèçâî­äèòñÿ ñëåäóþùàÿ ïðîöåäóðà: âñå ÷èñëà, êðàòíûå  k, ñ÷èòàþòñÿ ñîñòàâíûìè. Ïðîöåäóðà çàêàí÷èâàåòñÿ, êîãäà  k2>n. Ïîñëå ýòîãî ïîäñ÷èòû­âà­­åòñÿ ÷èñëî ïðîñòûõ ÷èñåë.
á). Ôóíêöèÿ íà Ïàñêàëå.
function  eratosphen (n: integer): integer;   {n <= 255}
var
   simple: set of  2..255;   {Ìíîæåñòâî ïðîñòûõ ÷èñåë}
   k,m,p,s: integer;
begin
   simple := [2..n];  {Ñíà÷àëà âñå ÷èñëà îò 2 äî n ñ÷èòàþòñÿ ïðîñòûìè}
   m := trunc (sqrt (n) );
   for  k:=2  to  m  do
      if  (k  in  simple)  then
         begin
             p := 2*k;
             while  p<=n  do
                begin
                   simple := simple - [p];  {×èñëî p íå ÿâëÿåòñÿ ïðîñòûì}
                   p := p+k
                end
         end;
   s := 0;
   for  k:=2  to  n  do
      if  (k  in  simple)  then  s := s+1;
   eratosphen := s
end;

Ñîäåðæàíèå ðàçäåëà