4-B. Подробней о циклических и вспомогательных алгоритмах

Постобработка циклов

Если сразу за телом цикла (for или while) использовать команду else: ,
то за ней с отступом будут расположены команды, обязательные для выполнения, при каждом завершении цикла.
Пример: надо исправить оценку

In [11]:

ball = 3
while ball<6:
  if ball<5:
    print('Оценка',ball,'- надо исправить!')
  ball=ball+1
else:
  print('Оценка исправлена!')
print('Я - отличник!')

Оценка 3 - надо исправить!
Оценка 4 - надо исправить!
Оценка исправлена!
Я - отличник!

Однако, данная программа будет несправедливо работать для ball равным 5

In [12]:

ball = 5
while ball<6:
  if ball<5:
    print('Оценка',ball,'- надо исправить!')
  ball=ball+1
else:
  print('Оценка исправлена!')
print('Я - отличник!')

Оценка исправлена!
Я - отличник!

Оценку "5" исправлять не следует!

Прерывание цикла

В подобной ситуации нам поможет команда break - принудительное прерывание всего цикла, вместе с else :

In [13]:

ball = 5
while ball<6:
  if ball==5: break
  print('Оценка',ball,'- надо исправить!')
  ball=ball+1
else:
  print('Оценка исправлена!')
print('Я - отличник!')

Я - отличник!

Прерывание текущего повторения

Допустим изначально получена оценка "2" или "3". За один раз можно исправить только на один балл,
Но нам не хочется сообщать об исправлении "2" или "3". Для этого будем использовать команду continue 
Все, что написано в теле цикла после нее - будет проигнорировано и выполниться переход к следующему повторению
(если не произойдет завершение цикла)

In [21]:

ball = 2
while ball<6:
  if ball==5: break
  ball=ball+1
  if ball<5: continue
  print('Надо исправить!')
else:
  print('Оценка исправлена!')
print('Я - отличник!')

Надо исправить!
Я - отличник!

Подробней о вспомогательных алгоритмах

Вспомогательные алгоритмы позволяют реализовать в программах ряд важных возможностей:

• реализовать программу методом последовательной детализации (разделить на простые подзадачи)
• избавляют от повторного написания одного и того же, не переодически повторяющегося кода
• реализовать рекурсивные алгоритмы (см. ниже)

Параметры вспомогательных алгоритмах

Вспомогательным алгоритмам в скобках можно передавать параметры, от которых будет зависеть результат их выполнения.
Это аналогично тому, как в алгебре значение функций зависят от их аргументов: y=f(x)

Процедуры и функции

Вспомогательные алгоритмы и функции в python - синонимы. Но могут вести себя как процедуры, если не содержат команду возврата результата своего выполнения - return.

In [26]:

def mom():  # Процедура - приветствие только с мамой
  print('Hello, mother!')
def dad():  # Процедура - приветствие только с папой
  print('Hello, father!')
def hi(x):   # Функция- приветствие с любым x
  return 'Hello, '+x+'!'
dad()
mom()
print(hi('mother'))
print(hi('brother'))
dad()

Hello, father!
Hello, mother!
Hello, mother!
Hello, brother!
Hello, father!

Локальные и глобальные объекты

Параметры вспомогательных алгоритмов, а также именованные внутри них объекты - являются локальными (внутренними).
Создаются во время вызова вспомогательного алгоритма, существуют только во время его работы и освобождают память после его завершения.
Объекты основной программы, даже с таким именем, и локальные взаимно независимы.

In [28]:

x=1
a=2
def f(x):
  a=3
  print(x+a) # a и x - локальные
f(a)
print(x+a)

5
3

Если объект создан в основной программе, а внутри вспомогательного - нет. При этом, если он используется во вспомогательном, то в таком случае - он будет вести как глобальный (Везде один и тот же).
В примере ниже - это объект с именем a.

In [32]:

x=1
a=2
def f(x):
  print(a+x)  # a - глобальная, x - локальные
f(a)
print(a+x)

4
3

Использование глобальных объектов - нежелательно!

Рекурсия

Рекурсия - хороша!

Рекурсия - это ситуация, когда вспомогательный алгоритм обращается к самому себе в качестве вспомогательного, с указанием граничащего(их) условия(й).
Пример: Найти через умножение n-ю степень числа x- x^n.
Решение:
рекуррентная формула: x^n = x x^(n-1)* , если n>0, иначе 1
Реализация:

In [36]:

def st(x,n):
  if n>0: return x*st(x,n-1)
  else: return 1
print(st(5,3))
print(st(2,10))
print(st(10,0))

125
1024
1

Рекурсия позволяет организовать повторения без использования циклов.
Кроме того, в математике (компьютер - машина вычислительная) большинство определений можно задать рекуррентными формулами, то рекурсия позволяет реализовать большинство задач. Но - не наоборот!
По этой причине, для сложных задач, лучше, сначала искать рекурсивное решение, а потом (если возможно)...

Плохая рекурсия

А зачем "потом...". Дело в том, что рекурсия имеет ряд недостатков.

• При своем выполнение рекурсивный алгоритм делает вызовы до достижения граничащего условия, а потом, как минимум, столько же возвращается обратно. Минимум в двое менее эффективный по времени.
• При каждом вызове обязаны создаваться локальные копии объектов. Теряется эффективность по памяти.

Поэтому, если удаются найти нерекурсивное решение, следует перейти к нему.
Сравним время выполнения рекурсивное решение рассмотренной ранее задачи для x=5 и n=15 и время выполнение нерекурсивной функции st1 для этой задачи:

In [56]:

%time
st(5,15)

CPU times: user 4 µs, sys: 0 ns, total: 4 µs
Wall time: 28.4 µs

Out[56]:

30517578125

In [60]:

%time
def st1(x,n):
  p=1
  while n:
    p*=x
    n=n-1
  return p
st1(5,15)

CPU times: user 2 µs, sys: 0 ns, total: 2 µs
Wall time: 5.01 µs

Out[60]:

30517578125

4-A. Базовые конструкции алгоритмов

4-A. Базовые конструкции (виды) алгоритмов - обзор

1.4.1 - Линейные алгоритмы¶

Пусть имеется ученик Миша, которого мы хотим наделить способностями Черепахи:
import turtle as Миша
После чего, Миша будет способен выполнять команды:
вперед на x шагов - forward(x)
повернись влево на x градусов - left(n)
 и другие ...

In [1]:

import turtle as Миша # Да прибудет с Мишей черепашья сила
Миша.forward(200)     # Миша - вперед на 200 шагов
Миша.left(90)         # Миша повернись влево на 90 градусов
Миша.mainloop()# Не закрывай окно выполнения (мы сами нажмем крестик)

В окне выполнения Миша был представлен стрелочкой, что не симпатично. 
Облачим Мишу в костюм Черепахи - shape('turtle')

In [1]:

import turtle as Миша
Миша.shape('turtle')
Миша.forward(200)
Миша.left(90)
Миша.mainloop()

В обоих программах все команды были записаны друг за другом - в одну линию.
В таких программах (алгоритмах) команды будут выполняться в том порядке, в котором они записаны.
В этом случае говорят, что это линейные алгоритмы

1.4.2 - Вспомогательные алгоритмы

Если мы хотим научить исполнителя новой команде, то мы должны описать вспомогательный алгоритм:

• с помощью команды def определить для него имя
• в скобках указать параметры, от которых он будет зависеть (или оставить их пустыми)
• поставить знак ":"
• далее, с красной строки написать то, как будет реализована новая команда

Когда исполнитель встретит такое описание - он научиться новой команде, а выполнять ее будет только тогда, когда произойдет вызов по ее имени. Затем вернется в место, следующее после ее вызова.

Научим нашего Мишу прходить один круг по квадратному стадиону. Благодаря вспомогательному алгоритму сторона(), у нас сократится количество записанных команд.

In [1]:

import turtle as Миша
Миша.shape('turtle')
def сторона():
    Миша.forward(200)
    Миша.left(90)
сторона()
сторона()
сторона()
сторона()

1.4.3 - Ветвления

• Сокращенное ветвление:  if (ответвление)
• Разветвление:  if - else:
• Множественное ветвление:  if - elif - ... - elif - else:

Научим Мишу менять цвет, оставляемого им следа
pencolor() - узнать текущий цвет
pencolor('цвет') - поменять на 'цвет'

In [1]:

import turtle as Миша
Миша.shape('turtle')
def сторона():
    Миша.forward(200)
    Миша.left(90)
# Сокращенное ветвление if (ответвление):
    if Миша.pencolor()=='black':
        Миша.pencolor('red')
сторона()
сторона()
сторона()
сторона()

In [1]:

import turtle as Миша
Миша.shape('turtle')
def сторона():
    Миша.forward(200)
    Миша.left(90)
# Разветвление if - else:
    if Миша.pencolor()=='black':
        Миша.pencolor('red')
    else:
        Миша.pencolor('black')
сторона()
сторона()
сторона()
сторона()

In [1]:

import turtle as Миша
Миша.shape('turtle')
def сторона():
    Миша.forward(200)
    Миша.left(90)
# Множественное ветвление if - elif - ... - elif - else:
    if Миша.pencolor()=='black':
        Миша.pencolor('red')
    elif Миша.pencolor()=='red':
        Миша.pencolor('blue')
    elif Миша.pencolor()=='blue':
        Миша.pencolor('green')
    elif Миша.pencolor()=='green':
        Миша.pencolor('gray')
    else:
        Миша.pencolor('black')
сторона()
сторона()
сторона()
сторона()

1.4.4 - Циклические

с многократно повторяющимися подряд командами

ТЦ - тело цикла (команды, которые надо повторять)
Цикл for - повторяет ТЦ, для каждого значения в объекте

In [1]:

import turtle as Миша
Миша.shape('turtle')
def сторона():
 Миша.forward(200)
 Миша.left(90)
 if Миша.pencolor()=='black':
  Миша.pencolor('red')
 elif Миша.pencolor()=='red':
  Миша.pencolor('blue')
 elif Миша.pencolor()=='blue':
  Миша.pencolor('green')
 elif Миша.pencolor()=='green':
  Миша.pencolor('gray')
 else:
  Миша.pencolor('black')
for __ in '1234': # будет выполнять ТЦ для каждого (1,2,3,4) из строки '1234'
    сторона()     # ТЦ
Миша.mainloop()

Цикл while - повторяет ТЦ (после двоеточия, с красной строки), пока истинно высказывание, записанное между while и двоеточием

In [ ]:

import turtle as Миша
Миша.shape('turtle')
def сторона():
 Миша.forward(200)
 Миша.left(90)
 if Миша.pencolor()=='black':
  Миша.pencolor('red')
 elif Миша.pencolor()=='red':
  Миша.pencolor('blue')
 elif Миша.pencolor()=='blue':
  Миша.pencolor('green')
 elif Миша.pencolor()=='green':
  Миша.pencolor('gray')
 else:
  Миша.pencolor('black')
Круг=6
while Круг:
 for __ in 1,2,3,4:
  сторона()
 Круг = Круг - 1 
Миша.mainloop()