÷åì àíàëèçèðîâàòü ïðèíöèïû
Ïðåæäå, ÷åì àíàëèçèðîâàòü ïðèíöèïû è ïðèåìû ñîñòâëåíèÿ àëãîðèòìîâ, ïðèâåäåì íåñêîëüêî ïðèìåðîâ.
Ïðèìåð 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. Âû÷èñëèòü ÷àñòíóþ ñóììó ðÿäà
à). Áëîê-ñõåìà àëãîðèòìà ñ ïðåäóñëîâèåì.
 |
á). Áëîê-ñõåìà àëãîðèòìà ñ ïîñòóñëîâèåì.
â). Ïðîãðàììà íà Ïàñêàëå ñ ïðåäóñëîâèåì è áåçóñëîâíûì ïåðåõîäîì.
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).
Ýëåìåíò â ìàññèâå îòñóòñòâóåò
á). Ôðàãìåíò ïðîãðàììû íà Ïàñêàëå.
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;
