POJ-3134-Power Calculus(迭代加深DFS)

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 integer n. Products and quotients appearing in the sequence
should be x to a positive integer’s power. In others words, x⁻³, 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

思路：用一个数组存每一次操作之后得到的数，剪下枝，迭代加深就可以。

详见代码。

#include <stdio.h>

#define max(A,B)(A>B?A:B)

int n,dep,num[15];

bool dfs(int cnt,int x)//x是上一次操作之后得到的最大的数

{

    if(num[cnt]==n) return 1;

    if(cnt>=dep) return 0;

    x=max(x,num[cnt]);

    if(x*(1<<(dep-cnt))<n) return 0;//假设最大的数都不能得到n就直接返回

    for(int i=0;i<=cnt;i++)

    {

        num[cnt+1]=num[cnt]+num[i];

        if(dfs(cnt+1,x)) return 1;

        if(num[cnt]>num[i]) num[cnt+1]=num[cnt]-num[i];

        else num[cnt+1]=num[i]-num[cnt];

        if(dfs(cnt+1,x)) return 1;

    }

    return 0;

}

int main()

{

    while(~scanf("%d",&n) && n)

    {

        if(n==1) printf("0\n");

        else

        {

            num[0]=1;

            for(dep=1;;dep++)

            {

                if(dfs(0,1)) break;

            }

            printf("%d\n",dep);

        }

    }

}

巴特西

POJ-3134-Power Calculus(迭代加深DFS)

最新文章

热门文章