文章作者: Donquixote
缘起:
某个网游里有个任务让玩家玩猜数字,猜对送物品,不怎么值钱
但是如果用脱机程序自动猜的话......挥钱如土,日耗万金,岂不快哉?!
找了个算法插进脱机程序里,无奈效率太低,而且耗费系统资源,一台机器挂5个号就很卡
于是自己写了一个,效果和效率要略好一些
思路:
没学过什么算法,所以换了个角度考虑,即如何找出更好的算法(而不在意它的具体实现)
显然猜数算法可分两类,确定的和非确定的.不包括随机函数或随机函数种子固定的算确定的算法,包括随机函数的算不确定算法
对于确定算法,对于同一个数字,每次猜测总是确定的,比如第一次总猜1234
可以证明,就概率来说,确定的算法一定不会比不确定的差,或者说最好算法可以在确定的算法中找到
因为对每个数字猜测总是确定的,很容易想到构件一张表来查表猜数,这样效率要提高若干倍
例如:让一个确定算法去猜所有可能的数字(从0开始就是5040个,从1开始是3024个),第一次猜1234,可能的结果有哪些?
0a0b0a1b0a2b...0a4b
1a0b1a1b...1a3b
....
4a0b
一共14种可能(为什么不是5+4+3+2+1=15种?因为3a1b是不可能的...)
如此,可把5040个数字归入guess=1234的14种情况中作为第一个节点,对每种情况建立字节点,每个子节点再分14类,以次类推
这样就建立一个树,总结了所有可能,查表就能猜数
上面是说从确定算法->树.显然,每个确定算法都可以构件这么个树,于是算法之好坏可化乎树之好坏,要找好的算法就是找好的树
既然如此,完全可以抛开算法不考虑,直接去构件树
什么样的树最好?可要求他的每个节点的14个子树所包括的数字中的最大的一支也最小,意思就是此节点尽可能的平均划分了数字
(调整条件会影响结果,下面代码中用幂函数来评估,取1.25次方时效果比较好)
以此思路,不用想什么算法,直接穷举找树就完了
代码:
#defineSTART0
intSPECISE[14]={00,01,02,03,04,10,11,12,13,20,21,22,30,40};
structNUM
{
chara,b,c,d;
intisvalid()
{
if(a9)return0;
if(b9)return0;
if(c9)return0;
if(d9)return0;
if(a==b||a==c||a==d)return0;
if(b==c||b==d)return0;
if(c==d)return0;
return1;
}
intin(intnum)
{
a=(num/1000)%10;
b=(num/100)%10;
c=(num/10)%10;
d=(num)%10;
returnisvalid();
}
NUM(){;}
NUM(intnum){in(num);}
};
intcheck(NUMn,NUMm)
{
intA=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++;
returnA*10+B;
}
intspecise(intcheck)
{
for(inti=0;i<14;i++)if(check==SPECISE)break;
returni;
}
intspecise(NUMn,NUMm)
{
returnspecise(check(n,m));
}
#definePOWER1.25
structNODE
{
intguess;
vectornums;
inttotal;
NODE*child[14];
NODE()
{
total=0;
for(inti=0;i<14;i++)child=NULL;
}
~NODE()
{
for(inti=0;i<14;i++)if(child)deletechild;
}
intfindguess()
{
if(nums.size()==1)
{
guess=*nums.begin();
return1;
}
NUMn;
doublemax=pow(5040,5);
vector::iteratorvi_cur;
for(vi_cur=nums.begin();vi_cur!=nums.end();vi_cur++)
//for(inti=0;i<10000;i++)
{
inti=*vi_cur;
if(!n.in(i))continue;
ints[14]={0};
vector::iteratorvi;
for(vi=nums.begin();vi!=nums.end();vi++)s[specise(*vi,n)]++;
doubles_max=0;
for(intj=0;j<14;j++)
{
//if(s_maxs_max+=pow(s[j],POWER);
//s_max+=sqrt(s[j]);
}
if(s_max{
max=s_max;
guess=i;
}
}
return1;
}
intgenerate()
{
if(nums.size()<=1)return1;
inti;
vectortmp_nums[14];
vector::iteratorvi;
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.size()==1&&*tmp_nums.begin()!=guess)
{
child=newNODE;
child->nums=tmp_nums;
}
if(tmp_nums.size()>1)
{
child=newNODE;
child->nums=tmp_nums;
}
}
for(i=0;i<14;i++)
{
if(child)child->findguess();
if(child)child->generate();
}
for(i=0;i<14;i++)if(child)total+=child->total;
total++;
return1;
}
};
intmain(intargc,char*argv[])
{
NODE*tree=newNODE;
tree->guess=1234;
NUMn;
for(inti=0;i<10000;i++)
{
if(!n.in(i))continue;
tree->nums.push_back(i);
}
tree->generate();
printf("treehasbeengenerated!\r\n");
inttimes[15]={0};
for(i=0;i<10000;i++)
{
if(!n.in(i))continue;
inttime=0;
NODE*node=tree;
while(1)
{
time++;
if(check(node->guess,i)==40)break;
node=node->child[specise(node->guess,i)];
}
times[time]++;
}
floatamount=0;
floattotal=0;
for(i=1;i<15;i++)
{
amount+=times;
total+=times*i;
printf("%d=%d\r\n",i,times);
}
printf("amount=%d\r\n",(int)amount);
printf("a=%f\r\n",total/amount);
deletetree;
return0;
}
结果:
从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次
