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