Доброго времени суток.
Задание такое: дан список (целых чисел. сколько элементов - не известно)
Надо разделить его на 2 списка (пополам. куда отнести средний элемент, если количество нечетное - не принципиально). Считать (и определять другими способами) кол-во элементов запрещено.
Поскольку речь идет про функцию, допустим, что она будет возвращать одну из половин (пусть первую - для определенности).
Как этого можно добиться?
У меня идея такая (весьма неоптимальная).
1) Терминальные случаи.
Если список пуст или состоит из 1 эл-та - все просто и понятно.
2) Иначе результатом будет первый элемент, соединенный с поделенным пополам остатком списка после откидывания последнего элемента.
Ну на примере:
на входе имеем '(1 2 3 4 5)
выделяем 1
отбрасываем 5
теперь так же ищем половину от нового списка - (2 3 4)
выделяем 2
отбрасываем 4
получаем терминальный случай.
на выходе (1 2 3)
для выделения первого элемента есть CAR, для получения остатка - CDR. Для отбрасывания последнего придется писать что-то свое.
и ничего умнее, чем рекурсивно перебирать элементы, пока остаток не будет равен NIL, я придумать не могу
Работать такой алгоритм, возможно, и способен - но уж больно много лишних операций.
Буду благодарна за идеи по оптимизации.
с лиспом к сожалению не знаком, но думаю там такое вполне можно сделать:
uses crt;
type
PTList = ^TList;
TList = record
data: integer;
next: PTList;
end;
var
first, last, temp, middle: PTList;
value, counter: integer;
begin
clrscr;
first := nil;
last := nil;
counter := 0;
repeat
GetMem(temp, sizeof(TList));
readln(value);
if value <> 0 then begin
temp^.data := value;
temp^.next := nil;
if first = nil then begin
first := temp;
last := temp;
middle := first;
end else begin
last^.next := temp;
last := temp;
end;
inc(counter);
if counter = 2 then begin
middle := middle^.next;
counter := 0;
end;
end;
until value = 0;
writeln('first half:');
while (first <> middle) do begin
writeln(first^.data:3);
first := first^.next;
end;
writeln('second half:');
while (first <> nil) do begin
writeln(first^.data:3);
first := first^.next;
end;
readln;
end.
Там, к сожалению, все совсем по-другому (( Как именно - я пока сама не очень понимаю
Цитируя моего препода: "На делфи вы пишете, КАК искать результат, а на ЛИСПе - ЧТО хотите получить".
И еще проблема - мы список не заполняем, а считаем уже данным. То есть считать добавленные элементы по ходу не получится.
Спасибо за готовность помочь!
А вообще, если интересно, это всё ради того, чтобы пройти матрицу (=список списков) по определенному маршруту.... На делфи это бы решилось кучей циклов, а здесь - еще большей кучей функций )))
ну а если так (алгоритм остается тот-же):
// ...
for value := 1 to 37 do begin
GetMem(temp, sizeof(TList));
temp^.data := value;
temp^.next := nil;
if first = nil then begin
first := temp;
last := temp;
middle := first;
end else begin
last^.next := temp;
last := temp;
end;
END;
// имеем заполненный список
// тепер проходим по нему и вычисляем середину
temp := first;
middle := first;
counter := 0;
while (temp <> nil) do begin
inc(counter);
if counter = 2 then begin
middle := middle^.next;
counter := 0;
end;
temp := temp^.next;
end;
// ...
А вот мой вариант (сорри, на лиспе тока читать умею).
Производим 2 прохода по списку:
1 проход. Выбираем из входного списка А только нечетные элементы в список Н.
2 проход. Выполняем проход по входному списку А одовременно с проходом по списку Н, полученному при первом проходе, и выбираем каждый элемент из А. Проход останавливается когда достигаем конца Н.
З.Ы. 2 проход можно впихнуть в возврат из рекурсии в первом проходе. тогда мы получим вторую половину списка.
варианты замечательные, но вот как их применить к лиспу... буду думать )))
спасибо.
Можно вот так
(Defun Func(L)
(Setq L1 '() L2 '())
(Loop
((eq L Nil) (Reverse L1))
(Push (Car L) L1)
(Push (Car (Reverse L) L2))
(Setq L (Cdr L))
(Setq L (Reverse (Cdr (Reverse L))))
)
)
Вот лисп я изучал...
спасибо...
...ушла читать про незнакомые слова )))