IsFibo не возвращает желаемый результат

Question

Это решение, о котором я думаю о проблеме IsFibo HackerRank. (https://www.hackerrank.com/challenges/is-fibo). Мне интересно, почему он не вернет «IsFibo» за 5. Моя логика, вероятно, ошибочна, и я был бы признателен, если кто-то отметит мою ошибку. Вот код:

import java.io.*; 
import java.util.*; 
import java.text.*; 
import java.math.*; 
import java.util.regex.*; 

public class Solution { 
    public static ArrayList<BigInteger> fibList = new ArrayList<BigInteger>(); 

    public static void main(String[] args) { 
    /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ 
     Scanner in = new Scanner(System.in); 
     int numCases = in.nextInt(); 

     fibList.add(BigInteger.valueOf(0)); 
     fibList.add(BigInteger.valueOf(1)); 

     while(in.hasNextLine()) { 
      System.out.println(checkFibo(in.nextBigInteger())); 
      System.out.println(fibList); 
     } 
    } 

    public static String checkFibo(BigInteger i) { 
     int lastIndex = fibList.size() - 1; 
     int compareRes = i.compareTo(fibList.get(lastIndex)); 

     System.out.println("Last fib num: " + fibList.get(lastIndex)); 
     System.out.println("CompareRes: " + compareRes); 

     switch(compareRes) { 
      case 0: 
       return "IsFibo"; 
      case 1: 
       BigInteger newFib = fibList.get(lastIndex-1).add(fibList.get(lastIndex)); 
       fibList.add(newFib); 
       checkFibo(i); 
       break; 
      default: 
       break; 
     } 

     return "IsNotFibo"; 

    } 
} 

Answer 1

У вас есть две проблемы с вашим кодом:

1. Случай 1: не проходит обратно возвращаемое значение из рекурсивного вызова
2. случае -1, которая падает по умолчанию реализация полностью игнорируется (т.е. код не может обрабатывать меньшие входов после уже обработано более крупных)

Вот рабочий код:

import java.math.BigInteger; 
import java.util.ArrayList; 
import java.util.Scanner; 

public class Solution { 
    public static ArrayList<BigInteger> fibList = new ArrayList<BigInteger>(); 

    public static void main(String[] args) { 
    /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ 
     Scanner in = new Scanner(System.in); 

     fibList.add(BigInteger.valueOf(0)); 
     fibList.add(BigInteger.valueOf(1)); 

     while(in.hasNextLine()) { 
      BigInteger nextBigDecimal = in.nextBigInteger(); 
      System.out.println("input:" + nextBigDecimal); 
      System.out.println("isFibo: " + checkFibo(nextBigDecimal)); 
      System.out.println(fibList); 
     } 
    } 

    public static boolean checkFibo(BigInteger i) { 
     int lastIndex = fibList.size() - 1; 
     int compareRes = i.compareTo(fibList.get(lastIndex)); 

     System.out.println("Last fib num: " + fibList.get(lastIndex)); 
     System.out.println("CompareRes: " + compareRes); 

     boolean isFibo = false; 

     switch(compareRes) { 
      case 0: 
       isFibo = true; 
       break; 
      case 1: 
       BigInteger newFib = fibList.get(lastIndex-1).add(fibList.get(lastIndex)); 
       fibList.add(newFib); 
       isFibo = checkFibo(i); 
       break; 
      case -1: 
       isFibo = fibList.contains(i); 
       break; 
     } 
     return isFibo; 
    } 
}