DjangoBB LoFi version

Полная версия: Задача "Разворот последовательности" без применения динамических структур данных

Начало » Центр помощи » Задача "Разворот последовательности" без применения динамических структур данных

1 2 3 4

kamikadze

Янв. 10, 2018 08:54:28

Всем Коничива! Условие задачи:

“Дана последовательность целых чисел (вводится с клавиатуры), заканчивающаяся числом 0. Выведите эту последовательность в обратном порядке. При решении этой задачи нельзя пользоваться массивами и прочими динамическими структурами данных.Рекурсия вам поможет.”

Мое решение:

 def reverse(l):
    if len(l) > 1:
        print(l[len(l)-1])
        del l[len(l)-1]
        return reverse(l)
    else:
        return l[0]
def ss(n):
    if n != 0:
        l.append(n)
        return ss(int(input()))
    elif n == 0 and len(l) == 0:
        return n
    elif n == 0 and len(l) != 0:
        l.append(n)
        return reverse(l)
l = []
print(ss(int(input())))

Проблема:

Да, я использовал динамическую структуру. Но, мне кажется, что структура алгоритма, с помощью которого поставленную задачу возможно решить, не может не содержать динамических структур. Принцип таков: для каждого нового значения необходимо место в памяти. Количество значений заранее не предопределено. Вопрос: как в такой ситуации, можно решить задачу без динамических структур? Кстати, рылся в интернете, так и не нашел толком, что такое ч точки зрения Python динамические и (не динамические) статические структуры данных. Проверил решение на тестах сайта Питон для начинающих (не помню точно адрес), все 5 возможных тестов проходит. В принципе для меня главное решить задачу в общем, а не изощряться с типами применяемых данных. Но на Курсере есть какой-то 6 тест, который мой алгоритм не проходит. Что он проверяет я не знаю. Может, в моем алгоритме есть ошибки? На малых числах все работает исправно.

py.user.next

Янв. 10, 2018 09:46:20

  
>>> def print_reversed(seq, pos=0):
...     elem = seq[pos]
...     if elem != 0:
...         print_reversed(seq, pos + 1)
...     print(elem)
... 
>>> print_reversed([1, 2, 3, 4, 5, 0])
0
5
4
3
2
1
>>>

kamikadze
Кстати, рылся в интернете, так и не нашел толком, что такое ч точки зрения Python динамические и (не динамические) статические структуры данных.

Динамическая структура данных - это такая структура данных, количество элементов которой может меняться после её создания. Примеры: стек, очередь, дек, линейный список, множество, динамический вектор. В питоне многие из этих динамических структур реализованы в виде встроенных типов: стек - list, множество - set(), нагруженное множество - dict, динамический вектор - list. При этом есть и библиотечный тип: дек - collections.deque. А вот динамической структуры последовательность в питоне не реализовано, но частично её роль выполняют итераторы, так как не все операции над последовательностью можно выполнять с итератором (нельзя добавить элемент после создания, нельзя сделать подсматривание следующего элемента без его взятия и нельзя опустошить итератор в любое время и начать заново заполнять).

kamikadze

Янв. 10, 2018 09:49:49

py.user.next

Спасибо, конечно, но последовательность вводится с клавиатуры. Поэтому у меня и стоят операторы input().

py.user.next

Янв. 10, 2018 10:02:34

kamikadze
но последовательность вводится с клавиатуры. Поэтому у меня и стоят операторы input().

После того, как ты ввёл последовательность, её надо подать в функцию обращения. То, что ты там трактуешь, что якобы ни одного списка быть не должно во всём коде, - это просто твои домыслы, потому что ты неправильно понял условия выполнения заданий подобного рода. Нельзя применять список внутри самой функции обращения для временного хранения элементов.

kamikadze

Янв. 10, 2018 10:13:27

py.user.next

Согласен, что я там неправильно что-то понял или не понял. Но только то, что написано в условиях задачи, то я и читаю. А там написано: “При решении этой задачи нельзя пользоваться массивами и прочими динамическими структурами данных.” Тут не сказано, что их нельзя использовать только в пределах функций или каких-то других конкретных частях кода. Тут сказано: “в пределах задачи”. А додумывать за автора задачи никто не может, кроме него самого. ХЗ, что он там имел ввиду. Ну а то, что у вас есть опыт решения подобных задач, просто потому, что вы с этим уже сталкивались, не дает права “тыкать” остальным. А за разъяснения спасибо большое.

py.user.next

Янв. 10, 2018 10:28:13

kamikadze
Но только то, что написано в условиях задачи, то я и читаю.

Ну вот и читай

kamikadze
Дана последовательность целых чисел (вводится с клавиатуры), заканчивающаяся числом 0.

Дана последовательность - это значит что? Это значит, что по условию задачи последовательность уже есть, а для решения задачи нужно проделать с ней действия и получить результат. Поэтому перевод строки из консоли в последовательность целых чисел не входит в задачу. Это уже дано по условию.

Ты просто делаешь

  
print_reversed(tuple(map(int, input().split())))

Можно это и на итераторе сделать, но я пока что нигде не вижу, что тесты это требуют. Разницы-то нет, так как на итераторе код самой рекурсии будет точно таким же. Цель упражнения - научить рекурсии, поэтому заморочек с памятью вообще быть не должно. А требование избегать динамических структур для того и введено, чтобы только рекурсией это решалось.

kamikadze

Янв. 10, 2018 10:38:37

py.user.next

Блин, никогда бы не поверил, что незатейливое обсуждение логики кода может перейти в “халивар” интелектов.

Так! Понимаю и принимаю ваше недоумение и заслуженный поток возмущений. В связи с тем прикладываю скриншот лично мной склеенный с сайта с задачей, чтобы Вы воочию смогли убедиться в вопиющей несправедливости происходящего.

py.user.next

Янв. 10, 2018 11:06:50

Скопируй сюда точно то, что туда отправил в последний раз.

kamikadze

Янв. 10, 2018 11:08:50

 def reverse(l):
    if len(l) > 1:
        print(l[len(l)-1])
        del l[len(l)-1]
        return reverse(l)
    else:
        return l[0]
def ss(n):
    if n != 0:
        l.append(n)
        return ss(int(input()))
    elif n == 0 and len(l) == 0:
        return n
    elif n == 0 and len(l) != 0:
        l.append(n)
        return reverse(l)
l = []
print(ss(int(input())))

py.user.next

Янв. 10, 2018 11:39:46

Отправь туда

  
def print_reversed(seq, pos=0):
    elem = seq[pos]
    if elem != 0:
        print_reversed(seq, pos + 1)
    print(elem)
 
print_reversed(tuple(map(int, input().split())))