如何找到计算 x^n 的最少操作数

Question

这是问题来自

ACM国际学院 编程大赛亚洲区域赛 比赛，横滨，2006-11-05

从 x 开始，反复乘以 x，我们可以通过 30 次乘法来计算 x^31：

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

编写一个程序来找到最小的数字计算x^n的操作 对于给定的正整数 n，通过从 x 开始的乘法和除法，

对于 n = 31 的 n<=200 ，最少的#操作是 6 < br> 对于 n = 50，最少 #operations 是 7

欢迎任何想法。

Answer 1

请参阅：http://en.wikipedia.org/wiki/Addition-chain_exponentiation

没有有效的算法可以让您获得最少的步骤数，并且动态规划不起作用。

我猜测 n 足够小，足以允许暴力解决方案通过，尽管它可能需要优化。你知道如何暴力破解吗？

Answer 2

#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;
}