【算法•日更•第三十九期】迭代加深搜索：洛谷SP7579 YOKOF - Power Calculus 题解...

￡神魔★判官ぃ 2023-06-03 02:52 15阅读 0赞

废话不多说，直接上题：

--------------------

# SP7579 YOKOF - Power Calculus #

### 题意翻译 ###

（略过没有营养的题干）

**题目大意**： 给出正整数n,若只能使用乘法或除法，输出使x经过运算（自己乘或除自己，以及乘或除运算过程中产生的中间结果）变成x^n的最少步数

***输入格式***： 若干行数据，每行一个正整数n，数据以单独成行的0结束

***输出格式***： 若干行数据，对应每行输入的n所需的步数

### 题目描述 ###

Starting with *x* and repeatedly multiplying by *x*, we can compute *x* ^\{31\}31 with thirty multiplications:

> *x* ^\{2\}2 = *x* \* *x*, *x* ^\{3\}3 = *x* ^\{2\}2 \* *x*, *x* ^\{4\}4 = *x* ^\{3\}3 \* *x*, ... , *x* ^\{31\}31 = *x* ^\{30\}30 \* *x*.

The operation of squaring can appreciably shorten the sequence of multiplications. The following is a way to compute *x* ^\{31\}31 with eight multiplications:

> *x* ^\{2\}2 = *x* \* *x*, *x* ^\{3\}3 = *x* ^\{2\}2 \* *x*, *x* ^\{6\}6 = *x* ^\{3\}3 \* *x* ^\{3\}3 , *x* ^\{7\}7 = *x* ^\{6\}6 \* *x*, *x* ^\{14\}14 = *x* ^\{7\}7 \* *x* ^\{7\}7 ,  
> *x* ^\{15\}15 = *x* ^\{14\}14 \* *x*, *x* ^\{30\}30 = *x* ^\{15\}15 \* *x* ^\{15\}15 , *x* ^\{31\}31 = *x* ^\{30\}30 \* *x*.

This is not the shortest sequence of multiplications to compute *x* ^\{31\}31 . There are many ways with only seven multiplications. The following is one of them:

> *x* ^\{2\}2 = *x* \* *x*, *x* ^\{4\}4 = *x* ^\{2\}2 \* *x* ^\{2\}2 , *x* ^\{8\}8 = *x* ^\{4\}4 \* *x* ^\{4\}4 , *x* ^\{10\}10 = *x* ^\{8\}8 \* *x* ^\{2\}2 ,  
> *x* ^\{20\}20 = *x* ^\{10\}10 \* *x* ^\{10\}10 , *x* ^\{30\}30 = *x* ^\{20\}20 \* *x* ^\{10\}10 , *x* ^\{31\}31 = *x* ^\{30\}30 \* *x*.

There however is no way to compute *x* ^\{31\}31 with fewer multiplications. Thus this is one of the most efficient ways to compute *x* ^\{31\}31 only by multiplications.

If division is also available, we can find a shorter sequence of operations. It is possible to compute *x* ^\{31\}31 with six operations (five multiplications and one division):

> *x* ^\{2\}2 = *x* \* *x*, *x* ^\{4\}4 = *x* ^\{2\}2 \* *x* ^\{2\}2 , *x* ^\{8\}8 = *x* ^\{4\}4 \* *x* ^\{4\}4 , *x* ^\{16\}16 = *x* ^\{8\}8 \* *x* ^\{8\}8 , *x* ^\{32\}32 = *x* ^\{16\}16 \* *x* ^\{16\}16 , *x* ^\{31\}31 = *x* ^\{32\}32÷ *x*.

This is one of the most efficient ways to compute *x* ^\{31\}31 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 *x* ^\{n\}*n* by multiplication and division starting with *x* for the given positive integer *n*. Products and quotients appearing in the sequence of operations should be *x* to a positive integer's power. In other words, *x* ^\{-3\}−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 *x* ^\{n\}*n* 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**复制

1
    31
    70
    91
    473
    512
    811
    953
    0

**输出 \#1**复制

0
    6
    8
    9
    11
    9
    13
    12

这道题有点尴尬，大多都是英语，幸好浏览器是可以翻译的。

![1551435-20190811171652788-1167478028.png][]

先来确定算法。

这道题先来思考用什么算法？似乎没什么特殊的算法，那么就只能搜索了。

是深搜呢？还是广搜呢？广搜没前途，状态不好记录，深搜又控制不住，一条路走到黑。

其实这道题直接迭代加深搜索就可以了。

什么是迭代加深搜索？就是深搜设定上一个搜索的边界，逐步加深这个边界，这样每次会限制其搜索的深度，就不会一条路走到黑了。

但是这是依旧相当的暴力啊！！！

小编试了一下，连样例数据都卡到爆了，所以必须进一步优化，这里使用剪枝优化。

如果当前的指数自乘剩下的次数之后仍然比n小，那么我们就一定会果断舍弃，这就是剪枝的内容。

代码如下：

1 #include<iostream>
     2 using namespace std;
     3 int num[10000],n,idt;//用num来存储已经创造过的可以用于计算的数，idt是限制的深度
     4 bool dfs(int step,int now)//step是当前用了多少次运算，now是当前指数
     5 {
     6     if(now<=0||step>idt||now<<(idt-step)<n) return false;//判断一定不能成功的条件和剪枝
     7     if(now<<(idt-step)==n) return true;//剪枝
     8     if(now==n) return true;//如果正确，那么就返回
     9     num[step]=now;//存储一下这个指数
    10     for(int i=0;i<=step;i++)
    11     {
    12         if(dfs(step+1,now+num[i])) return true;//乘
    13         if(dfs(step+1,now-num[i])) return true;//除
    14     }
    15     return false;//不成功一定要最后返回false
    16 }
    17 int main()
    18 {
    19     while(1)
    20     {
    21         cin>>n;
    22         if(n==0) break;
    23         for(idt=0;;idt++)//从0开始枚举深度
    24         if(dfs(0,1)==true) break;//发现可以就结束循环
    25         cout<<idt<<endl;
    26     }
    27     return 0;
    28 }

转载于:https://www.cnblogs.com/TFLS-gzr/p/11335906.html

[1551435-20190811171652788-1167478028.png]: /images/20230601/fbc46a4ed93e43369c43d5ed390558f2.png