Последовательность Фибоначчи. Сумма в последовательности Фибоначчи, сравниваемая с числом N

[Neitrosha]

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

[KobolD]

Поясни вот какой момент, тебе надо найти комбинацию с наименьшем количеством слогаемых из ряда фибоначи (т.е. 22= 21+1) или тебе надо найти все возможные комбинации для числа (22 = 21+1, 22=13+8+1, 22=13+5+3+1 и т.д)?
Но в любом случае тебе надо будет делать массив с последовательностью где первый и второй элементы это 1 и 2, а дальше A[i]=A[i-1]+A[i-2]

[Neitrosha]

скорее второй вариант, возможные комбинации

так-то, как я почитал, можно попробовать жадный метод, но не знаю его вообще.

можно продемонстрировать часть кода?

[KobolD]

я в паскале не очень, но смысл программы такой, если те сильно поможет то могу на C# навоять, но алгоритм такой:
1. Перебираешь числа фибоначи и сравниваешь с заданым числом, если число фибоначи меньше заданного то увеличиваеш счетчик n, если больше то переходишь к пункту 2.
2. Создаешь массив размерностью n и записываешь в него числа фибоначи.
А дальше тебе надо перебрать все комбинации этих чисел, причем так чтобы не повторялись. Я лично это делал так: Создавал массив размерностью n тип bool и использовал его как двоичный счетчик. Т.е. если элемент счетчика равер true то включаем элемент из массива фибоначи в сумму. Ну и в конце проверяем равна ли сумма нужному числу. Потом увеличиваем счетчик на единицу. Вот пример счетчика http://www.programmersforum.ru/showthread.php?t=142280

[Neitrosha]

как же всё сложно..

посижу, подумаю пока что

был бы очень благодарен, если хотя бы на С попытались объяснить.

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

вот уже есть на экране последовательность Фибоначчи,скажем, до 50.
вводим число Х, которое не больше 50, а дальше уже действительно не знаю, как делать

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

число 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

[KobolD]

Сообщение от Neitrosha

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

Этот способ не даст тебе все варианты, ты получишь 31 = 21+8+2, но пропустишь 31=21+5+3+2

static void Main(string[] args)
        {
            Console.WriteLine("Введите число");
            int N = Convert.ToInt32(Console.ReadLine());
            if (N < 3)//выходим если число меньше трех
                return;
            int i = 2;//число элементов фибоначи
            int F=2;
            int Pre1 = 1;
            while ((F+Pre1) <= N)//Ищем числа фибоначи которые меньше (или равны) введеному числу
            {
                F += Pre1;
                Pre1 = F - Pre1;
                i++;
            }
            int[] Fibonachi=new int[i];//Создаем массив для чисел фибоначи
            Fibonachi[0]=1;//Заполняем первые два элемента
            Fibonachi[1]=2;
            bool[] Maska = new bool[i];//Создаем масив маски для перебора
            int Sum;//Сумма элементов
            string OutPut;//Строка для вывода ответов

            for (int j=2;j<i;j++)//Заполняем массив числами фибоначи
                Fibonachi[j]=Fibonachi[j-1]+Fibonachi[j-2];
            while (Sdvig(ref Maska))//перебираем все варианты сочетаний
            {
                Sum=0;//обнуляем суму
                OutPut="";//обнуляем строку
                for (int j = 0; j <i; j++)//для всех элементов массива берем сумму по маске (т.е. если в маске стоит true то добавляем элемент в сумму)
                    if (Maska[j])
                    {
                        Sum+=Fibonachi[j];//Накапливаепм сумму
                        if (Sum > N)//Если смма больше введеного числа переходим к след комбинации (сделано для ускорения работы цыкла)
                            break;
                        if (OutPut=="")//формуруем строку ответа
                            OutPut=Fibonachi[j].ToString();
                        else
                            OutPut += "+" + Fibonachi[j].ToString();
                    }
                if (Sum==N)//Если сумма равна введеному числу то выводим на экран.
                    Console.WriteLine(OutPut+"="+N.ToString());
            }
            Console.ReadLine();



        }
        static bool Sdvig(ref bool[] Mask)//Процедура выполняет побитовое увеличение на единичку
        {
            bool CF = true;
            for (int i = 0; i < Mask.Length; i++)
            {
                if ((CF) && (Mask[Mask.Length - 1]) && (i == Mask.Length - 1))//достигнут конец перебора (все единицы)
                    return false;
                if (CF)
                {
                    Mask[i] = !Mask[i];
                    if (Mask[i])
                        return true;
                }

            }
            return true;
        }