Лекция 5. Язык Питон-базовые структуры. Итерационный цикл (Воробьева И.А. «Информатика. Язык Питон» (2016))

1Воробьева И.А. «Информатика. Язык Питон»Запись алгоритмов на языке программированияЯзык программирования Python. Структура программы. Концепция данных.Основные операторы. Приоритеты операций. Переход к записи алгоритма наалгоритмическом языке. Моделирование базовых управляющих структур.Итерационные циклы и рекуррентные вычисления.4. ЗАПИСЬ АЛГОРИТМОВ НА ЯЗЫКЕПРОГРАММИРОВАНИЯ4.5. Переход к записи алгоритма на алгоритмическом языке.Моделирование базовых управляющих структурЯзык программирования - язык, используемый для формальной записиалгоритмов.Большинствоязыковпрограммированияотносятсякалгоритмическим языкам.Запись алгоритма на алгоритмическом языке называют программой.Мы уже знаем базовые операции алгоритмов: следование, ветвление ицикл (ПОКА), то как они отображаются в блок-схемах (см.

рисунок ниже), а такжеи то, что с помощью только этих трех конструкций можно реализовать алгоритмлюбой сложности.По аналогии с базовыми операциями, можно встретить делениеалгоритмов на: линейные; с разветвлением; циклические.2Воробьева И.А. «Информатика. Язык Питон»Примеры таких алгоритмов представим в следующей таблице:ЛИНЕЙНЫЙС РАЗВЕТВЛЕНИЕМЗадача: найти среднее Задача: найти большеегеометрическоедвух из двух чисел.чисел.началоначаловвод A и Bввод A и B−A>BSr = √ ∗ ЦИКЛИЧЕСКИЙЗадача: найти суммупервых () натуральныхчисел.началоввод NS=0+i=1вывод SrMax = AMax = B−i≤Nконецвывод Max+S=S+iконецi=i+1вывод MaxконецНа самом деле большинство алгоритмов представляют собой смешанныетипы.ВетвлениеРассмотрим основные виды ветвленийпрограммирования Python: ветвление неполной формы; ветвление полной формы; вложенное ветвление.иихзаписьнаязыкПри этом блок-схемы будем давать в формальном виде, а запись на языкепрограммирования сразу с конкретными примерами для наглядности.3Воробьева И.А.

«Информатика. Язык Питон»ветвление неполной формыif n > 1:# ЕСЛИ n > 1, ТОГДАn = n**2 # возведем n в квадратprint (n) # результат на экранветвление полной формыif a > b:# ЕСЛИ > , ТОГДАa = a**2 # возведем в квадратprint (a) # результат на экранelse:# ИНАЧЕb = b/2# разделим на дваprint (b) # результат на экран4Воробьева И.А. «Информатика. Язык Питон»вложенное ветвлениетрадиционная форма записиif a > b: # ЕСЛИ > , ТОГДАprint (‘a > b’)else:# ИНАЧЕif a < b: # ЕСЛИ < , ТОГДАprint (‘a < b’)else: # ИНАЧЕ = print (‘a = b’)сокращенная форма записиif a > b: # ЕСЛИ > , ТОГДАprint (‘a > b’)elif: # ИНАЧЕ−ЕСЛИ < , ТОГДАprint (‘a < b’)else: # ИНАЧЕ = print (‘a = b’)ЦиклыРассмотрим основные виды циклов, применяемых в алгоритмах и языкахпрограммирования: итерационные (с условием):− циклы с предусловием;− циклы с постусловием; параметрические.Цикл – повторение выполнения однотипных действий (тела цикла) спроверкой условия необходимости повторения этих действий.5Воробьева И.А.

«Информатика. Язык Питон»Итерационный цикл – это цикл, в котором заранее не известно числоповторений тела цикла.Параметрический цикл – цикл, в котором заранее известно, сколькоповторений выполнения тела необходимо совершить.Выход из итерационного цикла осуществляется при выполнении заданногоусловия.Цикл с предусловием проверяет условие ДО выполнения тела цикла:1) проверка условия → 2) тело цикла.Цикл с постусловием проверяет условие ПОСЛЕ выполнения цикла:1) шаг цикла → 2)проверка условия..ЦИКЛ С ПРЕДУСЛОВИЕМЦИКЛ С ПОСТУСЛОВИЕМТЕЛО ЦИКЛАПРОВЕРКАУСЛОВИЯНетВЫПОЛНЕНИЯДаТЕЛО ЦИКЛАПРОВЕРКАУСЛОВИЯНетЗАВЕРШЕНИЯДаМожет ни разу не выполнитьсяУсловие = TRUE → выполнитьОдин раз выполнится всегдаУсловие = TRUE → завершить илипродолжить цикл: конструкцияможет быть реализована поразному в разных языках.6Воробьева И.А.

«Информатика. Язык Питон»В языке Python нет специальной команды для реализации цикла спостусловием – ее выполнение всегда можно обеспечить с помощью цикла спредусловием просто гарантировав выполнение первой итерации цикла (иногдаэто бывает необходимо по логике алгоритма).ЦИКЛ С ПРЕДУСЛОВИЕМ в Pythona = 99b = 10i=0while a > b: # ПОКА > ,# ВЫПОЛНЯТЬa = a-1 # уменьшим на «1»b = b+2 # увеличим на «2»i = i+1# после выполнения циклаprint (‘a стало ≤ b через ’, i, ‘шагов’)ЦИКЛ С ПОСТУСЛОВИЕМОбычноимитируютспомощьюбесконечного цикла и выхода поусловию через оператор break (одно издействительно полезных примененийэтогооператора,которыймырассмотрим подробнее в следующихлекциях):while True: # Бесконечный циклтело_циклаif условие_завершения:break # команда прервет циклВ Python нет цикла с постусловием, зато есть любопытная конструкция циклаwhile, которая до сих пор мне не встречалась: в случае, когда условие принимает«отрицательное значение», можно один раз выполнить блок операторов по ветвиelse.

Разумеется, что ветвь else не является обязательной в синтаксисе циклаwhile в Python.Приведем интересный пример программы «угадывание числа» взятый из [1].код программы в Pythonрезультат работы программыnum = 23 # загаданное числоFlg = True # условие повторения цикла введите число: 9нет, загаданное число меньшеa=0# здесь будем угадыватьвведите число: 90нет, загаданное число большеwhile Flg: # ПОКА Flg истинновведите число: 23# ВЫПОЛНЯТЬвы угадали!a = int( input(‘введите число: ’))Сработало один раз, когда условиеif a == num:стало ложным.print(‘вы угадали! ’)можетбытьFlg = False # можно завершать. Операторовнесколько.elif a < num:Программа завершена.print(‘нет, загаданное число7Воробьева И.А. «Информатика.

Язык Питон»больше’)else:print(‘нет, загаданное числоменьше)else:print (‘Сработало один раз, когдаусловие стало ложным.’)print (‘Операторов может бытьнесколько.’)print (‘Программа завершена.’).Обратите внимание, что в конструкциях «if <A> и «while <A>» <A> - может бытьи просто логической переменной и вычисляемым выражением, но результат этоговыражения вновь должен иметь логический тип, то есть принимать значение Trueили False.4.6. Итерационные циклы и рекуррентные вычисления:вычисление тригонометрической функции с помощьюразложения ее в рядРассмотрим ситуацию, когда число итераций цикла нам заранеене известно.

В качестве примера можно взять типичную задачу изчисленных методов по вычислению суммы бесконечного ряда сзаданной точностью. На практике подобная задача возникает,например, при необходимости вычисления интегралов или, приотсутствииматематическихбиблиотек,вычислениятригонометрических функций.8Воробьева И.А. «Информатика. Язык Питон»12Пример 4.1.

«Вычислить интеграл ∫0 − с точностью = 0.01».Известно представление функции в виде ряда Маклорена для :− 24 6 2=1− +− + ⋯ + (−1)+ ⋯ , ∈ ℛ.2! 3!!2Почленное интегрирование ряда от 0 до 1 даст следующую сумму:11∫− 20462 = ∫ (1 − 2 + − + ⋯ + (−1)+ ⋯ ) =2! 3!!0357 2+11= ( − +−+ ⋯ + (−1)+ ⋯)| .3 5 ∙ 2! 7 ∙ 3!(2 + 1) ∙ !0Всего лишь первых четырех членов ряда достаточно, чтобы получитьзаданную точность :1∫ − ≈ 1 − 1⁄3 + 1⁄10 − 1⁄42 ≈ 0.7428620Так как ряд знакочередующийся и убывающий, то модуль всего остаткабесконечной суммы будет меньше пятого члена ряда, который равен1 11∙ =≈ 0.00463 и очевидно меньше = 0.01.9 4!216Особенностью данной задачи является то, что число слагаемых заранеенеизвестно, а суммирование должно завершиться в момент достижениятребуемой точности .Здесь наиболее уместно использовать итерационный цикл: в теле циклабудет происходить суммирование очередного слагаемого, а условиепрекращения цикла – это сравнение очередного слагаемого с точностью .Таким образом, на каждом шаге вычислений в итерационном циклепроисходит последовательное приближение к искомому результату ипроверка условия достижения последнего.9Воробьева И.А.

«Информатика. Язык Питон»Замечание 4.1. Заданное условие окончания итераций цикла можетне достигнуть значения True – истина, например, в суммированиирядов с плохой сходимостью. Поэтому, с точки зрения грамотногопрограммирования, в подобных циклах особенно важно рассмотретьситуации возможного зацикливания (бесконечного выполненияпрограммой тела цикла).Если вы не можете гарантировать заранее выполнение условиявыхода из цикла, достаточно ввести специальную переменную Cnt –счетчик максимально допустимого выполнения циклов.При переполнении этого счетчика:1 зафиксировать ошибку: сообщение; установка так называемого флага ошибки в отдельной выделенной переменной Flg.2 обеспечить выход из цикла: ИЛИ принудительной установкой условия в состояние «истина»; ИЛИ, что гораздо лучше, включив сам счетчик в логическоеусловие окончания цикла.Подобные действия могут потребоваться в режимах отладкипрограммного кода, отладки предложенного метода решения задачии т.п.Вывод рекуррентного соотношенияДля того чтобы вычислить -й член последовательности (слагаемоеили множитель бесконечного ряда) используют так называемыерекуррентные вычисления.Рекуррентная формула (или рекуррентное соотношение) —формула, выражающая каждый член последовательности через предыдущих членов этой последовательности = (, −1 , −2 , .

. , − ).10Воробьева И.А. «Информатика. Язык Питон»Замечание 4.2. Получение рекуррентной формулы далеко не всегдатривиальная задача.Иногда выгодно считать последовательность, начиная с индекса «0»:0 ; 1 ; 2 ; . . . . .. , а не с индекса «1»: 1 ; 2 ; . . . … .Пусть p=1. Рекуррентную формулу могут искать в виде = (1, −1 ) = − ∙ ()(4.1)+ = (1, ) = ∙ ().(4.2)или в видеМы будем искать формулу в виде (4.1), так как исходя из практическогоопыта, в этом случае совершают меньше ошибок при выводе, проверкеформулы и последующем ее кодировании.Рассмотрим вывод рекуррентнойконкретного бесконечного ряда.формулынапримереПример 4.2.

Решение задачи «Вычисление функции разложением еев ряд» (из задачника Котаровой).Известно, что часть функций могут быть представлены в видесуммы бесконечного ряда. Например, вычислить функцию 3 ∙3√1 + − 3 для | | < 1 с заданной точностью – равносильно:вычислить бесконечную сумму рядаS  x  62 x 2  6295 x 3  ...  256...9...3i3i 4  x i  ... (4.3)с точностью для | | < 1 (ряд (4.3) сходится при | | < 1).Обратите внимание, что знаки слагаемых чередуются, а степеньпеременной в числителях возрастает – это означает, что при | | <1 для данной бесконечной суммы требуемая точность будетдостигнута, когда очередное слагаемое станет по абсолютнойвеличине меньше , при этом абсолютная величина суммы всехотброшенных членов ряда тоже оказывается меньше .11Воробьева И.А.

«Информатика. Язык Питон»Рассмотрим формулу (4.3) из задачи. В ней можно вычислитьмножитель 1 () , умножением на который получается слагаемоеi-го шага из слагаемого предыдущего (i-1)-го шага. () зависит от i –номера слагаемого в бесконечной сумме = ∑∞=1 . По формуле (4.1),получаем, что: () = −1= (−1) ∙2∙5…(3(−1)−4)∙(3−4)∙ 6∙9…3∙(−1)∙3∙=6∙9…3∙(−1)2∙5…(3(−1)−4)∙ −1= −3−43.(4.4)3−4Убедимся, что рекурсия = −1 ∗ (−1) ∙ верна.3Выполним проверку для второго и третьего слагаемого (проверкуформулы всегда делают для двух членов ряда минимум, длянадежности):шаг i1i-й член ряда из формулы (4.3)1 = 23∙2−42= − 23∙2623∙3−42∙53 = 2 ∙ 1 (3) = − 2 ∙ (−)= 363∙36∙932 = 1 ∙ 1 (2) = ∙ (−)……В этой таблице дополнительный материал к лекции (не обязательный)Сравнение рекуррентных соотношений, полученных поформулам (4.1) и (4.2)Как уже было сказано, рекуррентное соотношение можнополучить и по формуле (4.2): () = +1 == (−1) ∙2∙5…(3−4)∙(3(+1)−4)∙ +16∙9…3∙6∙9…3∙3(+1)2∙5…(3−4)∙ 3−1= − 3+3 .12Воробьева И.А.