缘起:
某个网游里有个任务让玩家玩猜数字,猜对送物品,不怎么值钱
但是如果用脱机程序自动猜的话......挥钱如土,日耗万金,岂不快哉?!
找了个算法插进脱机程序里,无奈效率太低,而且耗费系统资源,一台机器挂5个号就很卡
于是自己写了一个,效果和效率要略好一些

思路:
没学过什么算法,所以换了个角度考虑,即如何找出更好的算法(而不在意它的具体实现)
显然猜数算法可分两类,确定的和非确定的.不包括随机函数或随机函数种子固定的算确定的算法,包括随机函数的算不确定算法
对于确定算法,对于同一个数字,每次猜测总是确定的,比如第一次总猜1234
可以证明,就概率来说,确定的算法一定不会比不确定的差,或者说最好算法可以在确定的算法中找到
因为对每个数字猜测总是确定的,很容易想到构件一张表来查表猜数,这样效率要提高若干倍
例如:让一个确定算法去猜所有可能的数字(从0开始就是5040个,从1开始是3024个),第一次猜1234,可能的结果有哪些?
0a0b 0a1b 0a2b...0a4b
1a0b 1a1b...1a3b
....
4a0b
一共14种可能(为什么不是5+4+3+2+1=15种?因为3a1b是不可能的...)
如此,可把5040个数字归入guess=1234的14种情况中作为第一个节点,对每种情况建立字节点,每个子节点再分14类,以次类推
这样就建立一个树,总结了所有可能,查表就能猜数
上面是说从确定算法->树.显然,每个确定算法都可以构件这么个树,于是算法之好坏可化乎树之好坏,要找好的算法就是找好的树
既然如此,完全可以抛开算法不考虑,直接去构件树
什么样的树最好?可要求他的每个节点的14个子树所包括的数字中的最大的一支也最小,意思就是此节点尽可能的平均划分了数字
(调整条件会影响结果,下面代码中用幂函数来评估,取1.25次方时效果比较好)
以此思路,不用想什么算法,直接穷举找树就完了

代码:
#define START 0
int SPECISE[14]={00,01,02,03,04,10,11,12,13,20,21,22,30,40};

struct NUM
{
        char a,b,c,d;
        int isvalid()
        {
                if(a<START || a>9)return 0;
                if(b<START || b>9)return 0;
                if(c<START || c>9)return 0;
                if(d<START || d>9)return 0;
                if(a==b||a==c||a==d)return 0;
                if(b==c||b==d)return 0;
                if(c==d)return 0;
                return 1;
        }
        int in(int num)
        {
                a=(num/1000)%10;
                b=(num/100)%10;
                c=(num/10)%10;
                d=(num)%10;
                return isvalid();
        }
        NUM(){;}
        NUM(int num){in(num);}
};

int check(NUM n,NUM m)
{
        int A=0,B=0;
        if(m.a==n.a)A++;
        if(m.b==n.b)A++;
        if(m.c==n.c)A++;
        if(m.d==n.d)A++;
        if(m.a==n.b||m.a==n.c||m.a==n.d)B++;
        if(m.b==n.a||m.b==n.c||m.b==n.d)B++;
        if(m.c==n.a||m.c==n.b||m.c==n.d)B++;
        if(m.d==n.a||m.d==n.b||m.d==n.c)B++;
        return A*10+B;
}
int specise(int check)
{
        for(int i=0;i<14;i++)if(check==SPECISE[i])break;
        return i;
}
int specise(NUM n,NUM m)
{
        return specise(check(n,m));
}

#define POWER 1.25

struct NODE
{
        int guess;
        vector<int> nums;
        int total;
        NODE*child[14];
        NODE()
        {
                total=0;
                for(int i=0;i<14;i++)child[i]=NULL;
        }
        ~NODE()
        {
                for(int i=0;i<14;i++)if(child[i])delete child[i];
        }
       
        int findguess()
        {
                if(nums.size()==1)
                {
                        guess=*nums.begin();
                        return 1;
                }

                NUM n;
                double max=pow(5040,5);

                vector<int>::iterator vi_cur;
                for(vi_cur=nums.begin();vi_cur!=nums.end();vi_cur++)
                //for(int i=0;i<10000;i++)
                {
                        int i=*vi_cur;
                        if(!n.in(i))continue;

                        int s[14]={0};
                        vector<int>::iterator vi;
                        for(vi=nums.begin();vi!=nums.end();vi++)s[specise(*vi,n)]++;

                        double s_max=0;
                        for(int j=0;j<14;j++)
                        {
                                //if(s_max<s[j])s_max=s[j];
                                s_max+=pow(s[j],POWER);
                                //s_max+=sqrt(s[j]);
                        }

                        if(s_max<max)
                        {
                                max=s_max;
                                guess=i;
                        }
                }
                return 1;
        }

        int generate()
        {
                if(nums.size()<=1)return 1;

                int i;

                vector<int>tmp_nums[14];
                vector<int>::iterator vi;
                for(vi=nums.begin();vi!=nums.end();vi++)
                {
                        tmp_nums[specise(*vi,guess)].push_back(*vi);
                }
               
                for(i=0;i<14;i++)
                {
                        if(tmp_nums[i].size()==1 && *tmp_nums[i].begin()!=guess)
                        {
                                child[i]=new NODE;
                                child[i]->nums=tmp_nums[i];
                        }
                        if(tmp_nums[i].size()>1)
                        {
                                child[i]=new NODE;
                                child[i]->nums=tmp_nums[i];
                        }
                }
               
                for(i=0;i<14;i++)
                {
                        if(child[i])child[i]->findguess();
                        if(child[i])child[i]->generate();
                }

                for(i=0;i<14;i++)if(child[i])total+=child[i]->total;
                total++;

                return 1;
        }
};

int main(int argc, char* argv[])
{
        NODE*tree=new NODE;
        tree->guess=1234;
        NUM n;
        for(int i=0;i<10000;i++)
        {
                if(!n.in(i))continue;
                tree->nums.push_back(i);
        }
        tree->generate();
       
        printf("tree has been generated!\r\n");

        int times[15]={0};
        for(i=0;i<10000;i++)
        {
                if(!n.in(i))continue;

                int time=0;
                NODE*node=tree;
                while(1)
                {
                        time++;
                        if(check(node->guess,i)==40)break;
                        node=node->child[specise(node->guess,i)];
                }
                times[time]++;
        }

        float amount=0;
        float total=0;
        for(i=1;i<15;i++)
        {
                amount+=times[i];
                total+=times[i]*i;
                printf("%d=%d\r\n",i,times[i]);
        }
        printf("amount=%d\r\n",(int)amount);
        printf("a=%f\r\n",total/amount);

        delete tree;
        return 0;
}

结果:

从1开始
1=1
2=13
3=104
4=570
5=1520
6=784
7=32
平均5.008929次

从0开始
1=1
2=13
3=109
4=647
5=2072
6=1904
7=289
8=5
平均5.315278次

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课