[源码] 猜数字算法 [二] (as2.0)

刚实现了计算机出题,让我们猜,那可以让我们出题,让计算机来猜吗?当然可以,而且也可以验证一下计算机是不是都能在七次以内完成数字的猜测..首先先看一下算法的演示.[点进预览]

算法的原理,还是使用网上较为普遍的枚举排除法,因为原理简单,所以也较容易理解与实现.

从0~9随便取出四位组成一个互不相同的四位数,按照组合的算法,一共有10*9*8*7=5040个.也就是无论你想的是哪一个数,一定是在这 5040个里面.所以我们每一步就必须枚举出这5040个可能组合,并存于一个数组中,我们称这个数组为字典,我们的答案就存在这个字典里面,每一次我们 都从字典里取出一个来猜测,并排除一切不符合判断结果的项,从字典里删除,一直排除到只剩一项的时候,就是我们的正确答案了.

.我们可以先通过一个函数来检测这个四位数是否是各个位置上都不相同的.

var dictArray ;//当前可能枚举的数组

function chkSameNum(num)//检查数字中是否有相同的数字
{
 num = parseInt(num,10);//保证如0123这样的数能够正确的被转化为10进制的数
 var a=parseInt(num/1000)%10; 
 var b=parseInt(num/100)%10;
 var c=parseInt(num/10)%10;
 var d=parseInt(num)%10;
 
 if(a==b || a==c || a==d || b==c || b==d || c==d) return true;
 return false;
}

接着我们可以通过一个循环来存储整个初始枚举字典.

 dictArray = new Array();
 for(var i=123;i<=9876;i++)
 {
  if(!chkSameNum(i))
  {
   if(i<1000)dictArray.push("0"+i);
   else dictArray.push(""+i);
  } 
 }

对任何一个数的猜测,到底有多少种判断结果呢?我们先来罗列一下.

0A0B,0A1B,0A2B,0A3B,0A4B
1A0B,1A1B,1A2B,1A3B
2A0B,2A1B,2A2B
3A0B
4A0B

可以看到一共有十四种判断结果,注意,是不会有出现3A1B的情况的.我们可以将每一个判断用一个数字来表示.10位数表示A,个位数表示为B,则 任何一种判断可以表示为A*10+B .chkScore函数是对随意的两个四位数进行比较,并返回比较的判断结果,如两个数的判断结果为40,也即4A0B,所以两个数为相同的数.

function chkScore(guessnum,textnum)
{
 var a=0,b=0;
 for(var i=0;i<4;i++)
 {
  for(var j=0;j<4;j++)
  {
    if(guessnum.substr(j,1)==textnum.substr(i,1))
    {
     if(i==j)a++;
     else b++;
    }
  }
 }
 return a*10+b;
}

那么我们只要将每次猜测的数与字典里的每个数做比较得到判断结果,然后再独个的与用户输入的判断结果做比较,不相同的则从字典里删除,这样,只要多次猜测多次排除就可以得到一个唯一的结果,也即正确的结果.

 for(var i=dictArray.length-1;i>=0;i--)
  {
     if(chkScore(guessnum,dictArray[i])!=score)
    dictArray.splice(i,1);
  }

完整的源码可以通过演示预览,并通过右键查看源文件得到...

在枚举所有可能值与第一次猜测的时候,需要花费很长的时间(大概在10S左右)导致假死状态,也关无法响应,其实这并不是算法太慢的问题,而是下拉列表要显示太多的选项而拖慢了..