題目：輸入正整數n(1n1000)，問最少需要幾次乘法可以從x得到？例如，需要6次：=x*x，,,,，，計算過程中，x應總是正整數。

分析：每次可以從已經得到的狀態數組中任選兩個進行加法和減法，不能產生重復的數。

可以剪枝，每次判斷當前的當前的最大狀態數*剩余深度后是否還比n小（n為所求數）也就是每次都最大狀態相加，如果最后最大狀態都滿足不了，那么可以確定這個深度不夠。

代碼：

#include<cstdio> #include<cstring> #include<cctype> #include<queue> #include<iostream> #include<vector> #include<list> using namespace std; int a; int v[100]; int power(int n) {int ans = 1;for (int i = 0; i < n; i++)ans *= 2;return ans; } bool dfs(int d,int maxd) {if (v[d] == a)return true;if (d == maxd)return false;int maxv = v[0];for (int i = 1; i <= d; i++)maxv = max(maxv, v[i]);if (maxv*power(maxd-d)< a)return false;for (int i = d; i>=0; i--) {v[d + 1] = v[d] + v[i];if (dfs(d + 1, maxd))return true;v[d + 1] = v[d] - v[i];if (dfs(d + 1, maxd))return true;}return false; } int solve(int n) {if (n == 1) return 0;v[0] = 1;for (int maxd = 1; maxd < 13; maxd++) {if (dfs(0, maxd)) return maxd;}return 13; } int main() {while (cin >> a && a) {cout << solve(a) << endl;}//system("pause");return 0; }

?

總結

以上是生活随笔為你收集整理的UVA1374 Power Calcilus快速幂计算的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。