@max10110

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

Функция f определяется правилом: f(n) = n, если n < 3, и f(n) = f(n−1) +f(n−2) +f(n−3), если n ≥ 3. Напишите процедуру, вычисляющую f с помощью итеративного процесса. Уже 2 день сижу не могу решить. С помощью рекурсии все делается быстро и в лоб, с итеративным уже посложнее, но скорость растет в разы. Заранее спасибо!
  • Вопрос задан
  • 161 просмотр
Решения вопроса 2
jcmvbkbc
@jcmvbkbc
http://dilbert.com/strip/1998-08-24
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];
}
Ответ написан
john36allTa
@john36allTa
That`s calling Walker
// Опишем вашу функцию как есть
// 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]
  }
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы