Возвести в степень за наименьшее число операций. С++

[Tatiana_91]

Дано натуральное число n. Требуется определить выражение, которое вычисляет x^n за наименьшее число операций. Разрешается использовать операции умножения и возведения в степень, круглые скобки. Умножение считается одной операцией. Пример: n=5, тогда требуется три операции (x*x)^2*x.
Объясните кто-нибудь как сделать, или, может у кого есть что-то похожее, поделитесь.

[s-andriano]

Тогда в любом случае одна операция - возведение в степень.

[Sciv]

Разрешается использовать операции умножения

При таком условии можно использовать стандартную функцию возведения в степень из модуля math.

[Tatiana_91]

Сообщение от Sciv

При таком условии можно использовать стандартную функцию возведения в степень из модуля math.

Не сказано про условия.

[Sciv]

Не сказано про условия.

Ну тогда некорректна задача, извините.

[Tatiana_91]

Сообщение от Sciv

Ну тогда некорректна задача, извините.

Умножение считается одной операцией, возведению в степень n соответствует (n-1) операция. Может это...

[interacia]

Кажется вам нужно что то вроде этого кода.
Данный код возводит 2 в 15-ую степень за 6 операций умножения.
А в 31-ую степень за 8 операций умножения.

#include <iostream.h>
int main(void)
{
system("chcp 1251 > nul"); // руский язык в консоли
int i,j; // счетчик цикла
int KOL_UMN; // Подсчет количества операций умножения
long double M[100];
long double Stepen;
double X,N;
KOL_UMN=0; // начальное значение счетчика операций
cout<<"Введите число X"<<endl;
cin>>X;
cout<<"Введите степень N"<<endl;
cin>>N;
i=1;
j=1;
Stepen=X;
M[1]=X;
while (i<=N-i)
{ j++; i+=i;
 M[j]=M[j-1]*M[j-1]; KOL_UMN++; // учет операции
}
Stepen=M[j];
N-=i;
while (N>=1){
i=1;
j=1;
while (i<N-i)
{
j++;
i+=i;
}
Stepen*=M[j]; KOL_UMN++; // учет операции
N-=i; }
cout<<"Ответ"<<endl;  // вывод результата
cout<<Stepen<<endl;  // вывод результата
cout<<"Количества операций умножения "<<KOL_UMN<<endl;  // вывод результата
system("PAUSE"); //пауза при выходе можно убрать
return 0;
}

[Tatiana_91]

Сообщение от interacia

Кажется вам нужно что то вроде этого кода.
Данный код возводит 2 в 15-ую степень за 6 операций умножения.

Спасибо! Но вот мое решение, вдруг кому понадобится.

//----------------------------------------------------------------
#include <iostream.h>
#include<map.h>
#include<math.h>
#include <conio.h>
#include <time.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <sstream>
#pragma hdrstop
#include <vcl.h>
//---------------------------------------------------------------
int step(int x)
{
  int i, b;
  long c=0;
  for(i=0; x>0; i++)
     {
      b=x%2;
      x=(x-b)/2;
      c+=b * pow(10,i);
     }
 return c;
} ;
//-----------------------------------------------------------------------
int main()
{
 int e, d;
 const m = 100;
 cout<<"Vvedite chislo operacii: ";
 cin>>e;
d = step(e);
int m1;
m1 = log10(d)+1;
int mas[m];
int i=0;
  while (i < m1)
      {
       mas[i]=d%10;
       d/=10;
       i++;
      }
int j = m1-1;
 while (j >= 0)
     {
   //   cout<<mas[j]<<" ";
      j--;
     }
 cout<<endl;
 int x;
 int k;
 k = mas[0];
 string str;
ostringstream stream;
stream << k;
str ="(x^" + stream.str()+ ")^2";
string str1;
int i1=1;
while (i1 < (m1-1))
     {
      ostringstream stream;   //преобразование дробных и целых чисел
      k = mas[i1];
      stream << k;
      str1="(" + str + "*x^" + stream.str() + ")^2";
      i1++;
     }
k = mas[m1-1];
stream << k;
str = "(" + str1 + "*x^1)";// + stream.str()+"1)";
cout<<str;

getch();
return 0;
}
//------------------------------------------------------------------------