cómo encontrar el menor número de operaciones para calcular x ^ n
-
13-10-2019 - |
Pregunta
aquí está el problema de
ACM Internacional Colegiado Programación Concurso Regional de Asia Concurso, Yokohama, 2006-11-05
A partir de X y multiplicar repetidamente por x
, podemos calcular x^31
con treinta y multiplicaciones:
x^2 = x * x, x^3 = x^2 * x, x^6 = x^3 * x^3, x^7 = x^6 *x, x^14 = x^7 * x^7 ,
x^15 = x^14 * x, x^30 = x^15 * x^15 , x^31 = x^30 * x
escribir un programa para encontrar el menor número de operaciones de cálculo x^n
por multiplicación y división a partir de x
para el número entero positivo dado n
y n<=200
Para n = 31 la menor #Operations es 6
para n = 50 los menos #Operations es 7
Todas las ideas son bienvenidas.
Solución
Vea esto: http://en.wikipedia.org/wiki/Addition-chain_exponentiation
No existe un algoritmo eficiente que les permite conocer el número mínimo de pasos, y la programación dinámica no funciona.
Supongo que n
es lo suficientemente pequeño como para permitir una solución de fuerza bruta para pasar, a pesar de que podría tener que ser optimizado. ¿Sabe usted cómo la fuerza bruta es?
Otros consejos
#include<stdio.h>
long long int pow(long long int, long long int);
int count=0;
int main()
{
long long int a,b;
printf("Input: ");
scanf("%lld %lld",&a,&b);
pow(a,b);
printf("%d",count);
return 0;
}
long long int pow(long long int a, long long int b)
{
count++;
if(b==0)
return 1;
long long int res=pow(a,b/2);
if(b%2)
return res*res*a;
else
return res*res;
}