Помогите, пожалуйста, с решением задачи на двунаправленные списки
Дан двунаправленный список целых чисел. Переставить элементы списка так, чтобы сначала следовали элементы, являющиеся числами Фибоначчи, а затем остальные элементы списка.




Добавлено через 1 мин.
вот что я сделал, помогите с процедурой "fib" (определяет, является ли элемент списка числом фибоначчи и переставляет его в начало списка)

program spis;
uses crt;
type
pnode=^tnode;
tnode=record
val:integer;
pred,next:pnode;
end;
var
first,last,temp,temp2:pnode;
i,n,x,g:integer;
y:array[1..10] of integer;
 
procedure vvod(var first1,last1:pnode; xx:integer);
begin
if first1=nil then
begin
new(first1);
first1^.next:=nil;
first1^.pred:=nil;
last1:=first1;
end else
begin
new(last1^.next);
last1^.next^.pred:=last1;
last1:=last1^.next;
last1^.next:=nil;
end;
last1^.val:=xx;
end;
 
procedure fib(m:integer);
var i,j,k:integer;
temp,temp2:pnode;
begin
i:=1; j:=1; k:=1;
while k<m do
begin
k:=j+i;
i:=j;
j:=k;
end;
if k=m then
begin
 
while temp^.next<>nil do
begin
temp:=first;
if temp^.next^.val=m then begin
temp2:=temp^.next;
temp2^.pred:=temp^.pred;
temp^.next:=temp2^.next;
temp2^.next:=temp;
temp^.pred:=temp2;
end;
temp:=temp^.next;
end;
end;
end;
 
procedure vivod(first1:pnode);
begin
if first1=nil then
begin
writeln('Spisok pust');
exit;
end;
while first1<>nil do
begin
writeln(first1^.val);
first1:=first1^.next;
end;
end;
 
 
begin
clrscr;
write('n='); readln(n);
for i:=1 to n do
begin
write('x='); readln(x);
vvod(first,last,x);
y[i]:=x;
end;
for i:=1 to n do
begin
fib(y[i]);
end;
vivod(first);
readln;
end.

Тегами [CОDE=pas][/CОDE] пользуйся, программы с ним легче воспринимаются, чем простым куском текста...

Сообщение отредактировано: volvo - 21.09.2010 14:41

Стоп. Задача на списки? При чем тогда массив? Обходись без него, он не нужен для решения поставленной задачи.

А в процедуре Fib у тебя ошибка:

while temp^.next<>nil do
begin

А чему, собственно, в этот момент (перед началом цикла) равен temp? Это ж у тебя локальная, ничем не инициализированная переменная, там мусор. С большой степенью вероятности программа вылетит с ошибкой, но может и просто зависнуть (смотря, какой компилятор)...

хм, хорошо, буду без массивов
перед началом цикла наверное нужно принять temp:=first;

у меня программа работает, но не переставляет элементы равные числам фибоначчи в начало (наверное потому что в процедуре лажа написана...не погу понять что там писать нужно...)

Сообщение отредактировано: ссс - 21.09.2010 14:58

Работать и работать правильно - это разные вещи, да? Я ж не виноват, что компилятор Турбо Паскаля не отслеживает такие вещи? Вот FPC - отлавливает:

n=3
x=6
x=8
x=7
No heap dump by heaptrc unit
Exitcode = 216
Runtime error 216 at $004015F8
  $004015F8  FIB,  line 56 of f:/programs/pascal/__fpf.pp
  $004017FC  main,  line 87 of f:/programs/pascal/__fpf.pp
  $00408D71

(я добавил отладочный модуль, если что)

Так что, что-то делать надо... Подумай, что именно. Для начала - как определить, принадлежит ли заданное число последовательности Фибоначчи? Для этого совсем не надо строить всю эту последовательность Все проще: есть тест Ira M. Gessel, согласно которому число N является числом Фибоначчи тогда и только тогда, когда 5*N²+4 или 5*N²-4 - полный квадрат.

Как пример: 13 -> 5*13²-4 = 29²... Значит, это число - Фибоначчиево. Но это так, лирическое отступление. На самом деле я бы попробовал написать функцию сортировки, в которой функция сравнения элементов будет подобрана так, что числа Фибоначчи будут переноситься в начало списка, а остальные - оставаться на своих местах. Для сортировки списка (особенно двухсвязного) лучше использовать метод вставок...

Еще кое-что. Зачем тебе надо извращаться с указателями? Лучше работай со значениями элементов, будет гораздо проще...

Обычно в учебных задачах на списки требуется работать как раз с указателями... Хотя, конечно, не факт, что это тот случай.


я бы проверку, является ли число числом Фибоначчи выделила в функцию. а перестановку сделала отдельной процедурой...

по сути, деятельность должна выглядеть примерно так:
0. идем по списку с начала (curr:=head)
1. если элемент, следующий за текущим (curr) - число Фибоначчи, его надо переставить.
2. запоминаем указатель на переставляемый элемент (fib)
3. убираем его из списка, "перекинув" указатели соседей:
curr^.next:=curr^.next^.next
curr^.next^.next^.prev:=curr //разумеется, если этот элемент существует. надо проверять
4. вставляем в начало списка наш элемент fib.
fib^.prev:=nil;
fib^.next:=head;
head:=fib;

если перестановки не было, переходим к анализу следующего элемента (curr:=curr^.next), иначе ничего не делаем.
идем к шагу 1.

и так, пока список не кончится.
получается, первый элемент мы не анализируем на "фиббоначиевость". но в этом и необходимости нет.