Задача про степенные башни не работает

Я написал функцию, которая определяет, какая из подаваемых на вход степенных башен меньше.

Степенной башней называется степень a^b^c^..., которая вычисляется вот так: a^(b^(c^(...))). Количество степеней не превышает 9, а каждое число в этой степени не превышает 100 и не меньше 2, т. е. находится на отрезке [2; 100).

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

вот сам алгоритм:

bool f(vector<int> a, vector<int> b){
    if (a[0] == 1) return true;
    if (b[0] == 1) return false;
    int mx = min(a.size(), b.size());
 
    int k = 0;
    for (int i = 0; i < mx; i++){
        for (int j = 1; j <= 10; j++){
            if (pow(max(a[i], b[i]), j) / min(a[i], b[i]) >= j){
                k = max(k, j);
                break;
            }
        }
    }
 
    long double p = 1, q = 1;

    for (int i = max(a.size(), b.size()) - 1; i >= mx - 1; i--){
        if (i < a.size()){
            p = pow(a[i], p);
            if (p >= 100 * k) return false;
        }
        if (i < b.size()){
            q = pow(b[i], q);
            if (q >= 100 * k) return true;
        }
    }
    p = log(p); q = log(q);

    for (int i = mx - 2; i > 0; i--){
        p = log(log(a[i])) + p, q = log(log(b[i])) + q;
        if (p - q > 5) return false;
        if (q - p > 5) return true;
        if (log(exp(p - q) - 1) + q >= log(log(k))) return false;
        if (log(exp(q - p) - 1) + p >= log(log(k))) return true;
        p = exp(p); q = exp(q);
    }
    p = log(log(a[0])) + p, q = log(log(b[0])) + q;
    if (p >= q) return false;
    return true;
}

объяснение алгоритма на примере башен 2^5^2^7^2 и 4^3^5^8

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

сравнение чисел идет сверху, т. е. на первом шаге, программа сравнивает 7^2 и 8, если 7^2 не помещается в тип long double или оно больше 8 больше чем в 10 раз, то мы возвращаем что вторая степень меньше.

если ни то, ни другое, то добавляем снизу у обоих "хвостов" еще по основанию, так как числа с каждым шагом становятся все больше, то надо сравнивать их логарифмы, а еще лучше логарифмы логарифмов. loglog2^7^2 и loglog5^8 вычисляются и сравниваются аналогично, но уже с loglog10, и тд до последнего основания. Допустим мы дошли до последнего основания, тогда логарифмы логарифмов просто сравниваются на то, что меньше, а что больше.


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

Автор решения: zolars

Пример, когда программа не работает как надо: 9^99^99 и 99^99^98. Правильный ответ, что вторая больше первой, но программа говорит наоборот.

Так же, вот немного другой алгоритм для этой задачи: Вместо хранения логарифмов логарифмов степенных башен, лучше хранить в памяти их отношение (при этом полностью отказавшись от логарифмов). Т. е. в первой итерации (если идти сверху) мы сохраняем отношение последних степеней у башен, предварительно дополнив каждую башню до 9 степеней с помощью единиц, допустим в переменную k. И при каждой следующей итерации, надо сохранять в переменную k отношение ai / bi, где ai - i-тая степень в башне а, а bi - i-тая степень в башне б, возведенное в степень предыдущего k. делаем проверку k >= 10 или k <= 0.1 и идем дальше. если все 10 чисел у башен были проработаны, то вы в итоге получите отношение башни a к башне b, и надо будет просто вернуть верно ли утверждение k < 1.

→ Ссылка