程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 3134 Power Calculus(迭代加深dfs)

poj 3134 Power Calculus(迭代加深dfs)

編輯：C++入門知識

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 x³¹ with thirty multiplications:

x² = x × x, x³ = x² × x, x⁴ = x³ × x, …, x³¹ = x³⁰ × x.

The operation of squaring can be appreciably shorten the sequence of multiplications. The following is a way to compute x³¹ with eight multiplications:

x² = x × x, x³ = x² × x, x⁶ = x³ × x³, x⁷ = x⁶ × x, x¹⁴ = x⁷ × x⁷, x¹⁵ = x¹⁴ × x, x³⁰ = x¹⁵ × x¹⁵, x³¹ = x³⁰ × x.

This is not the shortest sequence of multiplications to compute x³¹. There are many ways with only seven multiplications. The following is one of them:

x² = x × x, x⁴ = x² × x², x⁸ = x⁴ × x⁴, x⁸ = x⁴ × x⁴, x¹⁰ = x⁸ × x², x²⁰ = x¹⁰ × x¹⁰, x³⁰ = x²⁰ × x¹⁰, x³¹ = x³⁰ × x.

If division is also available, we can find a even shorter sequence of operations. It is possible to compute x³¹ with six operations (five multiplications and one division):

x² = x × x, x⁴ = x² × x², x⁸ = x⁴ × x⁴, x¹⁶ = x⁸ × x⁸, x³² = x¹⁶ × x¹⁶, x³¹ = x³² ÷ x.

This is one of the most efficient ways to compute x³¹ 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ⁿ 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 xⁿ 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

Sample Output

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)