Как написать программу C для последовательности Фибоначчи без векторов/рекурсии?

Question

Последовательность, которую я пытаюсь достичь, похожа на Fibonacci, но вместо N-го числа N-1 + N-2 мы имеем значение K, а N-й номер будет N-1 + N-2 + ... + N-K.

Я хочу написать программу C для записи последовательности до N-го номера с K и N в качестве входных данных. Он НЕ ДОЛЖЕН использовать векторы или рекурсию.

Update:

Там нет никакого возможного решения, это было упражнение, чтобы доказать необходимость вектора (массива) в решении некоторых проблем.

Answer 1

Нет никакого реального ответа, поскольку это был вопрос о мертвецах.

Answer 2

Вам нужно какое-то хранилище для (по крайней мере) предыдущих значений K, и я полагаю, что суть вашего вопроса заключается в том, что вы можете использовать для этого.

Вы не можете использовать параметры стека/функции вызова, потому что вы не должны рекурсивно. Вы не можете использовать «вектор», по которому, я полагаю, вы имеете в виду массив. Было бы крайне беспорядочно использовать отдельные локальные переменные, и это было бы совершенно невозможно сделать, если бы не была очень низкая граница значений K. Единственными альтернативами, которые я вижу, являются

1. Некоторые ароматы связанного списка. (Но будьте осторожны - связанный список может считаться «вектором» в очень свободном смысле этого термина.)
2. Внешний файл. (Yuck!)

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

Я оставляю фактическую реализацию как упражнение, которым оно является.

Answer 3

Отказ от ответственности - это не, повторяю НЕ, что ваш профессор ищет, но ...

Если вы знаете, как решить recurrence relations, вы могли бы найти замкнутую форму из отношение для каждого значения K и просто вычислить, что (нет цикла, без хранения промежуточных значений). Например, ^п-й Фибоначчи число может быть вычислена с помощью функции

long double fib_closed(unsigned int n) 
{ 
    long double sqrt_5 = sqrtl(5.0); 
    long double phi = (1 + sqrt_5)/2.0; 
    long double psi = (1 - sqrt_5)/2.0; 

    return floorl((powl(phi, n) - powl(psi, n))/sqrt_5); 
} 

В вашем случае, вы бы иметь различное рекуррентное соотношение для каждого K (то есть, рекуррентное соотношение для N- 1 + N-2 + N-3 будет отличаться от рекуррентного отношения для N-1 + N-2 + N-3 + N-4 и т. Д.), Поэтому вам нужно будет написать столько функций, сколько значений K вы хотите использовать:

switch(K) 
{ 
    case 3: return f_closed_3(n); break; 
    case 4: return f_closed_4(n); break; 
    ... 
} 

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