Starting with x and repeatedly multiplying by x, we can compute x31 with thirty multiplications:
The operation of squaring can be appreciably shorten the sequence of multiplications. The following is a way to compute x31 with eight multiplications:
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:
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):
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.
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.
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.
1 31 70 91 473 512 811 953 0
0 6 8 9 11 9 13 12
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator