DjangoBB LoFi version

Полная версия: Задачка

starscream

Март 9, 2017 20:46:40

Здравствуйте. В общем, попалась мне интересная задачка. Если кто натолкнет на мысль буду признателен.
Есть массив из 100 элементов, элементы в нем от 1 до 100, то есть .
Из массива постепенно, итерация за итерацией удаляют элементы до тех пор, пока не останется один.
Удаляется каждый 3-й элемент и счет начинается с элемента,стоящего после удаленного. Причем счет каждого третьего не начинается с первого элемента нового массива, а продолжается с предыдущей итерации к следующей.
Например, если массив от 1 до 10, 10 -элементов, после исключения 9-го элемента, счет начинается с 10-го далее 1-ый, 2-й в итоге выбывает и т.д.

py.user.next

Март 10, 2017 01:17:45

collections.deque() подойдёт хорошо.

  
>>> import collections
>>> 
>>> d = collections.deque(range(1, 11))
>>> 
>>> while d:
...     'step'
...     d
...     d.rotate(-2)
...     d
...     d.popleft()
...     d
... 
'step'
deque([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
deque([3, 4, 5, 6, 7, 8, 9, 10, 1, 2])
3
deque([4, 5, 6, 7, 8, 9, 10, 1, 2])
'step'
deque([4, 5, 6, 7, 8, 9, 10, 1, 2])
deque([6, 7, 8, 9, 10, 1, 2, 4, 5])
6
deque([7, 8, 9, 10, 1, 2, 4, 5])
'step'
deque([7, 8, 9, 10, 1, 2, 4, 5])
deque([9, 10, 1, 2, 4, 5, 7, 8])
9
deque([10, 1, 2, 4, 5, 7, 8])
'step'
deque([10, 1, 2, 4, 5, 7, 8])
deque([2, 4, 5, 7, 8, 10, 1])
2
deque([4, 5, 7, 8, 10, 1])
'step'
deque([4, 5, 7, 8, 10, 1])
deque([7, 8, 10, 1, 4, 5])
7
deque([8, 10, 1, 4, 5])
'step'
deque([8, 10, 1, 4, 5])
deque([1, 4, 5, 8, 10])
1
deque([4, 5, 8, 10])
'step'
deque([4, 5, 8, 10])
deque([8, 10, 4, 5])
8
deque([10, 4, 5])
'step'
deque([10, 4, 5])
deque([5, 10, 4])
5
deque([10, 4])
'step'
deque([10, 4])
deque([10, 4])
10
deque([4])
'step'
deque([4])
deque([4])
4
deque([])
>>>

Естественно, ты можешь и на обычном списке сделать такой дек. Можно, конечно, и на одном индексе сделать.

Так что для тренировки можешь сделать все три варианта и посмотреть, какой из них читаемее, быстрее делается, быстрее работает и менее затратен по памяти.

starscream

Март 10, 2017 14:00:23

Спасибо. Пойду разбираться с этим модулем. И все же не могли бы вы показать как это будет выглядеть на обычном списке, если не трудно

py.user.next

Март 11, 2017 13:56:06

  
>>> lst = list(range(1, 11))
>>> 
>>> while lst:
...     'step'
...     lst
...     lst.append(lst.pop(0))
...     lst.append(lst.pop(0))
...     lst
...     lst.pop(0)
...     lst
... 
'step'
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[3, 4, 5, 6, 7, 8, 9, 10, 1, 2]
3
[4, 5, 6, 7, 8, 9, 10, 1, 2]
'step'
[4, 5, 6, 7, 8, 9, 10, 1, 2]
[6, 7, 8, 9, 10, 1, 2, 4, 5]
6
[7, 8, 9, 10, 1, 2, 4, 5]
'step'
[7, 8, 9, 10, 1, 2, 4, 5]
[9, 10, 1, 2, 4, 5, 7, 8]
9
[10, 1, 2, 4, 5, 7, 8]
'step'
[10, 1, 2, 4, 5, 7, 8]
[2, 4, 5, 7, 8, 10, 1]
2
[4, 5, 7, 8, 10, 1]
'step'
[4, 5, 7, 8, 10, 1]
[7, 8, 10, 1, 4, 5]
7
[8, 10, 1, 4, 5]
'step'
[8, 10, 1, 4, 5]
[1, 4, 5, 8, 10]
1
[4, 5, 8, 10]
'step'
[4, 5, 8, 10]
[8, 10, 4, 5]
8
[10, 4, 5]
'step'
[10, 4, 5]
[5, 10, 4]
5
[10, 4]
'step'
[10, 4]
[10, 4]
10
[4]
'step'
[4]
[4]
4
[]
>>>

starscream

Март 11, 2017 14:16:04

Блин, до этого и самому не так сложно было догадаться оказывается.

Спасибо еще раз)