разделить список на 2 части, LISP Опции

[мисс_граффити]

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

для выделения первого элемента есть CAR, для получения остатка - CDR. Для отбрасывания последнего придется писать что-то свое.
и ничего умнее, чем рекурсивно перебирать элементы, пока остаток не будет равен NIL, я придумать не могу

Работать такой алгоритм, возможно, и способен - но уж больно много лишних операций.
Буду благодарна за идеи по оптимизации.

[hardcase]

А вот мой вариант (сорри, на лиспе тока читать умею).
Производим 2 прохода по списку:
1 проход. Выбираем из входного списка А только нечетные элементы в список Н.
2 проход. Выполняем проход по входному списку А одовременно с проходом по списку Н, полученному при первом проходе, и выбираем каждый элемент из А. Проход останавливается когда достигаем конца Н.


З.Ы. 2 проход можно впихнуть в возврат из рекурсии в первом проходе. тогда мы получим вторую половину списка.

Сообщение отредактировано: hardcase - 5.09.2007 23:51