Golden Ratio Fibonacci Hell

Question

В одном из моих java программ Я пытаюсь прочитать число, а затем использовать коэффициент золотой (1.618034), чтобы найти следующий наименьший число фибоначчи, его индекс. Например, если я вхожу в 100000, я должен вернуть «наименьшее число фибоначчи, которое больше 100000, является 26-м, а его значение 121393».

Программа также должна рассчитать число фибоначчи по индексу (case 1 в коде ниже), который я кодировал до сих пор, но я не могу понять, как решить проблему, описанную выше (case 2). У меня ужасный учитель, и я не совсем понимаю, что мне нужно делать. Я не прошу код, просто шаг за шагом, что я должен сделать для case 2. Я не могу использовать рекурсию. Спасибо за любую помощь. Я серьезно сосать, обмотав голову вокруг этого.

import java.util.Scanner; 
public class Fibonacci { 

public static void main(String args[]) { 
    Scanner scan = new Scanner(System.in); 

    System.out.println("This is a Fibonacci sequence generator"); 
    System.out.println("Choose what you would like to do"); 
    System.out.println("1. Find the nth Fibonacci number"); 
    System.out.println("2. Find the smallest Fibonacci number that exceeds user given value"); 
    System.out.println("3. Find the two Fibonacci numbers whose ratio is close enough to the golden number"); 

    System.out.print("Enter your choice: "); 
    int choice = scan.nextInt(); 
    int xPre = 0; 
    int xCurr = 1; 
    int xNew = 0; 

    switch (choice) 
    { 
     case 1: 
      System.out.print("Enter the target index to generate (>1): "); 
      int index = scan.nextInt(); 

      for (int i = 2; i <= index; i++) 
      { 
       xNew = xPre + xCurr; 
       xPre = xCurr; 
       xCurr = xNew; 
      } 
      System.out.println("The " + index + "th number Fibonacci number is " + xNew); 
       break; 
     case 2: 
      System.out.print("Enter the target value (>1): "); 
      int value = scan.nextInt(); 

    } 
} 
} 

Answer 1

Во-первых, вы должны понимать, что это за история этого золотого рациона. Дело в том, что числа Фибоначчи могут быть запрограммированы рекурсивно, но есть также формула для n-го числа Фибоначчи:

φ (n) = [φ^n - (-φ)^(- n)]/√5

где φ = (√5 + 1)/2 - Золотое соотношение (приблизительно 1.61803). Теперь | (-φ)^(- 1) | < 1, что означает, что вы можете вычислять φ (n) в качестве ближайшего целого числа к φ^n/√5 (если n = 1).

Итак, вычисляем √5, вычисляем φ, затем узнаем, как получить целое число, самое близкое к значению действительной переменной, а затем вычислять φ (n) с использованием формулы φ^n/√5 (или просто использовать " main "[φ^n - (-φ)^(- n)]/√5) в цикле и в этом цикле сравнивают φ (n) с номером, который вводится пользователем. Когда φ (n) превышает номер пользователя, помните n и φ (n).