Программирование на языке Паскаль
Программирование на языке Паскаль
Простейшая программа
Вывод на экран
Задания
Сложение чисел
Сумма: псевдокод
Переменные
Имена переменных
Объявление переменных
Типы данных
Тип переменной
Ввод значения в переменную
Ввод значений переменной
Изменение значений переменной
Арифметические выражения
Вывод данных
Сложение чисел: простое решение
Сложение чисел: полное решение
Снова про оператор вывода
Программирование на языке Паскаль
Деление, div, mod
div и mod для отрицательных чисел
Вещественные числа
Стандартные функции
Документирование программы
Документирование программы
Документирование программы
Случайные числа
Случайные числа на компьютере
Линейный конгруэнтный генератор
Генератор случайных чисел
Другой отрезок
Задачи
Задачи
Программирование на языке Паскаль
Условный оператор
Условный оператор: полная форма
Условный оператор: неполная форма
Условный оператор
Знаки отношений
Вложенный условный оператор
Вложенный условный оператор
Выделение структуры отступами
Задачи
Задачи
Сложные условия
Задачи
Задачи
Задачи
Задачи
Задачи
Множественный выбор
Использование списков и диапазонов
Множественный выбор
Программирование на языке Паскаль
Что такое цикл?
Повторения в программе
Блок-схема цикла
Как организовать цикл?
Цикл с условием
Цикл с условием
Максимальная цифра числа
Цикл с условием
Сколько раз выполняется цикл?
Алгоритм Евклида
Алгоритм Евклида
Задачи
Задачи
Цикл с постусловием
Задачи
Задачи
Задачи-2
Задачи-2
Программирование на языке Паскаль
Цикл с переменной
Цикл с переменной: другой шаг
Сколько раз выполняется цикл?
Задачи
Задачи
Вложенные циклы
Вложенные циклы
Вложенные циклы
Поиск простых чисел: как улучшить?
Задачи
Задачи
Программирование на языке Паскаль
Зачем нужны процедуры?
Что такое процедура?
Процедура с параметрами
Процедура с параметрами
Процедура с параметрами
Несколько параметров
Локальные и глобальные переменные
Неправильная процедура
Правильная процедура
Задачи
Задачи
Изменяемые параметры
Изменяемые параметры
Задачи
Задачи
Программирование на языке Паскаль
Что такое функция?
Что такое функция?
Что такое функция?
Сумма цифр числа
Использование функций
Задачи
Задачи
Логические функции
Логические функции
Функция: простое число или нет?
Логические функции: использование
Задачи
Задачи
Задачи
Программирование на языке Паскаль
Что такое рекурсия?
Что такое рекурсия?
Фракталы
Ханойские башни
Ханойские башни – процедура
Ханойские башни – процедура
Вычисление суммы цифр числа
Вычисление суммы цифр числа
Вычисление суммы цифр числа
Вывод двоичного кода числа
Алгоритм Евклида
Задачи
Задачи
Как работает рекурсия?
Стек
Рекурсия – «за» и «против»
Анализ рекурсивных функций
Анализ рекурсивных функций
Анализ рекурсивных функций
Анализ рекурсивных функций
Анализ рекурсивных функций
Анализ рекурсивных функций
Конец фильма
Источники иллюстраций
4.23M
Категория: ПрограммированиеПрограммирование

Программирование на языке Паскаль (§ 54 - § 61)

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

1
Программирование
на языке Паскаль
§ 54. Введение в язык Паскаль
§ 55. Вычисления
§ 56. Ветвления
§ 57. Циклические алгоритмы
§ 58. Циклы по переменной
§ 59. Процедуры
§ 60. Функции
§ 61. Рекурсия
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

2
Программирование
на языке Паскаль
§ 54. Введение в язык Паскаль
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
3
Простейшая программа
название алгоритма
program
begin {
{
end. {
qq;
начало программы }
тело программы }
конец программы }
комментарии в скобках {}
не обрабатываются
?
Что делает эта программа?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
4
Вывод на экран
program qq;
begin
write('2+');
{ без перехода }
writeln('2=?'); { на новую строку}
writeln('Ответ: 4');
end.
Протокол:
2+2=?
Ответ: 4
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

5. Задания

Алгоритмизация и программирование, Паскаль, 10 класс
5
Задания
«B»: Вывести на экран текст «лесенкой»
Вася
пошел
гулять
«C»: Вывести на экран рисунок из букв
Ж
ЖЖЖ
ЖЖЖЖЖ
ЖЖЖЖЖЖЖ
HH HH
ZZZZZ
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
6
Сложение чисел
Задача. Ввести с клавиатуры два числа и найти их сумму.
Протокол:
Введите два целых числа
25 30
пользователь
25+30=55
компьютер
компьютер считает сам!
?
1.
2.
3.
4.
Как ввести числа в память?
Где хранить введенные числа?
Как вычислить?
Как вывести результат?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
7
Сумма: псевдокод
program qq;
begin
{ ввести два числа }
{ вычислить их сумму }
{ вывести сумму на экран }
end.
Псевдокод: алгоритм на
русском языке с элементами
Паскаля.
!
Компьютер не может исполнить псевдокод!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

8. Переменные

Алгоритмизация и программирование, Паскаль, 10 класс
8
Переменные
Переменная – это величина, имеющая имя, тип
и значение. Значение переменной можно
изменять во время работы программы.
Значение
Другой тип
данных
Имя
К.Ю. Поляков, Е.А. Ерёмин, 2018
!
?
Поместится?
В переменной хранятся данные
определенного типа!
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
9
Имена переменных
МОЖНО использовать
• латинские буквы (A-Z)
заглавные и строчные буквы НЕ различаются
• цифры
имя не может начинаться с цифры
• знак подчеркивания _
НЕЛЬЗЯ использовать
• русские буквы
• пробелы
• скобки, знаки +, =, !, ? и др.
Какие имена правильные?
AXby R&B 4Wheel Вася “PesBarbos”
TU154 [QuQu] _ABBA A+B
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
10
Объявление переменных
!
При объявлении выделяется место в памяти!
variable
список имён
переменных
тип – целые
var a, b, c: integer;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

11. Типы данных

Алгоритмизация и программирование, Паскаль, 10 класс
11
Типы данных
• byte
• shortint
• word
• longint
{
{
{
{
целые
целые
целые
целые
• single
• real
• double
• extended
{
{
{
{
вещественная,
вещественная,
вещественная,
вещественная,
• boolean
• char
• string
{ логическая, 1 байт }
{ символ, 1 байт }
{ символьная строка }
К.Ю. Поляков, Е.А. Ерёмин, 2018
0..255 }
-128..128 }
0..65535 }
–2147483648..2147483647 }
4 байта }
6 байта }
8 байтов }
10 байтов }
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
12
Тип переменной
• область допустимых значений
• допустимые операции
• объём памяти
• формат хранения данных
• для предотвращения случайных ошибок
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
13
Ввод значения в переменную
оператор
ввода
5
read ( a );
!
1. Программа ждет, пока пользователь введет
значение и нажмет Enter.
2. Введенное значение записывается в
переменную a.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
14
Ввод значений переменной
Ввод значений двух
переменных (через
пробел или Enter).
read ( a, b );
25 30
25 a
30 b
25
30
25 a
30 b
через пробел:
через Enter:
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
15
Изменение значений переменной
var a, b: integer;
a
?
5
...
a := 5;
b := a + 2;
a := (a + 2)*(b – 3);
b := b + 1;
5
b
5+2
?
7
a
28
5
7*4
b
7
8
К.Ю. Поляков, Е.А. Ерёмин, 2018
7+1
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
16
Арифметические выражения
3
1 2
4
5
6
a:= (c + b*5*3 - 1) / 2 * d;
Приоритет (старшинство):
c b 5 3 1
1) скобки
a
d
2
2) умножение и деление
3) сложение и вычитание
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

17. Вывод данных

Алгоритмизация и программирование, Паскаль, 10 класс
17
Вывод данных
write( a );
{ вывод значения
переменной a}
writeln( a ); { вывод значения
переменной a и переход
на новую строку}
writeln( 'Привет!' ); { вывод текста }
writeln( 'Ответ: ', c );
{вывод текста и значения переменной c}
writeln ( a, '+', b, '=', c );
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
18
Сложение чисел: простое решение
program Sum;
var a, b, c: integer;
begin
read ( a, b );
c := a + b;
Что плохо?
?
writeln ( c );
end.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
19
Сложение чисел: полное решение
program Sum;
var a, b, c: integer;
begin
writeln('Введите два целых числа');
read ( a, b );
c := a + b;
writeln ( a, '+', b, '=', c );
end.
Протокол:
компьютер
Введите два целых числа
25 30
пользователь
25+30=55
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
20
Снова про оператор вывода
Вычисление выражений:
writeln ( a, '+', b, '=', a+b );
Форматный вывод:
a:= 123;
write( a:5 );
123
5 знаков
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

21
Программирование
на языке Паскаль
§ 55. Вычисления
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

22. Деление, div, mod

Алгоритмизация и программирование, Паскаль, 10 класс
22
Деление, div, mod
Результат деления «/» – вещественное число:
var a: real;
a:= 2 / 3;
0.6666…
div – деление нацело (остаток отбрасывается)
mod – остаток от деления
var a, b, d: integer;
...
d := 85;
b := d div 10; { 8 }
a := d mod 10; { 5 }
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
23
div и mod для отрицательных чисел
write(-7 div 2, ',');
write(-7 mod 2);
-3
-1
-7 = (-3)*2 + (-1)
!
В математике не так!
-7 = (-4)*2 + 1
К.Ю. Поляков, Е.А. Ерёмин, 2018
остаток 0
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
24
Вещественные числа
!
Целая и дробная части числа разделяются
точкой!
var x: double;
...
x:= 123.456;
Форматный вывод:
a:= 1;
write( a/3 );
write( a/3:7:3 );
всего знаков
К.Ю. Поляков, Е.А. Ерёмин, 2018
3,333333 10-1 = 0,3333333
3.333333E-001
0.333
в дробной части
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
25
Стандартные функции
abs(x) —
sqrt(x) —
sin(x) —
cos(x) —
exp(x) —
ln(x)

trunc(x)—
round(x)—
модуль
квадратный корень
синус угла, заданного в радианах
косинус угла, заданного в радианах
экспонента ех
натуральный логарифм
отсечение дробной части
округление до ближайшего целого
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

26. Документирование программы

Алгоритмизация и программирование, Паскаль, 10 класс
26
Документирование программы
var a, b, c, D, x1, x2: real;
begin
writeln('Введите a, b, c:');
read(a, b, c);
D := b*b - 4*a*c;
if D < 0 then writen('Нет')
else begin
x1 := (-b + sqrt(D))/(2*a);
x2 := (-b - sqrt(D))/(2*a);
writeln('x1=', x1:5:3,
' x2=', x2:5:3);
end
end.
?
К.Ю. Поляков, Е.А. Ерёмин, 2018
Что делает?
http://kpolyakov.spb.ru

27. Документирование программы

Алгоритмизация и программирование, Паскаль, 10 класс
27
Документирование программы
Руководство пользователя:
• назначение программы
• формат входных данных
• формат выходных данных
• примеры использования программы
Назначение:
программа для решения уравнения
ax bx c 0
2
Формат входных данных:
значения коэффициентов a, b и c вводятся с
клавиатуры через пробел в одной строке
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

28. Документирование программы

Алгоритмизация и программирование, Паскаль, 10 класс
28
Документирование программы
Формат выходных данных:
значения вещественных корней уравнения;
если вещественных корней нет, выводится
слово «нет»
Примеры использования программы:
2
1. Решение уравнения x 5 x 1 0
Введите a, b, c: 1 -5 1
x1=4.791 x2=0.209
2
2. Решение уравнения x x 6 0
Введите a, b, c: 1 1 6
Нет.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
29
Случайные числа
Случайно…
• встретить друга на улице
• разбить тарелку
• найти 10 рублей
• выиграть в лотерею
Случайный выбор:
• жеребьевка на
соревнованиях
• выигравшие номера
в лотерее
Как получить случайность?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
30
Случайные числа на компьютере
Электронный генератор
• нужно специальное устройство
• нельзя воспроизвести результаты
Псевдослучайные числа – обладают свойствами
случайных чисел, но каждое следующее число
вычисляется по заданной формуле.
Метод середины квадрата (Дж. фон Нейман)
зерно
564321
318458191041
458191
в квадрате • малый период
(последовательность
повторяется через 106 чисел)
209938992481
938992
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
31
Линейный конгруэнтный генератор
X := (a*X+b) mod c | интервал от 0 до c-1
X := (X+3) mod 10 | интервал от 0 до 9
X := 0 3 6 9 2 5 8
8 1 4 7 0
зерно
!
зацикливание
Важен правильный выбор параметров
a, b и с!
Компилятор GCC:
a = 1103515245
b = 12345
c = 231
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
32
Генератор случайных чисел
Целые числа в интервале [0,10):
var K, L: integer;
...
K:= random( 10 ) { интервал от 0 до 9 (<10) }
L:= random( 10 ) { это уже другое число! }
англ. random – случайный
Вещественные числа в интервале [0,1):
var X, Y: double;
...
X:= random; { интервал от 0 до 1 (<1) }
Y:= random; { это уже другое число! }
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

33. Другой отрезок

Алгоритмизация и программирование, Паскаль, 10 класс
33
Другой отрезок
Целые числа [a, b]:
?
Какой отрезок?
var K, a, b: integer;
...
{ [5,14] }
K:= random(10) + 5;
X:= random(b-a+1) + a; { [a,b] }
Вещественные числа [a, b):
var X, a, b: double;
...
X:= random*10; { расширение: [0,10) }
X:= random*10 + 5;
{ расширение и сдвиг: [5,15) }
X:= random*(b-a) + a;
{ расширение и сдвиг: [a,b) }
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

34. Задачи

Алгоритмизация и программирование, Паскаль, 10 класс
34
Задачи
«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
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

35. Задачи

Алгоритмизация и программирование, Паскаль, 10 класс
35
Задачи
«C»: Получить случайное трехзначное число и вывести
через запятую его отдельные цифры.
Пример:
Получено число 123.
Его цифры 1, 2, 3.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

36
Программирование
на языке Паскаль
§ 56. Ветвления
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
37
Условный оператор
Задача: изменить порядок действий в зависимости от
выполнения некоторого условия.
да
a > b?
M:= a
полная
форма
ветвления
нет
M:= b
вывод M
?
К.Ю. Поляков, Е.А. Ерёмин, 2018
Если a = b?
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
38
Условный оператор: полная форма
if a > b then
M:= a
else
M:= b;
!
Перед else знак «;»
НЕ ставится!
if a > b then begin
M:= a;
end
else begin
M:= b;
end;
операторные
скобки
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
39
Условный оператор: неполная форма
M:= a
да
b > M?
нет
M:= a;
if b > M then
M:= b;
M:= b
неполная
форма
ветвления
вывод M
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
40
Условный оператор
if a < b then begin
с:= a;
a:= b;
b:= c
end;
?
Можно ли обойтись
без переменной c?
К.Ю. Поляков, Е.А. Ерёмин, 2018
?
Что делает?
b
a
4
6
6
4
2
?
4
c
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
41
Знаки отношений
> <
больше, меньше
>=
больше или равно
<=
меньше или равно
=
<>
равно
не равно
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
42
Вложенный условный оператор
Задача: в переменных a и b записаны возрасты Андрея и
Бориса. Кто из них старше?
Сколько вариантов?
if a = b then
writeln(' Одного возраста ')
else
if a > b then
writeln('Андрей старше')
else
writeln('Борис старше');
?
?
Зачем нужен?
К.Ю. Поляков, Е.А. Ерёмин, 2018
вложенный
условный оператор
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
43
Вложенный условный оператор
cost := 1500;
if cost < 1000 then
writeln('Скидок нет.')
else if cost < 2000 then
writeln('Скидка 2%.')
else if cost < 5000 then
writeln('Скидка 5%.')
else
writeln('Скидка 10%.');
?
Что выведет?
К.Ю. Поляков, Е.А. Ерёмин, 2018
первое сработавшее
условие
Скидка 2%.
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
44
Выделение структуры отступами
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('Б');
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

45. Задачи

Алгоритмизация и программирование, Паскаль, 10 класс
45
Задачи
«A»: Ввести три целых числа, найти максимальное из
них.
Пример:
Введите три целых числа:
1 5 4
Максимальное число 5
«B»: Ввести пять целых чисел, найти максимальное из
них.
Пример:
Введите пять целых чисел:
1 5 4 3 2
Максимальное число 5
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

46. Задачи

Алгоритмизация и программирование, Паскаль, 10 класс
46
Задачи
«C»: Ввести последовательно возраст Антона, Бориса и
Виктора. Определить, кто из них старше.
Пример:
Возраст Антона: 15
Возраст Бориса: 17
Возраст Виктора: 16
Ответ: Борис старше всех.
Пример:
Возраст Антона: 17
Возраст Бориса: 17
Возраст Виктора: 16
Ответ: Антон и Борис старше Виктора.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
47
Сложные условия
Задача: набор сотрудников в возрасте 25-40 лет
(включительно). сложное условие
if (v >= 25) and (v <= 40) then
writeln('подходит')
else
writeln('не подходит');
Приоритет :
исключающее
«ИЛИ»
1)not
2)and
3)or, xor
4) отношения (<, >, <=, >=, =, <>)
?
and
or
xor
not
Почему скобки обязательны?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

48. Задачи

Алгоритмизация и программирование, Паскаль, 10 класс
48
Задачи
«A»: Напишите программу, которая получает три числа и
выводит количество одинаковых чисел в этой
цепочке.
Пример:
Введите три числа:
5 5 5
Все числа одинаковые.
Пример:
Введите три числа:
5 7 5
Два числа одинаковые.
Пример:
Введите три числа:
5 7 8
Нет одинаковых чисел.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

49. Задачи

Алгоритмизация и программирование, Паскаль, 10 класс
49
Задачи
«B»: Напишите программу, которая получает номер
месяца и выводит соответствующее ему время года
или сообщение об ошибке.
Пример:
Введите номер месяца:
5
Весна.
Пример:
Введите номер месяца:
15
Неверный номер месяца.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

50. Задачи

Алгоритмизация и программирование, Паскаль, 10 класс
50
Задачи
«C»: Напишите программу, которая получает возраст
человека (целое число, не превышающее 120) и
выводит этот возраст со словом «год», «года» или
«лет». Например, «21 год», «22 года», «25 лет».
Пример:
Введите возраст: 18
Вам 18 лет.
Пример:
Введите возраст: 21
Вам 21 год.
Пример:
Введите возраст: 22
Вам 22 года.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

51. Задачи

Алгоритмизация и программирование, Паскаль, 10 класс
51
Задачи
«A»: Напишите условие, которое определяет
заштрихованную область.
а)
а
б) б
y
) x2 y 2 4
y
)
в
y sin( x)
)
y 0,5
x
y x
x
x 2
«B»: Напишите условие, которое определяет
заштрихованную область.
а)
б)
y
в)
y x
y
y 1
y
x2 y 2 1
y x 1
x
y x2
0
y 2 x
x
x2 y2 1
x
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

52. Задачи

Алгоритмизация и программирование, Паскаль, 10 класс
52
Задачи
«C»: Напишите условие, которое определяет
заштрихованную область.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
53
Множественный выбор
if m = 1 then
write('январь');
if m = 2 then
write('февраль');
...
if m = 12 then
write('декабрь');
case
1:
2:
...
12:
else
end;
m of
write('январь');
write('февраль');
write('декабрь')
write('ошибка')
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
54
Использование списков и диапазонов
Число дней в месяце:
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;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
55
Множественный выбор
var c: char;
несколько
...
операторов в
case c of
блоке
'а': begin
writeln('антилопа');
writeln('Анапа');
end;
...
'я': begin
writeln('ягуар');
writeln('Якутск');
end
else writeln('ошибка')
end;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

56
Программирование
на языке Паскаль
§ 57. Циклические
алгоритмы
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
57
Что такое цикл?
Цикл – это многократное выполнение одинаковых
действий.
Два вида циклов:
• цикл с известным числом шагов (сделать 10 раз)
• цикл с неизвестным числом шагов (делать, пока не
надоест)
Задача. Вывести на экран 10 раз слово «Привет».
?
Можно ли решить известными методами?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
58
Повторения в программе
writeln
writeln
writeln
...
writeln
('Привет');
('Привет');
('Привет');
('Привет');
?
К.Ю. Поляков, Е.А. Ерёмин, 2018
Что плохо?
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
59
Блок-схема цикла
начало
сделали 10 раз?
да
конец
нет
writeln('Привет!');
тело цикла
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
60
Как организовать цикл?
счётчик:= 0
пока счётчик < 10
writeln('привет');
увеличить счётчик на 1
счётчик:= 10
пока счётчик > 0
writeln('привет');
уменьшить счётчик на 1
?
результат операции
автоматически
сравнивается с нулём!
Какой способ удобнее для процессора?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
61
Цикл с условием
Задача. Определить количество цифр в десятичной
записи целого положительного числа, записанного в
переменную n.
n
счётчик
счётчик:= 0
пока n > 0
1234
0
отсечь последнюю цифру n
123
1
увеличить счётчик на 1
12
2
?
Как отсечь последнюю цифру?
n:= n div 10
?
1
0
3
4
Как увеличить счётчик на 1?
счётчик:= счётчик + 1
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
62
Цикл с условием
начальное значение
счётчика
заголовок
цикла
условие
продолжения
count:= 0;
while n > 0 do begin
n:= n div 10;
count:= count + 1
end;
?
!
Зачем begin-end?
тело цикла
Цикл с предусловием – проверка на входе в цикл!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

63. Максимальная цифра числа

Алгоритмизация и программирование, Паскаль, 10 класс
63
Максимальная цифра числа
Задача. Определить максимальную цифру в
десятичной записи целого положительного числа,
записанного в переменную n.
пока остались
read(n);
цифры
M := -1;
последняя while n > 0 do begin
цифра
d := n mod 10;
if d > M then
? Что плохо!
поиск
M := d;
максимума
n := n div 10
отсечь
end;
последнюю
writeln( M );
цифру
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
64
Цикл с условием
При известном количестве шагов:
k:= 0;
while k < 10 do begin
writeln('привет');
k:= k + 1
end;
Зацикливание:
k:= 0;
while k < 10 do
writeln('привет');
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
65
Сколько раз выполняется цикл?
a:= 4; b:= 6;
while a < b do a:= 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;
К.Ю. Поляков, Е.А. Ерёмин, 2018
зацикливание
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
66
Алгоритм Евклида
Алгоритм Евклида. Чтобы найти НОД двух натуральных
чисел, нужно вычитать из большего числа меньшее до
тех пор, пока они не станут равны. Это число и есть
НОД исходных чисел.
НОД(14,21) = НОД(14,7) = НОД(7, 7) = 7
пока a <> b
если a > b то
a:= a - b
иначе
b:= b - a
while a <> b do
if a > b then
a:= a - b
else
b:= b – a;
НОД(1998,2) = НОД(1996,2) = … = НОД(2, 2) = 2
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
67
Алгоритм Евклида
Модифицированный алгоритм Евклида. Заменять
большее число на остаток от деления большего на
меньшее до тех пор, пока меньшее не станет равно
нулю. Другое (ненулевое) число и есть НОД чисел.
НОД(1998,2) = НОД(0,2) = 2
пока a<>0
??? and b<>0
если a > b то
a:= a mod b
иначе
b:= b mod a
если a <> 0 то
вывести a
иначе:
вывести b
К.Ю. Поляков, Е.А. Ерёмин, 2018
? Какое условие?
? Как вывести
результат?
?
Как проще?
вывести a + b
http://kpolyakov.spb.ru

68. Задачи

Алгоритмизация и программирование, Паскаль, 10 класс
68
Задачи
«3»: Ввести с клавиатуры два натуральных числа и найти их
НОД с помощью алгоритма Евклида.
Пример:
Введите два числа:
21 14
НОД(21,14)=7
«4»: Ввести с клавиатуры два натуральных числа и найти их
НОД с помощью модифицированного алгоритма
Евклида. Заполните таблицу:
a
64168
358853
6365133
17905514
549868978
b
82678
691042
11494962
23108855
298294835
НОД(a,b)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

69. Задачи

Алгоритмизация и программирование, Паскаль, 10 класс
69
Задачи
«5»: Ввести с клавиатуры два натуральных числа и сравнить
количество шагов цикла для вычисления их НОД с
помощью обычного и модифицированного алгоритмов
Евклида.
Пример:
Введите два числа:
1998 2
НОД(1998,2)=2
Обычный алгоритм: 998
Модифицированный: 1
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
70
Цикл с постусловием
заголовок
цикла
тело цикла
repeat
write('Введите n > 0: ');
read(n)
until n > 0 ;
условие
окончания
• при входе в цикл условие не проверяется
• цикл всегда выполняется хотя бы один раз
• в последней строке указывают условие окончания
цикла, а не условие его продолжения
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

71. Задачи

Алгоритмизация и программирование, Паскаль, 10 класс
71
Задачи
«A»: Напишите программу, которая получает два целых числа
A и B (0 < A < B) и выводит квадраты всех натуральных
чисел в интервале от A до B.
Пример:
Введите два целых числа:
10 12
10*10=100
11*11=121
12*12=144
«B»: Напишите программу, которая получает два целых числа и
находит их произведение, не используя операцию
умножения. Учтите, что числа могут быть отрицательными.
Пример:
Введите два числа:
10 -15
10*(-15)=-150
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

72. Задачи

Алгоритмизация и программирование, Паскаль, 10 класс
72
Задачи
«C»: Ввести натуральное число N и вычислить сумму
всех чисел Фибоначчи, меньших N. Предусмотрите
защиту от ввода отрицательного числа N.
Пример:
Введите число N:
10000
Сумма 17710
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

73. Задачи-2

Алгоритмизация и программирование, Паскаль, 10 класс
73
Задачи-2
«A»: Ввести натуральное число и найти сумму его цифр.
Пример:
Введите натуральное число:
12345
Сумма цифр 15.
«B»: Ввести натуральное число и определить, верно ли, что в
его записи есть две одинаковые цифры, стоящие рядом.
Пример:
Введите натуральное число:
12342
Нет.
Пример:
Введите натуральное число:
12245
Да.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

74. Задачи-2

Алгоритмизация и программирование, Паскаль, 10 класс
74
Задачи-2
«C»: Ввести натуральное число и определить, верно ли,
что в его записи есть две одинаковые цифры (не
обязательно стоящие рядом).
Пример:
Введите натуральное число:
12342
Да.
Пример:
Введите натуральное число:
12345
Нет.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

75
Программирование
на языке Паскаль
§ 58. Циклы по переменной
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
76
Цикл с переменной
Задача. Вывести все степени двойки от 21 до 210.
?
Можно ли сделать с циклом «while»?
k:= 1;
n:= 2;
while k <= 10
begin
writeln(n);
n:= n * 2;
k:= k + 1
end;
К.Ю. Поляков, Е.А. Ерёмин, 2018
do
n:= 2;
for k:= 1 to 10 do
begin
writeln(n);
n:= n * 2
end;
!
Переменная k – целая!
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
77
Цикл с переменной: другой шаг
var k: integer;
целое
целое
for k:= 10 downto
writeln(k*k);
1 do
шаг «–1»
!
?
Шаг может быть равен только 1 или «–1» !
Как сделать шаг 2?
k:= 1;
for i:= 1 to 10 do begin
writeln(k*k);
k:= k + 2
end;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
78
Сколько раз выполняется цикл?
a := 1;
for i:=1 to 3 do a := 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
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

79. Задачи

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

80. Задачи

Алгоритмизация и программирование, Паскаль, 10 класс
80
Задачи
«С»: Натуральное число называется автоморфным,
если оно равно последним цифрам своего квадрата.
Например, 252 = 625. Напишите программу, которая
получает натуральное число N и выводит на экран
все автоморфные числа, не превосходящие N.
Пример:
Введите N:
1000
1*1=1
5*5=25
6*6=36
25*25=625
76*76=5776
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
81
Вложенные циклы
Задача. Вывести все простые числа в диапазоне
от 2 до 1000.
для n от 2 до 1000
если число n простое то
writeln(n);
нет делителей [2.. n-1]:
проверка в цикле!
?
Что значит «простое число»?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
82
Вложенные циклы
for n:= 2 to 1000 do begin
count:= 0;
for k:= 2 to n-1 do
if n mod k = 0 then
count:= count + 1;
if count = 0 then
writeln(n)
end;
К.Ю. Поляков, Е.А. Ерёмин, 2018
вложенный цикл
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
83
Вложенные циклы
for i:=1 to 4 do
for k:=1 to i do
writeln(i, ' ', k);
?
!
Как меняются переменные?
Переменная внутреннего
цикла изменяется быстрее!
К.Ю. Поляков, Е.А. Ерёмин, 2018
1
2
2
3
3
3
4
4
4
4
1
1
2
1
2
3
1
2
3
4
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
84
Поиск простых чисел: как улучшить?
n k m, k m k 2 n k n
while k <= sqrt(n) do begin
...
end;
?
Что плохо?
count:= 0;
k:= 2;
Как ещё улучшить?
while k*k <= n do begin
if n mod k = 0 then
count:= count + 1;
k:= k + 1
while (k*k <= n) and (count = 0)
end;
do begin
...
end;
?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

85. Задачи

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

86. Задачи

Алгоритмизация и программирование, Паскаль, 10 класс
86
Задачи
«C»: Ввести натуральное число N и вывести все
натуральные числа, не превосходящие N и
делящиеся на каждую из своих цифр.
Пример:
Введите N:
15
1 2 3 4 5 6 7 8 9 11 12 15
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

87
Программирование
на языке Паскаль
§ 59. Процедуры
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
88
Зачем нужны процедуры?
writeln('Ошибка программы');
много раз!
program withProc;
var n: integer;
procedure Error;
begin
writeln('Ошибка программы')
end;
begin
read(n);
if n < 0 then Error;
...
end.
вызов
процедуры
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
89
Что такое процедура?
Процедура – вспомогательный алгоритм, который
выполняет некоторые действия.
• текст (расшифровка) процедуры записывается
до основной программы
• в программе может быть много процедур
• чтобы процедура заработала, нужно вызвать её по
имени из основной программы или из другой
процедуры
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
90
Процедура с параметрами
Задача. Вывести на экран запись целого числа (0..255) в
8-битном двоичном коде.
много раз!
Алгоритм:
178 101100102
?
Как вывести первую цифру?
7
6 5 4
3 2 1
0
n:= 1 0 1 1 0 0 1 02
n div 128
?
разряды
n mod 128
Как вывести вторую цифру?
К.Ю. Поляков, Е.А. Ерёмин, 2018
n1 div 64
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
91
Процедура с параметрами
Задача. Вывести на экран запись целого числа (0..255) в
8-битном двоичном коде.
Алгоритм:
n
k
вывод
k:= 128;
while k > 0 do begin
178
128
1
write(n div k);
50
64
0
n:= n mod k;
50
32
1
k:= k div 2
18
16
1
end;
2
8
0
178 10110010
2
4
0
2
2
1
Результат зависит
от n!
0
1
0
!
0
К.Ю. Поляков, Е.А. Ерёмин, 2018
0
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
92
Процедура с параметрами
program binCode;
procedure printBin(n: integer);
var k: integer;
Параметры – данные,
begin
локальная
переменная
изменяющие работу
k:= 128;
while k > 0 do begin
процедуры.
write(n div k);
n:= n mod k;
k:= k div 2
end
значение параметра
end;
(аргумент)
begin
printBin(99)
end.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
93
Несколько параметров
procedure printSred(a: integer;
b: integer);
begin
write((a+b)/2);
end.
procedure printSred(a, b: integer);
begin
write((a+b)/2);
end.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

94. Локальные и глобальные переменные

Алгоритмизация и программирование, Паскаль, 10 класс
94
Локальные и глобальные переменные
глобальная
переменная
локальная
переменная
var a: integer;
procedure qq;
var a: integer;
begin
a:=
a
:=1;1;
1
writeln(a);
end;
begin
a:= 5;
qq;
writeln(a);
5
end.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

95. Неправильная процедура

Алгоритмизация и программирование, Паскаль, 10 класс
95
Неправильная процедура
var x, y: integer;
Что плохо?
?
procedure xSum;
procedure xSum;
begin
writeln( x+y ) begin
writeln( x+y )
end;
end;
begin
передавать
xSum()
данные через
end.
параметры
? Как исправить?
1) процедура связана с глобальными переменными,
нельзя перенести в другую программу
2) печатает только сумму x и y, нельзя напечатать
сумму других переменных или сумму x*y и 3x
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

96. Правильная процедура

Алгоритмизация и программирование, Паскаль, 10 класс
96
Правильная процедура
Глобальные:
x
y
5
10
z
w
17
3
procedure Sum2(a, b: integer);
begin
writeln( a+b )
end;
x = 5;
Sum2(
z=17;
Sum2(
Sum2(
y = 10;
x, y );
w=3;
z, w );
z+x, y*w );
Локальные:
a
b
17
22
5
10
30
3
15
20
52
1) процедура не зависит от глобальных
переменных
2) легко перенести в другую программу
3) печатает только сумму любых выражений
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

97. Задачи

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

98. Задачи

Алгоритмизация и программирование, Паскаль, 10 класс
98
Задачи
«C»: Напишите процедуру, которая выводит на экран
запись переданного ей числа в римской системе
счисления.
Пример:
Введите натуральное число:
2013
MMXIII
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
99
Изменяемые параметры
Задача. Написать процедуру, которая меняет местами
значения двух переменных.
передача по
program Exchange;
значению
var x, y: integer;
procedure Swap(a, b: integer);
var c: integer;
begin
c:= a; a:= b; b:= c;
end;
Процедура работает с копиями
begin
переданных значений параметров!
x:= 2; y:= 3;
Swap(x, y);
2 3
write(x, ' ', y)
end.
Почему не работает?
!
?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
100
Изменяемые параметры
переменные могут
изменяться
procedure Swap( var a, b: integer);
var c: integer;
передача по
begin
ссылке
c:= a; a:= b; b:= c;
end;
Вызов:
var a, b: integer;
...
Swap(a, b); { правильно }
Swap(2, 3); { неправильно }
Swap(a, b+3); { неправильно }
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

101. Задачи

Алгоритмизация и программирование, Паскаль, 10 класс
101
Задачи
«A»: Напишите процедуру, которая переставляет три
переданные ей числа в порядке возрастания.
Пример:
Введите три натуральных числа:
10 15 5
5 10 15
«B»: Напишите процедуру, которая сокращает дробь
вида M/N. Числитель и знаменатель дроби
передаются как изменяемые параметры.
Пример:
Введите числитель и знаменатель дроби:
25 15
После сокращения: 5/3
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

102. Задачи

Алгоритмизация и программирование, Паскаль, 10 класс
102
Задачи
«C»: Напишите процедуру, которая вычисляет
наибольший общий делитель и наименьшее общее
кратное двух натуральных чисел и возвращает их
через изменяемые параметры.
Пример:
Введите два натуральных числа:
10 15
НОД(10,15)=5
НОК(10,15)=30
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

103
Программирование
на языке Паскаль
§ 60. Функции
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
104
Что такое функция?
Функция – это вспомогательный алгоритм, который
возвращает значение-результат (число, символ или
объект другого типа).
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
105
Что такое функция?
Задача. Написать функцию, которая вычисляет младшую
цифру числа (разряд единиц).
число
1234
lastDigit
последняя цифра
4
тип
результата
function lastDigit(n: integer): integer;
var d: integer;
результат работы
begin
функции – значение d
d := n mod 10;
lastDigit := d
end;
{ вызов функции }
передача
k := lastDigit( 1234 );
результата
writeln( k );
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
106
Что такое функция?
Задача. Написать функцию, которая вычисляет сумму
цифр числа.
Алгоритм:
сумма:= 0;
while n <> 0 do begin
сумма:= сумма + n mod 10;
n:= n div 10
end;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
107
Сумма цифр числа
program Sum;
function sumDigits(n: integer): integer ;
var sum: integer;
begin
тип результата
sum:= 0;
while n <> 0 do begin
sum:= sum + n mod 10;
n:= n div 10;
end;
передача
sumDigits:= sum
результата
end;
begin
writeln(sumDigits(12345))
end.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
108
Использование функций
x:= 2*sumDigits(n+5);
z:= sumDigits(k) + sumDigits(m);
if sumDigits(n) mod 2 = 0 then begin
writeln('Сумма цифр чётная');
writeln('Она равна ', sumDigits(n))
end;
!
Функция, возвращающая целое число, может
использоваться везде, где и целая величина!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

109. Задачи

Алгоритмизация и программирование, Паскаль, 10 класс
109
Задачи
«A»: Напишите функцию, которая находит наибольший
общий делитель двух натуральных чисел.
Пример:
Введите два натуральных числа:
7006652 112307574
НОД(7006652,112307574) = 1234.
«B»: Напишите функцию, которая определяет сумму
цифр переданного ей числа.
Пример:
Введите натуральное число:
123
Сумма цифр числа 123 равна 6.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

110. Задачи

Алгоритмизация и программирование, Паскаль, 10 класс
110
Задачи
«C»: Напишите функцию, которая «переворачивает»
число, то есть возвращает число, в котором цифры
стоят в обратном порядке.
Пример:
Введите натуральное число:
1234
После переворота: 4321.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
111
Логические функции
Логическая функция – это функция, возвращающая
логическое значение (True/False).
function even(n: integer): boolean;
begin
if n mod 2 = 0 then
even := True
even := (n mod 2 = 0);
else
even := False
end;
read( k );
if even( k ) then
writeln( 'Число ', k, ' чётное.' )
else
writeln( 'Число ', k, ' нечётное.' );
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
112
Логические функции
Задача. Найти все простые числа в диапазоне
от 2 до 100.
program PrimeNum;
var i: integer;
begin
for i:=2 to 100 do
if iisPrime(i)
- простое then
writeln(i)
функция,
end.
возвращающая
логическое значение
(True/False)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
113
Функция: простое число или нет?
?
Какой алгоритм?
логическое значение
(True/False)
function isPrime(n: integer): boolean ;
var count, k: integer;
begin
count:= 0;
k:= 2;
while (k*k <= n) and (count = 0) do begin
if n mod k = 0 then
count:= count + 1; if count = 0 then
k:= k + 1
isPrime:= True
else isPrime:= False
end;
isPrime:= (count = 0)
end;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
114
Логические функции: использование
!
Функция, возвращающая логическое значение,
может использоваться везде, где и логическая
величина!
read(n);
while isPrime(n) do begin
writeln('простое число');
read(n)
end;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

115. Задачи

Алгоритмизация и программирование, Паскаль, 10 класс
115
Задачи
«A»: Напишите логическую функцию, которая
определяет, является ли переданное ей число
совершенным, то есть, равно ли оно сумме своих
делителей, меньших его самого.
Пример:
Введите натуральное число:
28
Число 28 совершенное.
Пример:
Введите натуральное число:
29
Число 29 не совершенное.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

116. Задачи

Алгоритмизация и программирование, Паскаль, 10 класс
116
Задачи
«B»: Напишите логическую функцию, которая
определяет, являются ли два переданные ей числа
взаимно простыми, то есть, не имеющими общих
делителей, кроме 1.
Пример:
Введите два натуральных числа:
28 15
Числа 28 и 15 взаимно простые.
Пример:
Введите два натуральных числа:
28 16
Числа 28 и 16 не взаимно простые.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

117. Задачи

Алгоритмизация и программирование, Паскаль, 10 класс
117
Задачи
«С»: Простое число называется гиперпростым, если любое
число, получающееся из него откидыванием нескольких
цифр, тоже является простым. Например, число 733 –
гиперпростое, так как и оно само, и числа 73 и 7 –
простые. Напишите логическую функцию, которая
определяет, верно ли, что переданное ей число –
гиперпростое. Используйте уже готовую функцию
isPrime, которая приведена в учебнике.
Пример:
Введите натуральное число:
733
Число 733 гиперпростое.
Пример:
Введите натуральное число:
19
Число 19 не гиперпростое.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

118
Программирование
на языке Паскаль
§ 61. Рекурсия
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

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

К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
120
Что такое рекурсия?
Натуральные числа:
• 1 – натуральное число
• если n – натуральное число,
то n 1 – натуральное число
индуктивное
определение
Рекурсия — это способ определения множества
объектов через само это множество на основе
заданных простых базовых случаев.
Числа Фибоначчи:
• F1 F2 1
• Fn Fn 1 Fn 2 при n 2
1, 1, 2, 3, 5, 8, 13, 21, 34, …
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

121. Фракталы

Алгоритмизация и программирование, Паскаль, 10 класс
121
Фракталы
Фракталы – геометрические фигуры, обладающие
самоподобием.
Треугольник Серпинского:
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
122
Ханойские башни
1
2
3
• за один раз переносится один диск
• класть только меньший диск на больший
• третий стержень вспомогательный
перенести (n, 1, 3)
перенести (n-1, 1, 2)
1 -> 3
перенести (n-1, 2, 3)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
123
Ханойские башни – процедура
сколько
откуда
куда
procedure Hanoi(n, k, m: integer);
var p: integer;
номер вспомогательного
begin
стержня (1+2+3=6!)
p := 6 - k – m;
рекурсия
Hanoi(n-1, k, p);
writeln(k, ' -> ', m);
рекурсия
Hanoi(n-1, p, m)
end;
?
!
Что плохо?
Рекурсия никогда не остановится!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
124
Ханойские башни – процедура
Рекурсивная процедура (функция) — это процедура
(функция), которая вызывает сама себя напрямую или
через другие процедуры и функции.
procedure Hanoi(n, k, m: integer);
var p: integer;
условие выхода из
begin
рекурсии
if n = 0 then exit;
p := 6 - k – m;
Hanoi(n-1, k, p);
writeln(k, ' -> ', m);
Hanoi(n-1, p, m)
program HanoiTower;
end;
...
begin
Hanoi(4, 1, 3)
end.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
125
Вычисление суммы цифр числа
Задача. Написать рекурсивную функцию, которая
вычисляет сумму цифр числа.
s:= sumDigits( 1234 );
1
2
3
4
n
sumDigits( 123 ) + 4
n div 10
n mod 10
sumDigits( n )= sumDigits( n div 10 )+(n mod 10)
sumDigits( n )= n для n < 10
Это всё?
?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
126
Вычисление суммы цифр числа
function sumDigits(n: integer): integer;
var sum: integer;
begin
последняя цифра
sum:= n mod 10;
рекурсивный вызов
if n >= 10 then
sum:= sum + sumDigits( n div 10 );
sumDigits:= sum
end;
Где условие окончания
рекурсии?
sumDigits( 1234 )
?
4 + sumDigits( 123 )
4 + 3 + sumDigits( 12 )
4 + 3 + 2 + sumDigits( 1 )
4 + 3 + 2 + 1
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
127
Вычисление суммы цифр числа
sumDigits ( 123 )
sum:= 3 + sumDigits ( 12 )
sumDigits ( 12 )
sum:= 2 + sumDigits ( 1 )
sumDigits ( 1 )
sumDigits:= 1 ;
sumnDigits:= 3 ;
sumDigits:= 6 ;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
128
Вывод двоичного кода числа
Задача. Написать рекурсивную процедуру, которая
выводит двоичную запись числа.
procedure printBin(n: integer);
begin
условие выхода из
if n = 0 then exit;
рекурсии
printBin ( n div 2 );
напечатать все
write( n mod 2 )
цифры, кроме
end;
последней
printBin(
01))
printBin(
printBin(
24))
printBin(
printBin(
))
printBin(919
10011
К.Ю. Поляков, Е.А. Ерёмин, 2018
вывести
последнюю цифру
?
Как без рекурсии?
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
129
Алгоритм Евклида
Алгоритм Евклида. Чтобы найти НОД двух натуральных
чисел, нужно вычитать из большего числа меньшее до
тех пор, пока меньшее не станет равно нулю. Тогда
второе число и есть НОД исходных чисел.
function NOD(a, b: integer): integer;
begin
if (a = 0) or (b = 0) then begin
NOD:= a + b;
условие окончания
exit
рекурсии
end;
if a > b then
NOD:= NOD(a - b, b)
рекурсивные вызовы
else NOD:= NOD(a, b - a)
end;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

130. Задачи

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

131. Задачи

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

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

Алгоритмизация и программирование, Паскаль, 10 класс
132
Как работает рекурсия?
Факториал:
1, N 1
N !
N ( N 1)!, N 1
function Fact(N: integer): integer;
begin
-> N = 3
writeln('-> N = ', N);
-> N = 2
if N <= 1 then
-> N = 1
Fact:= 1
<- N = 1
else Fact:= N * Fact(N-1);
<- N = 2
writeln('<- N = ', N)
<- N = 3
end;
?
Как сохранить состояние функции перед
рекурсивным вызовом?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

133. Стек

Алгоритмизация и программирование, Паскаль, 10 класс
133
Стек
Стек – область памяти, в которой хранятся локальные
переменные и адреса возврата.
SP
значение
параметра
адрес
возврата
SP
Fact(3)
3
A
локальная
переменная
рез
SP
Fact(2)
3
A
рез
2
AF
рез
SP
Fact(1)
3
A
К.Ю. Поляков, Е.А. Ерёмин, 2018
рез
2
AF
рез
1
AF
рез
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, Паскаль, 10 класс
134
Рекурсия – «за» и «против»
• с каждым новым вызовом расходуется память в стеке
(возможно переполнение стека)
• затраты на выполнение служебных операций при
рекурсивном вызове
программа становится более короткой и понятной
!
возможно переполнение стека
замедление работы
Любой рекурсивный
алгоритм можно заменить
нерекурсивным!
итерационный
алгоритм
К.Ю. Поляков, Е.А. Ерёмин, 2018
function Fact(N: integer):
integer;
var i, F: integer;
begin
F:= 1;
for i:= 1 to N do
F:= F * i;
Fact:= F
end;
http://kpolyakov.spb.ru

135. Анализ рекурсивных функций

Алгоритмизация и программирование, Паскаль, 10 класс
135
Анализ рекурсивных функций
Задача. Определите f(5).
function
begin
if x <
f :=
else
f :=
end;
f( x: integer ): integer;
3 then
1
1, x 3
f ( x)
f ( x 1) 2, x 3
f( x-1 ) + 2
Метод подстановки:
f(5) = f(4) + 2 = 5 + 2 = 7
f(4) = f(3) + 2 = 3 + 2 = 5
f(3) = f(2) + 2 = 1 + 2 = 3
f(2) = 1
К.Ю. Поляков, Е.А. Ерёмин, 2018
f (5)
f (4)
f (3)
линейная
структура
f (2)
http://kpolyakov.spb.ru

136. Анализ рекурсивных функций

Алгоритмизация и программирование, Паскаль, 10 класс
136
Анализ рекурсивных функций
Задача. Определите f(5).
function
begin
if x <
f :=
else
f :=
end;
f( x: integer ): integer;
3 then
1
1, x 3
f ( x)
f ( x 1) 2 f ( x 2), x 3
f(x-1) + 2*f(x-2)
f (5) 11
дерево
3 f (3)
1 f (2)
К.Ю. Поляков, Е.А. Ерёмин, 2018
f (3) 3
f (4) 5
f (2)
1
f (1) 1
f (2)
1
f (1)
1
http://kpolyakov.spb.ru

137. Анализ рекурсивных функций

Алгоритмизация и программирование, Паскаль, 10 класс
137
Анализ рекурсивных функций
Чему равно f (5)?
1, x 3
f ( x)
f ( x 1) 2 f ( x 2), x 3
Табличный метод :
x
f (x)
1
1
2
1
3
3
*2
начальные
значения
К.Ю. Поляков, Е.А. Ерёмин, 2018
4
5
*2
5
11
*2
f(3) = f(2) + 2*f(1) = 3
f(4) = f(3) + 2*f(2) = 5
f(5) = f(4) + 2*f(3) = 11
http://kpolyakov.spb.ru

138. Анализ рекурсивных функций

Алгоритмизация и программирование, Паскаль, 10 класс
138
Анализ рекурсивных функций
Задача. Сколько звёздочек выводится при вызове f(11)?
procedure g(x: integer); forward;
procedure f(x: integer);
begin
if x > 0 then g(x-1)
end;
procedure g(x: integer);
begin
write('*');
if x > 1 then f(x-3)
end;
f (11)
g(10)
Ответ: 3
*
К.Ю. Поляков, Е.А. Ерёмин, 2018
f (7)
g(6)
*
f (3)
g(2)
f (-1)
*
http://kpolyakov.spb.ru

139. Анализ рекурсивных функций

Алгоритмизация и программирование, Паскаль, 10 класс
139
Анализ рекурсивных функций
Задача. Сколько звёздочек выводится при вызове f(9)?
procedure g(x: integer); forward;
procedure f(x: integer);
begin
if x > 0 then begin
g( x-1 );
1, x 0
f( x-2 )
f ( x)
end;
g ( x 1) f ( x 2) 1, x 0
write( '*' );
end;
procedure g(x: integer);
begin
1, x 1
g ( x)
write( '*' );
1 f ( x 3), x 1
if x > 1 then f(x-3);
end;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

140. Анализ рекурсивных функций

Алгоритмизация и программирование, Паскаль, 10 класс
140
Анализ рекурсивных функций
1, x 0
f ( x)
g ( x 1) f ( x 2) 1, x 0
1, x 1
g ( x)
1 f ( x 3), x 1
x
f (x)
g(x)
–1
1
1
0
1
1
1
3
1
2
3
2
3
6
2
4
6
4
5 6 7 8 9
11 11 19 19 32
4 7 7 12 12
f (1) = g(0) + f (–1) + 1 = 3
f (2) = g(1) + f (0) + 1 = 3
Ответ: 32
g (2) = 1 + f (–1) = 2
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

141. Конец фильма

Алгоритмизация и программирование, Паскаль, 10 класс
141
Конец фильма
ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СОШ № 163, г. Санкт-Петербург
[email protected]
ЕРЕМИН Евгений Александрович
к.ф.-м.н., доцент кафедры мультимедийной
дидактики и ИТО ПГГПУ, г. Пермь
[email protected]
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

142. Источники иллюстраций

Алгоритмизация и программирование, Паскаль, 10 класс
142
Источники иллюстраций
1.
2.
3.
4.
5.
6.
7.
8.
old-moneta.ru
www.random.org
www.allruletka.ru
www.lotterypros.com
logos.cs.uic.edu
ru.wikipedia.org
иллюстрации художников издательства «Бином»
авторские материалы
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
English     Русский Правила