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

Программирование на языке C++. § 54. Простейшие программы

1. Программирование на языке C++

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

2. Программирование на языке C++

2
Программирование
на языке C++
§ 54. Простейшие программы
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык C++, 10 класс
3
Простейшая программа
результат –
целое число
это основная
программа
комментарии после //
int main()
не обрабатываются
{
// это основная программа
/* здесь записывают
операторы */
}
это тоже комментарий
? Что делает эта программа?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык C++, 10 класс
4
Вывод на экран
int main() character output – выходной
поток [символов] на консоль
{
cout << "2+";
"\n" – новая строка
cout << "2=?\n";
cout << "Ответ: 4";
}
Протокол:
2+2=?
Ответ: 4
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

5. Подключение библиотечных функций

Алгоритмизация и программирование, язык C++, 10 класс
5
Подключение библиотечных функций
#include <iostream>
стандартные потоки
ввода и вывода
using namespace std;
int main()
стандартное
{
пространство имен
cout << "2+";
cout << "2=?\n";
cout << "Ответ: 4";
cin.get();
ждать нажатия любой
}
клавиши
character input – входной
поток [символов] c консоли
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

6. Если не подключить пространство имён…

Алгоритмизация и программирование, язык C++, 10 класс
6
Если не подключить пространство имён…
#include <iostream>
int main()
пространство имен std
{
std::cout << "2+";
std::cout << "2=?\n";
std::cout << "Ответ: 4";
std::cin.get();
}
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

7. Вывод в поток

Алгоритмизация и программирование, язык C++, 10 класс
7
Вывод в поток
cout << "2+" << "2=?" << "\n"
<< "Ответ: 4";
cout << "2+" << "2=?" << endl
<< "Ответ: 4";
end of line – конец
строки
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

8. Задания

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

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

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

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

Алгоритмизация и программирование, язык C++, 10 класс
10
Сумма: псевдокод
int main()
{
// ввести два числа
// вычислить их сумму
// вывести сумму на экран
}
Псевдокод – алгоритм на
русском языке с элементами
языка программирования.
! Компьютер не может исполнить псевдокод!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

11. Переменные

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

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

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

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

Алгоритмизация и программирование, язык C++, 10 класс
13
Объявление переменных
тип – целые
список имен
переменных
int a, b, c;
выделение
места в памяти
Начальные значения:
int a, b = 1, c = 55;
? Что в переменной a?
К.Ю. Поляков, Е.А. Ерёмин, 2018
«мусор»!
не использовать!
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык C++, 10 класс
14
Типы данных
• int
// целое
• long int // длинное целое
• float
// вещественное
• double
// веществ. двойной точности
• bool
// логические значения
• char
// символ
• string
// символьная строка
• и др.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

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

16. Как записать значение в переменную?

Алгоритмизация и программирование, язык C++, 10 класс
16
Как записать значение в переменную?
оператор
присваивания
a = 5;
5
! При записи нового
значения старое
стирается!
Оператор – это команда языка
программирования (инструкция).
Оператор присваивания – это команда для
записи нового значения в переменную.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

17. Ввод значения с клавиатуры

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

18. Ввод значений двух переменных

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

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

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

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

Алгоритмизация и программирование, язык C++, 10 класс
20
Вывод данных
//вывод значения
//переменной a
cout << a;
cout << a << endl;
//...и переход
//на новую строку
cout << "Привет!";
//вывод текста
cout << "Ответ: " << c;
//вывод текста и значения переменной c
cout << a << "+" << b << "=" << c;
2+3=5
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык C++, 10 класс
21
Сложение чисел: простое решение
#include <iostream>
using namespace std;
int main()
{
int a, b, c;
cin >> a >> b;
c = a + b;
cout << c;
}
К.Ю. Поляков, Е.А. Ерёмин, 2018
далее эта «шапка» в
слайдах не
повторяется
? Что плохо?
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык C++, 10 класс
22
Сложение чисел: полное решение
подсказка
int a, b, c;
cout << "Введите два целых числа\n";
cin >> a >> b;
c = a + b;
cout << a << "+" << b << "=" << c;
Протокол:
компьютер
Введите два целых числа
25 30
пользователь
25+30=55
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык C++, 10 класс
23
Снова про оператор вывода
Вычисление выражений:
cout << a << "+" << b << "=" << a+b
a+b;
Форматный вывод:
#include <iomanip>
...
a = 123;
5 << a;
cout << setw(5)
манипуляторы для
управления потоками
123
5 знаков
set width – установить
ширину поля
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

24. Программирование на языке C++

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

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

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

26. Деление

Алгоритмизация и программирование, язык C++, 10 класс
26
Деление
Результат деления целого на целое – целое число
(остаток отбрасывается):
int a = 3, b = 4;
? Что запишется в x?
float x;
x = 3 / 4;
// = 0
x = 3. / 4; // = 0.75
x = 3 / 4.; // = 0.75
x = a / 4;
// = 0
x = a / 4.; // = 0.75
x = a / b;
// = 0
x = float(a) / 4; // = 0.75
x = a / float(b); // = 0.75
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

27. Остаток от деления

Алгоритмизация и программирование, язык C++, 10 класс
27
Остаток от деления
% – остаток от деления
int a, b, d;
d = 85;
b = d / 10;
// 8
a = d % 10;
// 5
d = a % b;
// 5
d = b % a;
// 3
Для отрицательных чисел:
int a = -7;
b = a / 2; // -3
d = a % 2; // -1
К.Ю. Поляков, Е.А. Ерёмин, 2018
! В математике не так!
остаток 0
-7 = (-4)*2 + 1
http://kpolyakov.spb.ru

28. Сокращенная запись операций

Алгоритмизация и программирование, язык C++, 10 класс
28
Сокращенная запись операций
int a, b;
...
a ++;
// a = a + 1;
a --;
// a = a – 1;
a += b; // a = a + b;
a -= b; // a = a - b;
a *= b; // a = a * b;
a /= b; // a = a / b;
a %= b; // a = a % b;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык C++, 10 класс
29
Вещественные числа
! Целая и дробная части числа разделяются
точкой!
Форматы вывода:
float x = 123.456;
cout.width(10);
cout.precision(5);
cout << x << endl;
cout.width(10);
cout.precision(2);
cout << x << endl;
5 значащих цифр
123.46
всего 10 знаков
1.2e+002
1,2 102
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык C++, 10 класс
30
Вещественные числа
Формат с фиксированной точкой:
#include <iomanip>
...
в дробной части
float x = 123.4567890123;
cout << fixed << setprecision(3)
<< x;
фиксированный
К.Ю. Поляков, Е.А. Ерёмин, 2018
123.456
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык C++, 10 класс
31
Вещественные числа
Экспоненциальный (научный) формат:
float x;
x = 1./30000;
cout << x;
x = 12345678.;
cout << x;
3,33333 10–5
3.33333e-005
1.23457e+007
1,23457 107
float x = 123.456;
cout.width(10);
в дробной части
cout.precision(2);
cout << scientific << x; 1.23e+002
научный
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык C++, 10 класс
Стандартные функции
#include <сmath>
32
подключить
математическую
библиотеку
abs(x) — модуль целого числа
fabs(x) — модуль вещественного числа
sqrt(x) — квадратный корень
sin(x) — синус угла, заданного в радианах
cos(x) — косинус угла, заданного в радианах
exp(x) — экспонента ех
ln(x)
— натуральный логарифм
pow(x,y) — xy: возведение числа x в степень y
floor(x) — округление «вниз»
ceil(x) — округление «вверх»
float x;
x = floor(1.6);// 1
x = ceil(1.6); // 2
К.Ю. Поляков, Е.А. Ерёмин, 2018
x = floor(-1.6);//-2
x = ceil(-1.6); //-1
http://kpolyakov.spb.ru

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

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

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

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

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

Алгоритмизация и программирование, язык C++, 10 класс
35
Линейный конгруэнтный генератор
X = (a*X+b) % c | интервал от 0 до c-1
X = (X+3) % 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

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

Алгоритмизация и программирование, язык C++, 10 класс
36
Генератор случайных чисел
#include <random>
англ. random – случайный
Генератор на отрезке [0,RAND_MAX]:
int X, Y;
X = rand(); // псевдослучайное число
Y = rand() // это уже другое число!
Целые числа на отрезке [a,b]:
int X, Y;
X = a + rand() % (b - a + 1);
Y = a + rand() % (b - a + 1);
? Почему так?
[0,b-a]
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

37. Задачи

Алгоритмизация и программирование, язык C++, 10 класс
37
Задачи
«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

38. Задачи

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

39. Программирование на языке C++

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

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

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

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

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

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

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

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

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

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

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

45. Задачи

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

46. Задачи

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

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

Алгоритмизация и программирование, язык C++, 10 класс
47
Сложные условия
Задача: набор сотрудников в возрасте 25-40 лет
(включительно). сложное условие
if ( v >= 25 && v <= 40 )
cout << "подходит";
else
cout << "не подходит";
&& «И»
|| «ИЛИ»
! «НЕ»
Приоритет :
1) отношения (<, >, <=, >=, ==, !=)
2)! («НЕ»)
3)&& («И»)
4)|| («ИЛИ»)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

48. Задачи

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

49. Задачи

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

50. Задачи

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

51. Задачи

Алгоритмизация и программирование, язык C++, 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. Задачи

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

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

Алгоритмизация и программирование, язык C++, 10 класс
53
Множественный выбор
if (m == 1) cout << "январь";
if (m == 2) cout << "февраль";
...
if (m == 12) cout << "декабрь";
switch ( m ) {
case 1: cout << "январь";
break;
case 2: cout << "февраль";
break;
...
case 12: cout << "декабрь";
break;
default: cout << "ошибка";
}
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык C++, 10 класс
54
Множественный выбор
Если не ставить break:
switch ( m ) {
case 1:
cout << "январь";
case 2:
cout << "февраль";
case 3:
cout << "март";
default: cout << "ошибка";
}
При m = 2:
февральмартошибка
! Берегись проваливания!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык C++, 10 класс
55
Множественный выбор
char c;
ждать нажатия клавиши,
c = getch();
получить её код
switch(c)
{
case 'а':
cout << "антилопа\n";
несколько
cout << "Анапа\n";
операторов в
break;
блоке
...
case 'я':
cout << "ягуар\n";
cout << "Якутск\n";
break;
default: cout << "Ошибка!";
}
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

56. Программирование на языке C++

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

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

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

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

Алгоритмизация и программирование, язык C++, 10 класс
58
Повторения в программе
cout << "Привет\n";
cout << "Привет\n";
...
cout << "Привет\n";
? Что плохо?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

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

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

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

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

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

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

Алгоритмизация и программирование, язык C++, 10 класс
62
Цикл с условием
начальное значение
счётчика
заголовок
цикла
конец
цикла
условие
продолжения
count = 0;
while ( n > 0 )
{
n = n / 10;
count ++;
}
тело цикла
! Цикл с предусловием – проверка на входе в цикл!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык C++, 10 класс
63
Цикл с условием
При известном количестве шагов:
k = 0;
while ( k < 10 )
{
cout << "привет\n";
k ++;
}
Зацикливание:
k = 0;
while ( k < 10 )
{
cout << "привет\n";
}
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык C++, 10 класс
64
Сколько раз выполняется цикл?
a = 4; b = 6;
while ( a < b ) a = a + 1;
2 раза
a=6
a = 4; b = 6;
while ( a < b ) a = a + b;
1 раз
a = 10
a = 4; b = 6;
while ( a > b ) a ++;
0 раз
a=4
a = 4; b = 6;
while ( a < b ) b = a - b;
1 раз
b = -2
a = 4; b = 6;
while ( a < b ) a --;
К.Ю. Поляков, Е.А. Ерёмин, 2018
зацикливание
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык C++, 10 класс
65
Цикл с постусловием
заголовок
цикла
do
тело цикла
{
cout << "Введите n > 0: ";
cin >> n;
}
while ( n <= 0 );
условие
продолжения
• при входе в цикл условие не проверяется
• цикл всегда выполняется хотя бы один раз
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

66. Задачи

Алгоритмизация и программирование, язык C++, 10 класс
66
Задачи
«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

67. Задачи

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

68. Задачи-2

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

69. Задачи-2

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

70. Программирование на языке C++

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

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

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

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

Алгоритмизация и программирование, язык C++, 10 класс
72
Цикл по переменной: другой шаг
это внутренняя
переменная цикла
for ( int k = 10; k >= 1; k-- )
cout << k*k << endl;
? Что получится?
for ( int k = 1; k <= 10; k += 2 )
cout << k*k << endl;
1
9
25
49
81
К.Ю. Поляков, Е.А. Ерёмин, 2018
100
81
64
49
36
25
16
9
4
1
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык C++, 10 класс
73
Сколько раз выполняется цикл?
int a = 1;
a= 4
for( int i = 1; i <= 3; i++ ) a = a + 1;
int a = 1;
a= 1
for( int i = 3; i <= 1; i++ ) a = a + 1;
зацикливание
int a = 1;
for( int i = 1; i <= 3; i-- ) a = a + 1;
a= 4
int a = 1;
for( int i = 3; i >= 1; i-- ) a = a + 1;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

74. Задачи

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

75. Задачи

Алгоритмизация и программирование, язык C++, 10 класс
75
Задачи
«С»: Натуральное число называется автоморфным, если
оно равно последним цифрам своего квадрата.
Например, 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

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

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

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

Алгоритмизация и программирование, язык C++, 10 класс
77
Вложенные циклы
for ( int n = 2; n <= 1000; n ++ )
{
count = 0;
for ( int k = 2; k < n; k ++ )
if ( n % k == 0 )
count ++;
вложенный цикл
if ( count == 0 )
cout << n << endl;
}
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык C++, 10 класс
78
Вложенные циклы
for ( int i = 1; i <= 4; i++ )
{
for ( int k = 1; k <= i; k++ )
{
cout << i << " " << k
<< endl;
}
}
? Как меняются переменные?
1 1
2 1
2 2
3 1
3 2
3 3
4 1
4 2
4 3
4 4
! Переменная внутреннего
цикла изменяется быстрее!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык C++, 10 класс
79
Поиск простых чисел – как улучшить?
n k m, k m k 2 n k n
? Что плохо?
while( k <= sqrt(n) )
{
...
}
int count = 0;
int k = 2;
Как ещё улучшить?
while ( k*k <= n )
{
if ( n % k == 0 ) count ++;
k ++;
0) ) {
while ( k*k <= n && (count
count == 0
}
...
?
}
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

80. Задачи

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

81. Задачи

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

82. Программирование на языке C++

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

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

Алгоритмизация и программирование, язык C++, 10 класс
83
Зачем нужны процедуры?
cout <<
"Ошибка программы";
void Error()
{
cout << "Ошибка программы";
}
много раз!
void – пустой,
нет результата
int main()
{
вызов
процедуры
int n;
cin >> n;
if ( n < 0 ) Error();
...
}
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

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

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

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

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

Алгоритмизация и программирование, язык C++, 10 класс
86
Процедура с параметрами
Задача. Вывести на экран запись целого числа (0..255) в
8-битном двоичном коде.
Решение:
n
k
вывод
int k = 128;
178
128
1
while ( k > 0 )
50
64
0
{
cout << n / k;
50
32
1
n = n % k;
18
16
1
k = k / 2;
2
8
0
}
2
4
0
178 10110010
2
2
1
зависит
! Результат
от n!
К.Ю. Поляков, Е.А. Ерёмин, 2018
0
0
1
0
0
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык C++, 10 класс
87
Процедура с параметрами
void printBin( int n )
{
int k;
Параметры – данные,
k = 128;
локальные
переменные
while ( k > 0 ) изменяющие работу
процедуры.
{
cout << n / k;
n = n % k;
k = k / 2;
}
}
int main()
значение параметра
{
(аргумент)
printBin( 99 );
}
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык C++, 10 класс
88
Несколько параметров
void printSred ( int a, int b )
{
cout << (a+b)/2.;
}
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

89. Задачи

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

90. Задачи

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

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

Алгоритмизация и программирование, язык C++, 10 класс
91
Изменяемые параметры
Задача. Написать процедуру, которая меняет местами
значения двух переменных.
передача по
void Swap ( int a, int b )
значению
{
int c;
Процедура работает с
c = a; a = b; b = c;
копиями переданных
}
значений параметров!
!
? Почему не работает?
int main()
{
int x = 2, y = 3;
Swap ( x, y );
cout << x << " " << y;
}
К.Ю. Поляков, Е.А. Ерёмин, 2018
2 3
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык C++, 10 класс
92
Изменяемые параметры
переменные могут изменяться
void Swap ( int & a, int & b )
{
передача по
int c;
ссылке
c = a; a = b; b = c;
}
!
Вызов:
Здесь не видно, изменяются
аргументы или нет!
int a, b;
Swap(a, b);
// правильно
Swap(2, 3);
// неправильно
Swap(a, b+3); // неправильно
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

93. Задачи

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

94. Задачи

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

95. Программирование на языке C++

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

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

Алгоритмизация и программирование, язык C++, 10 класс
96
Что такое функция?
Функция – это вспомогательный алгоритм, который
возвращает значение-результат (число, символ или
объект другого типа).
Примеры:
float s = sin(x);
char c = getch();
int v = rand() % 10;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык C++, 10 класс
97
Что такое функция?
Задача. Написать функцию, которая вычисляет младшую
цифру числа (разряд единиц).
число
1234
lastDigit
последняя цифра
4
int lastDigit( int n ) {
int d = n % 10;
результат работы
функции – значение d
return d;
}
передача
// вызов функции
результата
k = lastDigit( 1234 );
cout << k;
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык C++, 10 класс
98
Вычисление суммы цифр числа
Задача. Написать функцию, которая вычисляет сумму
цифр числа.
Алгоритм:
сумма = 0
пока n != 0
сумма = сумма + n % 10
n = n / 10
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык C++, 10 класс
99
Сумма цифр числа
int sumDigits( int n )
{
тип результата
int sum = 0;
while ( n != 0 )
{
sum += n % 10;
n /= 10;
передача
}
результата
return sum;
}
int main()
{
cout << sumDigits(12345);
}
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык C++, 10 класс
100
Использование функций
x = 2*sumDigits(n+5);
z = sumDigits(k) + sumDigits(m);
if ( sumDigits(n) % 2 == 0 )
{
cout << "Сумма цифр чётная\n";
cout << "Она равна " << sumDigits(n);
}
! Функция, возвращающая целое число, может
использоваться везде, где и целая величина!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

101. Задачи

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

102. Задачи

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

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

Алгоритмизация и программирование, язык C++, 10 класс
103
Логические функции
Задача. Найти все простые числа в диапазоне
от 2 до 100.
int main()
{
for ( int i = 2; i <= 100; i++)
if ( iisPrime(i)
- простое )
cout << i << endl;
}
функция, возвращающая
логическое значение
(true/false)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык C++, 10 класс
104
Функция: простое число или нет?
? Какой алгоритм?
bool isPrime ( int n )
{
int count = 0, k = 2;
while ( k*k <= n && count == 0 )
{
if ( n % k == 0 )
if( count == 0 )
count ++;
return true;
k ++;
else return false;
}
return (count == 0);
}
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык C++, 10 класс
105
Логические функции: использование
! Функция, возвращающая логическое значение,
может использоваться везде, где и логическая
величина!
cin >> n;
while ( isPrime(n) )
{
cout << "простое число\n";
cin >> n;
}
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

106. Задачи

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

107. Задачи

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

108. Задачи

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

109. Программирование на языке C++

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

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

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

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

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

Алгоритмизация и программирование, язык C++, 10 класс
111
Что такое рекурсия?
Натуральные числа:
• 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

112. Фракталы

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

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

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

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

Алгоритмизация и программирование, язык C++, 10 класс
114
Ханойские башни – процедура
сколько
откуда
куда
void Hanoi ( int n, int k, int m )
{
номер вспомогательного
int p;
стержня (1+2+3=6!)
p = 6 - k - m;
рекурсия
Hanoi ( n-1, k, p );
cout << k << " -> " << m << endl;
рекурсия
Hanoi ( n-1, p, m );
}
? Что плохо?
! Рекурсия никогда не остановится!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык C++, 10 класс
115
Ханойские башни – процедура
Рекурсивная процедура (функция) — это процедура
(функция), которая вызывает сама себя напрямую или
через другие процедуры и функции.
void Hanoi ( int n, int k, int m )
{
условие выхода из
int p;
рекурсии
if ( n == 0 ) return;
p = 6 - k - m;
Hanoi ( n - 1, k, p );
cout << k << " -> " << m << endl;
Hanoi ( n - 1, p, m ); int main()
}
{
Hanoi(4, 1, 3);
}
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык C++, 10 класс
116
Вывод двоичного кода числа
условие выхода из
рекурсии
void printBin( int n )
{
напечатать все
if ( n == 0 ) return;
цифры, кроме
printBin( n / 2 );
последней
cout << n % 2;
}
вывести
последнюю цифру
printBin(
01))
printBin(
printBin(
24))
printBin(
printBin(
))
printBin(919
? Как без рекурсии?
10011
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

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

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

Алгоритмизация и программирование, язык C++, 10 класс
118
Вычисление суммы цифр числа
int sumDigits( int n )
{
последняя цифра
int sum;
sum = n %10;
рекурсивный вызов
if ( n >= 10 )
sum += sumDigits ( n / 10 );
return sum;
}
Где условие окончания рекурсии?
?
sumDigits( 1234 )
4 + sumDigits( 123 )
4 + 3 + sumDigits( 12 )
4 + 3 + 2 + sumDigits( 1 )
4 + 3 + 2 + 1
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

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

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

Алгоритмизация и программирование, язык C++, 10 класс
120
Алгоритм Евклида
Алгоритм Евклида. Чтобы найти НОД двух натуральных
чисел, нужно вычитать из большего числа меньшее до
тех пор, пока меньшее не станет равно нулю. Тогда
второе число и есть НОД исходных чисел.
int NOD ( int a, int b )
{
if ( a == 0 || b == 0 )
условие окончания
рекурсии
return a + b;
if ( a > b )
return NOD( a - b, b );
else return NOD( a, b – a );
}
К.Ю. Поляков, Е.А. Ерёмин, 2018
рекурсивные вызовы
http://kpolyakov.spb.ru

121. Задачи

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

122. Задачи

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

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

Алгоритмизация и программирование, язык C++, 10 класс
123
Как работает рекурсия?
Факториал:
1, N 1
N!
N ( N 1)!, N 1
int Fact( int N )
-> N = 3
{
-> N = 2
int F;
-> N = 1
<- N = 1
cout << "-> N=" << N << endl;
<- N = 2
if ( N <= 1 )
<- N = 3
F = 1;
else F = N * Fact(N - 1);
cout << "<- N=" << N << endl;
return F;
}
Как сохранить состояние функции перед
рекурсивным вызовом?
?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

124. Стек

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

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

Алгоритмизация и программирование, язык C++, 10 класс
125
Рекурсия – «за» и «против»
• с каждым новым вызовом расходуется память в стеке
(возможно переполнение стека)
• затраты на выполнение служебных операций при
рекурсивном вызове
программа становится более короткой и понятной
!
возможно переполнение стека
замедление работы
int Fact( int N )
{
Любой рекурсивный
int F;
алгоритм можно заменить
F = 1;
нерекурсивным!
for(i = 2;i <= N;i++)
F = F * i;
итерационный
return F;
алгоритм
}
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык C++, 10 класс
126
Анализ рекурсивных функций
Задача. Определите f(5).
int f( int x ) {
1, x 3
f ( x)
if( x < 3 )
return 1;
f ( x 1) 2,
else
return 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)
x 3
линейная
структура
f (2)
http://kpolyakov.spb.ru

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

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

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

Алгоритмизация и программирование, язык C++, 10 класс
128
Анализ рекурсивных функций
Чему равно 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

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

Алгоритмизация и программирование, язык C++, 10 класс
129
Анализ рекурсивных функций
Задача. Сколько звёздочек выводится при вызове f(11)?
void g( int x ); // объявление функции
void f( int x ) {
if( x > 0 ) g( x-1 );
тут g(x) должна
}
быть известна!
void g( int x ) {
cout << '*';
if( x > 1 ) f( x-3 );
}
f (11)
g(10)
Ответ: 3
*
К.Ю. Поляков, Е.А. Ерёмин, 2018
f (7)
g(6)
*
f (3)
g(2)
f (-1)
*
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык C++, 10 класс
130
Анализ рекурсивных функций
Задача. Сколько звёздочек выводится при вызове f(9)?
void g( int x ); // объявление функции
void f( int x ) {
if( x > 0 ) {
g( x-1 );
f( x-2 );
1, x 0
f ( x)
}
g ( x 1) f ( x 2) 1, x 0
cout << '*';
}
void g( int x ) {
cout << '*';
if( x > 1 ) f( x-3 );
1, x 1
g ( x)
}
1 f ( x 3), x 1
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык C++, 10 класс
131
Анализ рекурсивных функций
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

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

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

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

Алгоритмизация и программирование, язык C++, 10 класс
133
Источники иллюстраций
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     Русский Rules