Очень часто возникает задача эффективного вычисления xn по данным x и n, где n - положительное целое число.
Предположим, например, что необходимо вычислить x16. Можно просто начать с x и 15 раз умножить его на x. Но тот же ответ можно получить всего за четыре умножения, если несколько раз возвести в квадрат получающийся результат, последовательно вычисляя x2, x4, x8, x16.
Эта же идея, в целом, применима к любому значению n следующим образом. Запишем n в виде числа в двоичной системе счисления (убирая нули слева). Затем заменим каждую "1" парой символов SX, а каждый "0" - символом S и вычеркнем крайнюю слева пару символов "SX". Результат представляет собой правило вычисления xn, в котором "S" трактуется как операция возведения в квадрат, а "X" - как операция умножения на x. Например, n = 23 имеет двоичное представление 10111. Таким образом, мы формируем последовательность SXSSXSXSX, из которой удаляем начальную пару SX для получения окончательного правила SSXSXSX. Это правило гласит, что необходимо "возвести в квадрат, возвести в квадрат, умножить на x, возвести в квадрат, умножить на x, возвести в квадрат и умножить на x", т.е. последовательно вычислить значения x2, x4, x5, x10, x11, x22, x23.
Вам нужно для заданного n сформулировать соответствующее правило быстрого возведения числа x в степень xn
Одно натуральное число n, не превышающее 2·109.
Выведите строку для правила возведения числа x в степень n для получения xn.
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
string dec_to_bin(unsigned long long num)
{
string bin;
while (num != 0)
{
bin = char((num & 0x01) + '0') + bin;
num >>= 1;
}
return bin;
}
int main()
{ string str,str2;
int a;
cin>>a;
str2.clear();
str=dec_to_bin(a);
for(int i=0;i<=str.length();i++){
if(str[i]=='1') str2=str2+"SX";
if(str[i]=='0') str2=str2+"S";
}
str2.erase(0,2);
cout<<str2<<endl;
return 0;
}
Есть решение которого нет на сайте? Пиши admin@devexe.top