IPB
ЛогинПароль:

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным.
В описании темы указываем язык!!!

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

 
 Ответить  Открыть новую тему 
> разделить список на 2 части, LISP
сообщение
Сообщение #1


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


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

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

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


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


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

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.


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

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


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


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

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


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


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


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



--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


code warrior
****

Группа: Пользователи
Сообщений: 484
Пол: Мужской
Реальное имя: Славен

Репутация: -  8  +


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


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

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


--------------------
ИзВ ин ИтЕ зА нЕ рОв НЫй П оч ЕРк
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


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


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Fanat
***

Группа: Пользователи
Сообщений: 261
Пол: Мужской
Реальное имя: Сергей

Репутация: -  5  +


Можно вот так

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

Вот лисп я изучал... smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


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


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


code warrior
****

Группа: Пользователи
Сообщений: 484
Пол: Мужской
Реальное имя: Славен

Репутация: -  8  +


Цитата(Fanat @ 6.09.2007 9:39) *
Можно вот так

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

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

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


--------------------
ИзВ ин ИтЕ зА нЕ рОв НЫй П оч ЕРк
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 2.10.2020 3:12
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name