Задача про степенные башни не работает
Я написал функцию, которая определяет, какая из подаваемых на вход степенных башен меньше.
Степенной башней называется степень 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 шт):
Пример, когда программа не работает как надо: 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.