程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 3134Power Calculus(IDA*)

POJ 3134Power Calculus(IDA*)

編輯: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 x31 with thirty multiplications:

x2 = x × x, x3 = x2 × x, x4 = x3 × x, …, x31 = x30 × x.

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

x2 = x × x, x3 = x2 × x, x6 = x3 × x3, x7 = x6 × x, x14 = x7 × x7, x15 = x14 × x, x30 = x15 × x15, x31 = x30 × x.

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

x2 = x × x, x4 = x2 × x2, x8 = x4 × x4, x8 = x4 × x4, x10 = x8 × x2, x20 = x10 × x10, x30 = x20 × x10, x31 = x30 × x.

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

x2 = x × x, x4 = x2 × x2, x8 = x4 × x4, x16 = x8 × x8, x32 = x16 × x16, x31 = x32 ÷ x.

This is one of the most efficient ways to compute x31 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 xn 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?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 xn 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

1
31
70
91
473
512
811
953
0

Sample Output

0
6
8
9
11
9
13
12



第一道IDA*。。。

題目大意:求用一個x,如何在最小的步數使用已經用過的湊出x^n,其中n是1~1000的,可以搜索,很容易想到,<=0和>=2000的點應該直接剪掉。 開始一直在糾結BFS會不會超時,實在不行就打表,但是寫到最後才發現自己寫的BFS有問題。因為你每次擴充點的時候,如果選擇不擴充,那麼就必須回溯,因為這個點不能選擇了。。。
最後看了度娘的博客,寫的IDA*,對那個理解也很淺顯,就是搜索的時候控制搜索的層數即可。然後還有一個剪枝a[pos]<<(deep-pos)
AC代碼:
#include
#include
using namespace std;

int a[2014];
int flag,deep,n;

void dfs(int pos)
{
    int t;
    if(flag||pos>deep) return;
    if(a[pos]<<(deep-pos)=1 && t<2000)
        {
            a[pos+1]=t;
            dfs(pos+1);
        }
    }
}

int main()
{
    while(cin>>n&&n)
    {
        deep=1,flag=0;
        a[1]=1;
        while(1)
        {
            dfs(1);
            if(flag) break;
            deep++;
        }
        cout<

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved