ПрограмКумир

Программирование
на алгоритмическом языке
Тема 1. Введение

Алгоритм
Свойства алгоритма
дискретность: состоит из отдельных шагов (команд)
понятность: должен включать только команды, известные исполнителю
конечность: позволяет получить решение задачи за конечное число шагов
определенность: при одинаковых исходных данных всегда выдает один и тот же результат
массовость: может применяться при различных исходных данных
Алгоритм – это четко определенный план решения задачи для исполнителя.

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

Простейшая программа
алг Первый
нач | начало алгоритма
кон | конец алгоритма
комментарии после |
не обрабатываются
название алгоритма

алг Вывод на экран
нач
вывод "2+"
вывод "2=?", нс
вывод "Ответ: 4"
кон
Вывод текста на экран
Протокол:
2+2=?
Ответ: 4
новая строка

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

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

Программа
алг Сумма
нач
| ввести два числа
| вычислить их сумму | вывести сумму на экран
кон
Псевдокод – алгоритм на русском языке с элементами языка программирования.

Переменные
Переменная – это величина, имеющая имя, тип и значение. Значение переменной можно изменять во время работы программы.
a
Значение
Имя
Другой тип данных

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

Объявление переменных
Типы переменных:
цел | целая
вещ | вещественная
и другие…
Объявление переменных:
цел a, b, c
выделение места в памяти
тип – целые
список имен переменных

Как записать значение в переменную?
a := 5
Оператор присваивания
5
Оператор – это команда языка программирова-ния (инструкция).
Оператор присваивания – это команда для записи нового значения в переменную.
a

Блок-схема линейного алгоритма
начало
конец
c := a + b
ввод a, b
блок «начало»
блок «ввод»
блок «процесс»
блок «вывод»
блок «конец»
вывод c

Как ввести значение с клавиатуры?
ввод a
Оператор ввода
5
a

Ввод значений двух переменных
через пробел:
25 30
через запятую:
25,30
ввод a, b
Ввод значений двух переменных.

Изменение значения переменной
алг Тест
нач
цел a, b
a := 5
b := a + 2
a := (a + 2)*(b – 3)
b := b + 1
кон
a
?
5
5
b
?
5+2
7
a
5
7*4
28
Пример:
b
7
7+1
8

Арифметические операции
+ сложение – вычитание
* умножение / деление
div деление нацело (остаток отбрасывается)
mod остаток от деления
цел a, b
a := 7*3 - 4 | 17
a := a * 5 | 85
b := div(a,10) | 8
a := mod(a,10) | 5

Вывод данных
|вывод значения |переменной a
|вывод значения |переменной a и переход |на новую строчку
|вывод текста
|вывод текста и значения переменной c
вывод a
вывод a, нс
вывод "Привет!"
вывод "Ответ: ", c
вывод a, "+", b, "=", c

Задача: сложение чисел
Задача. Ввести два целых числа и вывести на экран их сумму.
Простое решение:
алг Сумма
нач
цел a, b, c
ввод a, b
c := a + b
вывод c
кон

Полное решение
алг Сумма
нач
цел a, b, c
вывод "Введите два целых числа"
ввод a, b
c := a + b
вывод a, "+", b, "=", c
кон
Протокол:
Введите два целых числа
25 30
25+30=55
компьютер
пользователь
подсказка

Задания
«3»: Ввести три числа, найти их сумму.
Пример:
Введите три числа:
4 5 7
4+5+7=16
«4»: Ввести три числа, найти их сумму и произведение.
Пример:
Введите три числа:
4 5 7
4+5+7=16
4*5*7=140

Задания
«5»: Ввести три числа, найти их сумму, произведение и среднее арифметическое.
Пример: Введите три числа:
4 5 7
4+5+7=16
4*5*7=140
(4+5+7)/3=5.333333

Какие операторы неправильные?
алг Ошибки
нач
цел a, b
вещ x, y
a := 5
10 := x
y := 7,8
b := 2.5
x := 2*(a + y)
a := b + x
кон
имя переменной должно быть слева от знака :=
целая и дробная часть отделяются точкой
нельзя записывать вещественное значение в целую переменную

Порядок выполнения операций
вычисление выражений в скобках
умножение, деление, div, mod слева направо
сложение и вычитание слева направо
z := (5*a+c)/a*(b-c)/ b
x:=(5*c*c-d*(a+b))/((c+d)*(d-2*a))
1 2 4 5 3 6
2 3 5 4 1 10 6 9 8 7

Ручная прокрутка программы
алг Тест
нач
цел a, b
a := 5
b := a + 2
a := (a + 2)*(b – 3)
b := div(a,5)
a := mod(a,b)
a := a + 1
b := mod(a+14,7)
кон

Команда «вывод»
цел a = 1, b = 3
вывод a, "+", b, "=", a+b
список вывода
элементы разделяются запятыми
элементы в кавычках – выводятся без изменений
выражения (элементы без кавычек) вычисляются и выводится их результат
1+3=4

Что будет выведено?
цел a = 1, b = 3
вывод "a+", b, "=a+b"
a+3=a+b
цел a = 1, b = 3
вывод a, "=F(", b, ")"
1=F(3)
цел a = 1, b = 3
вывод "a=F(", b, ");"
цел a = 1, b = 3
вывод a+b, ">", b, "!"
цел a = 1, b = 3
вывод "F(", b, ")=X(", a, ")"
a=F(3);
4>3!
F(3)=X(1)

Как записать оператор «вывод»?
цел a = 1, b = 3
вывод "X(", b, ")=", a
X(3)=1
4=1+3
f(1)>f(3)
<1<>3>
1+3=?
цел a = 1, b = 3
вывод a+b, "=", a, "+", b
цел a = 1, b = 3
вывод "f(", a, ")>f(", b, ")"
цел a = 1, b = 3
вывод "<", a, "<>", b, ">"
цел a = 1, b = 3
вывод a, "+", b, "=?"

Программирование
на алгоритмическом языке
Тема 2. Ветвления

Разветвляющиеся алгоритмы
Задача. Ввести два целых числа и вывести на экран наибольшее из них.
Идея решения: надо вывести на экран первое число, если оно больше второго, или второе, если оно больше первого.
Особенность: действия исполнителя зависят от некоторых условий (если … иначе …).
Алгоритмы, в которых последовательность шагов зависит от выполнения некоторых условий, называются разветвляющимися.

Вариант 1. Блок-схема
полная форма ветвления
блок «решение»

Вариант 1. Программа
алг Максимум
нач цел a, b, M
вывод "Введите два целых числа", нс
ввод a, b
если a > b то
иначе
все
вывод "Наибольшее число ", M
кон
M:=a
M:=b
полная форма условного оператора

Условный оператор
если условие то
| что делать, если условие верно
иначе
| что делать, если условие неверно
все

Вариант 2. Блок-схема
неполная форма ветвления

Вариант 2. Программа
алг Максимум 2
нач цел a, b, M
вывод "Введите два целых числа", нс
ввод a, b
M:= a
если b > a то
M:= b
все
вывод "Наибольшее число ", M
кон
неполная форма условного оператора

Вариант 2б. Программа
алг Максимум 2б
нач цел a, b, M
вывод "Введите два целых числа", нс
ввод a, b
M:= b
если ??? то
??? все
вывод "Наибольшее число ", M
кон
M:= a
a > b

Задания
«3»: Ввести два числа и вывести их в порядке возрастания.
Пример:
Введите два числа:
15 9
Ответ: 9 15
«4»: Ввести три числа и найти наибольшее из них.
Пример:
Введите три числа:
4 15 9
Наибольшее число 15

Задания
«5»: Ввести пять чисел и найти наибольшее из них.
Пример:
Введите пять чисел:
4 15 9 56 4
Наибольшее число 56

Программирование
на алгоритмическом языке
Тема 3. Сложные условия

Сложные условия
Задача. Фирма набирает сотрудников от 25 до 40 лет включительно. Ввести возраст человека и определить, подходит ли он фирме (вывести ответ «подходит» или «не подходит»).
Особенность: надо проверить, выполняются ли два условия одновременно.

Вариант 1. Алгоритм
начало
ввод x
конец
да
нет
x >= 25?
да
нет
x <= 40?
“подходит”
“не подходит”
“не подходит”

Вариант 1. Программа
алг Сотрудник
нач
цел x
вывод "Введите ваш возраст", нс ввод x
если x >= 25 то
если x <= 40 то
вывод "Подходит!"
иначе
вывод "Не подходит."
все
иначе
вывод "Не подходит."
все
кон

Вариант 2. Алгоритм
начало
ввод x
да
нет
x >= 25
и
x <= 40?
“подходит”
“не подходит”

Вариант 2. Программа
сложное условие
алг Сотрудник
нач
цел x
вывод "Введите ваш возраст", нс
ввод x
если x >= 25 и x <= 40 то
вывод "Подходит!"
иначе
вывод "Не подходит."
все
кон

Сложные условия
Простые условия (отношения)
< <= > >= = <>
Сложное условие – это условие, состоящее из нескольких простых условий (отношений), связанных с помощью логических операций:
И – одновременное выполнение условий
x >= 25 И x <= 40
ИЛИ – выполнение хотя бы одного из условий
x <= 25 ИЛИ x >= 40
НЕ – отрицание, обратное условие
НЕ (x > 25) ⇔ ???
равно
не равно
x <= 25

Сложные условия
Порядок выполнения (приоритет = старшинство)
выражения в скобках
НЕ
<, <=, >, >=, =, <>
И
ИЛИ
Пример
2 1 6 3 5 4
если не (a > 2) или c <> 5 и b < a то
...
все

Сложные условия
Истинно или ложно при a := 2; b := 3; c := 4;
не (a > b)
a < b и b < c
a > c или b > c
a < b и b > c
a > c и b > d
не (a >= b) или c = d
a >= b или не (c < b)
a > c или b > c или b > a
Да
Да
Нет
Да
Да
Нет
Нет
Да

Сложные условия
Для каких значений x истинны условия:
x < 6 и x < 10
x < 6 и x > 10
x > 6 и x < 10
x > 6 и x > 10
x < 6 или x < 10
x < 6 или x > 10
x > 6 или x < 10
x > 6 или x > 10
x < 6
x > 10
x < 10
x > 6
нет таких
6 < x < 10
все x

Задания
«3»: Ввести три числа и определить, верно ли, что они вводились в порядке возрастания.
Пример:
Введите три числа:
4 5 17
да
«4»: Ввести номер месяца и вывести название времени года.
Пример:
Введите номер месяца:
4
весна

Задания
«5»: Ввести возраст человека (от 1 до 150 лет) и вывести его вместе с последующим словом «год», «года» или «лет».
Пример:
Введите возраст: Введите возраст:
24 57
Вам 24 года Вам 57 лет

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

Циклы
Цикл – это многократное выполнение одинаковых действий.
цикл с известным числом шагов
цикл с неизвестным числом шагов (цикл с условием)
Задача. Вывести на экран 5 раз слово «Привет».
Особенность: одинаковые действия выполняются 5 раз.

Циклы
алг Привет
нач
вывод "Привет", нс
вывод "Привет", нс
вывод "Привет", нс вывод "Привет", нс
вывод "Привет", нс
кон

Циклы
алг Привет
нач
нц 5 раз
вывод "Привет!", нс
кц
кон
конец цикла
начало цикла
вывод "Привет!", нс
тело цикла

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

Число шагов – переменная
алг Привет
нач
цел N
вывод "Сколько раз?", нс
ввод N
нц N раз
вывод "Привет!", нс
кц
кон
Задача: ввести количество повторения с клавиатуры.

Задания
«3»: Ввести натуральное число и вывести в строчку все числа от 1 до этого числа.
Пример:
Введите натуральное число:
4
Ответ: 1 2 3 4
«4»: Ввести два целых числа, найти их произведение, не используя операцию умножения.
Пример:
Введите два числа:
4 15
4*15=60

Задания
«5»: Ввести натуральное число N и найти сумму всех чисел от 1 до N (1+2+3+…+N).
Пример:
Введите число слагаемых:
100
Сумма чисел от 1 до 100 равна 5050

Циклы
алг Привет
нач
нц 5 раз
вывод "Привет!", нс
кц
кон
N := N + 1

Блок-схема алгоритма
начало
конец
да
нет
N = 5?
N := 0
N := N + 1
еще не сделали ни одного раза
проверить, все ли сделали
считаем очередной шаг
цикл

Цикл с условием
алг Привет 2
нач
цел N
N:= 0
нц пока N <> 5
вывод "Привет!", нс
N:= N + 1
кц
кон

Цикл с условием
алг Привет 3
нач
цел N
N:= 5
нц пока N <> ???
вывод "Привет!", нс
???
кц
кон
Вместо знаков вопроса добавьте числа и операторы так, чтобы цикл выполнился ровно 5 раз:
0
N:= N - 1

Что получим?
алг Пример 1
нач
цел N
N:= 1
нц пока N <= 5
вывод N, нс
N:= N + 1
кц
кон
1
2
3
4
5

Что получим?
алг Пример 2
нач
цел N
N:= 1
нц пока N <= 5
вывод N, нс
N:= N + 2
кц
кон
1
3
5

Что получим?
алг Пример 3
нач
цел N
N:= 2
нц пока N <> 5
вывод N, нс
N:= N + 2
кц
кон
2
4
6
8
10
12
14
16
...

Что получим?
алг Пример 4
нач
цел N
N:= 1
нц пока N <= 5
вывод N*N*N, нс
N:= N + 1
кц
кон
1
8
27
64
125

Что получим?
алг Пример 5
нач
цел N
N:= 5
нц пока N >= 1
вывод N*N*N, нс
N:= N - 1
кц
кон
125
64
27
8
1

Задания
«3»: Ввести натуральное число вывести квадраты и кубы всех чисел от 1 до этого числа.
Пример:
Введите натуральное число:
3
1: 1 1
2: 4 8
3: 9 27
«4»: Ввести два целых числа a и b (a ≤ b) и вывести квадраты все чисел от a до b.
Пример:
Введите два числа:
4 5
4*4=16
5*5=25

Задания
«5»: Ввести два целых числа a и b (a ≤ b) и вывести сумму квадратов всех чисел от a до b.
Пример:
Введите два числа:
4 10
Сумма квадратов 371

Циклы с условием
Пример: Отпилить полено от бревна. Сколько раз надо сделать движения пилой?
Задача: Ввести целое число (<2000000) и определить число цифр в нем.
Идея решения: Отсекаем последовательно последнюю цифру, увеличиваем счетчик.
Проблема: Неизвестно, сколько шагов надо сделать.
Решение: Надо остановиться, когда n = 0, т.е. надо делать «пока n <> 0».

Блок-схема алгоритма
начало
конец
нет
да
n <> 0?
count := 0
count := count + 1
n := div(n, 10)
обнулить счетчик цифр
ввод n
выполнять «пока n <> 0»
вывод count

Программа
алг Число цифр
нач
цел n, count
вывод "Введите целое число", нс
ввод n
count:= 0
вывод "В числе ", n, " нашли ", count, " цифр"
кон
нц пока n<>0
count:= count + 1
n:= div(n,10)
кц
, n1
; n1:= n
n1,

Цикл с условием
Особенности:
можно использовать сложные условия:
можно записывать в одну строчку, разделяя команды точкой с запятой:

Цикл с условием
Особенности:
условие пересчитывается при каждом входе в цикл
если условие на входе в цикл ложно, цикл не выполняется ни разу
если условие никогда не станет ложным, программа зацикливается
a := 4; b := 6
нц пока a > b; a:= a – b кц
a:= 4; b:= 6
нц пока a < b; d:= a + b кц

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

Задания
«3»: Ввести целое число и определить, верно ли, что в нём ровно 3 цифры.
Пример:
Введите число: Введите число:
123 1234
Да. Нет.
«4»: Ввести целое число и найти сумму его цифр.
Пример:
Введите целое число:
1234
Сумма цифр числа 1234 равна 10.

Задания
«5»: Ввести целое число и определить, верно ли, что в его записи есть две одинаковые цифры, стоящие рядом.
Пример:
Введите целое число: Введите целое число:
1232 1224
Нет. Да.
«6»: Ввести целое число и определить, верно ли, что в его записи есть две одинаковые цифры, НЕ обязательно стоящие рядом.
Пример:
Введите целое число: Введите целое число:
1234 1242
Нет. Да.

Задания-2
«3»: Ввести целое число и определить, верно ли, что в нём ровно 1 цифра «9».
Пример:
Введите число: Введите число:
193 1994
Да. Нет.
«4»: Ввести целое число и определить, верно ли, что все его цифры четные.
Пример:
Введите число: Введите число:
2684 2994
Да. Нет.

Задания-2
«5»: Ввести целое число и определить, верно ли, что все его цифры расположены в порядке возрастания.
Пример:
Введите целое число: Введите целое число:
1238 1274
Да. Нет.
«6»: Ввести целое число и «перевернуть» его, так чтобы первая цифра стала последней и т.д.
Пример:
Введите целое число: Введите целое число:
1234 782
4321 287

Вычисление НОД
НОД = наибольший общий делитель двух натуральных чисел – это наибольшее число, на которое оба исходных числа делятся без остатка.
Перебор:
Записать в переменную k минимальное из двух чисел.
Если a и b без остатка делятся на k, то стоп.
Уменьшить k на 1.
Перейти к шагу 2.
это цикл с условием!

Алгоритм Евклида
Евклид
(365-300 до. н. э.)
НОД(a,b)= НОД(a-b, b)
= НОД(a, b-a)
Заменяем большее из двух чисел разностью большего и меньшего до тех пор, пока они не станут равны. Это и есть НОД.
НОД (14, 21) = НОД (14, 21-14) = НОД (14, 7)
НОД (1998, 2) = НОД (1996, 2) = … = 2
Пример:
много шагов при большой разнице чисел:
= НОД (7, 7) = 7
Надо: вычислить наибольший общий делитель (НОД) чисел a и b.

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

Алгоритм Евклида
нц пока a <> b
если a > b
то a:= a - b
иначе b:= b - a
все
кц

Модифицированный алгоритм Евклида
НОД(a,b)= НОД(mod(a,b), b)
= НОД(a, mod(b,a))
Заменяем большее из двух чисел остатком от деления большего на меньшее до тех пор, пока меньшее не станет равно нулю. Тогда большее — это НОД.
НОД (14, 21) = НОД (14, 7) = НОД (0, 7) = 7
Пример:
Еще один вариант:
НОД(2·a,2·b)= 2·НОД(a, b)
НОД(2·a,b)= НОД(a, b) | при нечетном b

Алгоритм Евклида
«3»: Составить программу для вычисления НОД с помощью алгоритма Евклида.
«4»: Составить программу для вычисления НОД с помощью модифицированного алгоритма Евклида и заполнить таблицу:

Алгоритм Евклида
«5»: Выполнить задание на «4» и подсчитать число
шагов алгоритма для каждого случая.

Цикл с переменной
Задача: вывести кубы чисел от 1 до 8.
Нужны ли переменные? Сколько?
Как они должны изменяться?
Нужен ли цикл?

Блок-схема алгоритма
начало
конец
нет
да
N <= 8?
N := 1
N := N + 1
кубN := N*N*N

Цикл с переменной
Задача: вывести кубы натуральных чисел от 1 до 8.
алг Кубы
нач
цел N, кубN
N:= 1
нц пока N <= 8
кубN:= N*N*N
вывод кубN, нс
N:= N + 1
кц
кон
N:= 1
N <= 8
N:= N + 1
3 действия с N

Цикл с переменной
Задача: вывести кубы натуральных чисел от 1 до 8.
алг Кубы
нач
цел N, кубN
кон
нц для N от 1 до 8
кубN:= N*N*N
вывод кубN, нс
кц
для 1,2,3,…,8

Цикл с переменной
Задача: вывести кубы чётных чисел от 2 до 8.
алг Кубы
нач
цел N, кубN
кон
нц для N от 2 до 8 шаг 2
кубN:= N*N*N
вывод кубN, нс
кц
для 2,4,6,8

Сколько раз выполняется цикл?
a := 1
нц для i от 1 до 3; a:=a+1 кц
a = 4
a := 1
нц для i от 3 до 1; a:=a+1 кц
a = 1
a := 1
нц для i от 1 до 3 шаг -1; a:=a+1 кц
a = 1
a := 1
нц для i от 3 до 1 шаг -1; a:=a+1 кц
a = 4

Цикл с переменной
Особенности:
переменная цикла может быть только целой (цел)
начальное и конечное значения и шаг – целые
можно записывать в одну строчку, разделяя команды точкой с запятой:
если шаг > 0 и конечное значение < начального, цикл не выполняется ни разу (проверка условия в начале цикла, цикл с предусловием)
если шаг < 0 и конечное значение > начального, цикл не выполняется ни разу

Замена одного вида цикла на другой
нц для i от 1 до 10
| тело цикла
кц
i:= 1
нц пока i <= 10
| тело цикла
i:= i + 1
кц
нц для i от a до b шаг -1
| тело цикла
кц
i:= a
нц пока i >= b
| тело цикла
i:= i - 1
кц
Замена пока на для возможна только тогда, когда можно заранее вычислить число шагов цикла.
Замена цикла для на пока возможна всегда.

Задания
«3»: Ввести натуральное число N и вывести числа от N до 1 (через одно) в порядке убывания.
Пример:
Введите натуральное число:
8
Ответ: 8 6 4 2

Задания
«4»: Ввести два целых числа a и b (a ≤ b) и вывести кубы всех чисел от a до b.
Пример:
Введите два числа:
4 6
4*4*4=64
5*5*5=125
6*6*6=216
«5»: Ввести целое число a и вывести сумму квадратов всех чисел от 1 до a с шагом 0.1.
Пример:
Введите последнее число:
3
Сумма 91.7
12 + 1.12 + 1.22 +…+ a2

Задания
«4»: Ввести a и b и вывести квадраты и кубы чисел от a до b.
Пример:
Введите границы интервала:
4 6
4: 16 64
5: 25 125
6: 36 216
«5»: Вывести квадраты и кубы 10 чисел следующей последовательности: 1, 2, 4, 7, 11, 16, …
Пример:
1: 1 1
2: 4 8
4: 16 64
...
46: 2116 97336

Программирование
на алгоритмическом языке
Тема 5. Графика

Система координат
(0,0)
(x,y)
X
Y
x
y

Исполнитель Рисователь
использовать Рисователь
алг
нач
| текст программы
кон

Цвет и толщина линий:
перо(2, "синий")
Линии
толщина линии
перо(1, "зеленый") линия(10, 15, 90, 80)
перо(1, "красный“)
в точку(5, 5)
линия в точку(50, 5)
линия в точку(70, 50)
линия в точку(30, 80)
линия в точку(5, 60)

Фигуры с заливкой
перо(1, "синий")
кисть("желтый")
прямоугольник(0, 0, 80, 40)
перо(1, "красный")
кисть("зеленый")
эллипс(0, 0, 100, 50)
кисть("фиолетовый")
залить(70, 80)
кисть(""); | отменить заливку

Пример
использовать Рисователь
алг Домик
нач
перо(2, "фиолетовый")
кисть("синий")
прямоугольник(100, 100, 300, 200)
в точку(100, 100)
линия в точку(200, 50)
линия в точку(300, 100)
кисть("желтый")
залить(200, 75);
перо(2, "белый");
кисть("зеленый");
эллипс(150, 100, 250, 200);
кон
(200, 50)
(100, 100)
(300, 200)

«3»: «Домик»
«4»: «Лягушка»
Задания

«5»: «Корона»
Задания

Штриховка
(x1, y1)
(x2, y2)
N линий (N=5)
h
прямоугольник (x1, y1, x2, y2)
x:= x1 + h
линия(x, y1, x, y2)
x:= x + h
линия(x, y1, x, y2)
x:= x + h
...
x
y2
y1
цикл N раз

Штриховка (программа)
использовать Рисователь
алг Штриховка
нач
цел N = 5 | число линий
цел x1 = 100, x2 = 300
цел y1 = 100, y2 = 200
вещ h, x
h:=(x2 - x1)/(N + 1)
прямоугольник(x1, y1, x2, y2)
x:= x1 + h
нц N раз
линия(int(x), y1, int(x), y2)
x:= x + h
кц
кон
целая часть
вещ h, x

Штриховка
(x1, y1)
(x2, y2)
hx
hy
x:= x1 + hx; y:= y1 + hy
линия(x1, int(y), int(x), int(y))
x:= x + hx; y:= y + hy
линия(x1, int(y), int(x), int(y))
x:= x + hx; y:= y + hy
...
цикл N раз

Штриховка
(x1, y1)
(x2, y2)
hx
hy
вещ hx, hy, x, y
hx:=(x2 - x1)/(N + 1)
hy:=(y2 - y1)/(N + 1)
в точку(x1, y1)
линия в точку(x1, y2)
линия в точку(x2, y2)
линия в точку(x1, y1)
x:= x1 + hx; y:= y1 + hy
нц N раз
линия(x1,int(y),int(x),int(y))
x:= x + hx
y:= y + hy
кц

Задания
«3»: Ввести с клавиатуры количество линий, построить фигуру и выполнить штриховку:
«4»: Ввести с клавиатуры количество линий, построить фигуру и выполнить штриховку:
или

Задания
«5»: Ввести с клавиатуры количество линий и построить фигуру:

Программирование
на алгоритмическом языке
Тема 6. Вспомогательные
алгоритмы

Задача
Особенность: три похожие фигуры.
общее: размеры, угол поворота
отличия: координаты, цвет

С чего начать?
найти похожие действия (три фигуры)
найти общее (размеры, форма, угол поворота) и отличия (координаты, цвет)
отличия = параметры алгоритма (доп. данные)
(x+100, y)
(x, y-60)
использовать Рисователь
алг Тр (цел x, y, лит цвет)
нач
в точку(x, y)
линия в точку(x, y-60)
линия в точку(x+100, y)
линия в точку(x, y)
кисть(цвет)
залить(x+20, y-20)
кон
цепочка символов

Если запустить?
(50,100)

Как использовать?
использовать Рисователь
алг Треугольники
нач
перо(1, "черный")
Тр(100, 100, "синий")
Тр(200, 100, "зеленый") Тр(200, 160, "красный")
кон
(100,100)
100
60
вызовы алгоритма
алг Тр(цел x, y, лит цвет)
нач
...
кон
основной
алгоритм
вспомогательный
алгоритм

Вспомогательные алгоритмы
расположены ниже основного
в заголовке перечисляются формальные параметры, они обозначаются именами
для каждого параметра указывают тип
однотипные параметры перечисляются через запятую
при вызове в скобках указывают фактические параметры в том же порядке
алг Тр(цел x, y, лит цвет)
Тр(200, 100, "зеленый")
x
y
цвет

Задания
«3»: Используя одну процедуру, построить фигуру.
«4»: Используя одну процедуру, построить фигуру.

Задания
«5»: Используя одну процедуру, построить фигуру.

Рекурсивные объекты
Рекурсивный объект – это объект, определяемый через один или несколько таких же объектов.
У попа была собака, он ее любил.
Она съела кусок мяса, он ее убил.
В ямку закопал, надпись написал:
Сказка о попé и собаке
Примеры:
Сказка о попé и собаке:
Факториал:
если
если
Рисунок с рекурсией:

Рекурсивная фигура
3 уровня:
Фигура из N уровней – это
окружность и
4 фигуры из N-1 уровней
N-1
N-1
N-1
N-1

Рекурсивная фигура: алгоритм
алг РекОк(цел x, y, R, N)
нач
если N <= 0 то выход все
окружность(x, y, R)
РекОк(x, y-R, div(R,2), N-1)
РекОк(x+R, y, div(R,2), N-1)
РекОк(x, y+R, div(R,2), N-1)
РекОк(x-R, y, div(R,2), N-1)
кон
центр
радиус
уровней
рекурсивные вызовы
Рекурсивный алгоритм – это алгоритм, который вызывает сам себя (с другими параметрами!).
окончание рекурсии
(x,y-R)
(x+R,y)
(x-R,y)
(x,y+R)
(x,y)

Рекурсивная фигура: программа
использовать Рисователь
алг Рекурсия
нач
РекОк(200, 200, 100, 3)
кон
алг РекОк(цел x, y, R, N)
нач
...
кон

Рекурсивные алгоритмы
вызывают сами себя прямо
… или через другой алгоритм:
должно быть условие окончания рекурсии (иначе?)
рекурсия может стать бесконечной
все задачи могут быть решены без рекурсии, но…
часто рекурсивные алгоритмы проще и понятнее
как правило, алгоритмы без рекурсии работают быстрее и требуют меньше памяти
A
A
B
прямая рекурсия
косвенная рекурсия

«3»: Нарисовать рекурсивную фигуру, число уровней вводить с клавиатуры:
«4»: Нарисовать рекурсивную фигуру, число уровней вводить с клавиатуры:
Задания

«5»: Нарисовать рекурсивную фигуру, число уровней вводить с клавиатуры:
Задания

Программирование
на алгоритмическом языке
Тема 8. Анимация

Анимация
Анимация (англ. animation) – оживление изображения на экране.
Задача: внутри синего квадрата 200 на 200 пикселей слева направо двигается желтый квадрат 20 на 20 пикселей. Программа останавливается, если нажата клавиша Esc или квадрат дошел до границы синей области.
Проблема: как изобразить перемещение объекта на экране?
Привязка: состояние объекта задается координатами (x,y)
Принцип анимации:
рисуем объект в точке (x,y)
задержка на несколько миллисекунд
стираем объект
изменяем координаты (x,y)
переходим к шагу 1

Процедура (рисование и стирание)
алг Фигура(цел x, y, лит цвет)
нач
кисть(цвет)
прямоугольник(x,y,x+20,y+20)
кон
(x, y)
(x+20, y+20)
одна процедура рисует и стирает
стереть = рисовать цветом фона
границу квадрата отключить
рисуем: цвет кисти – желтый
стираем: цвет кисти – синий

Полная программа
использовать Рисователь
алг Анимация
нач
цел x, y | текущие координаты
кисть("синий") перо(1, "") | отключить контур
прямоугольник(0, 0, 200, 200) | синий фон
x:= 0; y:= 100 | начальные координаты
кон
алг Фигура(цел x, y, лит цвет)
нач
...
кон
нц пока x < 180
Фигура(x, y, "желтый")
delay(50)
Фигура(x, y, "синий")
x:= x + 5
кц
пока не дошли до границы

Задания
«3»: Квадрат двигается справа налево:
«4»: Два квадрата двигаются в противоположных направлениях:

Задания
«5»: Два квадрата двигаются в противоположных направлениях
и отталкиваются от стенок синего квадрата:

Управление клавишами
Задача: жёлтый квадрат внутри синего квадрата управляется клавишами-стрелками. Коды клавиш:
влево – 16777234 вверх – 16777235
вправо – 16777236 вниз – 16777237
Проблема: как изменять направление движения?
Решение:
c:= клав
выбор
при c = 16777234: x:= x – 5 | влево
при c = 16777235: y:= y – 5 | вверх
при c = 16777236: x:= x + 5 | вправо
при c = 16777237: y:= y + 5 | вниз
все
ждать нажатия на клавишу, записать ее код в переменную c

Программа
использовать Рисователь
алг Управление клавишами
нач
цел x, y, c
| нарисовать синий квадрат x:= 100; y:= 100 | начальная точка
нц пока x < 180
Фигура(x, y,"желтый") | рисуем фигуру
c:= клав | ждем нажатия клавиши
Фигура(x, y,"синий") | стираем фигуру
выбор
при c = 16777234: x:= x - 5
при c = 16777235: y:= y - 5
при c = 16777236: x:= x + 5
при c = 16777237: y:= y + 5
все
кц
кон

Задания
«3»: Квадрат в самом начале стоит в правом нижнем углу, и двигается при нажатии стрелок только вверх или влево:
«4»: Квадрат двигается при нажатии стрелок, однако не может выйти за границы синего квадрата:

Задания
«5»: Квадрат непрерывно двигается, при нажатии стрелок меняет направление и отталкивается от стенок синего квадрата:

Программирование
на алгоритмическом языке
Тема 9. Случайные числа

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

Электронный генератор
нужно специальное устройство
нельзя воспроизвести результаты
318458191041
564321
209938992481
458191
938992
малый период
(последовательность повторяется через 106 чисел)
Метод середины квадрата (Дж. фон Нейман)
в квадрате
Псевдослучайные числа – обладают свойствами случайных чисел, но каждое следующее число вычисляется по заданной формуле.
Случайные числа на компьютере

Модель: снежинки падают на отрезок [a,b]
распределение
равномерное
неравномерное
Распределение случайных чисел

Особенности:
распределение – это характеристика всей последовательности, а не одного числа
равномерное распределение одно, компьютерные датчики случайных чисел дают равномерное распределение
неравномерных – много
любое неравномерное можно получить с помощью равномерного
a
b
a
b
Распределение случайных чисел

Вещественные числа в интервале [0,10):
Генератор случайных чисел
вещ X, Y
X:= rand(0, 10) | интервал от 0 до 10 (<10)
Y:= rand(0, 10) | это уже другое число!
англ. random – случайный
Целые числа в интервале [0,10]:
цел K, L
K:= irand(0, 10) | интервал от 0 до 10 (<=10)
L:= irand(0, 10) | это уже другое число!
англ. integer – целый

Случайные числа
Задача: заполнить прямоугольник
200 на 150 пикселей равномерно
точками случайного цвета
Как получить случайные координаты пикселя?
Как добиться равномерности?
автоматически при использовании irand
цел X, Y
X:= irand(0, 200)
Y:= irand(0, 150)

Цвет пикселя на мониторе
Вывод: цвет можно разложить на составляющие (каждая кодируется числом от 0 до 255).
Модель RGB:
RGB(0,0,0)
R G B
RGB(255,255,255)
RGB(255,0,0)
RGB(0,255,0)
RGB(0,0,255)
RGB(255,0,255)
RGB(255,255,0)
RGB(0,255,255)
RGB(100,100,100)

Случайный цвет пикселя
цел r, g, b
r:= irand(0, 255)
g:= irand(0, 255)
b:= irand(0, 255)
Случайные составляющие цвета:
это разные числа!
Управление цветом пикселя:
пиксель(X, Y, RGB(r,g,b))
случайный цвет

Программа
использовать Рисователь
алг Случайные точки
нач
цел x, y, r, g, b
нц пока да
x:=irand(0,200)
y:=irand(0,100)
r:=irand(0,255)
g:=irand(0,255)
b:=irand(0,255)
пиксель(x,y,RGB(r,g,b))
кц
кон
это бесконечный цикл:
нц пока да
…
кц

Задания
«3»: Заполнить квадрат точками случайного цвета. размер квадрата ввести с клавиатуры:
Пример: Введите размер квадрата:
150
«4»: Заполнить область точками случайного цвета:

Задания
«5»: Заполнить область точками случайного цвета:
или