Напишите эффективный код для нижеприведенной программы?

Question

Я хотел проверить, для 12-значных чисел, если они принадлежали к серии Фибоначчи. Я написал следующий код, но он кажется неэффективным, и я столкнулся с ошибкой тайм-аута. Как я могу оптимизировать свой код?

Scanner sc=new Scanner(System.in); 
    List<Long> test_list=new ArrayList<>(); 
    List<String> final_list=new ArrayList<>(); 
    long cases=sc.nextLong(); 

    for(int i=0;i<cases;i++) 
    { 
     long input=sc.nextLong(); 
     test_list.add(input); 
    } 

    for(int j=0;j<test_list.size();j++) 
    { 
     long check_number=test_list.get(j); 
     long a=0l,b=1l,c=0l; 
     while(c<check_number) 
     { 
      c=a+b; 
      a=b; 
      b=c; 
     } 
     if(c == check_number) 
     { 
      final_list.add("IsFibo"); 
     } 
     else 
     { 
      final_list.add("IsNotFibo"); 
     } 

    } 

    for(String s:final_list) 
    { 
     System.out.println(s); 
    } 

Answer 1

Вы можете сделать что-то вроде этого:

Scanner sc = new Scanner(System.in); 
    List<Long> fibonaci = new ArrayList<Long>(); // Added to store already calculated fibo number 
    fibonaci.add(0L); 
    fibonaci.add(1L); 

    List<Long> test_list = new ArrayList<>(); 
    List<String> final_list = new ArrayList<>(); 
    long cases = sc.nextLong(); 

    for (int i = 0; i < cases; i++) { 
     long input = sc.nextLong(); 
     test_list.add(input); 
    } 

    for (int j = 0; j < test_list.size(); j++) { 
     long check_number = test_list.get(j); 
     long a = fibonaci.get(fibonaci.size()-2), b = fibonaci.get(fibonaci.size() - 1), c = 0l; 
     if (check_number > b) { //To Check whether last number in fibo is less than input 

      while (c < check_number) { 
       c = a + b; 
       fibonaci.add(c); 
       a = b; 
       b = c; 
      } 
     } 
     if (c == check_number || fibonaci.contains(check_number)) { 
      final_list.add("IsFibo"); 
     } else { 
      final_list.add("IsNotFibo"); 
     } 

    } 
    for (String s : final_list) { 
     System.out.println(s); 
    } 

Что я сделал:

• Взял один дополнительный список для хранения уже вычисленных fibonaci номера.
• Проверьте, не превышает ли это число последнего числа фибоначчи.
• Если да, то подсчитайте следующий номер фибоначчи, пока ввод не станет меньше, чем число фибоначчи.
• Если нет, то проверьте, существует ли ваш номер в списке фибоначчи или нет.

Answer 2

простой хард-код для 12-значных номеров фибоначчи.

long f55 = 139583862445L; 
long f56 = 225851433717L; 
long f57 = 365435296162L; 
long f58 = 591286729879L; 
long f59 = 956722026041L;  

for(int j=0;j<test_list.size();j++) 
    { 
     long n=test_list.get(j); 


     if(n == f55 || n == f56 || n == f57 || n == f58 || n == f59) 
     { 
      final_list.add("IsFibo"); 
     } 
     else 
     { 
      final_list.add("IsNotFibo"); 
     } 

    }