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

Question

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

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

Обновить:

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

Answer 1

Там нет реального ответа, так как это был тупой вопрос.

Answer 2

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

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

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;
  ...
}

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

Answer 3

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

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

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

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

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