1 Программирование на языке Python § 54. Алгоритм и его свойства § 55. Простейшие программы § 56. Вычисления § 57. Ветвления § 58. Циклические алгоритмы § 59. Процедуры § 60. Функции § 61. Рекурсия
§ 54. Алгоритм и его свойства 2
3 Мухаммед ал-Хорезми (ок. 783–ок. 850 гг.) Алгоритм — это точное описание порядка действий, которые должен выполнить исполнитель для решения задачи за конечное время. Исполнитель – это устройство или одушёвленное существо (человек), способное понять и выполнить команды, составляющие алгоритм. Формальные исполнители : не понимают (и не могут понять) смысл команд.
4 Дискретность — алгоритм состоит из отдельных команд, каждая из которых выполняется за конечное время. Детерминированность ( определённость ) — при каждом запуске алгоритма с одними и теми же исходными данными получается один и тот же результат. Понятность — алгоритм содержит только команды, входящие в систему команд исполнителя. Конечность (результативность) — для корректного набора данных алгоритм должен завершаться через конечное время. Корректность — для допустимых исходных данных алгоритм должен приводить к правильному результату.
5 дискретный объект 1 2 3 4 алгоритм шаг 1 шаг 2 шаг 3 2 3 4 5 5 4 3 2 дискретный объект 25 16 9 4 получает на вход дискретный объект в результате строит другой дискретный объект (или выдаёт сообщение об ошибке) обрабатывает объект по шагам на каждом шаге получается новый дискретный объект
6 естественный язык псевдокод установить соединение пока не принята команда «стоп» принять команду выполнить команду завершить сеанс связи установить соединение начало цикла принять команду выполнить команду конец цикла при команда = 'stop' завершить сеанс связи
7 блок-схема установитьСоединение начало цикла cmd := получитьКоманду выполнитьКоманду ( cmd ) конец при cmd = 'stop' закрытьСоединение программа принять команду установить соединение завершить соединение выполнить команду «стоп»? да нет
§ 55. Простейшие программы 8
9 # Это пустая программа Что делает эта программа ? ? комментарии после # не обрабатываются # -*- coding: utf-8 -*- # Это пустая программа кодировка utf-8 по умолчанию) Windows: cp 1251 """ Это тоже комментарий """
10 print ( "2+2=?" ) print ( " Ответ : 4" ) Протокол: 2+2=? Ответ: 4 автоматический переход на новую строку print ( '2+2=?' ) print ( ' Ответ : 4' )
11 « B »: Вывести на экран текст «лесенкой» Вася пошел гулять « C »: Вывести на экран рисунок из букв Ж ЖЖЖ ЖЖЖЖЖ ЖЖЖЖЖЖЖ HH HH ZZZZZ
12 Задача. Ввести с клавиатуры два числа и найти их сумму. Протокол: Введите два целых числа 25 30 25+30=55 компьютер пользователь компьютер считает сам! Как ввести числа в память? Где хранить введенные числа ? Как вычислить? Как вывести результат? ?
13 ввести два числа вычислить их сумму вывести сумму на экран Псевдокод – алгоритм на русском языке с элементами языка программирования. Компьютер не может исполнить псевдокод! !
14 Переменная – это величина, имеющая имя, тип и значение. Значение переменной можно изменять во время работы программы. a Значение Имя
15 МОЖНО использовать латинские буквы ( A-Z, a-z) русские буквы ( не рекомендуется! ) цифры знак подчеркивания _ заглавные и строчные буквы различаются НЕЛЬЗЯ использовать скобки знаки +, =, !, ? и др. имя не может начинаться с цифры Какие имена правильные? AXby R&B 4Wheel Вася “PesBarbos” TU154 [QuQu] _ABBA A+B
16 a = 4 print ( type ( a ) ) <class 'int'> целое число ( integer ) a = 4.5 print ( type ( a ) ) <class ' floa t'> вещественное число a = "Вася" print ( type ( a ) ) <class ' str '> символьная строка a = True print ( type ( a ) ) <class ' bool '> логическая
17 Тип определяет: область допустимых значений допустимые операции объём памяти формат хранения данных
18 a = 5 оператор присваивания При записи нового значения старое удаляется из памяти! ! 5 Оператор – это команда языка программирования (инструкция). Оператор присваивания – это команда для записи нового значения переменной. a a = 7 7
19 Программа ждет, пока пользователь введет значение и нажмет Enter. Введенное значение записывается в переменную a (связывается с именем a ) ! 5 a
20 a = input () ввести строку с клавиатуры и связать с переменной a b = input () с = a + b print ( c ) Протокол: 21 33 2133 Почему? ? Результат функции input – строка символов! ! a = int ( input () ) b = int ( input () ) преобразовать в целое число
21 a, b = map ( int, input (). split () ) input () ввести строку с клавиатуры 21 33 input (). split () 21 33 разделить строку на части по пробелам map ( int, input (). split () ) 21 33 целые применить эту операцию к каждой части a, b = map ( int, input (). split () )
22 a = input ( "Введите число: " ) подсказка Введите число: 26 Что не так? ? a = int ( input ( "Введите число: " ) )
23 a = 5 b = a + 2 a = (a + 2 )*(b – 3 ) b = b + 1 a 5 b = 5+2 7 28 = (5+2)*(7-3) = 7+1 8
24 print ( a ) значение переменной print ( "Ответ: ", a ) значение и текст перечисление через запятую print ( "Ответ: ", a+b ) вычисление выражения print ( a, "+", b, "=", c ) 2 + 3 = 5 через пробелы print ( a, "+", b, "=", c, sep = "" ) 2+3=5 sep = "" убрать разделители
25 a = int ( input () ) b = int ( input () ) c = a + b print ( c ) Что плохо? ?
p rint ( "Введите два числа: " ) a = int ( input () ) b = int ( input () ) c = a + b print ( a, "+", b, "=", c ) Сложение чисел: полное решение 26 Протокол: Введите два целых числа 25 30 25 + 30 = 55 компьютер пользователь подсказка
27 a = 123 print ( "{:5d}". format (a) ) 5 знаков 123 5 a = 5 print ( "{:5d}{:5d}{:5d}". format (a, a*a, a*a*a) ) целое 5 знаков 5 5 знаков 2 5 5 знаков 12 5
§ 56. Вычисления 28
29 int # целое float # вещественное bool # логические значения str # символьная строка a = 5 print ( type (a) ) a = 4.5 print ( type (a) ) a = True print ( type (a) ) a = " Вася " print ( type (a) ) <class 'int'> <class 'float'> <class 'bool'> <class 'str'>
30 a = (c + b ** 5 * 3 - 1 ) / 2 * d Приоритет ( старшинство ): скобки возведение в степень ** умножение и деление сложение и вычитание 1 2 3 4 5 6 a = (c + b * 5 * 3 - 1 ) \ / 2 * d \ перенос на следующую строку a = (c + b * 5 * 3 - 1 ) / 2 * d перенос внутри скобок разрешён
31 Классическое деление: a = 9 ; b = 6 x = 3 / 4 # = 0.75 x = a / b # = 1.5 x = -3 / 4 # = - 0.75 x = - a / b # = - 1.5 Целочисленное деление ( округление «вниз»! ) : a = 9 ; b = 6 x = 3 / / 4 # = 0 x = a // b # = 1 x = -3 / / 4 # = -1 x = - a // b # = -2
32 % – остаток от деления d = 85 b = d // 10 # 8 a = d % 10 # 5 d = a % b # 5 d = b % a # 3 Для отрицательных чисел : a = -7 b = a // 2 # -4 d = a % 2 # 1 Как в математике! ! -7 = ( -4 )*2 + 1 остаток 0
33 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 a %= b # a = a % b a += 1 увеличение на 1
34 Целая и дробная части числа разделяются точкой ! ! Форматы вывода : x = 123.456 print ( x ) print ( "{:10.2f}". format (x)) 123.456 всего знаков 123.46 в дробной части print ( "{:10.2g}". format (x)) значащих цифр 1.2e+02 1,2 10 2
35 Экспоненциальный формат : x = 1. / 30000 print ( "{:e}". format (x)) x = 12345678. print ( "{:e}". format (x)) 3.333333e - 0 5 1.234568e+07 3,333333 10 –5 x = 123.456 print ( "{:e}". format ( x)) print ( "{:10.2e}". format ( x)) 1.234560 e +02 1.23e+02 1,234568 10 7 всего знаков в дробной части
36 abs (x) — модуль числа int (x) — преобразование к целому числу round (x) — округление math.pi — число «пи» math. sqrt ( x ) — квадратный корень math. sin ( x ) — синус угла, заданного в радианах math. cos ( x ) — косинус угла, заданного в радианах math. exp ( x ) — экспонента е х math. ln ( x ) — натуральный логарифм math.floor ( x ) — округление «вниз» math.ceil ( x ) — округление «вверх» import math подключить математический модуль x = math.floor ( 1.6 ) # 1 x = math.ceil ( 1.6 ) # 2 x = math.floor (- 1.6 ) #-2 x = math.ceil (- 1.6 ) #-1
37 Случайно… встретить друга на улице разбить тарелку найти 10 рублей выиграть в лотерею Случайный выбор : жеребьевка на соревнованиях выигравшие номера в лотерее Как получить случайность?
38 Электронный генератор нужно специальное устройство нельзя воспроизвести результаты 318458191041 564321 209938992481 458191 938992 малый период (последовательность повторяется через 10 6 чисел) Метод середины квадрата (Дж. фон Нейман) в квадрате Псевдослучайные числа – обладают свойствами случайных чисел, но каждое следующее число вычисляется по заданной формуле. зерно
39 X = ( a*X+b) % c | интервал от 0 до c-1 X = ( X+ 3 ) % 10 | интервал от 0 до 9 X = 0 зерно 3 6 9 2 5 8 0 зацикливание 8 1 4 7 Важен правильный выбор параметров a, b и с ! ! Компилятор GCC : a = 1103515245 b = 12345 c = 2 31
40 Генератор на [0,1) : X = r a ndom.r a ndom () # псевдослучайное число Y = r a ndom.r a ndom () # это уже другое число! англ. random – случайный Целые числа на отрезке [a,b] : X = r a ndom. randint ( 1, 6 ) # псевдосл. число Y = r a ndom. randint ( 1, 6 ) # уже другое! import random
41 Генератор на [0,1) : X = r a ndom () ; # псевдослучайное число Y = r a ndom () # это уже другое число! Целые числа на отрезке [a,b] : X = randint ( 10, 60 ) # псевдослучайное число Y = randint ( 10, 60 ) # это уже другое число! from random import * англ. random – случайный подключить все!
42 « 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
43 « C »: Получить случайное трехзначное число и вывести через запятую его отдельные цифры. Пример : Получено число 123. Его цифры 1, 2, 3.
§ 57. Ветвления 44
45 Задача: изменить порядок действий в зависимости от выполнения некоторого условия. M = a a > b? M = b да нет вывод M полная форма ветвления Если a = b? ? if a > b: M = a else : M = b отступы
46 M = b b > a? да нет вывод M M = a неполная форма ветвления M = a if b > a: M = b M = max (a, b) Решение в стиле Python: M = a if a > b else b
47 if a > b: с = a a = b b = c Что делает ? ? 4 6 ? 4 6 4 a b 3 2 1 Можно ли обойтись без переменной c ? ? c a, b = b, a Решение в стиле Python:
48 > < > = < = = = != больше, меньше больше или равно меньше или равно равно не равно
49 if a > b: print ( " Андрей старше " ) else : if a == b: print ( " Одного возраста " ) else : print ( " Борис старше " ) вложенный условный оператор Зачем нужен ? ? Задача : в переменных a и b записаны возрасты Андрея и Бориса. Кто из них старше? Сколько вариантов ? ?
50 if a > b: print ( " Андрей старше " ) elif a == b: print ( " Одного возраста " ) else : print ( " Борис старше " ) elif = else if !
51 cost = 1500 if cost < 1000 : print ( " Скидок нет." ) elif cost < 2000 : print ( " Скидка 2%." ) elif cost < 5000 : print ( " Скидка 5%." ) else : print ( "Скидка 10%. " ) Что выведет ? ? первое сработавшее условие Скидка 2%.
52 « A »: Ввести три целых числа, найти максимальное из них. Пример : Введите три целых числа: 1 5 4 Максимальное число 5 « B »: Ввести пять целых чисел, найти максимальное из них. Пример : Введите пять целых чисел: 1 5 4 3 2 Максимальное число 5
53 « C »: Ввести последовательно возраст Антона, Бориса и Виктора. Определить, кто из них старше. Пример : Возраст Антона: 15 Возраст Бориса: 17 Возраст Виктора: 16 Ответ: Борис старше всех. Пример : Возраст Антона: 17 Возраст Бориса: 17 Возраст Виктора: 16 Ответ: Антон и Борис старше Виктора.
54 Задача : набор сотрудников в возрасте 25-40 лет (включительно). if : print ( "подходит" ) else : print ( "не подходит " ) and or not Приоритет : отношения ( <, >, <=, >=, ==, != ) not («НЕ») and («И») or («ИЛИ») v >= 25 and v <= 40 сложное условие «И» «ИЛИ» «НЕ»
55 « A »: Напишите программу, которая получает три числа и выводит количество одинаковых чисел в этой цепочке. Пример : Введите три числа: 5 5 5 Все числа одинаковые. Пример : Введите три числа: 5 7 5 Два числа одинаковые. Пример : Введите три числа: 5 7 8 Нет одинаковых чисел.
56 « B »: Напишите программу, которая получает номер месяца и выводит соответствующее ему время года или сообщение об ошибке. Пример : Введите номер месяца: 5 Весна. Пример : Введите номер месяца: 15 Неверный номер месяца.
57 « C »: Напишите программу, которая получает возраст человека (целое число, не превышающее 120) и выводит этот возраст со словом «год», «года» или «лет». Например, «21 год», «22 года», «25 лет». Пример : Введите возраст: 18 Вам 18 лет. Пример : Введите возраст: 21 Вам 21 год. Пример : Введите возраст: 2 2 Вам 22 года.
58 « A »: Напишите условие, которое определяет заштрихованную область. « B »: Напишите условие, которое определяет заштрихованную область.
59 « C »: Напишите условие, которое определяет заштрихованную область.
§ 58. Циклические алгоритмы 60
61 Цикл – это многократное выполнение одинаковых действий. Два вида циклов : цикл с известным числом шагов ( сделать 10 раз ) цикл с неизвестным числом шагов (делать, пока не надоест) Задача. Вывести на экран 10 раз слово «Привет». Можно ли решить известными методами ? ?
62 print ( " Привет “ ) print ( " Привет " ) ... print ( " Привет " ) Что плохо ? ?
63 начало конец да нет тело цикла сделали 10 раз ? print ( "Привет!" )
64 счётчик = 0 пока счётчик < 10 : print ( " Привет “ ) увеличить счётчик на 1 счётчик = 10 пока счётчик > 0 : print ( " Привет " ) уменьшить счётчик на 1 Какой способ удобнее для процессора ? ? результат операции автоматически сравнивается с нулём!
65 Задача. Определить количество цифр в десятичной записи целого положительного числа, записанного в переменную n. счётчик = 0 пока n > 0 : отсечь последнюю цифру n увеличить счётчик на 1 n счётчик 1234 0 123 1 12 2 1 3 0 4 Как отсечь последнюю цифру ? ? n = n // 10 Как увеличить счётчик на 1 ? ? счётчик = счётчик + 1 счётчик + = 1
66 count = 0 while : n = n // 10 count += 1 тело цикла начальное значение счётчика n > 0 условие продолжения заголовок цикла Цикл с предусловием – проверка на входе в цикл! !
67 k = 0 while k < 10 : print ( " привет " ) k += 1 При известном количестве шагов: k = 0 while k < 10 : print ( " привет " ) Зацикливание:
68 a = 4 ; b = 6 while a < b: a += 1 2 раза a = 6 a = 4 ; b = 6 while a < b: a += b 1 раз a = 10 a = 4 ; b = 6 while a > b: a += 1 0 раз a = 4 a = 4 ; b = 6 while a < b: b = a - b 1 раз b = -2 a = 4 ; b = 6 while a < b: a -= 1 зацикливание
69 while True : if n > 0 : break условие выхода print ( "Введите положительное число:" ) n = int ( input () ) тело цикла при входе в цикл условие не проверяется цикл всегда выполняется хотя бы один раз Задача. Обеспечить ввод положительного числа в переменную n. бесконечный цикл прервать цикл
70 « 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
71 « C »: Ввести натуральное число N и вычислить сумму всех чисел Фибоначчи, меньших N. Предусмотрите защиту от ввода отрицательного числа N. Пример : Введите число N: 10000 Сумма 17709
72 « A »: Ввести натуральное число и найти сумму его цифр. Пример : Введите натуральное число: 12345 Сумма цифр 15. « B »: Ввести натуральное число и определить, верно ли, что в его записи есть две одинаковые цифры, стоящие рядом. Пример : Введите натуральное число: 12342 Нет. Пример : Введите натуральное число: 12 2 4 5 Да.
73 « C »: Ввести натуральное число и определить, верно ли, что в его записи есть две одинаковые цифры (не обязательно стоящие рядом). Пример : Введите натуральное число: 12342 Да. Пример : Введите натуральное число: 1234 5 Нет.
74 Задача. Вывести 10 раз слово «Привет!». Можно ли сделать с циклом «пока» ? ? while : print ( " Привет!" ) i = 0 i < 10 i + = 1 for : print ( " Привет! " ) i in range ( 10 ) в диапазоне [0, 10 ) Цикл с переменной: Не включая 10 ! ! range ( 10 ) 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
75 Задача. Вывести все степени двойки от 2 1 до 2 10. Как сделать с циклом «пока» ? ? while : print ( 2 **k ) k = 1 k <= 10 k + = 1 for : print ( 2 **k ) k in range ( 1, 11 ) в диапазоне [ 1, 11 ) Цикл с переменной: Не включая 1 1 ! ! range ( 1, 11 ) 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
76 10 0 81 64 49 36 25 16 9 4 1 Что получится ? ? 1 9 25 49 81 for : print ( k** 2 ) k in range ( 1, 11, 2 ) for : print ( k** 2 ) k in range ( 10, 0, -1 ) шаг 10, 9,8,7,6,5,4,3,2,1 1,3,5,7,9
77 a = 1 for i in range ( 3 ): a += 1 a = 4 a = 1 for i in range ( 3, 1 ): a += 1 a = 1 a = 1 for i in range ( 1, 3, -1 ): a += 1 a = 1 a = 1 for i in range ( 3, 1, -1 ): a += 1 a = 3
78 « A »: Найдите все пятизначные числа, которые при делении на 133 дают в остатке 125, а при делении на 134 дают в остатке 111. « B »: Натуральное число называется числом Армстронга, если сумма цифр числа, возведенных в N-ную степень (где N – количество цифр в числе) равна самому числу. Например, 153 = 1 3 + 5 3 + 3 3. Найдите все трёхзначные Армстронга.
79 «С»: Натуральное число называется автоморфным, если оно равно последним цифрам своего квадрата. Например, 25 2 = 6 25. Напишите программу, которая получает натуральное число N и выводит на экран все автоморфные числа, не превосходящие N. Пример : Введите N: 1000 1*1=1 5*5=25 6*6=36 25*25=625 76*76=5776
80 Задача. Вывести все простые числа в диапазоне от 2 до 1000. сделать для n от 2 до 1000 если число n простое то вывод n число n простое нет делителей [ 2.. n -1 ] : проверка в цикле! Что значит «простое число» ? ? for n in range ( 2, 100 1 ): if число n простое : print ( n )
81 for n in range( 2, 100 1 ) : count = 0 if count == 0 : print ( n ) for k in range ( 2,n): if n % k == 0 : count += 1 вложенный цикл
82 for i in range( 1, 4 ): for k in range( 1, 4 ): print ( i, k ) Как меняются переменные? ? 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3 Переменная внутреннего цикла изменяется быстрее! !
83 for i in range( 1, 5 ): for k in range( 1,i+1): print ( i, k ) Как меняются переменные? ? 1 1 2 1 2 2 3 1 3 2 3 3 4 1 4 2 4 3 4 4 Переменная внутреннего цикла изменяется быстрее! !
84 count = 0 k = 2 while : if n % k == 0 : count += 1 k += 1 while k <= math. sqrt ( n ): … Что плохо? ? while k*k <= n: if n % k == 0 : break k += 1 if k * k > n : print ( n ) k*k <= n Как ещё улучшить? ? выйти из цикла если вышли по условию
85 « A »: Напишите программу, которая получает натуральные числа A и B (A<B) и выводит все простые числа в интервале от A до B. Пример : Введите границы диапазона: 10 20 11 13 17 19 « B »: В магазине продается мастика в ящиках по 15 кг, 17 кг, 21 кг. Как купить ровно 185 кг мастики, не вскрывая ящики? Сколькими способами можно это сделать?
86 « C »: Ввести натуральное число N и вывести все натуральные числа, не превосходящие N и делящиеся на каждую из своих цифр. Пример : Введите N: 15 1 2 3 4 5 6 7 8 9 11 12 15
§ 59. Процедуры 87
88 print ( "Ошибка программы" ) много раз! def Error(): print ( "Ошибка программы" ) n = int ( input () ) if n < 0 : Error() вызов процедуры Процедура: define определить
89 Процедура – вспомогательный алгоритм, который выполняет некоторые действия. текст (расшифровка) процедуры записывается до её вызова в основной программе в программе может быть много процедур чтобы процедура заработала, нужно вызвать её по имени из основной программы или из другой процедуры
90 Задача. Вывести на экран запись целого числа (0..255) в 8-битном двоичном коде. много раз! Алгоритм: 178 10110010 2 Как вывести первую цифру ? ? 7 6 5 4 3 2 1 0 1 0 1 1 0 0 1 0 2 разряды n := n / / 128 n % 128 Как вывести вторую цифру ? ? n 1 // 64
91 Задача. Вывести на экран запись целого числа (0..255) в 8-битном двоичном коде. Решение: k = 128 while k > 0 : print ( n // k, end = "" ) n = n % k k = k // 2 n k вывод 178 128 1 50 64 0 50 32 1 18 16 1 2 8 0 2 4 0 2 2 1 0 1 0 0 0 178 10110010 Результат зависит от n ! !
92 printBin ( 99 ) значение параметра ( аргумент ) def printBin ( n ): k = 128 while k > 0 : print ( n // k, end = "" ) n = n % k ; k = k // 2 Параметры – данные, изменяющие работу процедуры. локальная переменная def printSred ( a, b ): print ( ( a + b )/ 2 ) Несколько параметров:
93 a = 5 def qq (): a = 1 print ( a ) qq () print ( a ) глобальная переменная локальная переменная 1 5 a = 5 def qq (): print ( a ) qq () 5 a = 5 def qq (): global a a = 1 qq () print ( a ) 1 global a работаем с глобальной переменной
94 x = 5 ; y = 10 def sum (): print ( x+y ) sum () Что плохо ? ? def sum (): print ( x+y ) процедура связана с глобальными переменными, нельзя перенести в другую программу печатает только сумму x и y, нельзя напечатать сумму других переменных или сумму x*y и 3x Как исправить ? ? передавать данные через параметры
95 x = 5 ; y = 10 sum ( x, y ) z= 1 7 ; w= 3 sum( z, w ) sum( z+x, y*w ) def sum ( a, b ): print ( a+b ) a b x 5 y 10 12 3 z w 5 10 1 7 3 22 3 0 15 20 52 Глобальные: Локальные: процедура не зависит от глобальных переменных легко перенести в другую программу печатает только сумму любых выражений
96 « A »: Напишите процедуру, которая принимает параметр – натуральное число N – и выводит на экран линию из N символов '–'. Пример : Введите N: 10 ---------- « B »: Напишите процедуру, которая выводит на экран в столбик все цифры переданного ей числа, начиная с первой. Пример : Введите натуральное число: 1234 1 2 3 4
97 « C »: Напишите процедуру, которая выводит на экран запись переданного ей числа в римской системе счисления. Пример : Введите натуральное число: 2013 MMXIII
§ 60. Функции 98
99 Функция – это вспомогательный алгоритм, который возвращает значение-результат (число, символ или объект другого типа). Задача. Написать функцию, которая вычисляет сумму цифр числа. Алгоритм: сумма = 0 пока n != 0 : сумма += n % 10 n = n // 10
100 # основная программа print ( sumDigits( 12345 ) ) def sumDigits ( n ): s um = 0 while n!= 0 : sum += n % 10 n = n // 10 return sum return sum передача результата
101 x = 2 *sumDigits(n+ 5 ) z = sumDigits(k) + sumDigits(m) if sumDigits(n) % 2 == 0 : print ( " Сумма цифр чётная " ) print ( " Она равна ", sumDigits(n) ) Функция, возвращающая целое число, может использоваться везде, где и целая величина! ! Одна функция вызывает другую: def middle ( a, b, c ): mi = min ( a, b, c ) ma = max ( a, b, c ) return a + b + c - mi - ma вызываются min и max Что вычисляет? ?
102 « A »: Напишите функцию, которая находит наибольший общий делитель двух натуральных чисел. Пример : Введите два натуральных числа: 7006652 112307574 НОД(7006652,112307574) = 1234. « B »: Напишите функцию, которая определяет сумму цифр переданного ей числа. Пример : Введите натуральное число: 123 Сумма цифр числа 123 равна 6.
103 « C »: Напишите функцию, которая «переворачивает» число, то есть возвращает число, в котором цифры стоят в обратном порядке. Пример : Введите натуральное число: 1234 После переворота: 4321.
104 def divmod ( x, y ): d = x // y m = x % y return d, m d – частное, m – остаток a, b = divmod ( 7, 3 ) print ( a, b ) # 2 1 q = divmod ( 7, 3 ) print ( q ) # ( 2, 1 ) ( 2, 1 ) кортеж – набор элементов
105 « A »: Напишите функцию, которая переставляет три переданные ей числа в порядке возрастания. Пример : Введите три натуральных числа: 10 15 5 5 10 15 « B »: Напишите функцию, которая сокращает дробь вида M/N. Пример : Введите числитель и знаменатель дроби: 25 15 После сокращения: 5/3
106 « C »: Напишите функцию, которая вычисляет наибольший общий делитель и наименьшее общее кратное двух натуральных чисел. Пример : Введите два натуральных числа: 10 15 НОД(10,15)=5 НОК(10,15)=30
107 Задача. Найти все простые числа в диапазоне от 2 до 100. for i in range ( 2, 10 0 1 ): if i - простое : print ( i ) i - простое isPrime ( i ) функция, возвращающая логическое значение ( True / False )
108 Какой алгоритм? ? def isPrime ( n ): k = 2 while k*k <= n and n % k != 0 : k += 1 return (k*k > n) return (k*k > n) if k*k > n: return True else : return False
109 n = int ( input () ) while isPrime(n): print ( n, "– простое число" ) n = int ( input () ) Функция, возвращающая логическое значение, может использоваться везде, где и логическая величина! !
110 « A »: Напишите логическую функцию, которая определяет, является ли переданное ей число совершенным, то есть, равно ли оно сумме своих делителей, меньших его самого. Пример : Введите натуральное число: 28 Число 28 совершенное. Пример : Введите натуральное число: 2 9 Число 2 9 не совершенное.
111 « B »: Напишите логическую функцию, которая определяет, являются ли два переданные ей числа взаимно простыми, то есть, не имеющими общих делителей, кроме 1. Пример : Введите два натуральных числа: 28 15 Числа 28 и 15 взаимно простые. Пример : Введите два натуральных числа: 28 1 6 Числа 28 и 1 6 не взаимно простые.
112 «С»: Простое число называется гиперпростым, если любое число, получающееся из него откидыванием нескольких цифр, тоже является простым. Например, число 733 – гиперпростое, так как и оно само, и числа 73 и 7 – простые. Напишите логическую функцию, которая определяет, верно ли, что переданное ей число – гиперпростое. Используйте уже готовую функцию isPrime, которая приведена в учебнике. Пример : Введите натуральное число: 733 Число 733 гиперпростое. Пример : Введите натуральное число: 19 Число 19 не гиперпростое.
§ 61. Рекурсия 113
114 У попа была собака, он её любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал: У попа была собака, он её любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал: …
115 Натуральные числа : 1 – натуральное число если – натуральное число, то – натуральное число индуктивное определение Рекурсия — это способ определения множества объектов через само это множество на основе заданных простых базовых случаев. Числа Фибоначчи : при 1, 1, 2, 3, 5, 8, 13, 21, 34, …
116 Фракталы – геометрические фигуры, обладающие самоподобием. Треугольник Серпинского:
117 1 2 3 за один раз переносится один диск класть только меньший диск на больший третий стержень вспомогательный перенести (n- 1, 1, 2 ) 1 -> 3 перенести (n- 1, 2, 3 ) перенести ( n, 1, 3 )
118 def Hanoi ( n, k, m ): p = 6 - k - m Hanoi ( n- 1, k, p ) print ( k, "->", m ) Hanoi ( n- 1, p, m ) номер вспомогательного стержня (1+2+3=6!) сколько откуда куда Что плохо? ? Рекурсия никогда не остановится! ! рекурсия рекурсия
119 Рекурсивная процедура (функция) — это процедура (функция), которая вызывает сама себя напрямую или через другие процедуры и функции. def Hanoi ( n, k, m ): p = 6 - k - m Hanoi ( n- 1, k, p ) print ( k, "->", m ) Hanoi ( n- 1, p, m ) if n == 0 : return условие выхода из рекурсии # основная программа Hanoi ( 4, 1, 3 )
120 def printBin ( n ): if n == 0 : return printBin ( n // 2 ) print ( n % 2, end = "" ) условие выхода из рекурсии напечатать все цифры, кроме последней вывести последнюю цифру 10011 printBin ( 19 ) printBin ( 9 ) printBin ( 4 ) printBin ( 2 ) printBin ( 1 ) printBin ( 0 ) Как без рекурсии? ?
121 def sumDig ( n ): sum = n % 10 if n >= 10 : sum += sumDig ( n // 10 ) return sum Где условие окончания рекурсии? ? рекурсивный вызов sumDig ( 1234 ) 4 + sumDig ( 123 ) 4 + 3 + sumDig ( 12 ) 4 + 3 + 2 + sumDig ( 1 ) 4 + 3 + 2 + 1 последняя цифра
122 Алгоритм Евклида. Чтобы найти НОД двух натуральных чисел, нужно вычитать из большего числа меньшее до тех пор, пока меньшее не станет равно нулю. Тогда второе число и есть НОД исходных чисел. def NOD ( a, b ): if a == 0 or b == 0 : if a > b: return NOD( a - b, b ) else : return NOD( a, b – a ) return a + b ; рекурсивные вызовы условие окончания рекурсии
123 « A »: Напишите рекурсивную функцию, которая вычисляет НОД двух натуральных чисел, используя модифицированный алгоритм Евклида. Пример : Введите два натуральных числа: 7006652 112307574 НОД(7006652,112307574)=1234. « B »: Напишите рекурсивную функцию, которая раскладывает число на простые сомножители. Пример : Введите натуральное число: 378 378 = 2*3*3*3*7
124 « C »: Дано натуральное число N. Требуется получить и вывести на экран количество всех возможных различных способов представления этого числа в виде суммы натуральных чисел (то есть, 1 + 2 и 2 + 1 – это один и тот же способ разложения числа 3). Решите задачу с помощью рекурсивной процедуры. Пример : Введите натуральное число: 4 Количество разложений: 4.
125 def Fact(N): print ( "->", N ) if N <= 1 : F = 1 else : F = N * Fact ( N – 1 ) print ( "<-", N ) return F -> N = 3 -> N = 2 -> N = 1 <- N = 1 <- N = 2 <- N = 3 Как сохранить состояние функции перед рекурсивным вызовом? ? Факториал:
126 Стек – область памяти, в которой хранятся локальные переменные и адреса возврата. SP SP 3 A F SP 3 A F 2 A F F 3 A F 2 A F F 1 A F F SP Fact(3) Fact( 2 ) Fact(1) значение параметра адрес возврата локальная переменная
127 с каждым новым вызовом расходуется память в стеке (возможно переполнение стека) затраты на выполнение служебных операций при рекурсивном вызове программа становится более короткой и понятной возможно переполнение стека замедление работы Любой рекурсивный алгоритм можно заменить нерекурсивным ! ! def Fact ( n ): f = 1 for i in range ( 2,n+ 1 ): f *= i return f итерационный алгоритм
128 Конец фильма ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики ГБОУ СОШ № 163, г. Санкт-Петербург kpolyakov@mail.ru ЕРЕМИН Евгений Александрович к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО ПГГПУ, г. Пермь eremin@pspu.ac.ru
129 old-moneta.ru www.random.org www.allruletka.ru www.lotterypros.com logos.cs.uic.edu ru.wikipedia.org иллюстрации художников издательства «Бином» авторские материалы
