缘起:
某个网游里有个任务让玩家玩猜数字,猜对送物品,不怎么值钱
但是如果用脱机程序自动猜的话......挥钱如土,日耗万金,岂不快哉?!
找了个算法插进脱机程序里,无奈效率太低,而且耗费系统资源,一台机器挂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次