Различия между версиями 5 и 6
Версия 5 от 2019-10-22 17:25:49
Размер: 2480
Редактор: FrBrGeorge
Комментарий:
Версия 6 от 2019-10-25 15:32:47
Размер: 4037
Редактор: FrBrGeorge
Комментарий:
Удаления помечены так. Добавления помечены так.
Строка 32: Строка 32:
  * ⇒ элемент стека (пространство имён) состоит из трёх ячеек
 1. В общем цикле, в который превратится рекурсия, надо различать ситуации
  * ⇒ кадр стека (пространство имён) состоит из трёх ячеек
 1. Рекурсивный вызов — это добавление очередного кадра в стек. Возврат из вызова — удаление кадра из стека. В рекурсивной записи это могут быть последовательные команды. В цикле, в который превращается рекурсия, всё это соответствует очередному обороту цикла. Так что в стеке нужно дополнительно хранить, в какую часть исходного рекурсивного кода мы выполняем:
Строка 39: Строка 39:
 1. Это можно сделать, например, запоминая `None` вместо `s1` и `res` на первых этапах, и подменяя их на результат вычисления на более поздних  1. Это можно сделать, например, с помощью переменной, хранящей состояние. В примере мы просто запоминаем `None` вместо `s1` и `res` на первых этапах, и подменяем их на результат вычисления на более поздних, и такм образом отличаем один от другого.
Вот пример решения:
{{{#!python
def jsorts(seq):
    stack = [[seq, None, None]]
    while stack[0][-1] is None:
        seq, s1, res = stack[-1]
        if len(seq)<2: # res = seq
            seq, s1, res = stack[-1] = [seq, seq, seq]
        if s1 is None: # jsort(seq[len(seq)//2:])
            stack.append([seq[len(seq)//2:], None, None])
            continue
        if res is None: # jsort(seq[:len(seq)//2])
            stack.append([seq[:len(seq)//2], None, None])
            continue
        stack.pop() # return res
        seq, s1, oldres = stack[-1]
        if s1 is None: # s1 = ...
            stack[-1][1] = res
        else: # s2 = ... and other
            stack[-1][-1] = sjoin(s1, res)
    return stack[-1][-1]
    }}}

10/22 рекурсия

Замещение рекурсии стеком. Рекурсивная реализация алгоритма сортировки слиянием:

   1 def sjoin(s1, s2):
   2     res = []
   3     while s1 and s2:
   4         res.append(s1.pop() if s1[-1]>s2[-1] else s2.pop())
   5     return s1+s2+list(reversed(res))
   6 
   7 def jsort(seq):
   8     l = len(seq)
   9     if l<2:
  10         return list(seq)
  11     return sjoin(jsort(seq[l//2:]), jsort(seq[:l//2]))

Здесь для эффективности pop() и append() работают с концом списка, но полученный слиянием результат оказывается в обратном порядке, поэтому его надо перевернуть.

Д/З: стековая реализация алгоритма сортировки слиянием

Подсказка:

  1. Избавимся в алгоритме от создания неименованных объектов, тупо поименовав их :)

    def jsort(seq):
        if len(seq)<2:
            res = seq
        else:
            s1 = jsort(seq[len(seq)//2:])
            s2 = jsort(seq[:len(seq)//2])
            res = sjoin(s1, s2)
        return res
  2. Посмотрим, какие из имён должны пережить рекурсивный вызов jsort(). В данном случае это seq, s1. А s2 вычисляется после рекурсивного вызова, его хранить не надо. Кроме того, надо как-то возвращать res

    • ⇒ кадр стека (пространство имён) состоит из трёх ячеек
  3. Рекурсивный вызов — это добавление очередного кадра в стек. Возврат из вызова — удаление кадра из стека. В рекурсивной записи это могут быть последовательные команды. В цикле, в который превращается рекурсия, всё это соответствует очередному обороту цикла. Так что в стеке нужно дополнительно хранить, в какую часть исходного рекурсивного кода мы выполняем:
    1. До вычисления s1

    2. После вычисления s1, но до собственно присваивания s1=

    3. До вычисления s2

    4. После вычисления s2, но до собственно присваивания s2= и вычисления res

    5. Собственно return

  4. Это можно сделать, например, с помощью переменной, хранящей состояние. В примере мы просто запоминаем None вместо s1 и res на первых этапах, и подменяем их на результат вычисления на более поздних, и такм образом отличаем один от другого.

Вот пример решения:

   1 def jsorts(seq):
   2     stack = [[seq, None, None]]
   3     while stack[0][-1] is None:
   4         seq, s1, res = stack[-1]
   5         if len(seq)<2:          # res = seq
   6             seq, s1, res = stack[-1] = [seq, seq, seq]
   7         if s1 is None:          # jsort(seq[len(seq)//2:])
   8             stack.append([seq[len(seq)//2:], None, None])
   9             continue
  10         if res is None:         # jsort(seq[:len(seq)//2])
  11             stack.append([seq[:len(seq)//2], None, None])
  12             continue
  13         stack.pop()             # return res
  14         seq, s1, oldres = stack[-1]
  15         if s1 is None:          # s1 = ...
  16             stack[-1][1] = res
  17         else:                   # s2 = ... and other
  18             stack[-1][-1] = sjoin(s1, res)
  19     return stack[-1][-1]

LecturesCMC/PythonIntro2019/Prac/1022 (последним исправлял пользователь FrBrGeorge 2019-10-25 15:32:47)