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

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

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

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

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

[klem4]

с лиспом к сожалению не знаком, но думаю там такое вполне можно сделать:

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.

тока список почистить забыл

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

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

Там, к сожалению, все совсем по-другому (( Как именно - я пока сама не очень понимаю
Цитируя моего препода: "На делфи вы пишете, КАК искать результат, а на ЛИСПе - ЧТО хотите получить".
И еще проблема - мы список не заполняем, а считаем уже данным. То есть считать добавленные элементы по ходу не получится.
Спасибо за готовность помочь!

А вообще, если интересно, это всё ради того, чтобы пройти матрицу (=список списков) по определенному маршруту.... На делфи это бы решилось кучей циклов, а здесь - еще большей кучей функций )))

[klem4]

ну а если так (алгоритм остается тот-же):

// ...
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;
// ...

[hardcase]

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


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

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

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

варианты замечательные, но вот как их применить к лиспу... буду думать )))
спасибо.

[Fanat]

Можно вот так

(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))))
)
)

Вот лисп я изучал...

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

спасибо...
...ушла читать про незнакомые слова )))

[hardcase]

Можно вот так

(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))))
)
)

Вот лисп я изучал...

Это и есть вариант мисс_граффити, предложенный в первом сообщении темы.