=== Python 3.8.3 ===
def fastExp(b, n):
def even(n):
if n % 2 == 0:
return True
return False
if n == 0:
return 1
if even(n):
#Можно было написать return fastExp(b, b/2) ** 2, но операцию возведения в степень использовать нам запретили.
res = fastExp(b, n/2)
return res*res
return b*fastExp(b, n-1)
def main():
base = float(input())
exp = int(input())
print(fastExp(base, exp))
if __name__ == "__main__":
main()
Предложенные тесты проходит. Сам алгоритм быстрого возведения в степень реализован в виде функции fastExp(b, n)
/*Простейшая реализация. Подразумевается, что вводятся корректные данные, n вмещается в int, а a и результат - в double. Визуализация зависимости числа операций умножения от степени n для чисел от 0 до 5000 прилагается */
#include <iostream>
double s_pow(double a, int power)
{
if (power == 0)
{
return 1;
}
if (power % 2 == 0)
{
return s_pow(a * a, power / 2);
}
return a * s_pow(a, power - 1);
}
int main()
{
double a;
int n;
std::cin >> a >> n;
std::cout << s_pow(a, n);
return 0;
}
#include <iostream>
#include <cmath>
using namespace std;
int main(){
long long a, answer=0;
int n, bits[64]={0}, i=0;
cin>>a>>n;
while(a!=0){
if(a%2==0)
a/=2;
else {
bits[i]=1;
a=(a-1)/2;
}
i++;
}
bits[n-1]=1-bits[n-1];
for(int j=0; j<i; j++)
answer+=bits[j]*pow(2,j);
cout<<answer;
}