как найти наименьшее количество операций для вычисления x ^ n

Question

здесь проблема из

ACM International Collegiate Programming Contest Азиатский региональный конкурс, Иокогама, 2006-11-05

Начиная с x и многократно умножая на 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 путем умножения и деления, начиная с x для данного положительногоцелое число n и n<=200

для n = 31 наименьшее количество # операций составляет 6
для n = 50 наименьшее количество # операций составляет 7

Любые идеи приветствуются.

Answer 1

Смотрите это: http://en.wikipedia.org/wiki/Addition-chain_exponentiation

Не существует эффективного алгоритма, который бы обеспечивал минимальное количество шагов, а динамическое программирование не работает.

Я предполагаю, что n достаточно мал для того, чтобы пройти решение грубой силы, хотя, возможно, его нужно оптимизировать. Вы знаете, как это сделать?