Main.java - master - hel_bumer/Recursive

Main.java
93 строки3 KB
hel_bumer
Recursive
18 янв 2026, 10:19
18 янв 2026, 10:194d5869d
import java.util.ArrayList;
import java.util.List;

public class Main {
    // логика
//int[] startNumbers = {21, 1, 20, 23};  // Дни: 0, 1, 2, 3
// значение_дня_N = (значение_дня_N-1 × значение_дня_N-3) % 10 + 1
//    Шаг 0: Инициализация массива
//    numbers = [21, 1, 20, 23]  ← дни 0, 1, 2, 3
//    Шаг 1: Вычисляем день 4 (d = 0, index = 4)
//
//     prev = numbers[3] = 23          (день 3)
//    prePrePrev = numbers[1] = 1     (день 1)
//    день 4 = (23 × 1) % 10 + 1 = (23 % 10) + 1 = 3 + 1 = 4
//    numbers = [21, 1, 20, 23, 4]
//    Результат для day = 1: 4 (значение дня 4)

    public static void main(String[] args) {
        compare(1);
        compare(2);
        compare(5);
        compare(15);
    }

    public static void compare(int day) {
        System.out.println("=== Day " + day + " ===");
        int[] startNumbers = {21, 1, 20, 23};
        int iterative = chooseHobbyIterative(startNumbers, day);
        int recursive = chooseHobbyRecursive(startNumbers, day);
        System.out.println("Iterative = " + iterative + " | Recursive = " + recursive);
        System.out.println();
    }

    public static int chooseHobbyRecursive(int[] startNumbers, int day) {

        int targetDay = day + 3;

        // Мемоизация
        int[] memo = new int[targetDay + 1];
        for (int i = 0; i <= targetDay; i++) {
            memo[i] = -1;
        }

        return chooseHobbyRecursiveMemo(startNumbers, targetDay, memo);
    }

    private static int chooseHobbyRecursiveMemo(int[] startNumbers, int day, int[] memo) {
        if (memo[day] != -1) {
            return memo[day];
        }

        // Базовые случаи: дни 0-3
        if (day == 0) {
            memo[day] = startNumbers[0];
            return memo[day];
        }
        if (day == 1) {
            memo[day] = startNumbers[1];
            return memo[day];
        }
        if (day == 2) {
            memo[day] = startNumbers[2];
            return memo[day];
        }
        if (day == 3) {
            memo[day] = startNumbers[3];
            return memo[day];
        }

        // Рекурсивный случай
        memo[day] = (chooseHobbyRecursiveMemo(startNumbers, day - 1, memo) *
                chooseHobbyRecursiveMemo(startNumbers, day - 3, memo)) % 10 + 1;
        return memo[day];
    }

    public static int chooseHobbyIterative(int[] startNumbers, int day) {
        List<Integer> numbers = new ArrayList<>();

        numbers.add(startNumbers[0]);
        numbers.add(startNumbers[1]);
        numbers.add(startNumbers[2]);
        numbers.add(startNumbers[3]);

        for (int d = 0; d < day; d++) {
            int index = d + 4; // индексы дней в массиве сдвинуты на 4
            int prev = numbers.get(index - 1); // предыдущее значение
            int prePrePrev = numbers.get(index - 3); // пре-пре-предыдущее значение
            numbers.add((prev * prePrePrev) % 10 + 1);
        }

        return numbers.get(numbers.size() - 1);
    }
}