当前位置：首页 -> 基础 -> c++编程基础

poj 3134 Power Calculus(迭代加深dfs)

2014-11-24 07:49:46 · 作者: · 浏览: 0
标签: poj 3134 Power Calculus 加深 dfs
Power Calculus
Time Limit: 5000MS Memory Limit: 65536K
Total Submissions: 1615 Accepted: 856

Description

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 integern. 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

Source

Japan 2006

题意：

算x^n的快速乘法。算过的结果可以利用。乘和除都可以问最少的运算次数。

思路：

由于涉及到最少次数。想用bfs但是。bfs会出问题。因为求解x^n的过程中只能使用已算出的结果。但是bfs不能确定某个状态时那些结果已经算出。所以只能用dfs来求解。但是盲目用dfs每次搜到底的话。时间开销太大。但是我们大概知道需要的运算次数。所以我们可以逐渐加深的来搜这样就可以最快的找到解了。

详细见代码：

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #include
             //#pragma comment(linker,"/STACK:1024000000,1024000000") using namespace std; const int INF=0x3f3f3f3f; const double eps=1e-8; const double PI=acos(-1.0); const int maxn=100010; typedef __int64 ll; int deep,n,get; int have[1010];//have[i]第i层得到的数 void iddfs(int dep) { int i,tp; if(get||dep>deep||have[dep]<<(deep-dep)