чем анализировать принципы
Прежде, чем анализировать принципы и приемы соствления алгоритмов, приведем несколько примеров.
Пример 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;
