Программирование на языке Паскаль

Простейшие программы
§ 56. Вычисления
§ 57. Ветвления
§ 58. Циклические алгоритмы
§ 59.

должен выполнить исполнитель для решения задачи за конечное время.
Исполнитель –

Формальные исполнители: не понимают (и не могут понять) смысл команд.

которых выполняется за конечное время.
Детерминированность (определённость) — при каждом запуске

3 4 5
5 4 3 2
дискретный
объект
25 16 9 4
получает

команду
выполнить команду
завершить сеанс связи
установить соединение
нц
принять команду
выполнить

тело программы }
end. { конец программы }
комментарии в скобках

название алгоритма

writeln('2=?'); { на новую строку}
writeln('Ответ: 4');
end.
Протокол:
2+2=?
Ответ:

пошел
гулять
«C»: Вывести

сумму.
Протокол:
Введите два целых числа
25 30
25+30=55
компьютер
пользователь
компьютер считает сам!

их сумму }
{ вывести сумму на экран }
end.

Псевдокод: алгоритм на русском языке с элементами Паскаля.

переменной можно изменять во время работы программы.
a
Значение
Имя
Другой тип данных

НЕ различаются
НЕЛЬЗЯ использовать
русские буквы
пробелы
скобки, знаки +, =, !, ? и

имя не может начинаться с цифры

Какие имена правильные?
AXby R&B 4Wheel Вася “PesBarbos” TU154 [QuQu] _ABBA A+B

b, c: integer;
выделение места в памяти
variable – переменная
тип –

список имен переменных

ошибок

);
Ввод значений двух переменных (через пробел или Enter).

+ 2;
a := (a + 2)*(b – 3);
b := b

a

?

5

5

b

?

5+2

7

a

5

7*4

28

b

7

7+1

8

и переход на новую строку}
{ вывод текста }
{вывод текста и

write( a );

writeln( a );

writeln( 'Привет!' );

writeln( 'Ответ: ', c );

writeln ( a, '+', b, '=', c );

read ( a, b );
c := a +

writeln('Введите два целых числа');
read ( a, b );

Протокол:
Введите два целых числа
25 30
25+30=55

компьютер

пользователь

a, '+', b, '=', a+b );
a+b

-128..128 }
word { целые 0..65535 }
longint { целые

d;
Приоритет (старшинство):
скобки
умножение и деление
сложение и вычитание
2
1
3
4
5
6

3;
var a: single;
0.6666…
div – деление нацело (остаток отбрасывается)
mod – остаток

var a, b, d: integer;
...
d := 85;
b := d div 10; { 8 }
a := d mod 10; { 5 }

2);
-3
-1
-7 = (-3)*2 + (-1)
-7 = (-4)*2 + 1
остаток 

);
3.333333E-001
3,333333  10-1 = 0,3333333
всего знаков
в дробной части

заданного в радианах
cos(x) — косинус угла, заданного в радианах
exp(x) —

выбор:
жеребьевка на соревнованиях
выигравшие номера в лотерее
Как получить случайность?

(последовательность повторяется через 106 чисел)
Метод середины квадрата (Дж. фон Нейман)
в

Псевдослучайные числа – обладают свойствами случайных чисел, но каждое следующее число вычисляется по заданной формуле.

зерно

0 до c-1
X := (X+3) mod 10 | интервал от

X := 0

зерно

 3

 6

 9

 2

 5

 8

 0

зацикливание

8

 1

 4

 7

Компилятор GCC:
a = 1103515245
b = 12345
c = 231

double;
...
X:= random; { интервал от 0 до 1 (

англ. random – случайный

Целые числа в интервале [0,10):

var K, L: integer;
...
K:= random( 10 ) { интервал от 0 до 9 (<10) }
L:= random( 10 ) { это уже другое число! }

расширение интервала: [0,10) }
X:= random*10 + 5;

var K, a, b: integer;
...
K:= random(10) + 5; { [5,14] }
X:= random(b-a+1) + a; { [a,b] }

Целые числа:

произведение и среднее арифметическое.
Пример:
Введите три целых числа:
5 7 8
5+7+8=20
5*7*8=280
(5+7+8)/3=6.667
«B»:

отдельные цифры.
Пример:
Получено число 123.
Его цифры 1, 2, 3.

условия.
полная форма ветвления

a
else
M:= b;
if a > b then

> a then
M:= b;

a:= b;
b:= c
end;
4
6
?
4
6
4
a
b
3
2
1
c

= b then
writeln('Одного возраста')
else
writeln('Борис старше');
вложенный условный оператор
Задача: в

a = b then write('=') else write('Б');
if a > b

три целых числа:
1 5 4
Максимальное число 5
«B»: Ввести пять целых

из них старше.
Пример:
Возраст Антона: 15
Возраст Бориса: 17
Возраст

and

or

not

Приоритет :
not
and
or, xor
отношения (<, >, <=, >=, =, <>)

xor

исключающее «ИЛИ»

(v >= 25) and (v <= 40)

сложное условие

одинаковых чисел в этой цепочке.
Пример:
Введите три числа:
5 5

ему время года или сообщение об ошибке.
Пример:
Введите номер месяца:
5
Весна.
Пример:
Введите

превышающее 120) и выводит этот возраст со словом «год», «года»

которое определяет заштрихованную область.

2 then
write('февраль');
...
if m = 12 then
write('декабрь');
case

{ невисокосный год }
1,3,5,7,8,10,12: d:= 31
else d:=

Число дней в месяце:

Социальный статус:

case v of
0..6: write('дошкольник');
7..17: write('школьник')
else write('взрослый')
end;

writeln('антилопа');

несколько операторов в блоке

циклов:
цикл с известным числом шагов (сделать 10 раз)
цикл с неизвестным

Задача. Вывести на экран 10 раз слово «Привет».

на 1
счётчик:= 10
пока счётчик > 0
writeln('привет');
уменьшить счётчик



результат операции автоматически сравнивается с нулём!

положительного числа, записанного в переменную n.
счётчик:= 0
пока n > 0

n:= n div 10

счётчик:= счётчик + 1

div 10;
count:= count + 1

тело цикла
начальное значение счётчика
n > 0
условие

заголовок цикла

k:= k + 1
end;
При известном количестве шагов:
k:= 0;
while k

Зацикливание:

do a:= a + 1;
2 раза
a = 6
a:= 4; b:=

1 раз
a = 10

a:= 4; b:= 6;
while a > b do a:= a + 1;

0 раз
a = 4

a:= 4; b:= 6;
while a < b do b:= a - b;

1 раз
b = -2

a:= 4; b:= 6;
while a < b do a:= a - 1;

зацикливание

> 0: ');
read(n)
n > 0
тело цикла
при входе в цикл условие

B (0 < A < B) и выводит квадраты всех

«B»: Напишите программу, которая получает два целых числа и находит их произведение, не используя операцию умножения. Учтите, что числа могут быть отрицательными.
Пример:
Введите два числа:
10 -15
10*(-15)=-150

Фибоначчи, меньших N. Предусмотрите защиту от ввода отрицательного числа N.

натуральное число:
12345
Сумма цифр 15.
«B»: Ввести натуральное число и определить, верно

его записи есть две одинаковые цифры (не обязательно стоящие рядом).

210.
 
n:= 2;
while   do
begin
writeln(n);
n:= n *

k:= 1;

k <= 10

k:= k + 1

n:= 2;
for do
begin
writeln(n);
n:= n * 2
end;

k:= 1 to 10

1 do 
writeln(k*k);
downto
var k: integer;
целое
целое
шаг «–1»

for i:=

k:= 1;

k:= k + 2

a := a+1;
a = 4
a := 1;
for i:=3 to 1

a = 1

a := 1;
for i:=1 downto 3 do a := a+1;

a = 1

a := 1;
for i:=3 downto 1 do a := a+1;

a = 4

дают в остатке 125, а при делении на 134 дают

своего квадрата. Например, 252 = 625. Напишите программу, которая получает

1000.
для n от 2 до 1000
если число n

число n простое

нет делителей [2.. n-1]: проверка в цикле!

0;



if count = 0 then
writeln(n)
end;
for k:= 2

вложенный цикл

do
writeln(i, ' ', k);
1 1
2 1
2 2
3 1
3

do begin
if n mod k = 0 then

while k <= sqrt(n) do begin
...
end;

while (k*k <= n) and
do begin
...
end;

k*k <= n

(count = 0)

(A

не превосходящие N и делящиеся на каждую из своих цифр.

n < 0 then Error;
...
end.
procedure Error;
begin
writeln('Ошибка программы')
end;
вызов

(расшифровка) процедуры записывается до основной программы
в программе может быть много

в 8-битном двоичном коде.
много раз!
Алгоритм:
178

101100102
7 6 5 4 3

1 0 1 1 0 0 1 02

разряды

n:=

n div 128

n mod 128

n1 div 64

в 8-битном двоичном коде.
Алгоритм:
k:= 128;
while k > 0 do

178



10110010

128;
while k > 0 do begin
write(n div

Параметры – данные, изменяющие работу процедуры.

локальная переменная

значение параметра
(аргумент)

b: integer);
begin
write((a+b)/2);
end.
procedure printSred(a, b: integer);
begin
write((a+b)/2);
end.

– и выводит на экран линию из N символов '–'.

числа в римской системе счисления.
Пример:
Введите натуральное число:
2013
MMXIII

program Exchange;
var x, y: integer;






begin
x:= 2; y:= 3;
Swap(x,

procedure Swap(a, b: integer);
var c: integer;
begin
c:= a; a:= b; b:= c;
end;

2 3

передача по значению

c:= a; a:= b; b:= c;
end;
var
передача по ссылке
переменные могут изменяться
var

Вызов:

порядке возрастания.
Пример:
Введите три натуральных числа:
10 15 5
5 10 15
«B»:

общее кратное двух натуральных чисел и возвращает их через изменяемые

(число, символ или объект другого типа).
Задача. Написать функцию, которая вычисляет

Алгоритм:

сумма:= 0;
while n <> 0 do begin
сумма:= сумма + n mod 10;
n:= n div 10
end;

;
var sum: integer;
begin
sum:= 0;
while n 0

sumDigits:= sum

передача результата

integer

тип результата

0 then begin
writeln('Сумма цифр чётная');
writeln('Она равна ', sumDigits(n))

чисел.
Пример:
Введите два натуральных числа:
7006652 112307574
НОД(7006652,112307574) = 1234.
«B»: Напишите функцию,

в котором цифры стоят в обратном порядке.
Пример:
Введите натуральное число:
1234
После

до 100.
program PrimeNum;
var i: integer;
begin
for i:=2 to 100

i - простое

функция, возвращающая логическое значение (True/False)

isPrime(i)

;
var count, k: integer;
begin
count:= 0;
k:= 2;
while (k*k

boolean

логическое значение (True/False)

isPrime:= (count = 0)

if count = 0 then
isPrime:= True
else isPrime:= False

read(n)
end;

число совершенным, то есть, равно ли оно сумме своих делителей,

ей числа взаимно простыми, то есть, не имеющими общих делителей,

него откидыванием нескольких цифр, тоже является простым. Например, число 733

кусок мяса, он её убил, В землю закопал, Надпись написал:
У попа была

объектов через само это множество на основе заданных простых базовых

Числа Фибоначчи:

1, 1, 2, 3, 5, 8, 13, 21, 34, …

на больший
третий стержень вспомогательный
перенести (n-1, 1, 2)
1 -> 3
перенести (n-1,

перенести (n, 1, 3)

integer;
begin
p := 6 - k – m;
Hanoi(n-1, k,

номер вспомогательного стержня (1+2+3=6!)

сколько

откуда

куда

рекурсия

рекурсия

(функция), которая вызывает сама себя напрямую или через другие процедуры

proceduer Hanoi(n, k, m: integer);
var p: integer;
begin

p := 6 - k – m;
Hanoi(n-1, k, p);
writeln(k, ' -> ', m);
Hanoi(n-1, p, m)
end;

if n = 0 then exit;

условие выхода из рекурсии

program HanoiTower;
...
begin
Hanoi(4, 1, 3)
end.

then exit;
printBin ( n div 2 );
write( n

условие выхода из рекурсии

напечатать все цифры, кроме последней

вывести последнюю цифру

10011

printBin( 19 )

printBin( 9 )

printBin( 4 )

printBin( 2 )

printBin( 1 )

printBin( 0 )

n mod 10;
if n >= 10 then
sum:=

рекурсивный вызов

последняя цифра

sumDig( 1234 )

4 + sumDig( 123 )

4 + 3 + sumDig( 12 )

4 + 3 + 2 + sumDig( 1 )

4 + 3 + 2 + 1

вычитать из большего числа меньшее до тех пор, пока меньшее

function NOD(a, b: integer): integer;
begin
if (a = 0) or (b = 0) then begin

exit
end;
if a > b then
NOD:= NOD(a - b, b)
else NOD:= NOD(a, b - a)
end;

NOD:= a + b;

рекурсивные вызовы

условие окончания рекурсии

используя модифицированный алгоритм Евклида.
Пример:
Введите два натуральных числа:
7006652 112307574
НОД(7006652,112307574)=1234.
«B»: Напишите

экран количество всех возможных различных способов представления этого числа в

N);
if N

-> N = 3
-> N = 2
-> N = 1
<- N = 1
<- N = 2
<- N = 3

Факториал:

адреса возврата.
Fact(3)
Fact(2)
Fact(1)
значение параметра
адрес возврата
локальная переменная

в стеке (возможно переполнение стека)
затраты на выполнение служебных операций при

программа становится более короткой и понятной

возможно переполнение стека
замедление работы

function Fact(N: integer): integer;
var i, F: integer;
begin
F:= 1;
for i:= 1 to N do
F:= F * i;
Fact:= F
end;

итерационный алгоритм

Санкт-Петербург
kpolyakov@mail.ru
ЕРЕМИН Евгений Александрович
к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО

«Бином»
авторские материалы