Подготовка к экзамену по Java - рекурсивное задание

Question

Это моя задача:

Используйте рекурсию, чтобы найти 13-й член массива, в котором каждый член умножается на два последних члена минус второй член. Первые два члена 3 и 3.

Вот что я придумал:

public class Zadatak2 {

    int array[] = {3,3,0,0,0,0,0,0,0,0,0,0,0};

    public Zadatak2(){
        find13(2);
    }

    public int find13(int index){
        if (index == 13){
            System.out.println("Member 13: " + array[index-1]);
            return 0;
        }
        else{
            array[index] = array[index-1] * array[index-2] - array[1];
            System.out.println(index + " : " + array[index]);
            return find13(index + 1);
        } 
    }
}

Консольный вывод, где я вижу индекс в массиве: значение:

2 : 6
3 : 15
4 : 87
5 : 1302
6 : 113271
7 : 147478839
8 : 1947758222
9 : 465247871
10 : 818773103
11 : -459621106
12 : 383828239
Member 13: 383828239

Но я почти уверен, что ошибся, или есть лучшее решение. Любая помощь приветствуется.

Answer 1

Как сказал Кевин В. в комментарии, в будущем "если вы хотите, чтобы кто-то просмотрел ваш код... используйте обмен стеками просмотра кода". Тем не менее, вот несколько предложений.

Во-первых, нужно помнить, что проблема, с которой вы столкнулись, очень похожа на вычисление последовательности Фибоначчи, и, вероятно, существует множество примеров использования рекурсии для вычисления членов этой последовательности.

Во-вторых, способ, которым вы создали свою рекурсивную функцию, ограничивает ее использование только для поиска 13-го числа в последовательности. Вы начинаете с начала последовательности и продвигаетесь до 13-го числа, и то, что вы делаете, - это, в основном, итеративное решение проблемы с незначительными изменениями, чтобы заставить его работать через рекурсию.

Лучшим подходом было бы обобщить вашу функцию, чтобы вы могли передать порядковый номер члена в качестве параметра, и функция вычислит его с помощью рекурсии. Способ сделать это состоит в том, чтобы начать с вашего целевого номера участника и через рекурсию, получить членов, необходимых для этого члена. Это позволяет использовать функцию для вычисления любого числа в последовательности, а не только 13-го числа. Это также имеет дополнительное преимущество, заключающееся в том, что ваш код может быть сокращен и делать больше.

Это код:

// index is the member number; it is 1 based e.g. index of 1 gives the first number in the sequence
int find(int index)
{
    if (index == 1 || index == 2)
        return 3;

    return (find(index - 1) * find(index - 2)) - find(2);
}

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

При применении рекурсии к последовательности сначала запишите математическое определение последовательности, и это то, что должно быть возвращено из рекурсивной функции. Например, в вашей задаче определение

a[n] = (a[n-1] * a[n-2]) - a[2]

Теперь взгляните на решение, которое я написал. То, что я возвращаю, является именно этим определением последовательности, только с точки зрения рекурсивной функции. Базовый случай в начале функции - это просто начальный элемент (ы), необходимый для вычисления остальной части последовательности. Я призываю вас проработать алгоритм на бумаге и поиграть с ним, чтобы точно увидеть, что происходит.

В заключение, этот алгоритм ужасен с точки зрения времени выполнения. Существует три рекурсивных вызова для вызова find(), что означает, что поиск 13-го члена имеет порядок 3^13, что является экспоненциальным. Экспоненциальные алгоритмы - ужасные алгоритмы, и их всегда следует избегать.

Если рекурсия проверена внимательно, вы можете увидеть, что для вычисления [n], код вычисляет a [n-1] и a[n-2]. Но для того, чтобы вычислить [n-1], a[n-2] и a[n-3] оба вычисляются, что означает, что [n-2] вычисляется ДВАЖДЫ. Это наблюдение очень важно, потому что мы прошли только один уровень рекурсии. В общей сложности около 3 ^ 13 членов вычислений происходит, когда все должно быть 13 (для 13 членов). Все это время, выполняя одни и те же вычисления миллионы раз, является ужасной тратой и делает экспоненциальные алгоритмы такими ужасными.

Так что, если мы сохраним каждый из членов, которые вычисляет функция? Этот метод называется динамическим программированием, и в нем ответы на подзадачи хранятся на пути к решению более крупной проблемы, поэтому вычисления не выполняются несколько раз. Решение, реализующее динамическое программирование:

// a variable that persists across function calls such as an instance field
int[] array = new int[20];    // just giving some extra memory in case you want to calculate other members
array[0] = -1;      //invalid member of the sequence since it is 1-based
array[1] = 3;
array[2] = 3;

//set the rest of the numbers to values letting you know they have not been set/found/calculated yet
for (int i = 3; i < 20; i++)
{
    array[i] = -1;
}

// index is the member number; it is 1 based e.g. index of 1 gives the first number in the sequence
int find(int index)
{
    if (array[index] != -1)   //if already calculated that member, just return it
        return array[index];

    //store the answer
    array[index] = (find(index - 1) * find(index - 2)) - find(2);
    return array[index];
}

С помощью этого кода вы можете вызвать find () для любого номера, и он рассчитает его для вас, а не только 13-го числа.

Наконец, и самое главное, как отметил Кевин В. в комментарии, наличие отрицательного числа в качестве члена означает, что вы получаете слишком большие числа для целых чисел. Лука Милошевич говорит, что 13-й член на самом деле является числом х10^90, что слишком долго для длинных даже. Двойные числа могут работать до тех пор, пока вам не понадобится более 20 или около того цифр точности, но из-за не менее 90 цифр в ответе двойные числа недостаточно точны. К счастью, в Java есть класс BigInteger, который может хранить столько больших чисел, сколько вам нужно, независимо от размера. Чтобы получить ответ, вам, вероятно, придется использовать их, если вы не хотите делать математику вручную. Документация для BigInteger находится здесь.

Answer 2

Так как это задание, которое вам было поручено, я хотел бы дать вам только подсказку. В нашем случае рекурсивная функция вызывала бы себя с более низким аргументом и в конце концов заканчивалась некоторыми определенными значениями.

В нашем случае более низкие значения f(1) а также f(2) уже определены как 3,

Так f(n) = f(n-1) * f(n-2) - f(2) где f(1) = 3 а также f(2) = 3,

(Если я правильно понял задачу)

Теперь ваша задача сделать кодирование и найти f(13),

Это помогает?