Рекурсивная памятка Фибоначчи - PullRequest
Новая
       32

Рекурсивная памятка Фибоначчи

13 голосов
/ 24 октября 2011

Мне нужна помощь с программой, которую я пишу для моего класса Programming II в университете. Вопрос состоит в том, что вычисляется последовательность Фибоначчи с использованием рекурсии. Нужно сохранить вычисленные числа Фибоначчи в массиве, чтобы остановить ненужные повторные вычисления и сократить время вычисления.

Мне удалось заставить программу работать без массива и запоминания, теперь я пытаюсь реализовать это, и я застрял. Я не уверен, как это структурировать. Я гуглил и пролистал некоторые книги, но не нашел много, чтобы помочь мне решить, как реализовать решение. 

import javax.swing.JOptionPane;
public class question2
{
static int count = 0;
static int [] dictionary;

public static void main(String[] args)
{

int answer;
int num = Integer.parseInt(javax.swing.JOptionPane.showInputDialog("Enter n:"));

javax.swing.JOptionPane.showMessageDialog(null, 
        "About to calculate fibonacci(" + num + ")");

//giving the array "n" elements
dictionary= new int [num];

if (dictionary.length>=0)
dictionary[0]= 0;

if (dictionary.length>=1)
dictionary[0]= 0;
dictionary[1]= 1;


//method call
answer = fibonacci(num);

//output
JOptionPane.showMessageDialog(null,"Fibonacci("+num+") is "+answer+" (took "+count+" calls)");
}



  static int fibonacci(int n)
  {
count++;

// Only defined for n >= 0
if (n < 0) {
  System.out.println("ERROR: fibonacci sequence not defined for negative numbers.");
  System.exit(1);
}

// Base cases: f(0) is 0, f(1) is 1
// Other cases: f(n) = f(n-1) + f(n-2)/
if (n == 0) 
{
  return dictionary[0];
}

else if (n == 1) 
{
  return dictionary[1];
}

else
return dictionary[n] = fibonacci(n-1) + fibonacci(n-2);



}

}

Вышеприведенное неверно, конец моего метода фиби - главная проблема. Я понятия не имею, как заставить это добавить числа рекурсивно к правильным частям массива.

Ответы [ 11 ]

0 голосов
/ 18 марта 2018 
#include <stdio.h>
long int A[100]={1,1};
long int fib(int n){
    if (A[n])
    {
        return A[n];
    }
    else
    {
         return A[n]=fib(n-1)+fib(n-2);
    }
}
int main(){
    printf("%ld",fib(30));
}
Страница:
...