Статья Автор: Лебедев Дмитрий

TUZ_2-21 Определение совершенной степени

TUZ_2-21 Определение совершенной степени

TUZ_2-21 Определение совершенной степени
2.21 Определение совершенной степени
Положительное целое число считается совершенной степенью, если его можно выразить в виде basepower, где base и power являются целыми числами больше 1.
Ваша задача: написать функцию, которая принимает положительное целое число n, и если ей удастся найти basepower = n, то она возвращает True, иначе она должна возвращать False.
Например, для n = 64 существует пара чисел base = 2 и power = 6, т. е. 26 = 64.
В табл. 2.21 показаны ожидаемые результаты для некоторых входных данных.
Таблица 2.21. Некоторые ожидаемые результаты для задачи определения идеальной степени
n Ожидаемый результат
2 False
27 True 
729 True 
1369 True 

Алгоритм
.Чтобы определить, является ли положительное целое число n совершенной степенью, используется алгоритм, выполняющий двоичный поиск основания совершенной степени.
Алгоритм начинается с показателя степени, равного 2, и продолжает перебирать в цикле все возрастающие числа, пока не найдет идеальную степень или не выяснит, что таковой не существует. Вот подробное описание шагов алгоритма.
1. Принимается целое положительное число n.
2. Показателю степени power присваивается значение 2.
3. Запускается цикл while True:.
4. Если 2 ** power > n, возвращается False.
5. Инициализируются переменные low = 2 и high = n.
6. Пока low меньше или равно high:
1) переменной mid присваивается результат деления (low + high) на 2 с округлением вниз;
2) переменной guess присваивается значение mid, возведенное в степень power;
3) если guess равно n, верните True;
4) иначе, если guess меньше n, переменной low присваивается значение mid + 1;
5) иначе переменной high присваивается значение mid – 1.
7. Если base ** power равно n, то возвращается True.
8. Значение power увеличивается на 1.
Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация
Печать