例如, 如果他们想计算x^31, 一种计算方法是:
WV1 WV2
开始: x 1
存储器1和存储器1相乘&＃xff0c;结果存于存储器2: x x^2
存储器2和存储器2相乘&＃xff0c;结果存于存储器2: x x^4
存储器2和存储器2相乘&＃xff0c;结果存于存储器2: x x^8
存储器2和存储器2相乘&＃xff0c;结果存于存储器2: x x^16
存储器2和存储器2相乘&＃xff0c;结果存于存储器2: x x^32
存储器2和存储器1相除&＃xff0c;结果存于存储器2: x x^31
因此, x^31可以通过6次计算得出。给出要计算的幂次&＃xff0c;要求求出最少需要几次计算。 输入输出格式
输入
输出
输入样例
31
输出样例
6
别看什么乘啊除的&＃xff0c;就看它们的幂相加相减就行就是有a&＃61;1,b&＃61;0&＃xff0c;经过最小次数加减得到p 。
我先用的分支限界枚举深度&＃xff0c;然后就五个剪枝在题解里见啦
题解 1 #include
2 using namespace std;
3 int p;
4 int qwe;//随手打的&＃xff0c;表示深度&＃xff0c;分支限界必备
5 int _pow[100];//存2的次方的
6 void dfs(int a,int b,int dep)
7 {
8 if(a
9 swap(a,b);
10 if(dep&＃61;&＃61;qwe&＃43;1)//深度达到
11 {
12 if(a&＃61;&＃61;p||b&＃61;&＃61;p)//判断是否有p
13 {
14 cout<<qwe;
15 exit(0);//这里直接停止就可以避免其他搜索&＃xff0c;大大节省时间&＃xff0c;居家旅行必备
16 }
17 return;
18 }
19 if(a!&＃61;0&&b!&＃61;0&&p%(__gcd(a,b))!&＃61;0)return;//因为a&＃43;-b&＃61;&＃xff08;a0&＃43;b0&＃xff09;*gcd(a,b)&＃61;k*gcd(a,b),k为整数&＃xff0c;所以p必须能被gcd(a,b) 整除
20 if(a*_pow[qwe-dep&＃43;1]
21 if(a>p&&b&＃61;&＃61;0)return;//这个只能加自己或减自己&＃xff0c;而本来就大所以不能加&＃xff0c; 而减就变成0&＃xff0c;所以不优秀
22 if(a>2*p)return;//这个一看就知道加到两倍的p去了&＃xff0c;肯定不优秀
23 if(a&＃61;&＃61;b)return;//两个数相等和一个数差不多&＃xff0c;所以不优秀
24 /*下面8种自己慢慢枚举
25 原来是有12种的&＃xff0c;但是0的话就等于只有一个数可操作&＃xff0c;不够优秀
26 而加上负数等于减去正数&＃xff0c;减去负数等于加上正数&＃xff0c;所以这里 用的abs */
27 dfs(a&＃43;b,b,dep&＃43;1);
28 dfs(a&＃43;b,a,dep&＃43;1);
29
30 dfs(abs(a-b),b,dep&＃43;1);
31 dfs(abs(a-b),a,dep&＃43;1);
32
33 dfs(a&＃43;a,b,dep&＃43;1);
34 dfs(a&＃43;a,a,dep&＃43;1);
35
36 dfs(b&＃43;b,b,dep&＃43;1);
37 dfs(b&＃43;b,a,dep&＃43;1);
38 }
39 int main()
40 {
41 _pow[0]&＃61;1;//0次方是1
42 for(int i&＃61;1;i<&＃61;16;i&＃43;&＃43;)//枚举2的次方&＃xff0c;方便极大化剪枝
43 {
44 _pow[i]&＃61;_pow[i-1]*2;
45 }
46 cin>>p;
47 //分支限界
48 for(qwe&＃61;1;;qwe&＃43;&＃43;)//一定从0开始&＃xff0c;万一碰到那些p&＃61;&＃61;0或者p&＃61;&＃61;1 就等着~~听取WA声一片~~吧
49 {
50 dfs(1,0,1);
51 }
52 return 0;
53 }
京公网安备 11010802041100号