从 x 开始，反复乘以 x ，我们可以用 30 次乘法计算得到x^{31}：

x^2=x \times x，x^3=x^2 \times x，x^4=x^3 \times x，…，x^{31}=x^{30} \times x。

平方运算可以明显缩短乘法的计算次数。以下是 8 次计算得到 x^{31} 的算法：

x^2=x \times x，x^3=x^2 \times x，x^6=x^3 \times x^3，x^7=x^6 \times x，x^{14}=x^7 \times x^7，x^{15}=x^{14} \times x，x^{30}=x^{15} \times x^{15}，x^{31}=x^{30} \times x。

这不是计算x^{31}的最快方法。实际上有多种方法可以用 7 步运算得到结果。以下方法是其中之一：

x^2=x \times x，x^4=x^2 \times x^2，x^8=x^4 \times x^4，x^{10}=x^8 \times x^2，x^{20}=x^{10} \times x^{10}，x^{30}=x^{20} \times x^{10}，x^{31}=x^{30} \times x。

如果可以用除法，我们会发现有步数更少的方法计算出结果，比如：可以用六步运算（五次乘一次除）计算 x^{31}：

x^2=x \times x，x^4=x^2 \times x^2，x^8=x^4 \times x^4，x^{16}=x^8 \times x^8，x^{32}=x^{16} \times x^{16}，x^{31}=x^{32} \div x。

这是计算x^{31}最有效的方法之一。

你的任务是编写一个程序，通过对给定的正整数 n 进行从 x 开始的乘法和除法运算，找到计算出 x^n 的最少运算次数。计算中出现的乘和除的值应该是 x 的正整数幂。换句话说，x^{−3} 不应该出现。

输入包含一个或多个测试数据（不超过 20 组），每行包含一个整数 n 。

n 为正整数且小于或等于 1000，输入 0 表示测试数据的读入结束。

输出计算到 xⁿ 所需的最小乘法或除法计算总次数，每个输出占 1 行。

POJ

迭代加深搜索