编程介的小学生 2017-03-26 16:08 采纳率: 20.5%
浏览 793
已采纳

Power Calculus

Starting with x and repeatedly multiplying by x, we can compute x31 with thirty multiplications:

x2 = x �� x, x3 = x2 �� x, x4 = x3 �� x, ��, x31 = x30 �� x.

The operation of squaring can be appreciably shorten the sequence of multiplications. The following is a way to compute x31 with eight multiplications:

x2 = x �� x, x3 = x2 �� x, x6 = x3 �� x3, x7 = x6 �� x, x14 = x7 �� x7, x15 = x14 �� x, x30 = x15 �� x15, x31 = x30 �� x.

This is not the shortest sequence of multiplications to compute x31. There are many ways with only seven multiplications. The following is one of them:

x2 = x �� x, x4 = x2 �� x2, x8 = x4 �� x4, x8 = x4 �� x4, x10 = x8 �� x2, x20 = x10 �� x10, x30 = x20 �� x10, x31 = x30 �� x.

If division is also available, we can find a even shorter sequence of operations. It is possible to compute x31 with six operations (five multiplications and one division):

x2 = x �� x, x4 = x2 �� x2, x8 = x4 �� x4, x16 = x8 �� x8, x32 = x16 �� x16, x31 = x32 �� x.

This is one of the most efficient ways to compute x31 if a division is as fast as a multiplication.

Your mission is to write a program to find the least number of operations to compute xn by multiplication and division starting with x for the given positive integer n. Products and quotients appearing in the sequence should be x to a positive integer��s power. In others words, x−3, for example, should never appear.

Input

The input is a sequence of one or more lines each containing a single integer n. n is positive and less than or equal to 1000. The end of the input is indicated by a zero.

Output

Your program should print the least total number of multiplications and divisions required to compute xn starting with x for the integer n. The numbers should be written each in a separate line without any superfluous characters such as leading or trailing spaces.

Sample Input

1
31
70
91
473
512
811
953
0
Sample Output

0
6
8
9
11
9
13
12

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-04-04 15:18
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 matlab数字图像处理频率域滤波
  • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
  • ¥15 ELGamal和paillier计算效率谁快?
  • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
  • ¥15 ubuntu系统下挂载磁盘上执行./提示权限不够
  • ¥15 Arcgis相交分析无法绘制一个或多个图形
  • ¥15 关于#r语言#的问题:差异分析前数据准备,报错Error in data[, sampleName1] : subscript out of bounds请问怎么解决呀以下是全部代码:
  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
  • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误