Создание рекурсивной функции итеративной

Question

Назначение: вычислите _n по формулам:

• a ₀ = 1
• a ₁ = 3
• a ₂ = 5
• a _n = a _n-1 * a ² _n-2 * a ³ _п-3

У меня проблемы с выполнением итеративной функции. Я понял, как сделать это рекурсивно. Как бы я делал это специально для этой задачи и в целом?

Мой код для рекурсии:

public static BigInteger recurs(int bigInteger){
    BigInteger sum;

    if (bigInteger == 0) {
        sum = new BigInteger(String.valueOf("1"));
    } else if (bigInteger == 1) {
        sum = new BigInteger(String.valueOf("3"));
    } else if (bigInteger == 2) {
        sum = new BigInteger(String.valueOf("5"));
    } else {
        sum = recurs(bigInteger-1).multiply(recurs(bigInteger-2).pow(2).multiply(recurs(bigInteger-3).pow(3)));
    }

    return sum;

}

Answer 1

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

static int compute_iterative(int n) {
    if (n == 0) return 1;
    if (n == 1) return 3;
    if (n == 2) return 5;

    int a_n3 = 1;
    int a_n2 = 3;
    int a_n1 = 5;
    int a_n = a_n1;
    int i = 3;
    while (i <= n) {
        a_n = a_n1 * (int) Math.pow(a_n2, 2) * (int) Math.pow(a_n3, 3);
        a_n3 = a_n2;
        a_n2 = a_n1;
        a_n1 = a_n;
        i++;
    }
    return a_n;
}

Версия с использованием BigInterger:

static BigInteger compute_iterative(int n) {
    if (n < 0) {
        throw new IllegalArgumentException("Unsupported input value: " + n);
    }
    final BigInteger[] values = { BigInteger.valueOf(1), BigInteger.valueOf(3), BigInteger.valueOf(5) };
    if (n < values.length) {
        return values[n];
    }
    int i = 3;
    while (i <= n) {
        final BigInteger result = values[2].multiply(values[1].pow(2)).multiply(values[0].pow(3));
        values[0] = values[1];
        values[1] = values[2];
        values[2] = result;
        i++;
    }
    return values[2];
}

Answer 2

Вам нужно запомнить последние три значения и каждый раз вычислять новое значение в терминах последнего.

public static BigInteger iter(int n) {
    BigInteger a = BigInteger.valueOf(1);
    BigInteger b = BigInteger.valueOf(3);
    BigInteger c = BigInteger.valueOf(5);
    switch (n) {
        case 0: return a;
        case 1: return b;
        case 2: return c;
        default:
            for (int i = 2; i < n; i++) {
                BigInteger next = c.multiply(b.pow(2)).multiply(a.pow(3));
                a = b;
                b = c;
                c = next;
            }
            return c;
    }
}

Обратите внимание, что это O (n) вместо O (n ^ 3)

Answer 3

Чтобы дать вам подсказку:

Инициализируйте массив размером n, в котором будут храниться ответы. Например, i-й индекс будет хранить ответ для a_i. Инициализируйте a_0, a_1 и a_2 для значений, данных вам (1,3 и 5 в вашем случае). Теперь начните итерацию с индекса 3 и далее по формуле для расчета a_i.