Программа, которая считает числа Леонарда в диапазоне от A до B

Question

Почему-то не получается вывести результат.

import java.util.Scanner;

public class Leonardo {

    private static final String NUMBER_A = "Введите число а: ";

    private static final String NUMBER_B = "Введите число b: ";

    private static final String ANSVER = "Количество чисел: ";


    public static void main(String[] args){

        Scanner console = new Scanner(System.in);

        int a = readDoubleValueFromConsole(console, NUMBER_A);

        int b = readDoubleValueFromConsole(console,NUMBER_B);

        printResult(countFromAtoB(a, b), ANSVER);


    }
    public static int countFromAtoB(int a, int b) {
        if (a > b) {
            return 0; // Некорректный ввод: a должно быть меньше или равно b
        } else {
            int count = 0;
            int leonardoNumber = 1;

            while (leonardoNumber <= b) {
                if (leonardoNumber >= a) {
                    count += 1;
                }
                leonardoSubsequence(leonardoNumber);
            }
            return count;
        }
    }
    public static int leonardoSubsequence(int n) {
        if (n == 0) return 1; // L(0) = 1
        if (n == 1) return 1; // L(1) = 1
        return leonardoSubsequence(n - 1) + leonardoSubsequence(n - 2) + 1; // L(n) = L(n-1) + L(n-2) + 1
    }
    //ввод
    public static int readDoubleValueFromConsole(Scanner console, String hint) {
        while (true) {
            System.out.printf(" %s = ", hint);
            String line = console.nextLine();
            try {
                return (int) Double.parseDouble(line);
            } catch (Exception e) {
                System.out.printf("  значение %s - некорректно!%n", line);
            }
        }
    }
    //вывод
    public static void printResult(int result, String hint){
        System.out.print(hint);
        System.out.print(result);
    }

}

Answer 1

В представленном коде результат может быть выведен, если НЕ будет выполнено начальное условие в цикле while (leonardoNumber <= b) метода countFromAtoB, то есть, если введённая пользователем верхняя граница диапазона b окажется меньше минимального числа Леонардо L(0) = 1.

Если же данный цикл начнёт выполняться, он окажется бесконечным, так как ни одна из переменных, входящих в его условие, НЕ изменяется внутри самого цикла, и программа просто зависнет.

При этом, не поможет и присваивание переменной leonardoNumber результата, возвращаемого из метода leonardoSubsequence, так как в начале он будет всегда возвращать 1, т.е. опять-таки leonardoNumber будет сохранять значение.

Поэтому необходимо ввести переменную n для индекса числа Леонардо, и исправить логику в цикле:

public static int countFromAtoB(int a, int b) {
    if (a > b || b < 1) {
        return 0;
    }
    int count = 0;
    int n = 0;

    while (true) {
        int leonardoNumber = leonardoSubsequence(n++);
        if (leonardoNumber > b) {
            break;
        }
        if (leonardoNumber >= a) {
            count++;
        }
    }
    return count;
}

Однако следует заметить, что такое исправленное решение не является оптимальным, так как при рекурсивном вычислении чисел Леонардо для N > 1 каждый раз теряется информация о ранее вычисленных значениях.

Можно либо заменить рекурсию обычным циклом с переприсваиванием ранее вычисленных значений, либо накапливать такие значения в списке или мапе при рекурсивных вызовах для их повторного использования (мемоизация).

// список для хранения чисел Леонардо
// инициализируется двумя первыми числами Леонардо с индексами 0 и 1
private static List<Integer> leos = new ArrayList<>(Arrays.asList(1, 1));

public static int leonardoSubsequence(int n) {
    if (n < leos.size()) {
        return leos.get(n); // возвращаем известное N-е число
    }
    int ln = leonardoSubsequence(n - 1) + leonardoSubsequence(n - 2) + 1;
    leos.add(n, ln); // запоминаем только что вычисленное "новое" значение
    return ln;
}

БЛОГ НА HUSL

Программа, которая считает числа Леонарда в диапазоне от A до B

Ответы (1 шт):