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

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Двунаправленные списки
сообщение
Сообщение #1





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

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


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




Добавлено через 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 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






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

А в процедуре Fib у тебя ошибка:
while temp^.next<>nil do
begin

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





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

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


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

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

Сообщение отредактировано: ссс -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






Цитата
у меня программа работает, но не переставляет элементы
Работать и работать правильно - это разные вещи, да? Я ж не виноват, что компилятор Турбо Паскаля не отслеживает такие вещи? Вот 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

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

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

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

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


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

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

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


Цитата(volvo @ 21.09.2010 17:37) *

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

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

Цитата
помогите с процедурой "fib"

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

по сути, деятельность должна выглядеть примерно так:
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.

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


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

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

 





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