被搞残了,还把袁源也连累了,主要昨天写的有点厌烦情绪,不愿意静心来分析代码!
这个习惯太差了,不会思考的人就不会写代码,我悔过我认错!
可以用Gprof来分析代码:gprof -a 。。。。https://www.cs.drexel.edu/cgi-bin/manServer.pl/usr/share/man/man1/gprof.1可以导出函数调用次数,唉!要能用VS的工具就好了,可惜MS的工具要交钱,买不起哟!~~~~
提醒自己:
1。消栈的时候,要注意状态如何减去,很重要[可以多次剪枝],尤其是启发函数加最优剪枝是可以并举!这点是付出代价才学会的!
2。有函数增减性来剪枝的时候,千万要好好写,就是这个把正确的子数给砍掉了!
很奇怪福建的那个为什么不能Accept呢,难道还有什么地方不同,我想自己写个测试数据来试验,结果直接把那个“标程”给跑死了,俄!
算了,点到即止,等把下面的问题搞定再回头优化!
时间:370ms
#include <iostream>
#include <fstream>
using namespace std;
const int MAXSH=10;
unsigned long x,y;
typedef struct state{
    unsigned long a,b,i;
    int g;
    unsigned long path[MAXSH];
}state;
typedef state* stateptr;
const int MAXSK=10000000, INC=1;
state stack[MAXSK];
//pre-defined
void IDAstar(unsigned long x, unsigned long y);
unsigned long gcd(unsigned long x, unsigned long y);
//implementation
unsigned long gcd(unsigned long x, unsigned long y){
    //assert(x>0&&y>0);
    if(x==y) return x;//void swap
    if(x>y) x^=y,y^=x,x^=y;
    if(x==0) return y;
    //x<y
    if(x&0x1){//x odd
        if(y&0x1)//y odd
            return gcd(x, (y-x)>>1);
        else return gcd(x, y>>1);
    }
    else{//x is even
        if(y&0x1) return gcd(x>>1, y);
        else return 2*gcd(x>>1, y>>1);
    }
}
unsigned long path[MAXSK];
unsigned long best[MAXSK];
void IDAstar(unsigned long x, unsigned long y){
    assert(y>=x);
    if(x==1){
        cout<<1<<" "<<y<<endl;return;
    }
    if(y%x==0){
        cout<<1<<" "<<y/x<<endl;return;
    }
    int top=0,pathT=0u,bindex; unsigned long min=INC;
    bool success=false;
    do{
        //intial
        top=0,pathT+=INC;
        bindex=pathT;
        min=ULONG_MAX;
        stack[0].a=x,stack[0].b=y,stack[0].g=0,stack[0].i=y/x;
        memset((void*)best, 0xff, sizeof(long)*MAXSK);//sigh!
        top++;//stack top
        do{//pop-up first item
            state cur=stack[–top];
            if(cur.a==1){
                if(cur.g<=bindex&&cur.b>cur.i&&cur.b<best[bindex]){//incremental order
                    best[cur.g]=cur.b,bindex=cur.g;
                    memcpy((void*)best, cur.path, sizeof(long)*cur.g);
                    success=true;
                }
            }
            else{//cur.a!=1
                if(cur.a*(cur.i+1)/cur.b+cur.g<=pathT){//branches cut-off
                    long pre=(cur.b/cur.a>cur.i+1?cur.b/cur.a:cur.i+1),//incremental
                    next=(cur.b*(pathT-cur.g))/cur.a;//low boundary wrong!
                    if(cur.b/cur.a+pathT-cur.g+1>best[bindex]&&next<=cur.i){
                        continue;
                    }
                    if(pre<=next&&pre<=best[bindex]){//f value
                        for(long k=next;k>=pre;k–){//best[num] to cut off branches
                            long a=cur.a*k-cur.b, b=cur.b*k;//overflow
                            if(a<=0||b<=0) continue;//incremental function
                            long h=a*(k+1)/b;
                            //(a/b-1/k)*(k+1)=(k+1)a/b-(1+1/k),k des!
                            if(b/a+pathT-cur.g+1>best[bindex]) break;
                            if(h+cur.g+1>pathT) continue;
                            unsigned long d=gcd(a,b);
                            stack[top].a=a/d,stack[top].b=b/d,stack[top].g=cur.g+1;
                            stack[top].i=k;//previous value
                            stack[top].path[cur.g]=k;//copy into path
                            memcpy(stack[top].path, cur.path, sizeof(long)*cur.g);
                            top++;
                        }
                    }
                }
                else{
                    if(cur.g+cur.b/cur.a<min){
                        min=cur.g+cur.b/cur.a;//cut-off branches’s boundary
                    }
                }
            }
        }while(top>0&top<MAXSK);
    }while(!success&&top<MAXSK&&pathT<MAXSH);//top is valid?
    int i=0;
    while(best[i]!=ULONG_MAX){cout<<best[i]<<" ";i++;}
    cout<<endl;
}
#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>0){
        cin>>x,cin>>y;
        IDAstar(x,y);
        n–;
    }
    #ifdef fbase
    in.close();
    #endif
    return 0;
}
#undef fbase
 
递归版本的标程在CSDN上有,不过有些特殊的测试数据没有我的跑得快!但是福建的居然说我的答案有问题,我自己写了个程序来生成数据验证,都没发现错!
算了吧,没必要较真聊!
 
我的两组稀奇古怪的测试数据:那个递归的标程跑了3分钟多,我的只用了16s,不过牛人的程序应该瞻仰的,写得很飘逸!
袁源说的对,程序就是要思路清晰,我一定要加油,把基本算法的框架都要烂熟于胸[那种一边写一边写的习惯太要不的了!虽然我现在还完全做不到,但我一直会向着对程序框架和关键点都能熟练实现的目标加油的!]
Advertisements