Представить натуральное число в виде суммы чисел Фибоначчи так, чтобы в сумме не было соседних чисел Фибоначчи

Рассмотрим последовательность натуральных чисел a(0),a(1),..., образованную по закону- a(k)=a(k-1)+a(k-2), где a(0)=1,a(1)=2.Любое натуральное число n можно единственным способом представить с помощью некоторых неотрицательных целых b(0),b(1),..b(t) в виде b(t)a(t)+b(t-1)a(t-1)+...+b(0)a(0). При этом 0<= b(i)<=1, i=0,1,...t, b(t)<>0 и две единицы не могут стоять рядом. Дано натуральное число n. Найти соответствующие b(0),...,b(t).

Помогите, пожалуйста, с программой и с пояснением

0

Ekaterinaif, пожалуйста, темы называйте осмысленно.

Я переименовал Вашу тему из бессмысленного "Одномерные массивы" в соответствующее Вашему заданию "Представить натуральное число в виде суммы чисел Фибоначчи так, чтобы в сумме не было соседних чисел Фибоначчи". Согласитесь, осмысленное и понятное название темы - уже половина решения.

Ряд Фибоначчи: 1, 1, 2, 3, 5, 8, 13 и так далее. Каждое следующее число Фибоначчи является суммой двух предыдущих. Обратите внимание: закон образования (Вашей) последовательности "a" тот же самый, что и у чисел Фибоначчи, а нулевой и первый члены последовательности "a" - это второй и третий члены ряда Фибоначчи. Получается, что последовательности "a" - это ряд Фибоначчи без первого члена.

Фактически, Вам по заданию требуется представить число так, как я указал в новом названии Вашей темы, и напечатать ряд из 0 и 1 такой, чтобы 1 соответствовали местам расположения слагаемых из последовательности "a", которые есть в сумме.

Алгоритм нахождения членов последовательности "a", входящих в сумму, равную n, достаточно прост.

• Нужно сначала найти такое максимальное t, чтобы было a(t)<=n, и вычесть n := n - a(t), и скопировать значение t в другую переменную, например, k. Присвоить b(t) := 1.
• Затем, до тех пор, пока n > 0, повторять следующие действия:
  • присвоить k := k - 2 (вычитаем 2, чтобы в сумме не было двух соседних членов последовательности "a");
  • присваивать k := k - 1 (вычитать из k по единичке) до тех пор, пока n > a(k);
  • присвоить n := n - a(k) и b(k) = 1;
• после всего этого напечатать получившуюся последовательность b, от b(0) до b(t) включительно.

Так как разложение из Вашего задания существует на самом деле, последовательность b будет обязательно найдена.

Вряд ли в Вашей учебной задаче предполагается использование длинной арифметики, поскольку применение длинной арифметики в учебных задачах всегда оговаривается отдельно. Следовательно, нужно обходиться стандартными типами данных. Целые числа в Pascal ABC имеют тип integer.

Максимальное число Фибоначчи, которое может поместиться в тип integer -
соток шестое число Фибоначчи F(46)=1836311903.
Максимальное n будет не более максимального числа, представимого типом integer -
MaxInt=2³¹-1=2147483647.

Для простоты можно представить последовательность "a" в виде массива из 45 элементов, с индексами от 0 до 44, в который заранее поместим числа Фибоначчи от F(2) до F(46).
Числа последовательности "b" будем записывать в такой же массив. В него будем писать только 1, поскольку все глобальные числовые переменные инициализируются нулями, и нули в массиве b уже есть.
Вышеописанный алгоритм теперь можно дополнительно упростить, упразднив явный поиск t. Получится так:

• Присваиваем переменной k значение, на 2 большее максимального индекса последовательности "a";
• Затем, до тех пор, пока n > 0, повторять следующие действия:
  • присвоить k := k - 2 (вычитаем 2, чтобы в сумме не было двух соседних членов последовательности "a");
  • присваивать k := k - 1 (вычитать из k по единичке) до тех пор, пока n > a(k);
  • если t ещё не найдено (это будет t = 0), то присваиваем t := k (это будет сделано один раз);
  • присвоить b(k) = 1 и n := n - a(k);
• после всего этого напечатать получившуюся последовательность b, от b(0) до b(t) включительно.

Программа:

0