【题解】AcWing 193. 算乘方的牛
2024-10-18 19:12:41
题目描述
约翰的奶牛希望能够非常快速地计算一个数字的整数幂P(1 <= P <= 20,000)是多少,这需要你的帮助。
在它们计算得到最终结果的过程中只能保留两个工作变量用于中间结果。
第一个工作变量初始化为x,第二个工作变量初始化为1。
奶牛可以将任意一对工作变量相乘或相除(可以是一个工作变量与自己相乘或相除),并将结果储存在任意一个工作变量中,但是所有结果都只能储存为整数。
举个例子,如果它们想要得到x的31次方,则得到这一结果的一种执行方法如下所示:
工作变量1 工作变量2
开始 : x 1
工作变量1与本身相乘,结果置于工作变量2: x x^2
工作变量2与本身相乘,结果置于工作变量2: x x^4
工作变量2与本身相乘,结果置于工作变量2: x x^8
工作变量2与本身相乘,结果置于工作变量2: x x^16
工作变量2与本身相乘,结果置于工作变量2: x x^32
工作变量2除以工作变量1,结果置于工作变量2: x x^31
因此,x的31次方经过六个操作就可得到。
现在给出你希望求得的具体次幂数,请你计算至少需要多少个操作才能得到。
输入格式
输入包含一个整数P,表示具体次幂数。
输出格式
输出包含一个整数,表示所需最少操作数。
数据范围
1≤P≤20000
样例
输入样例:
31
输出样例:
6
算法1 迭代加深IDA*
剪枝:
1.首先容易考虑到:负数和零是不够优秀的。减去负数等效于加上正数,加上负数等效于减去正数,这样可以避免讨论多余的状态;而除了初始状态外,出现零是没有用的:因为这样相当于只有一个数可供操作。这样一定不会比这个非零的数与另一个非零的数合起来更优。
因此,除法操作时,总是用次数的多的除以次数少的,不使用自己除以自己的操作。乘法操作后,不保留0。
2.在当前深度限制下,如果剩下的步骤全部都把较大的数扩大为两倍还是比目标状态小,显然剪枝。
3.对于当前存储器中次数(a,b),设gcd(a,b)=d,那么不管之后怎么操作,得到的次数一定会是d的倍数。因此,如果不满足d|P,那么剪掉。
参考文献
https://blog.csdn.net/rgnoH/article/details/78469464
C++ 代码
#include <cstdio>
#include <iostream>
using namespace std;
int p,depth=0;
int gcd( int a,int b )
{
if ( !b ) return a;
return gcd( b,a%b );
}
bool IDAstar( int sum,int x,int y )
{
if ( sum==depth )
{
if ( x==p ) return 1;
else return 0;
}
if ( x<<(depth-sum)<p ) return 0;
if ( p%(gcd(x,y))!=0 ) return 0;
int a,b;
a=x+y; b=y;
if ( b && IDAstar( sum+1,a,b ) ) return 1;
a=x+y; b=x;
if ( b && IDAstar( sum+1,a,b ) ) return 1;
a=x+x; b=y;
if ( b && IDAstar( sum+1,a,b ) ) return 1;
a=x+x; b=x;
if ( b && IDAstar( sum+1,a,b ) ) return 1;
a=y+y; b=x; if ( a<b ) swap( a,b );
if ( b && IDAstar( sum+1,a,b ) ) return 1;
a=y+y; b=y;
if ( b && IDAstar( sum+1,a,b ) ) return 1;
a=x-y; b=x; if ( a<b ) swap( a,b );
if ( b && IDAstar( sum+1,a,b ) ) return 1;
a=x-y; b=y; if ( a<b ) swap( a,b );
if ( b && IDAstar( sum+1,a,b ) ) return 1;
return 0;
}
int main()
{
scanf( "%d",&p );
while ( !IDAstar( 0,1,0 ) ) depth++;
printf( "%d",depth );
}
最新文章
- VirtualBox安装MS-DOS6.22(图文教程)
- 跨域资源共享(CORS)在ASP.NET Web API中是如何实现的?
- java基本数据类型的字面量
- canvas知识点
- 关于struts2中的相对路径与绝对路径
- MYSQL数据表建立外键
- WeUI—微信官方UI库
- JLINK V8 Keil MDK4.10 STM32
- 【linux】
- SQL Server如何使用XML格式传输解析
- wamp的mysql密码修改
- COJN 0585 800604鸡蛋的硬度
- 改造百度UMeditor(UEditor-min)富文本编辑器的图片上传功能
- HDU [P3605] Escape
- RxJava系列7(最佳实践)
- BZOJ5418[Noi2018]屠龙勇士——exgcd+扩展CRT+set
- centos7.5 修改网卡名称
- C# GDI+编程之剖析startAngle和sweepAngle
- java:冒泡排序、选择排序、插入排序实现
- psd页面切割成html技巧总结
热门文章
- linux 进程间通信 共享内存 shmat
- 《GNU_Makefile》第4章——makefile规则
- linux正则表达式符号集
- 支付宝电脑网站支付 alipay.trade.page.pay
- 莫小安 Linux下Redis的安装与配置
- 新鲜出炉!面试90%会被问到的Java多线程面试题,史上最全系列!
- 面试官:小伙子,你给我说一下Java Exception 和 Error 的区别吧?
- python字节自适应转化单位KB、MB、GB
- [python学习手册-笔记]003.数值类型
- 【ACwing 93】【模版】非递归实现组合型枚举——模拟递归