以为自己很聪明用脑壳想,然后就开始写代码,结果。。。
其实完全不然,有些东西在纸上画一下,才不容易出错,细节的东西不需要多了!几点就可以搞定!
自己还完全不到打个腹稿就可以写出来的程度,尤其是与数学相关的题目!
IDA*的递归版本,我终于知道那个“标程”为什么那么慢了,呵呵,牛人偷了一下懒!
我的自己的递归IDA*程序,可惜在算最优值的时候,又把公式写错了,唉!失败,还是调试找出来的,太失败料!
这个教训就是,在没有把握的时候,还有要在草稿纸上写点关键的东西,“欲速则不达”,要一步一步地来,熟练了,再说
直接用腹稿写代码吧!
 
#include <iostream>
#include <fstream>
using namespace std;
//.data segment
unsigned long x,y;
const int MAXSL=10000, INC=1;//path is shorter then stack height
unsigned long tempa[MAXSL], tempb[MAXSL], v[MAXSL], best[MAXSL];
//recursive IDAstar
void IDAstar(unsigned long x, unsigned long y);
void dfs(int step, const int& PathLimits, bool& success);//don’t use bool,then logic operation, ref is faster.
unsigned long gcd(unsigned long x, unsigned long y);
//implementation
void IDAstar(unsigned long x, unsigned long y){
    //cut-off simple case
    assert(x<=y);
    if(x==1){cout<<"1 "<<y<<endl;return;}
    if(y%x==0){cout<<"1 "<<y/x<<endl;return;}
    int pathLimits=1;//inc=1
    bool success=false;
    do{
        pathLimits+=INC;
        tempa[0]=x,tempb[0]=y;//input
        best[pathLimits-1]=ULONG_MAX;//max
        dfs(0, pathLimits, success);
    }while(!success);
    for(int i=0; i<pathLimits; i++) cout<<best[i]<<" ";
    cout<<endl;
}
void dfs(int step, const int& PathLimits, bool& success){//0…pathLimts[pathLimts] MAX
    if(step==PathLimits-1){
        if(tempa[step]==1&&tempb[step]>v[step-1]&&tempb[step]<best[PathLimits-1]){
            memcpy((void*)best, (void*)v, sizeof(unsigned long)*(PathLimits-1));
            best[PathLimits-1]=tempb[step];
            success=true;
        }
        return;
    }
    unsigned long pre=tempb[step]/tempa[step];
    if(step>0&&v[step-1]+1>pre) pre=v[step-1]+1;
    unsigned long next=(PathLimits-step)*tempb[step]/tempa[step];
    //best cut-off
    if(tempb[step]/tempa[step]+PathLimits-step-1>best[PathLimits-1]) return;
    for(unsigned long cur=pre;cur<=next;cur++){
        v[step]=cur;
        //cut-off all zero
        tempa[step+1]=tempa[step]*cur-tempb[step], tempb[step+1]=tempb[step]*cur;
        //cur incremental function
        if(tempa[step+1]<=0) continue;
        if(tempb[step+1]<=0) break;//cur overflow
        assert(tempa[step+1]>0&&tempb[step+1]>0);
        unsigned long d=gcd(tempa[step+1], tempb[step+1]);
        tempa[step+1]/=d,tempb[step+1]/=d;
        //pre-cut-off,f and best
        if(tempb[step+1]/tempa[step+1]+PathLimits-step-1<=best[PathLimits-1]
            &&step+1+(cur+1)*tempa[step+1]/tempb[step+1]<=PathLimits){
                dfs(step+1, PathLimits, success);
        }
    }
}
unsigned long gcd(unsigned long x, unsigned long y){
    assert(x>=0&&y>=0);
    if(x==y)return x;
    if(x>y) x^=y,y^=x,x^=y;
    if(x==0) return y;
    if(x&0x1){
        if(y&0x1) return gcd(x, (y-x)>>1);
        else return gcd(x, y>>1);
    }
    else{
        if(y&0x1) return gcd(x>>1, y);
        else return gcd(x>>1,y>>1)*2;
    }
}
#define fbase
int main()
{
    #ifdef fbase
    ifstream in("input.txt");
    if(!in) return EXIT_FAILURE;
    cin.rdbuf(in.rdbuf());
    #endif
    int n;
    cin>>n;
    while(n){
        cin>>x,cin>>y;
        IDAstar(x,y);
        n–;
    }
    #ifdef fbase
    in.close();
    #endif
    return 0;
}
#undef fbase
Advertisements