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