Учитывая этот псевдокод функции
f(0) = 1;
f(1) = 3;
f(n) = 3 * f(n - 1) - f(n - 2); // for n >= 2.
Есть ли нерекурсивный способ сделать это?
Что такое нерекурсивное решение для последовательности, подобной Фибоначчи, в Java?
Ответ 1
Да, все рекурсивные алгоритмы могут быть преобразованы в итеративные. Рекурсивное решение вашей проблемы - это что-то вроде (псевдокода):
def f(n):
if n == 0: return 1
if n == 1: return 3
return 3 * f(n-1) - f(n-2)
Поскольку вам нужно только помнить предыдущие два выражения для вычисления текущего, вы можете использовать что-то вроде следующего псевдокода:
def f(n):
if n == 0:
return 1
if n == 1:
return 3
grandparent = 1
parent = 3
for i = 2 to n:
me = 3 * parent - grandparent
grandparent = parent
parent = me
return me
Это просто сначала обрабатывает условие "рекурсивного" завершения, затем выполняет итерацию, где он обычно называет себя. На каждой итерации вы вычисляете текущий термин, затем вращаете члены через grandparent и parent.
Нет необходимости держать бабушку и дедушку, как только вы вычислили текущую итерацию, поскольку она больше не используется.
На самом деле можно сказать, что итеративное решение лучше (с точки зрения производительности), поскольку термины не пересчитываются, поскольку они находятся в рекурсивном решении. Рекурсивное решение имеет определенную элегантность, хотя (обычно рекурсивные решения).
Конечно, как и последовательность Фибоначчи, это значение, которое вы вычисляете, быстро растет, поэтому, если вы хотите, чтобы, пожалуй, самое быстрое решение (вы должны проверить все требования к производительности, включая мои), предварительно рассчитанная таблица поиска может быть способом идти.
Используя следующий код Java для создания таблицы с длинными значениями (условие while - это всего лишь хитроумный трюк, чтобы перехватить переполнение, то есть точку, в которой вы можете остановить построение массива):
class GenLookup {
public static void main(String args[]) {
long a = 1, b = 3, c;
System.out.print ("long lookup[] = { " + a + "L, " + b + "L");
c = 3 * b - a;
while ((c + a) / 3 == b) {
System.out.print (", " + c + "L");
a = b; b = c; c = 3 * b - a;
}
System.out.println (" };");
}
}
дает вам определение массива, которое вы можете просто подключить к функции поиска, как показано в следующем примере:
public static long fn (int n) {
long lookup[] = { 1L, 3L, 8L, 21L, 55L, 144L, 377L, 987L, 2584L, 6765L,
17711L, 46368L, 121393L, 317811L, 832040L, 2178309L, 5702887L,
14930352L, 39088169L, 102334155L, 267914296L, 701408733L,
1836311903L, 4807526976L, 12586269025L, 32951280099L, 86267571272L,
225851433717L, 591286729879L, 1548008755920L, 4052739537881L,
10610209857723L, 27777890035288L, 72723460248141L, 190392490709135L,
498454011879264L, 1304969544928657L, 3416454622906707L,
8944394323791464L, 23416728348467685L, 61305790721611591L,
160500643816367088L, 420196140727489673L, 1100087778366101931L,
2880067194370816120L, 7540113804746346429L };
if ((n < 1) || (n > lookup.length))
return -1L;
return lookup[n-1];
}
Интересно, что WolframAlpha предлагает формульный подход, который даже не использует итерацию. Если вы перейдете на их сайт и введите f(0)=1, f(1)=3, f(n)=3f(n-1)-f(n-2), вы получите формулу:
К сожалению, это может быть не так быстро, как итерация, учитывая ограниченное количество входных значений, которые приводят к чему-то, что может поместиться в Java long, поскольку оно использует с плавающей точкой. Это почти наверняка (но, опять же, вам нужно будет проверить это) медленнее, чем поиск в таблице.
И, вероятно, он идеален в мире математики, где реальные ограничения, такие как бесконечное хранилище, не вступают в игру, но, возможно, из-за пределов точности IEEE, он разбивается при более высоких значениях n.
Следующие функции эквивалентны этому выражению и поисковому решению:
class CheckWolf {
public static long fn2 (int n) {
return (long)(
(5.0 - 3.0 * Math.sqrt(5.0)) *
Math.pow(((3.0 - Math.sqrt(5.0)) / 2.0), n-1) +
(5.0 + 3.0 * Math.sqrt(5.0)) *
Math.pow(((3.0 + Math.sqrt(5.0)) / 2.0), n-1)
) / 10;
}
public static long fn (int n) {
long lookup[] = { 1L, 3L, 8L, 21L, 55L, 144L, 377L, 987L, 2584L, 6765L,
17711L, 46368L, 121393L, 317811L, 832040L, 2178309L, 5702887L,
14930352L, 39088169L, 102334155L, 267914296L, 701408733L,
1836311903L, 4807526976L, 12586269025L, 32951280099L, 86267571272L,
225851433717L, 591286729879L, 1548008755920L, 4052739537881L,
10610209857723L, 27777890035288L, 72723460248141L, 190392490709135L,
498454011879264L, 1304969544928657L, 3416454622906707L,
8944394323791464L, 23416728348467685L, 61305790721611591L,
160500643816367088L, 420196140727489673L, 1100087778366101931L,
2880067194370816120L, 7540113804746346429L };
if ((n < 1) || (n > lookup.length)) return -1L;
return lookup[n-1];
}
Теперь нам нужна ссылка для сравнения:
public static void main(String args[]) {
for (int i = 1; i < 50; i++)
if (fn(i) != fn2(i))
System.out.println ("BAD: " + i + ": " + fn(i) + ", " + fn2(i)
+ " (" + Math.abs(fn(i) - fn2(i)) + ")");
else
System.out.println ("GOOD: " + i + ": " + fn(i) + ", " + fn2(i));
}
}
Это выведет:
GOOD: 1: 1, 1
GOOD: 2: 3, 3
GOOD: 3: 8, 8
GOOD: 4: 21, 21
GOOD: 5: 55, 55
GOOD: 6: 144, 144
GOOD: 7: 377, 377
GOOD: 8: 987, 987
GOOD: 9: 2584, 2584
GOOD: 10: 6765, 6765
GOOD: 11: 17711, 17711
GOOD: 12: 46368, 46368
GOOD: 13: 121393, 121393
GOOD: 14: 317811, 317811
GOOD: 15: 832040, 832040
GOOD: 16: 2178309, 2178309
GOOD: 17: 5702887, 5702887
GOOD: 18: 14930352, 14930352
GOOD: 19: 39088169, 39088169
GOOD: 20: 102334155, 102334155
GOOD: 21: 267914296, 267914296
GOOD: 22: 701408733, 701408733
GOOD: 23: 1836311903, 1836311903
GOOD: 24: 4807526976, 4807526976
GOOD: 25: 12586269025, 12586269025
Хорошо смотрим здесь, еще несколько:
GOOD: 26: 32951280099, 32951280099
GOOD: 27: 86267571272, 86267571272
GOOD: 28: 225851433717, 225851433717
GOOD: 29: 591286729879, 591286729879
GOOD: 30: 1548008755920, 1548008755920
GOOD: 31: 4052739537881, 4052739537881
GOOD: 32: 10610209857723, 10610209857723
GOOD: 33: 27777890035288, 27777890035288
GOOD: 34: 72723460248141, 72723460248141
GOOD: 35: 190392490709135, 190392490709135
GOOD: 36: 498454011879264, 498454011879264
Но тогда что-то начинает срываться:
BAD: 37: 1304969544928657, 1304969544928658 (1)
BAD: 38: 3416454622906707, 3416454622906709 (2)
BAD: 39: 8944394323791464, 8944394323791472 (8)
BAD: 40: 23416728348467685, 23416728348467705 (20)
BAD: 41: 61305790721611591, 61305790721611648 (57)
BAD: 42: 160500643816367088, 160500643816367232 (144)
BAD: 43: 420196140727489673, 420196140727490048 (375)
Тот факт, что приведенное выше мучительно близко, и что число цифр в ошибке пропорционально количеству цифр в результате, указывает на то, что это, вероятно, проблема потери точности.
После этой точки формульная функция только начинает возвращать максимальное длинное значение:
BAD: 44: 1100087778366101931, 922337203685477580 (177750574680624351)
BAD: 45: 2880067194370816120, 922337203685477580 (1957729990685338540)
BAD: 46: 7540113804746346429, 922337203685477580 (6617776601060868849)
И тогда наша функция поиска также ломается, так как числа слишком велики надолго:
BAD: 47: -1, 922337203685477580 (922337203685477581)
BAD: 48: -1, 922337203685477580 (922337203685477581)
BAD: 49: -1, 922337203685477580 (922337203685477581)
Ответ 2
Ответы верны, но они работают в O (n), в то время как вы можете сделать это в O (log n), экспоненциально быстрее. Заметим, что
[f(n) ] = [3 -1] [f(n-1)]
[f(n-1)] [1 0] [f(n-2)]
Пусть v n - вектор [f (n), f (n-1)] и A - матрица, как указано выше, поэтому вы получаете v n= A v n-1, поэтому v n= A n-1 v 1. Вычислите (n-1) -й степени матрицы A, используя двоичное возведение в степень и умножьте его на v 1. Подробнее о линейных повторениях см. здесь.
Ответ 3
Если вы задали вопрос о том, можно ли найти эквивалентное нерекурсивное определение функции, вы должны искать свойства последовательность Фибоначчи.
Ваша последовательность может быть найдена, написав Фибоначчи (без первых двух чисел) и удаляя каждый второй номер: 1, 3, 8, 21, 55, 144,...
sqrt5 = sqrt(5)
phi = ( 1 + sqrt5 ) / 2
fibonacci(n) = round( power( phi, n ) / sqrt5 )
f(n) = fibonacci( 2*n + 2 )
Ответ 4
Это просто, в Java решение выглядит так:
public int f(int n) {
int tmp;
int a = 3;
int b = 1;
for (int i = 0; i < n; i++) {
tmp = a;
a = 3 * a - b;
b = tmp;
}
return b;
}
Все рекурсивные решения могут быть преобразованы в итеративные решения (это также верно, см. этот пост), хотя это проще, если рекурсивное решение оно в хвостовой рекурсивной форма.
Вышеупомянутый алгоритм можно понимать как решение динамического программирования исходной рекурсии, он очень эффективен, так как ему нужно сохранить только два предыдущих значения в каждой точке итерации.
Ответ 5
[Ой, я думал, что это вопрос Perl. Тем не менее, код должен быть достаточно читабельным для Java-разработчика. ]
Это действительно просто перемещение рекурсии в пользовательскую область, но вы можете использовать:
sub f {
my ($n) = @_;
my @f = (1,3);
$f[$_] = 3 * $f[$_-1]- $f[$_-2] for 2 .. $n;
return $f[$n];
}
Конечно, это требует кэширования. Нет необходимости пересчитывать значения, которые мы уже знаем.
my @f = (1,3);
sub f {
my ($n) = @_;
$f[$_] = 3 * $f[$_-1]- $f[$_-2] for @f .. $n;
return $f[$n];
}
Ответ 6
Функция определена в терминах самого себя, поэтому в каком-то смысле любая реализация рекурсивна, если не придет какой-нибудь математик и говорит, что f(n) можно оценить без оценки f(n-1) и f(n-2). Как показали другие, есть способ реализовать его в Java-функции, которая не называет себя.
Ответ 7
def func(n):
f= array(n+1)
f[0]=1
f[1]=3
for i in 2:n :
f[i] = 3*f[i-1]-f[i-2]
return f[n]
Ответ 8
Последовательность чисел рядов Фибоначчи начинается с: 0,1,1,2,3,5,8,13,21,34,55....
это можно определить с помощью простого рекуррентного соотношения F (n) = F (n-1) + F (n-2) при n > 1 и двух начальных условий F (0) = 1 и F ( 1) = 1
Алгоритм Фибоначчи
//Вычисляет n-й номер Фибоначчи
//Ввод: неотрицательное целое число
//Вывод: n-й номер Фибоначчи
1. Begin Fibo
2. integer n, i;
3. if n<=1 then
4. return n;
5. else
6. F(0)<-0; F(1)<-1;
7. for i<-2 to n do
8. F(i)<-F(i-1)+F(i-2);
9. F(i-2)=F(i-2);
10. F(i-1)=F(i);
11. done
12. end if
13. end Fibo
Ответ 9
Вот просто функция с минимальной строкой кода и максимальной гибкостью.
Вы можете добавить любые "начальные значения" и любую другую рекурсивную "функцию", которую вы хотите просто.
def fib(n):
fibs = [1, 3] # <-- your initial values here
if n == 1:
return fibs[0]
if n == 2:
return fibs[:1]
for i in range(2, n):
fibs.append(3*fibs[-1] - fibs[-2]) # <-- your function here
return fibs
И результат:
n=10
print(fib(n))
[1, 3, 8, 21, 55, 144, 377, 987, 2584, 6765]
Ответ 10
Как просил @paxdiablo, я делаю это ответом. Это рекуррентное отношение и может быть решено нерекурсивно, подобно последовательности фибоначчи, упомянутой в другом ответе. Оказывается (обозначение Python).
def f(n):
return int((13**0.5-3)/(2*13**0.5)*((3-13**0.5)/2)**n + (0.5+3/(2*13**0.5))*((3+13**0.5)/2)**n)
Однако эта форумла, скорее всего, не работает для больших n, из-за ограниченной точности float. Данная версия python не работает для n = 30:
>>> print ([f(n) == 3 * f(n-1) + f(n-2) for n in range(2, 30)])
[True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, False]
>>> print([f(n) for n in range(30)])
[1, 3, 10, 33, 109, 360, 1189, 3927, 12970, 42837, 141481, 467280, 1543321, 5097243, 16835050, 55602393, 183642229, 606529080, 2003229469, 6616217487, 21851881930, 72171863277, 238367471761, 787274278560, 2600190307441, 8587845200883, 28363725910090, 93679022931153, 309400794703549, 1021881407041801]
Предупреждение: Я использовал "+" вместо "-", поэтому формула неверна. См. Комментарии.