Редактировать:
Функции вставки будут выполняться только после того, как рекурсивные функции будут использовать пустой стек.
START DELETE 0 [only one while loop executed]
START DELETE 1 [only one while loop executed]
START DELETE 2 [only one while loop executed]
START DELETE 3 [only one while loop executed]
START DELETE 4 [only one while loop executed]
START DELETE 5 [NO while loop executed because list is empty]
-------------------------
START INSERT iteration 4
END INSERT iteration 4
END DELETE 4
-------------------------
START INSERT iteration 3
END INSERT iteration 3
END DELETE 3
-------------------------
START INSERT iteration 2
END INSERT iteration 2
END DELETE 2
-------------------------
START INSERT iteration 1
END INSERT iteration 1
END DELETE 1
-------------------------
START INSERT iteration 0
END INSERT iteration 0
END DELETE 0
Итак, у нас сначала выполняется функция вставки (4), потому что, когда последний delete_middle (5) выполняется, список, стек пуст и не выполняет функцию вставки, как указано:
while len(stack)>0:
...........
insert(stack,temp,curr,n)
Вышеуказанное в delete_middle с n=5 не будет выполнено, потому что len(stack)==0.
Как работает middle :
#first executed delete_middle([2,4,1,18,34],5,0)
def delete_middle(stack,n,curr): iteration 1
while len(stack)>0: initial stack [2,4,1,18,34]
temp=stack.pop() stack after removal [2,4,1,18]
.....
delete_middle(stack,n,curr+1) -> becomes: delete_middle([2,4,1,18],5,1) iteration 2
while len(stack)>0: initial stack [2,4,1,18]
temp=stack.pop() stack after removal [2,4,1]
.....
delete_middle(stack,n,curr+1) > becomes: delete_middle([2,4,1],5,2) and so on until stack = [] (empty)
.....
(!) During these iterations insert(stack,temp,curr,n) is not executed because:
Как вставить выполнить:
delete_middle([2,4,1,18,34],5,0)
# Iteration 1
#delete_middle(stack, n, curr+1)
delete_middle([2,4,1,18], 5, 1 )
insert not executed!
# Iteration 2
delete_middle([2,4,1],5,2)
insert not executed!
# Iteration 3
delete_middle([2,4],5,3)
insert not executed!
# Iteration 4
delete_middle([2],5,4)
insert not executed!
# Iteration 5
delete_middle([],5,5) # returns nothing because it does not enter the while loop
insert not executed!
Only from now -> each insert will be executed from inside delete_middle!
insert 4
insert 3
insert 2
insert 1
О сложности времени:
Time complexity = time taken to build the final list;
= (1 pop + 1 insert) * n
= O(n)
В худшем и худшем случае, вы могли бы скажем, что сложность O (n), потому что уменьшение размера списка на 1 элемент предполагает добавление 1 элемента в список, потому что у вас есть только одна рекурсия на уровень. (while .. return indentation)
Хотя pop равно O (1) и список уменьшается каждый раз (O (log n)), когда каждый middle_delete называется временем выполнения вашего алгоритма увеличивается с размером входных данных, выполняя (n-1) сложений в сумме; добавление всего оставшегося списка.
Некоторая отправная точка.
END edit
Что касается вашего кода, да, он работает, с некоторыми ограничениями, если можно:
- длина целевого списка должна быть нечетной
- принимает некоторые дополнительные ненужные * критерии (
curr,n ) [необязательно, см. последнюю часть] - функция не «вполне правильно» выполнена
Пояснения:
Попробуйте сами
Конец ответа (наберитесь терпения со мной :))
- Например:
В вашем коде:
while len(stack)>0:
.....
return stack
Похоже, вы возвращаете первое значение while l oop. Пример:
c = 0
def func(d):
while d < 5:
d+=1
return d
print(func(c))
Рекурсивный эффект вызван умным использованием None результирующего веселья c (вставка) внутри while l oop. Это все равно что тянуть ручную остановку вместо педали. :)
Относительно ваших вопросов :
Как видно ниже, (среднее веселье c выполняется + вставить веселье c) для каждого элемента.
delete middle iterion 0
--------------------------
temp 34 0
delete middle iterion 1
--------------------------
temp 18 1
delete middle iterion 2
--------------------------
temp 1 2
delete middle iterion 3
--------------------------
temp 4 3
delete middle iterion 4
--------------------------
temp 2 4
delete middle iterion 5
--------------------------
======================
insert iteration 4
curr:4, stack:[], temp:2,n:5
======================
insert iteration 3
curr:3, stack:[2], temp:4,n:5
======================
insert iteration 2
curr:2, stack:[2, 4], temp:1,n:5
======================
insert iteration 1
curr:1, stack:[2, 4], temp:18,n:5
======================
insert iteration 0
curr:0, stack:[2, 4, 18], temp:34,n:5
[2, 4, 18, 34]
Почему мы не видим здесь первое значение curr как 5?
Если вы начнете (curr) с 0, вы увидите итерации от 4-> 0, в то время как при первоначальном curr равен 1, итерация будет 5-> 1; таким образом, 5 (N) удалить удовольствие c вызовы будут запущены.
Я немного переработал ваш код с помощью простой логики c:
Если у вас есть целевой список [1,2, .., n-1, n] и если вы хотите чтобы удалить среднюю часть с помощью рекурсивных функций, возможно, вам подойдет такой подход:
Давайте начнем со счетчика 0 count = 0, для каждого элемента списка счетчик будет увеличен на 1 count+=1
Теперь, чтобы убрать по одному элементу с каждой стороны (слева, справа), чтобы попасть в середину, мы можем сказать: если счетчик равен 0 или счетчик даже удаляет последний элемент из списка, если не удаляет первый элемент таким образом список теряет один элемент за итерацию.
if count == 0 and count % 2 == 0:
target_list.pop(-1)
else:
target_list.pop(0)
Тогда что, если список содержит четное количество элементов? Затем мы также включим этот сценарий: if len(target) == 2.
Также я предлагаю использовать один маленький трюк, тот факт, что значение по умолчанию для аргумента функции оценивается только один раз, во время определения функции.
что я имею в виду под этим? Проверьте пример для Распространенная ошибка # 1 .
Чтобы включить все вышеперечисленное в финальное веселье c (O (N)):
def eliminate_middle(target, count=0, beg_l=[],end_l=[]):
print(count) # O(N)
if len(target) == 1: # if target has only one element
return beg_l+sorted(end_l)
else:
if count == 0 or count % 2 == 0:
if len(target) == 2: # case len(target) is Even
return beg_l+sorted(end_l) #eliminates the two middle elements
end_l.append(target.pop(-1)) #target loses last element
return eliminate_middle(target,count+1)
else:
beg_l.append(target.pop(0)) # target loses first element
return eliminate_middle(target, count+1)
print(eliminate_middle([2,4,1,18,34]))