Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 04.04.2011, 14:44
Новичок

Отправить личное сообщение для neitrosha Посмотреть профиль Найти все сообщения от neitrosha
 
Регистрация: 20.03.2011
Сообщений: 18

Последовательность Фибоначчи. Сумма в последовательности Фибоначчи
смысл задачи - каждое число можно представить как сумму чисел из ряда Фибоначчи.
1>2>3>5>8>13>21
Скажем, число 22-это 21+1, 13+8.
Не представляю, как можно сделать. Конечно, можно сделать для небольших чисел.
Так-то нужно, чтобы проверялись числа в последовательности, и их сумма сравнивалась с вводимым числом N, как мне кажется. Код для вывода последовательности-

program Project2;

{$APPTYPE CONSOLE}

uses
SysUtils;

var n,a,b,c:integer;
begin
write('n=');
readln(n);
writeln('Chisla fibonacci menshe ',n);
a:=1;
write(a,' ->');
b:=2;
repeat
c:=a+b;
a:=b;
write(a,' ->');
b:=c;
until c>=n;
readln
end.
  #2  
Старый 04.04.2011, 15:06
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Решается жадным методом - выбирается наибольшее число из ряда Фиб., не превосходящее остаток, отнимается от остатка до достижения нуля.
20 - 13 = 7
7 - 5 = 2
2 - 2 = 0
  #3  
Старый 04.04.2011, 16:48
Новичок

Отправить личное сообщение для neitrosha Посмотреть профиль Найти все сообщения от neitrosha
 
Регистрация: 20.03.2011
Сообщений: 18

то есть нужно создать еще один указатель?
I max:=максимальное число в ряду?
и вычитать предыдущее.
и в случае если не получается, то передвинуть на предыдущий и выполнять снова?

можно показать, я не знаю, как задать, чтобы он брал последнее число из ряда. и чтобы передвигал на предыдущий
  #4  
Старый 04.04.2011, 16:51
Новичок

Отправить личное сообщение для neitrosha Посмотреть профиль Найти все сообщения от neitrosha
 
Регистрация: 20.03.2011
Сообщений: 18

скажем, A[i], а потом А[i-1]?
  #5  
Старый 04.04.2011, 17:04
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

примерно так:
while (Fib[j] > Value) and (j > 0) do
Dec(j);
  #6  
Старый 04.04.2011, 18:54
Новичок

Отправить личное сообщение для neitrosha Посмотреть профиль Найти все сообщения от neitrosha
 
Регистрация: 20.03.2011
Сообщений: 18

у меня вопрос. а не фибоначчиева система исчисления тут используется, если зашла речь про остаток?

число 31.
последовательность до него-
1>2>3>5>8>13>21.
берется число 21, оно уже автоматически попадает, так как меньше 31
остаток 10. 10 сравниваем с 13, число 13 отпадает. 10 сравниваем с 8, берем, остаток 2. и сравнивая с 2, получим остаток 0.

в итоге, если использовать 0 и 1:
1*21+0*13+1*8+0*5+0*3+1*2+0*1. т.е. 31=21+8+2
  #7  
Старый 04.04.2011, 22:31
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

>а не фибоначчиева система исчисления тут используется
да
  #8  
Старый 04.04.2011, 22:59
Новичок

Отправить личное сообщение для neitrosha Посмотреть профиль Найти все сообщения от neitrosha
 
Регистрация: 20.03.2011
Сообщений: 18

у меня в теме внизу можете посмотреть, посоветовать?
там реализовано, но несколько не до конца, вернее, не так, как я хочу.
запутался
  #9  
Старый 05.04.2011, 07:55
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

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


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
qBasic сумма бесконечного ряда club Реализация, исходники, языки 1 04.04.2010 03:00
сумма длин максимальных последовательностей гость Задачи 0 03.11.2009 18:13
сумма делителей гость Математические алгоритмы 1 30.10.2009 00:25
Наименьшая сумма от 2-х точек до заданной. daishell Вычислительная геометрия 3 19.12.2008 10:56
Строки Фибоначчи seregarem Математические алгоритмы 3 17.05.2008 17:38