9

ここからの問題です

ACM International Collegiate Programming Contest Asia Regional Contest, 横浜, 2006-11-05

x から始めて を繰り返し掛けると、30 回の掛け算でx計算できます。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 から始まる乗算と除算によって計算する演算の最小数を見つけるプログラムを作成し、xnn<=200

n = 31 の場合、最小操作数は 6
n = 50 の場合、最小操作数は 7

どんなアイデアでも大歓迎です。

4

2 に答える 2

11

これを参照してください: http://en.wikipedia.org/wiki/Addition-chain_exponentiation

最小ステップ数を得る効率的なアルゴリズムはなく、動的計画法は機能しません。

n最適化する必要があるかもしれませんが、ブルートフォースソリューションを通過させるのに十分なほど小さいと思います。ブルートフォースする方法を知っていますか?

于 2010-12-28T20:11:22.157 に答える