x^nを計算するための操作の最小数を見つける方法

Question

これが問題です

ACM International Collegiateプログラミングコンテストアジア地域コンテスト、横浜、2006-11-05

Xから始めて、繰り返し増加します x, 、計算できます x^31 30の乗算で：

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からの乗算と除算によって x 与えられた正の整数の場合 n と n<=200

n = 31の場合、最小#operationsは6です
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;
}