Доброго времени суток.
Задание такое: дан список (целых чисел. сколько элементов - не известно)
Надо разделить его на 2 списка (пополам. куда отнести средний элемент, если количество нечетное - не принципиально). Считать (и определять другими способами) кол-во элементов запрещено.
Поскольку речь идет про функцию, допустим, что она будет возвращать одну из половин (пусть первую - для определенности).
Как этого можно добиться?
У меня идея такая (весьма неоптимальная).
1) Терминальные случаи.
Если список пуст или состоит из 1 эл-та - все просто и понятно.
2) Иначе результатом будет первый элемент, соединенный с поделенным пополам остатком списка после откидывания последнего элемента.
Ну на примере:
на входе имеем '(1 2 3 4 5)
выделяем 1
отбрасываем 5
теперь так же ищем половину от нового списка - (2 3 4)
выделяем 2
отбрасываем 4
получаем терминальный случай.
на выходе (1 2 3)
для выделения первого элемента есть CAR, для получения остатка - CDR. Для отбрасывания последнего придется писать что-то свое.
и ничего умнее, чем рекурсивно перебирать элементы, пока остаток не будет равен NIL, я придумать не могу
Работать такой алгоритм, возможно, и способен - но уж больно много лишних операций.
Буду благодарна за идеи по оптимизации.
разделить список на 2 части, LISP |