Как решить задачу итеративным процессом?

Question

[Макс]

Функция f определяется правилом: f(n) = n, если n < 3, и f(n) = f(n−1) +f(n−2) +f(n−3), если n ≥ 3. Напишите процедуру, вычисляющую f с помощью итеративного процесса. Уже 2 день сижу не могу решить. С помощью рекурсии все делается быстро и в лоб, с итеративным уже посложнее, но скорость растет в разы. Заранее спасибо!

Answer 1

[jcmvbkbc]

f(n) = n, если n < 3, f(n) = f(n−1) +f(n−2) +f(n−3), если n ≥ 3

Ну, начиная с четвёртого значения равны сумме предыдущих трёх. В чем сложность?

int f(int n)
{
    int v[3] = {0, 1, 2};
    int i;
    if (n < 3)
        return n;
    for (i = 3; i <= n; ++i)
        v[i % 3] = v[0] + v[1] + v[2];
    return v[n % 3];
}

Answer 2

[Somewhere Intech]

// Опишем вашу функцию как есть
// f(n) = f(n - 1) + f(n - 2) + ... + f(n-n)
const f = n => {
  if (n < 3) return n
  for ( var i=1, x = 0; i <= n; i++ )
    x += f(n-i)
  return x
}, // смотрим 10 результатов вычислений и видим ярковыраженную последовательность
//Понимая что итерации здесь избыточны, выводим формулу:
  fn = n => n < 4 ? n : 3 * (2 ** (n-3))
// проверяем
let i = 1;
while (++i < 1000)
  if (f(i) !== fn(i)) 
    throw new Error('Where is my mind? %`')
console.log('finished')

upd: если функция f(n) = f(n-1) + f(n-2) + f(n-3)

var numbers = [0,1,2], // кэш чисел для оптимизации повторных вычислений
   f = n => {
    for (let i = numbers.length; i <= n; i++)
      numbers.push(numbers[i-1] + numbers[i-2] + numbers[i-3])
    return numbers[n]
  }

Comments

[jcmvbkbc]

// Опишем вашу функцию как есть
// f(n) = f(n - 1) + f(n - 2) + ... + f(n-n)

в задании другая функция.

[Somewhere Intech]

jcmvbkbc, а я думал там недоописанная последовательность x)