Программа для дезинтеграции числа на номера фибоначчи

Question

Я пытаюсь написать программу в C. Я хочу разложить число (только если его можно разложить) на меньшие числа, которые могут быть только числом фибоначчи. Например:

Если у меня есть число п = 20, то мой вывод должен быть 1,1,2,3,5,8 так, когда я добавить эти меньшие числа Фибоначчи это дает мне номер 20.

Answer 1

Его можно уменьшить до subset-sum problem, где множество - число фибоначчи, меньшее/равно заданному числу.

Сначала сгенерируйте все числа меньше/равно заданному числу n. C-подобный псевдокод:

int i = 1; 
int* arr = //sufficiently large array 
arr[0] = arr[1] = 1; 
while (arr[i] <= n) { 
    i++; 
    arr[i] = arr[i-1] + arr[i-2]; 
} 

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

D(x,i) = false x<0 
D(0,i) = true 
D(x,0) = false x != 0 
D(x,i) = D(x,i-1) OR D(x-arr[i]-1,i) 

позже вы, просто нужно повторить свои шаги и выяснить фактическое количество используемого DP:

Псевдо код:

x = n; 
i = number_of_candidates; 
while (i>0) { 
    if (x >= arr[i] && DP[i][x-arr[i]]) { 
     //arr[i] is in the solution, add it 
     x = x-arr[i]; 
    } 
    i--; //do it for both cases, successful 'if' or not. 
} 

Общая сложность ответа - O(nlogn), а узким местом является решение DP.
Обратите внимание, что число «кандидатов» находится в O(logn), так как номер i-й номер фибоначчи находится в O(phi^i).

Answer 2

Каждое целое число имеет представление как сумму уникальных чисел Фибоначчи. Это легко доказать по индукции: если такое представление существует для всех чисел с точностью до Fib (n), то Fib (n) + k для k в 1, 2, ..., Fib (n-1) имеет представление Fib (n) + (представление для k). Доказательство предлагает простой рекурсивный алгоритм для нахождения представления для N: выберите наибольшее число Фибоначчи, которое меньше N, скажем, это Fib (k). Тогда найдем представление для N-Fib (k).