2480
Комментарий:
|
← Версия 6 от 2019-10-25 15:32:47 ⇥
4037
|
Удаления помечены так. | Добавления помечены так. |
Строка 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 рекурсия
Замещение рекурсии стеком. Рекурсивная реализация алгоритма сортировки слиянием:
Здесь для эффективности pop() и append() работают с концом списка, но полученный слиянием результат оказывается в обратном порядке, поэтому его надо перевернуть.
Д/З: стековая реализация алгоритма сортировки слиянием
Подсказка:
Избавимся в алгоритме от создания неименованных объектов, тупо поименовав их
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
Посмотрим, какие из имён должны пережить рекурсивный вызов jsort(). В данном случае это seq, s1. А s2 вычисляется после рекурсивного вызова, его хранить не надо. Кроме того, надо как-то возвращать res
- ⇒ кадр стека (пространство имён) состоит из трёх ячеек
- Рекурсивный вызов — это добавление очередного кадра в стек. Возврат из вызова — удаление кадра из стека. В рекурсивной записи это могут быть последовательные команды. В цикле, в который превращается рекурсия, всё это соответствует очередному обороту цикла. Так что в стеке нужно дополнительно хранить, в какую часть исходного рекурсивного кода мы выполняем:
До вычисления s1
После вычисления s1, но до собственно присваивания s1=
До вычисления s2
После вычисления s2, но до собственно присваивания s2= и вычисления res
Собственно return
Это можно сделать, например, с помощью переменной, хранящей состояние. В примере мы просто запоминаем 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]