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

Содержание

Слайд 2

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

§ 54. Алгоритм и его свойства

Программирование на языке Паскаль § 54. Алгоритм и его свойства

Слайд 3

Что такое алгоритм?

Алгоритм — это точное описание порядка действий, которые должен выполнить

Что такое алгоритм? Алгоритм — это точное описание порядка действий, которые должен
исполнитель для решения задачи за конечное время.

Исполнитель – это устройство или одушёвленное существо (человек), способное понять и выполнить команды, составляющие алгоритм.

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

Слайд 4

Свойства алгоритма

Дискретность — алгоритм состоит из отдельных команд, каждая из которых выполняется

Свойства алгоритма Дискретность — алгоритм состоит из отдельных команд, каждая из которых
за конечное время.
Детерминированность (определённость) — при каждом запуске алгоритма с одними и теми же исходными данными получается один и тот же результат.
Понятность — алгоритм содержит только команды, входящие в систему команд исполнителя.
Конечность (результативность) — для корректного набора данных алгоритм должен завершаться через конечное время.
Корректность — для допустимых исходных данных алгоритм должен приводить к правильному результату.

Слайд 5

Как работает алгоритм?

дискретный
объект
1 2 3 4

алгоритм

шаг 1

шаг 2

шаг 3

2 3 4

Как работает алгоритм? дискретный объект 1 2 3 4 алгоритм шаг 1
5

5 4 3 2

дискретный
объект
25 16 9 4

получает на вход дискретный объект
в результате строит другой дискретный объект (или выдаёт сообщение об ошибке)
обрабатывает объект по шагам
на каждом шаге получается новый дискретный объект

Слайд 6

Способы записи алгоритмов

естественный язык
псевдокод

установить соединение
пока не принята команда «стоп»
принять команду
выполнить

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

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

Слайд 7

Способы записи алгоритмов

блок-схема

setConnection;
repeat
cmd:= getCommand;
executeCommand(cmd);
until cmd = "stop";
closeConnection;

программа

Способы записи алгоритмов блок-схема setConnection; repeat cmd:= getCommand; executeCommand(cmd); until cmd = "stop"; closeConnection; программа

Слайд 8

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

§ 55. Простейшие программы

Программирование на языке Паскаль § 55. Простейшие программы

Слайд 9

Простейшая программа

program qq;
begin { начало программы }
{ тело программы }
end.

Простейшая программа program qq; begin { начало программы } { тело программы
{ конец программы }

комментарии в скобках {} не обрабатываются

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

Слайд 10

Вывод на экран

program qq;
begin
write('2+'); { без перехода }
writeln('2=?'); { на

Вывод на экран program qq; begin write('2+'); { без перехода } writeln('2=?');
новую строку}
writeln('Ответ: 4');
end.

Протокол:
2+2=?
Ответ: 4

Слайд 11

Задания

«B»: Вывести на экран текст «лесенкой»
Вася
пошел
гулять
«C»: Вывести на экран

Задания «B»: Вывести на экран текст «лесенкой» Вася пошел гулять «C»: Вывести
рисунок из букв
Ж
ЖЖЖ
ЖЖЖЖЖ
ЖЖЖЖЖЖЖ
HH HH
ZZZZZ

Слайд 12

Сложение чисел

Задача. Ввести с клавиатуры два числа и найти их сумму.

Протокол:
Введите

Сложение чисел Задача. Ввести с клавиатуры два числа и найти их сумму.
два целых числа
25 30
25+30=55

компьютер

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

компьютер считает сам!

Слайд 13

Сумма: псевдокод

program qq;
begin
{ ввести два числа }
{ вычислить их сумму

Сумма: псевдокод program qq; begin { ввести два числа } { вычислить
}
{ вывести сумму на экран }
end.

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

Слайд 14

Переменные

Переменная – это величина, имеющая имя, тип и значение. Значение переменной можно

Переменные Переменная – это величина, имеющая имя, тип и значение. Значение переменной
изменять во время работы программы.

a

Значение

Имя

Другой тип данных

Слайд 15

Имена переменных

МОЖНО использовать
латинские буквы (A-Z)
цифры
знак подчеркивания _

заглавные и строчные буквы НЕ различаются

НЕЛЬЗЯ

Имена переменных МОЖНО использовать латинские буквы (A-Z) цифры знак подчеркивания _ заглавные
использовать
русские буквы
пробелы
скобки, знаки +, =, !, ? и др.

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

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

Слайд 16

Объявление переменных

Типы переменных:
integer { целая }
real { вещественная }
и другие…

Объявление переменных:

var a, b, c:

Объявление переменных Типы переменных: integer { целая } real { вещественная }
integer;

выделение места в памяти

variable – переменная

тип – целые

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

Слайд 17

Тип переменной

область допустимых значений
допустимые операции
объём памяти
формат хранения данных
для предотвращения случайных ошибок

Тип переменной область допустимых значений допустимые операции объём памяти формат хранения данных для предотвращения случайных ошибок

Слайд 18

Ввод значения в переменную

read ( a );

оператор ввода

5

a

Ввод значения в переменную read ( a ); оператор ввода 5 a

Слайд 19

Ввод значений переменной

через пробел:
25 30
через Enter:
25
30

read ( a, b );

Ввод значений

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

Слайд 20

Изменение значений переменной

var a, b: integer;
...
a := 5;
b := a + 2;
a

Изменение значений переменной var a, b: integer; ... a := 5; b
:= (a + 2)*(b – 3);
b := b + 1;

a

?

5

5

b

?

5+2

7

a

5

7*4

28

b

7

7+1

8

Слайд 21

Вывод данных

{ вывод значения переменной a}

{ вывод значения переменной a и переход

Вывод данных { вывод значения переменной a} { вывод значения переменной a
на новую строку}

{ вывод текста }

{вывод текста и значения переменной c}

write( a );

writeln( a );

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

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

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

Слайд 22

Сложение чисел: простое решение

program Sum;
var a, b, c: integer;
begin
read ( a,

Сложение чисел: простое решение program Sum; var a, b, c: integer; begin
b );
c := a + b;
writeln ( c );
end.

Слайд 23

Сложение чисел: полное решение

program Sum;
var a, b, c: integer;
begin
writeln('Введите два целых

Сложение чисел: полное решение program Sum; var a, b, c: integer; begin
числа');
read ( a, b );
c := a + b;
writeln ( a, '+', b, '=', c );
end.

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

компьютер

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

Слайд 24

Снова про оператор вывода

a:= 123;
write( a:5 );

Форматный вывод:

Вычисление выражений:

writeln ( a, '+',

Снова про оператор вывода a:= 123; write( a:5 ); Форматный вывод: Вычисление
b, '=', a+b );

a+b

Слайд 25

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

§ 56. Вычисления

Программирование на языке Паскаль § 56. Вычисления

Слайд 26

Типы данных

byte { целые 0..255 }
shortint { целые -128..128 }
word { целые

Типы данных byte { целые 0..255 } shortint { целые -128..128 }
0..65535 }
longint { целые –2147483648..2147483647 }
single { вещественная, 4 байта }
real { вещественная, 6 байта }
double { вещественная, 8 байтов }
extended { вещественная, 10 байтов }
boolean { логическая, 1 байт }
char { символ, 1 байт }
string { символьная строка }

Слайд 27

Арифметические выражения

a:= (c + b*5*3 - 1) / 2 * d;

Приоритет (старшинство):
скобки
умножение

Арифметические выражения a:= (c + b*5*3 - 1) / 2 * d;
и деление
сложение и вычитание

2

1

3

4

5

6

Слайд 28

Деление, div, mod

Результат деления «/» – вещественное число:

a:= 2 / 3;

var a:

Деление, div, mod Результат деления «/» – вещественное число: a:= 2 /
single;

0.6666…

div – деление нацело (остаток отбрасывается)
mod – остаток от деления

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

Слайд 29

div и mod для отрицательных чисел

write(-7 div 2, ',');
write(-7 mod 2);

-3
-1

-7 =

div и mod для отрицательных чисел write(-7 div 2, ','); write(-7 mod
(-3)*2 + (-1)

-7 = (-4)*2 + 1

остаток ≥ 0

Слайд 30

Вещественные числа

var x: double;
...
x:= 123.456;

Форматный вывод:

a:= 1;
write( a/3 );
write( a/3:7:3 );

3.333333E-001

3,333333 ⋅

Вещественные числа var x: double; ... x:= 123.456; Форматный вывод: a:= 1;
10-1 = 0,3333333

всего знаков

в дробной части

Слайд 31

Стандартные функции

abs(x) — модуль
sqrt(x) — квадратный корень
sin(x) — синус угла, заданного в

Стандартные функции abs(x) — модуль sqrt(x) — квадратный корень sin(x) — синус
радианах
cos(x) — косинус угла, заданного в радианах
exp(x) — экспонента ех
ln(x) — натуральный логарифм
trunc(x)— отсечение дробной части
round(x)— округление до ближайшего целого

Слайд 32

Случайные числа

Случайно…
встретить друга на улице
разбить тарелку
найти 10 рублей
выиграть в лотерею

Случайный выбор:
жеребьевка на

Случайные числа Случайно… встретить друга на улице разбить тарелку найти 10 рублей
соревнованиях
выигравшие номера в лотерее

Как получить случайность?

Слайд 33

Случайные числа на компьютере

Электронный генератор

нужно специальное устройство
нельзя воспроизвести результаты

318458191041

564321

209938992481

458191

938992

малый период (последовательность повторяется

Случайные числа на компьютере Электронный генератор нужно специальное устройство нельзя воспроизвести результаты
через 106 чисел)

Метод середины квадрата (Дж. фон Нейман)

в квадрате

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

зерно

Слайд 34

Линейный конгруэнтный генератор

X := (a*X+b) mod c | интервал от 0 до

Линейный конгруэнтный генератор X := (a*X+b) mod c | интервал от 0
c-1

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

X := 0

зерно

→ 3

→ 6

→ 9

→ 2

→ 5

→ 8

→ 0

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

8

→ 1

→ 4

→ 7

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

Слайд 35

Генератор случайных чисел

Вещественные числа в интервале [0,1):

var X, Y: double;
...
X:= random;

Генератор случайных чисел Вещественные числа в интервале [0,1): var X, Y: double;
{ интервал от 0 до 1 (<1) }
Y:= random; { это уже другое число! }

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

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

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

Слайд 36

Другой интервал

Вещественные числа:

var X, a, b: double;
...
X:= random*10; { расширение интервала:

Другой интервал Вещественные числа: var X, a, b: double; ... X:= random*10;
[0,10) }
X:= random*10 + 5;
{ расширение и сдвиг: [5,15) }
X:= random*(b-a) + a;
{ расширение и сдвиг: [a,b) }

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

Целые числа:

Слайд 37

Задачи

«A»: Ввести с клавиатуры три целых числа, найти их сумму, произведение и

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

«B»: Ввести с клавиатуры координаты двух точек (A и B) на плоскости (вещественные числа). Вычислить длину отрезка AB.
Пример:
Введите координаты точки A:
5.5 3.5
Введите координаты точки B:
1.5 2
Длина отрезка AB = 4.272

Слайд 38

Задачи

«C»: Получить случайное трехзначное число и вывести через запятую его отдельные цифры.

Задачи «C»: Получить случайное трехзначное число и вывести через запятую его отдельные

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

Слайд 39

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

§ 57. Ветвления

Программирование на языке Паскаль § 57. Ветвления

Слайд 40

Условный оператор

Задача: изменить порядок действий в зависимости от выполнения некоторого условия.

полная форма

Условный оператор Задача: изменить порядок действий в зависимости от выполнения некоторого условия. полная форма ветвления
ветвления

Слайд 41

Условный оператор: полная форма

if a > b then
M:= a
else

Условный оператор: полная форма if a > b then M:= a else

M:= b;

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

Слайд 42

Условный оператор: неполная форма

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

M:= a;
if b > a then

Условный оператор: неполная форма неполная форма ветвления M:= a; if b > a then M:= b;
M:= b;

Слайд 43

Условный оператор

if a < b then begin
с:= a;
a:=

Условный оператор if a с:= a; a:= b; b:= c end; 4
b;
b:= c
end;

4

6

?

4

6

4

a

b

3

2

1

c

Слайд 44

Знаки отношений

>

<

>=

<=

=

<>

больше, меньше

больше или равно

меньше или равно

равно

не равно

Знаки отношений > >= = больше, меньше больше или равно меньше или равно равно не равно

Слайд 45

Вложенный условный оператор

if a > b then
writeln('Андрей старше')
else

if a = b

Вложенный условный оператор if a > b then writeln('Андрей старше') else if
then
writeln('Одного возраста')
else
writeln('Борис старше');

вложенный условный оператор

Задача: в переменных a и b записаны возрасты Андрея и Бориса. Кто из них старше?

Слайд 46

Выделение структуры отступами

if a > b then write('А') else if a =

Выделение структуры отступами if a > b then write('А') else if a
b then write('=') else write('Б');

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

Слайд 47

Задачи

«A»: Ввести три целых числа, найти максимальное из них.
Пример:
Введите три целых

Задачи «A»: Ввести три целых числа, найти максимальное из них. Пример: Введите
числа:
1 5 4
Максимальное число 5

«B»: Ввести пять целых чисел, найти максимальное из них.
Пример:
Введите пять целых чисел:
1 5 4 3 2
Максимальное число 5

Слайд 48

Задачи

«C»: Ввести последовательно возраст Антона, Бориса и Виктора. Определить, кто из них

Задачи «C»: Ввести последовательно возраст Антона, Бориса и Виктора. Определить, кто из
старше.
Пример:
Возраст Антона: 15
Возраст Бориса: 17
Возраст Виктора: 16
Ответ: Борис старше всех.
Пример:
Возраст Антона: 17
Возраст Бориса: 17
Возраст Виктора: 16
Ответ: Антон и Борис старше Виктора.

Слайд 49

Сложные условия

Задача: набор сотрудников в возрасте 25-40 лет (включительно).

if then

Сложные условия Задача: набор сотрудников в возрасте 25-40 лет (включительно). if then
writeln('подходит')
else
writeln('не подходит');

and

or

not

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

xor

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

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

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

Слайд 50

Задачи

«A»: Напишите программу, которая получает три числа и выводит количество одинаковых чисел

Задачи «A»: Напишите программу, которая получает три числа и выводит количество одинаковых
в этой цепочке.
Пример:
Введите три числа:
5 5 5
Все числа одинаковые.
Пример:
Введите три числа:
5 7 5
Два числа одинаковые.
Пример:
Введите три числа:
5 7 8
Нет одинаковых чисел.

Слайд 51

Задачи

«B»: Напишите программу, которая получает номер месяца и выводит соответствующее ему время

Задачи «B»: Напишите программу, которая получает номер месяца и выводит соответствующее ему
года или сообщение об ошибке.
Пример:
Введите номер месяца:
5
Весна.
Пример:
Введите номер месяца:
15
Неверный номер месяца.

Слайд 52

Задачи

«C»: Напишите программу, которая получает возраст человека (целое число, не превышающее 120)

Задачи «C»: Напишите программу, которая получает возраст человека (целое число, не превышающее
и выводит этот возраст со словом «год», «года» или «лет». Например, «21 год», «22 года», «25 лет».
Пример:
Введите возраст: 18
Вам 18 лет.
Пример:
Введите возраст: 21
Вам 21 год.
Пример:
Введите возраст: 22
Вам 22 года.

Слайд 53

Задачи

«A»: Напишите условие, которое определяет заштрихованную область.

«B»: Напишите условие, которое определяет

Задачи «A»: Напишите условие, которое определяет заштрихованную область. «B»: Напишите условие, которое определяет заштрихованную область.
заштрихованную область.

Слайд 54

Задачи

«C»: Напишите условие, которое определяет заштрихованную область.

Задачи «C»: Напишите условие, которое определяет заштрихованную область.

Слайд 55

Множественный выбор

if m = 1 then
write('январь');
if m = 2 then

Множественный выбор if m = 1 then write('январь'); if m = 2

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

case m of
1: write('январь');
2: write('февраль');
...
12: write('декабрь')
else write('ошибка')
end;

Слайд 56

Использование списков и диапазонов

case m of
2: d:= 28; { невисокосный

Использование списков и диапазонов case m of 2: d:= 28; { невисокосный
год }
1,3,5,7,8,10,12: d:= 31
else d:= 30
end;

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

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

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

Слайд 57

Множественный выбор

var c: char;
...
case c of
'а': begin
writeln('антилопа');
writeln('Анапа');

Множественный выбор var c: char; ... case c of 'а': begin writeln('антилопа');
end;
...
'я': begin
writeln('ягуар');
writeln('Якутск');
end
else writeln('ошибка')
end;

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

Слайд 58

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

§ 58. Циклические алгоритмы

Программирование на языке Паскаль § 58. Циклические алгоритмы

Слайд 59

Что такое цикл?

Цикл – это многократное выполнение одинаковых действий.

Два вида циклов:
цикл с

Что такое цикл? Цикл – это многократное выполнение одинаковых действий. Два вида
известным числом шагов (сделать 10 раз)
цикл с неизвестным числом шагов (делать, пока не надоест)

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

Слайд 60

Повторения в программе

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

Повторения в программе writeln ('Привет'); writeln ('Привет'); writeln ('Привет'); ... writeln ('Привет');

Слайд 61

Блок-схема цикла

начало

конец

да

нет

тело цикла

Блок-схема цикла начало конец да нет тело цикла

Слайд 62

Как организовать цикл?

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

Как организовать цикл? счётчик:= 0 пока счётчик writeln('привет'); увеличить счётчик на 1

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


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

Слайд 63

Цикл с условием

Задача. Определить количество цифр в десятичной записи целого положительного числа,

Цикл с условием Задача. Определить количество цифр в десятичной записи целого положительного
записанного в переменную n.

счётчик:= 0
пока n > 0
отсечь последнюю цифру n
увеличить счётчик на 1

n:= n div 10

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

Слайд 64

Цикл с условием

count:= 0;
while do begin
end;

n:= n div 10;
count:= count + 1

тело

Цикл с условием count:= 0; while do begin end; n:= n div
цикла

начальное значение счётчика

n > 0

условие продолжения

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

Слайд 65

Цикл с условием

k:= 0;
while k < 10 do begin
writeln('привет');
k:= k

Цикл с условием k:= 0; while k writeln('привет'); k:= k + 1
+ 1
end;

При известном количестве шагов:

k:= 0;
while k < 10 do
writeln('привет');

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

Слайд 66

Сколько раз выполняется цикл?

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

Сколько раз выполняется цикл? a:= 4; b:= 6; while a 2 раза
a + 1;

2 раза
a = 6

a:= 4; b:= 6;
while a < b do a:= a + 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;

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

Слайд 67

Цикл с постусловием

repeat
until ;

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

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

write('Введите n > 0: ');
read(n)

n > 0

тело

Цикл с постусловием repeat until ; условие окончания заголовок цикла write('Введите n
цикла

при входе в цикл условие не проверяется
цикл всегда выполняется хотя бы один раз
в последней строке указывают условие окончания цикла, а не условие его продолжения

Слайд 68

Задачи

«A»: Напишите программу, которая получает два целых числа A и B (0

Задачи «A»: Напишите программу, которая получает два целых числа A и B
< A < B) и выводит квадраты всех натуральных чисел в интервале от A до B.
Пример:
Введите два целых числа:
10 12
10*10=100
11*11=121
12*12=144

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

Слайд 69

Задачи

«C»: Ввести натуральное число N и вычислить сумму всех чисел Фибоначчи, меньших

Задачи «C»: Ввести натуральное число N и вычислить сумму всех чисел Фибоначчи,
N. Предусмотрите защиту от ввода отрицательного числа N.
Пример:
Введите число N:
10000
Сумма 17710

Слайд 70

Задачи-2

«A»: Ввести натуральное число и найти сумму его цифр.
Пример:
Введите натуральное число:
12345
Сумма

Задачи-2 «A»: Ввести натуральное число и найти сумму его цифр. Пример: Введите
цифр 15.

«B»: Ввести натуральное число и определить, верно ли, что в его записи есть две одинаковые цифры, стоящие рядом.
Пример:
Введите натуральное число:
12342
Нет.
Пример:
Введите натуральное число:
12245
Да.

Слайд 71

Задачи-2

«C»: Ввести натуральное число и определить, верно ли, что в его записи

Задачи-2 «C»: Ввести натуральное число и определить, верно ли, что в его
есть две одинаковые цифры (не обязательно стоящие рядом).
Пример:
Введите натуральное число:
12342
Да.
Пример:
Введите натуральное число:
12345
Нет.

Слайд 72

Цикл с переменной

Задача. Вывести все степени двойки от 21 до 210.

 
n:= 2;
while  

Цикл с переменной Задача. Вывести все степени двойки от 21 до 210.
do
begin
writeln(n);
n:= n * 2;
end;

k:= 1;

k <= 10

k:= k + 1

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

k:= 1 to 10

Слайд 73

Цикл с переменной: другой шаг

for k:= 10 1 do 
writeln(k*k);

downto

var k:

Цикл с переменной: другой шаг for k:= 10 1 do writeln(k*k); downto
integer;

целое

целое

шаг «–1»
for i:= 1 to 10 do begin 
writeln(k*k);
end;

k:= 1;

k:= k + 2

Слайд 74

Сколько раз выполняется цикл?

a := 1;
for i:=1 to 3 do a :=

Сколько раз выполняется цикл? a := 1; for i:=1 to 3 do
a+1;

a = 4

a := 1;
for i:=3 to 1 do a := a+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

Слайд 75

Задачи

«A»: Найдите все пятизначные числа, которые при делении на 133 дают в

Задачи «A»: Найдите все пятизначные числа, которые при делении на 133 дают
остатке 125, а при делении на 134 дают в остатке 111.
«B»: Натуральное число называется числом Армстронга, если сумма цифр числа, возведенных в N-ную степень (где N – количество цифр в числе) равна самому числу. Например, 153 = 13 + 53 + 33. Найдите все трёхзначные Армстронга.

Слайд 76

Задачи

«С»: Натуральное число называется автоморфным, если оно равно последним цифрам своего квадрата.

Задачи «С»: Натуральное число называется автоморфным, если оно равно последним цифрам своего
Например, 252 = 625. Напишите программу, которая получает натуральное число N и выводит на экран все автоморфные числа, не превосходящие N.
Пример:
Введите N:
1000
1*1=1
5*5=25
6*6=36
25*25=625
76*76=5776

Слайд 77

Вложенные циклы

Задача. Вывести все простые числа в диапазоне от 2 до 1000.

для n

Вложенные циклы Задача. Вывести все простые числа в диапазоне от 2 до
от 2 до 1000
если число n простое то
writeln(n);

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

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

Слайд 78

Вложенные циклы

for n:= 2 to 1000 do begin
count:= 0;
if count

Вложенные циклы for n:= 2 to 1000 do begin count:= 0; if
= 0 then
writeln(n)
end;

for k:= 2 to n-1 do
if n mod k = 0 then
count:= count + 1;

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

Слайд 79

Вложенные циклы

for i:=1 to 4 do
for k:=1 to i do
writeln(i,

Вложенные циклы for i:=1 to 4 do for k:=1 to i do
' ', k);

1 1
2 1
2 2
3 1
3 2
3 3
4 1
4 2
4 3
4 4

Слайд 80

Поиск простых чисел: как улучшить?

count:= 0;
k:= 2;
while do begin
if n mod

Поиск простых чисел: как улучшить? count:= 0; k:= 2; while do begin
k = 0 then
count:= count + 1;
k:= k + 1
end;

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

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

k*k <= n

(count = 0)

Слайд 81

Задачи

«A»: Напишите программу, которая получает натуральные числа A и B (A

Задачи «A»: Напишите программу, которая получает натуральные числа A и B (A
выводит все простые числа в интервале от A до B.
Пример:
Введите границы диапазона:
10 20
11 13 17 19
«B»: В магазине продается мастика в ящиках по 15 кг, 17 кг, 21 кг. Как купить ровно 185 кг мастики, не вскрывая ящики? Сколькими способами можно это сделать?

Слайд 82

Задачи

«C»: Ввести натуральное число N и вывести все натуральные числа, не превосходящие

Задачи «C»: Ввести натуральное число N и вывести все натуральные числа, не
N и делящиеся на каждую из своих цифр.
Пример:
Введите N:
15
1 2 3 4 5 6 7 8 9 11 12 15

Слайд 83

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

§ 59. Процедуры

Программирование на языке Паскаль § 59. Процедуры

Слайд 84

Зачем нужны процедуры?

writeln('Ошибка программы');

много раз!

program withProc;
var n: integer;
begin
read(n);
if n <

Зачем нужны процедуры? writeln('Ошибка программы'); много раз! program withProc; var n: integer;
0 then Error;
...
end.

procedure Error;
begin
writeln('Ошибка программы')
end;

вызов процедуры

Слайд 85

Что такое процедура?

Процедура – вспомогательный алгоритм, который выполняет некоторые действия.

текст (расшифровка) процедуры

Что такое процедура? Процедура – вспомогательный алгоритм, который выполняет некоторые действия. текст
записывается до основной программы
в программе может быть много процедур
чтобы процедура заработала, нужно вызвать её по имени из основной программы или из другой процедуры

Слайд 86

Процедура с параметрами

Задача. Вывести на экран запись целого числа (0..255) в 8-битном

Процедура с параметрами Задача. Вывести на экран запись целого числа (0..255) в
двоичном коде.

много раз!

Алгоритм:

178


101100102

7 6 5 4 3 2 1 0

1 0 1 1 0 0 1 02

разряды

n:=

n div 128

n mod 128

n1 div 64

Слайд 87

Процедура с параметрами

Задача. Вывести на экран запись целого числа (0..255) в 8-битном

Процедура с параметрами Задача. Вывести на экран запись целого числа (0..255) в
двоичном коде.

Алгоритм:

k:= 128;
while k > 0 do begin
write(n div k);
n:= n mod k;
k:= k div 2
end;

178


10110010

Слайд 88

Процедура с параметрами

program binCode;
begin
printBin(99)
end.

procedure printBin(n: integer);
var k: integer;
begin
k:= 128;
while

Процедура с параметрами program binCode; begin printBin(99) end. procedure printBin(n: integer); var
k > 0 do begin
write(n div k);
n:= n mod k;
k:= k div 2
end
end;

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

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

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

Слайд 89

Несколько параметров

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

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

Несколько параметров procedure printSred(a: integer; b: integer); begin write((a+b)/2); end. procedure printSred(a,

Слайд 90

Задачи

«A»: Напишите процедуру, которая принимает параметр – натуральное число N – и

Задачи «A»: Напишите процедуру, которая принимает параметр – натуральное число N –
выводит на экран линию из N символов '–'.
Пример:
Введите N:
10
----------
«B»: Напишите процедуру, которая выводит на экран в столбик все цифры переданного ей числа, начиная с первой.
Пример:
Введите натуральное число:
1234
1
2
3
4

Слайд 91

Задачи

«C»: Напишите процедуру, которая выводит на экран запись переданного ей числа в

Задачи «C»: Напишите процедуру, которая выводит на экран запись переданного ей числа
римской системе счисления.
Пример:
Введите натуральное число:
2013
MMXIII

Слайд 92

Изменяемые параметры

Задача. Написать процедуру, которая меняет местами значения двух переменных.

program Exchange;
var

Изменяемые параметры Задача. Написать процедуру, которая меняет местами значения двух переменных. program
x, y: integer;
begin
x:= 2; y:= 3;
Swap(x, y);
write(x, ' ', y)
end.

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

2 3

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

Слайд 93

Изменяемые параметры

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

Изменяемые параметры procedure Swap( a, b: integer); var c: integer; begin c:=
b:= c;
end;

var

передача по ссылке

переменные могут изменяться

var a, b: integer;
...
Swap(a, b); { правильно }
Swap(2, 3); { неправильно }
Swap(a, b+3); { неправильно }

Вызов:

Слайд 94

Задачи

«A»: Напишите процедуру, которая переставляет три переданные ей числа в порядке возрастания.

Задачи «A»: Напишите процедуру, которая переставляет три переданные ей числа в порядке

Пример:
Введите три натуральных числа:
10 15 5
5 10 15
«B»: Напишите процедуру, которая сокращает дробь вида M/N. Числитель и знаменатель дроби передаются как изменяемые параметры.
Пример:
Введите числитель и знаменатель дроби:
25 15
После сокращения: 5/3

Слайд 95

Задачи

«C»: Напишите процедуру, которая вычисляет наибольший общий делитель и наименьшее общее кратное

Задачи «C»: Напишите процедуру, которая вычисляет наибольший общий делитель и наименьшее общее
двух натуральных чисел и возвращает их через изменяемые параметры.
Пример:
Введите два натуральных числа:
10 15
НОД(10,15)=5
НОК(10,15)=30

Слайд 96

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

§ 60. Функции

Программирование на языке Паскаль § 60. Функции

Слайд 97

Что такое функция?

Функция – это вспомогательный алгоритм, который возвращает значение-результат (число, символ

Что такое функция? Функция – это вспомогательный алгоритм, который возвращает значение-результат (число,
или объект другого типа).

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

Алгоритм:

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

Слайд 98

Сумма цифр числа

program Sum;
begin
writeln(sumDigits(12345))
end.

function sumDigits(n: integer): ;
var sum: integer;
begin
sum:=

Сумма цифр числа program Sum; begin writeln(sumDigits(12345)) end. function sumDigits(n: integer): ;
0;
while n <> 0 do begin
sum:= sum + n mod 10;
n:= n div 10;
end;
end;

sumDigits:= sum

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

integer

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

Слайд 99

Использование функций

x:= 2*sumDigits(n+5);
z:= sumDigits(k) + sumDigits(m);
if sumDigits(n) mod 2 = 0 then

Использование функций x:= 2*sumDigits(n+5); z:= sumDigits(k) + sumDigits(m); if sumDigits(n) mod 2
begin
writeln('Сумма цифр чётная');
writeln('Она равна ', sumDigits(n))
end;

Слайд 100

Задачи

«A»: Напишите функцию, которая находит наибольший общий делитель двух натуральных чисел.
Пример:
Введите

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

Слайд 101

Задачи

«C»: Напишите функцию, которая «переворачивает» число, то есть возвращает число, в котором

Задачи «C»: Напишите функцию, которая «переворачивает» число, то есть возвращает число, в
цифры стоят в обратном порядке.
Пример:
Введите натуральное число:
1234
После переворота: 4321.

Слайд 102

Логические функции

Задача. Найти все простые числа в диапазоне от 2 до 100.

Логические функции Задача. Найти все простые числа в диапазоне от 2 до

program PrimeNum;
var i: integer;
begin
for i:=2 to 100 do
if then
writeln(i)
end.

i - простое

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

isPrime(i)

Слайд 103

Функция: простое число или нет?

function isPrime(n: integer): ;
var count, k: integer;
begin
count:=

Функция: простое число или нет? function isPrime(n: integer): ; var count, k:
0;
k:= 2;
while (k*k <= n) and (count = 0) do begin
if n mod k = 0 then
count:= count + 1;
k:= k + 1
end;
end;

boolean

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

isPrime:= (count = 0)

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

Слайд 104

Логические функции: использование

read(n);
while isPrime(n) do begin
writeln('простое число');
read(n)
end;

Логические функции: использование read(n); while isPrime(n) do begin writeln('простое число'); read(n) end;

Слайд 105

Задачи

«A»: Напишите логическую функцию, которая определяет, является ли переданное ей число совершенным,

Задачи «A»: Напишите логическую функцию, которая определяет, является ли переданное ей число
то есть, равно ли оно сумме своих делителей, меньших его самого.
Пример:
Введите натуральное число:
28
Число 28 совершенное.
Пример:
Введите натуральное число:
29
Число 29 не совершенное.

Слайд 106

Задачи

«B»: Напишите логическую функцию, которая определяет, являются ли два переданные ей числа

Задачи «B»: Напишите логическую функцию, которая определяет, являются ли два переданные ей
взаимно простыми, то есть, не имеющими общих делителей, кроме 1.
Пример:
Введите два натуральных числа:
28 15
Числа 28 и 15 взаимно простые.
Пример:
Введите два натуральных числа:
28 16
Числа 28 и 16 не взаимно простые.

Слайд 107

Задачи

«С»: Простое число называется гиперпростым, если любое число, получающееся из него откидыванием

Задачи «С»: Простое число называется гиперпростым, если любое число, получающееся из него
нескольких цифр, тоже является простым. Например, число 733 – гиперпростое, так как и оно само, и числа 73 и 7 – простые. Напишите логическую функцию, которая определяет, верно ли, что переданное ей число – гиперпростое. Используйте уже готовую функцию isPrime, которая приведена в учебнике.
Пример:
Введите натуральное число:
733
Число 733 гиперпростое.
Пример:
Введите натуральное число:
19
Число 19 не гиперпростое.

Слайд 108

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

§ 61. Рекурсия

Программирование на языке Паскаль § 61. Рекурсия

Слайд 109

Что такое рекурсия?

У попа была собака, он её любил, Она съела кусок мяса,

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

Слайд 110

Что такое рекурсия?

Натуральные числа:

индуктивное определение

Рекурсия — это способ определения множества объектов через

Что такое рекурсия? Натуральные числа: индуктивное определение Рекурсия — это способ определения
само это множество на основе заданных простых базовых случаев.

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

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

Слайд 111

Фракталы

Фракталы – геометрические фигуры, обладающие самоподобием.

Треугольник Серпинского:

Фракталы Фракталы – геометрические фигуры, обладающие самоподобием. Треугольник Серпинского:

Слайд 112

Ханойские башни

за один раз переносится один диск
класть только меньший диск на больший
третий

Ханойские башни за один раз переносится один диск класть только меньший диск
стержень вспомогательный

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

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

Слайд 113

Ханойские башни – процедура

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

Ханойские башни – процедура proceduer Hanoi(n, k, m: integer); var p: integer;
:= 6 - k – m;
Hanoi(n-1, k, p);
writeln(k, ' -> ', m);
Hanoi(n-1, p, m)
end;

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

сколько

откуда

куда

рекурсия

рекурсия

Слайд 114

Ханойские башни – процедура

Рекурсивная процедура (функция) — это процедура (функция), которая

Ханойские башни – процедура Рекурсивная процедура (функция) — это процедура (функция), которая
вызывает сама себя напрямую или через другие процедуры и функции.

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.

Слайд 115

Вывод двоичного кода числа

procedure printBin(n: integer);
begin
if n = 0 then exit;

Вывод двоичного кода числа procedure printBin(n: integer); begin if n = 0
printBin ( n div 2 );
write( n mod 2 )
end;

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

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

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

10011

printBin( 19 )

printBin( 9 )

printBin( 4 )

printBin( 2 )

printBin( 1 )

printBin( 0 )

Слайд 116

Вычисление суммы цифр числа

function sumDig(n: integer): integer;
var sum: integer;
нач
sum:= n mod

Вычисление суммы цифр числа function sumDig(n: integer): integer; var sum: integer; нач
10;
if n >= 10 then
sum:= sum + sumDig( n div 10 );
sumDig:= sum
end;

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

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

sumDig( 1234 )

4 + sumDig( 123 )

4 + 3 + sumDig( 12 )

4 + 3 + 2 + sumDig( 1 )

4 + 3 + 2 + 1

Слайд 117

Алгоритм Евклида

Алгоритм Евклида. Чтобы найти НОД двух натуральных чисел, нужно вычитать из

Алгоритм Евклида Алгоритм Евклида. Чтобы найти НОД двух натуральных чисел, нужно вычитать
большего числа меньшее до тех пор, пока меньшее не станет равно нулю. Тогда второе число и есть НОД исходных чисел.

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;

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

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

Слайд 118

Задачи

«A»: Напишите рекурсивную функцию, которая вычисляет НОД двух натуральных чисел, используя модифицированный

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

Слайд 119

Задачи

«C»: Дано натуральное число N. Требуется получить и вывести на экран количество

Задачи «C»: Дано натуральное число N. Требуется получить и вывести на экран
всех возможных различных способов представления этого числа в виде суммы натуральных чисел (то есть, 1 + 2 и 2 + 1 – это один и тот же способ разложения числа 3). Решите задачу с помощью рекурсивной процедуры.
Пример:
Введите натуральное число:
4
Количество разложений: 4.

Слайд 120

Как работает рекурсия?

function Fact(N: integer): integer;
begin
writeln('-> N = ', N);
if

Как работает рекурсия? function Fact(N: integer): integer; begin writeln('-> N = ',
N <= 1 then
Fact:= 1
else Fact:= N * Fact(N-1);
writeln('<- N = ', N)
end;

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

Факториал:

Слайд 121

Стек

Стек – область памяти, в которой хранятся локальные переменные и адреса возврата.

Fact(3)

Fact(2)

Fact(1)

значение

Стек Стек – область памяти, в которой хранятся локальные переменные и адреса
параметра

адрес возврата

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

Слайд 122

Рекурсия – «за» и «против»

с каждым новым вызовом расходуется память в стеке

Рекурсия – «за» и «против» с каждым новым вызовом расходуется память в
(возможно переполнение стека)
затраты на выполнение служебных операций при рекурсивном вызове

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

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

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

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

Слайд 123

Конец фильма

ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СОШ № 163, г. Санкт-Петербург
kpolyakov@mail.ru
ЕРЕМИН

Конец фильма ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики ГБОУ СОШ № 163,
Евгений Александрович
к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО ПГГПУ, г. Пермь
eremin@pspu.ac.ru