首页 > Web开发, 挨踢(IT) > “猜手机号游戏”的源码分析:二分查找+面向对象

“猜手机号游戏”的源码分析:二分查找+面向对象

2012年12月17日 发表评论 阅读评论 1,889 人阅读    

  很多朋友体验了“给哥三十五次机会,哥就能猜中你的手机号”,反馈还不错。有些明眼的朋友,一眼就看出来所用的算法。D瓜哥表示很佩服。另外有一些朋友也问所使用的算法,D瓜哥今天就把源代码和算法全部揭晓。

  其实,这个代码很简单。不过也有三个看点:二分查找算法、面向对象编程和对数的计算。下面我们一一讲解。

二分查找算法

  基本原理是二分查找算法。首先,我们先简要介绍一下“二分查找算法”。

  二分查找又称折半查找,它充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下时间复杂度是O(log2n)。由此看出,二分查找的优点很明显:比较次数少,查找速度快,,平均性能好;不过,也有一些缺点。其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。

  二分查找运行时,会首先,假设列表中元素是按升序排列,将列表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将列表分成前、后两个子列表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子列表,否则进一步查找后一子列表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子列表不存在为止,此时查找不成功。

  基本原理是这样。不过,我在处理的时候没有列表,直接拿(min+max)/2来显示“猜测结果”。说到这里了,再多说一句。其实是用(min+max)/2的计算有Bug,可能会产生溢出问题。更好的计算方法是:min+(max-min)/2;或是(min+max)>>>1。

面向对象编程

  在Javascript中进行“面向对象编程”一直是我提倡的实践。这样,能良好的封装代码,提高代码的可重用性、可读性以及可维护性。以前的文章里面,也多次提到要整几篇文章,讲解一下“面向对象编程”。只是因为各种原因,一直未能兑现。抱歉,这篇也只能讲解个大概。不过,我保证,这方面的内容,一定会写出来的。

  扯淡为目的的文章不是好文章。转入正题。因为,我这篇文章只要是分析“猜手机号游戏”的源代码,所以就直接拿源代码讲解面向对象了。

  在对象封装方面,我使用了“构造函数模式”。具体代码如下:


/**
* numberScope 需要猜测的数字范围
*/
function GuessNumber(numberScope){
	this._maxNumber = -1; // 猜测范围中,最大的数
	this._minNumber = 0; // 猜测范围中,最小的数
	this._nowNumber = -1; // 目前猜测出来的数
	this._count = 0;  // 需要猜测的次数
	this._times = 0;  // 猜测的次数
	this._result = 0; // 猜测结果
	this._complete = false; // 猜测是否完成
	this._success = false; // 猜测是否成功。

	this.setNumberScope(numberScope); //设置猜数范围,这里默认从0开始.

}

  这样的话,就可以使用new 来创建对象,同时一些必要的值,也可以在new的时候,通过构造函数的参数传进去。创建对象的代码如下:


var guess = new GuessNumber(100);

  大家也许注意到了,上面构造函数中的有一行方法调用的代码,如下:


this.setNumberScope(numberScope); //设置猜数范围,这里默认从0开始.

也许大家会奇怪,这个方法是从哪里来的呢?

  在对象上添加方法,我使用了“原型模式”。JavaScript中的原型prototype,最大的特点就是“共享”。由于,函数只需要“一套”,所有对象都可以共用一套函数。所以,这种共享特性非常适合用来定义函数。代码如下:


GuessNumber.prototype = {
    constructor: GuessNumber,

    //设置数字范围
    setNumberScope: function(numberScope){
        if(numberScope < 0){
            alert("数字范围不能小于0!");
            return;
        }
        this._numberScope = numberScope;
        this.start(this._minNumber, numberScope);
    },

    //开始游戏,初始化一些必要的数据。主要是为方便重新设定最小值。所以将最小值作为第一个参数
    start: function(minNumber, maxNumber) {
        var inMinNum = this._minNumber;
        var inMaxNum = this._numberScope;
        this._minNumber = -1;
        this._maxNumber = 1;

        // 当minNumber为0时,需要特殊处理一下。
        var minNumberStr = minNumber + ""; 
        if (minNumberStr != "") {
            inMinNum = minNumber;
        }

        if (maxNumber) {
            inMaxNum = maxNumber;
            this._numberScope = maxNumber;
        }
        
        this._complete = false;
        this._success = false;
        this._times = 0;
        
        this.changeFields(inMaxNum, inMinNum);
        this.setCount();
    },

    // 计算所需猜测的次数
    setCount: function() {
        this._count = Math.ceil(Math.log(this._maxNumber - this._minNumber) / Math.log(2)) + 1;
    },

    //猜测的数字太小,调大数字
    toLarger: function(){
        this.changeFields(this._maxNumber, this._nowNumber);
    },

    //猜测的数字太大,调小数字
    toSmaller: function(){
        this.changeFields(this._nowNumber, this._minNumber);
    },

    //计算数字大小,修改相应值
    changeFields: function(maxNumber, minNumber){

        if(maxNumber <= minNumber || maxNumber == this._minNumber + 1) {
            if(!this._complete) {
                this.complete();
            }				
            return;
        }
        if(this._maxNumber !== maxNumber) {
            this._maxNumber = maxNumber;
        }

        if(this._minNumber !== minNumber) {
            this._minNumber = minNumber;
        }

        this._nowNumber = Math.round((this._maxNumber + this._minNumber) / 2);
        this._times ++;
    },
    ……
}

  注意,这个的第二行。使用这种语法是非常方便。但是,却从本质上改变了GuessNumber.prototype。致使constructor不再指向GuessNumber函数。这样做是特意将其设置成GuessNumber,以使其能访问到合适的值。

  这样,最主要的代码都已经完成。剩下的工作就是调用相应的方法就行。更加详细、完整的代码将在下面展示。

对数的计算

  这里讲解一些数学上的知识。不喜欢的,可以忽略过去。

  大家也许好奇,为啥我能准确估算出“猜测次数”。其实,我们可以反过来考虑,比我们需要找一个比n(n为正整数)大的数。我们可以从1开始向后数,数到n,再到n+1就可以了。但是这种效率有点低,我们都学过乘方,我们可以从1开始,反复乘以2,假如需要乘以x个2,即2x >= n,这样效率就会很高。再反过来,负负得正,在一个1到2x范围内,我们每次砍去一半,最多砍到第x次,就肯定能找出这个数过来。那么,这个x怎么求呢?

  其实,这就要用到数学的对数知识。用数学公式来求解的话,就是x = log2n。在Javascript中,数学相关的计算方法都在Math中。查一下Math的API,我们就会发现只有一个Math.log(n)方法,而且这个方法求的是以10为底n的对数。我们需要求的是以2为底n的对数,不符合我们的需求。肿么办?这时,数学知识再次向我们展示了她的无穷魅力。

  可能我们在高中学过对数,了解对数的变换公式。其中一个就能帮助我们:logab = logmb / logma。所以,我们的问题就迎刃而解:x = log10n / log102。在数学中,log10n可以简写成logn,所以 x = log10n / log102 = logn / log2。不过,这样计算出来的结果还会有小数点,这是我们只需要来个“向上取整”就可以了。具体代码如下:


// 计算所需猜测的次数
setCount: function() {
    this._count = Math.ceil(Math.log(this._maxNumber - this._minNumber) / Math.log(2)) + 1; //加1,确保次数肯定用。
},

完整代码实现

  下面把完整代码贴出来,方便大家阅读。


/**
* numberScope 需要猜测的数字范围
*/
function GuessNumber(numberScope){
    this._maxNumber = -1; // 猜测范围中,最大的数
    this._minNumber = 0; // 猜测范围中,最小的数
    this._nowNumber = -1; // 目前猜测出来的数
    this._count = 0;  // 需要猜测的次数
    this._times = 0;  // 猜测的次数
    this._result = 0; // 猜测结果
    this._complete = false; // 猜测是否完成
    this._success = false; // 猜测是否成功。

    this.setNumberScope(numberScope); //设置猜数范围,这里默认从0开始.

}

GuessNumber.prototype = {
    constructor: GuessNumber,

    //设置数字范围
    setNumberScope: function(numberScope){
        if(numberScope < 0){
            alert("数字范围不能小于0!");
            return;
        }
        this._numberScope = numberScope;
        this.start(this._minNumber, numberScope);
    },

    //根据数字长度,设定数字访问
    setNumberScopeWithNumberLength: function(numLength){
        this.setNumberScope(Math.pow(10, numLength));
    },

    // 设置最小的数
    setMinNumber: function(minNumber) {
        this.start(minNumber);
    },

    //开始游戏,初始化一些必要的数据。主要是为方便重新设定最小值。所以将最小值作为第一个参数
    start: function(minNumber, maxNumber) {
        var inMinNum = this._minNumber;
        var inMaxNum = this._numberScope;
        this._minNumber = -1;
        this._maxNumber = 1;

        // 当minNumber为0时,需要特殊处理一下。
        var minNumberStr = minNumber + ""; 
        if (minNumberStr != "") {
            inMinNum = minNumber;
        }

        if (maxNumber) {
            inMaxNum = maxNumber;
            this._numberScope = maxNumber;
        }
        
        this._complete = false;
        this._success = false;
        this._times = 0;
        
        this.changeFields(inMaxNum, inMinNum);
        this.setCount();
    },

    // 计算所需猜测的次数
    setCount: function() {
        this._count = Math.ceil(Math.log(this._maxNumber - this._minNumber) / Math.log(2)) + 1;
    },

    // 获取总的猜测次数
    getCount: function() {
        if (this._count === 0) {
            this.setCount();
        }
        return this._count;
    },

    //猜测的数字太小,调大数字
    toLarger: function(){
        this.changeFields(this._maxNumber, this._nowNumber);
    },

    //猜测的数字太大,调小数字
    toSmaller: function(){
        this.changeFields(this._nowNumber, this._minNumber);
    },

    //计算数字大小,修改相应值
    changeFields: function(maxNumber, minNumber){

        if(maxNumber <= minNumber || maxNumber == this._minNumber + 1) {
            if(!this._complete) {
                this.complete();
            }				
            return;
        }
        if(this._maxNumber !== maxNumber) {
            this._maxNumber = maxNumber;
        }

        if(this._minNumber !== minNumber) {
            this._minNumber = minNumber;
        }

        this._nowNumber = Math.round((this._maxNumber + this._minNumber) / 2);
        this._times ++;
    },

    //提前完成猜数
    complete: function() {
        this._complete = true;
        if (this._maxNumber === this._minNumber) {
            this._success = true;
            this._result = this._maxNumber;
        } else if (this._maxNumber < this._minNumber) {
            this._success = false;
            this._result = "Sorry! I failed.";
        } else {
            this._success = true;
            this._result = this._nowNumber = Math.round((this._maxNumber + this._minNumber) / 2);
            if (this._nowNumber == this._minNumber + 1) {
                this._nowNumber = this._minNumber;
            }
        }
    },

    //获取结果
    getResult: function() {
        if(!this._success) {
            return "Sorrry! I failed.";
        }
        return this._result;
    },

    // 获取猜测的数
    getGuess: function() {
        if(this._nowNumber == this._minNumber) {
            return Math.round((this._maxNumber + this._minNumber) / 2);
        }
        return this._nowNumber;
    },
    
    //获取猜测次数
    getTimes: function() {
        if(this._times === 0) {
            this.start();
        }
        return this._times;
    }
    
}

  剩下的,就是创建对象,事件绑定。另外,GuessNumber主程序输出的是数字,还要根据实际情况进行格式化。这个不多说,具体代码如下:


$(document).ready(function(){
	//格式化显示结果
	function formatResult(num, type) {
		if (type == 1) {
			var tmp = new Date(num * 1000 * 3600 * 24);
			return tmp.getFullYear()+"年"+(tmp.getMonth()+1)+"月"+tmp.getDate()+"日";
		} else {
			var numStr = num + "";
			var strLeng = numStr.length;
			var result = "";
			for(var i = strLeng; i >= 0; i -= 4) {
				var startIndex = i-4 > 0 ? i-4 : 0;
				result = numStr.substring(startIndex, i) + result;
				if(i > 4) {
					result = "-" + result;
				}
			}
			return result;
		}
	}
	
	function showResult() {
		if(guess._complete){
			// 为了简化处理结果,把结果展示暂时写到这里。
			if(guess._success) {
				alert("您猜测的结果是:" + formatResult(guess.getGuess(), type));
			} else {
				alert("猜测失败。要不,咱试试其他的?");
			}
			
			return;
		}
		document.getElementById("showNumber").value = formatResult(guess.getGuess(), type);
		document.getElementById("showTimes").innerHTML = guess.getTimes();
		document.getElementById("showCount").innerHTML = guess.getCount();
	}

	var guess = new GuessNumber(100);

	// 定义个猜数范围数组
	var scopeArr = [{min: 0, max: 100, tip: ""}, // 小试牛刀
					{min: Math.round(new Date(0).getTime() / (1000*3600*24)), 
						max: Math.round(new Date().getTime() / (1000*3600*24)), 
						tip: ""}, // 猜猜生日
					{min:Math.pow(10, 10), max: 2*Math.pow(10, 10), 
						tip: ""} // 猜猜手机号
				   ];

	var type = 0; //1 代表日期;其余代表数字

	guess.start(scopeArr[type].min, scopeArr[type].max);
	showResult();

	$("#guessType").change(function(){
		type = $(this).val();
		guess.start(scopeArr[type].min, scopeArr[type].max);
		showResult();
	});
	//alert("Scope:"+guess._numberScope+",Max:"+guess._maxNumber+",Min:"+guess._minNumber+",Now:"+guess._nowNumber+",Count:"+guess._count);
	$("#maxButton").click(function(){
		guess.toSmaller();
		showResult();
	});

	$("#minButton").click(function(){
		guess.toLarger();
		showResult();
	});
	
	$("#initButton").click(function(){
		guess.start(scopeArr[type].min, scopeArr[type].max);
		showResult();
	});
});

   原来不想贴HTML的代码了,不过想想,既然是完整的,就都贴出来吧。


<div style="background: #E6FAE6; padding-left: 15px; border: 1px dashed #E0E0E0;">
<p>开始猜:最多需要<span id="showCount"></span>次</p>
<p>  选择一个类型:
<select id="guessType">
    <option value ="0">小试牛刀-猜一百以内的正整数</option>
    <option value ="1">猜猜你的生日</option>
    <option value="2">信不信,我能猜出你的手机号</option>
</select></p>
<p>   <input type="text" value="" size="24" maxlength="50" readonly="true" id="showNumber"  style="font-size:150%;"></p>
<p>   <input type="button" value="出错就重来" id="initButton"> <input name="tooMax" type="button" value="太大" id="maxButton" style="font-size:140%;"> 第<span id="showTimes"></span>次 <input name="tooMin" type="button" value="太小" id="minButton" style="font-size:140%;"></p>
</div>

   所有代码都贴出来了,从这些代码中也可以看出来,猜测的时候没有和后台进行通信。所以,大家可以放心大胆的试。

  稍后,我会把代码发布到Github上,请大家关注我的Github账号:D瓜哥

参考资料:

  1. 《代码之美》读书笔记之二分查找算法
  2. 百度百科对“二分查找”的介绍


作 者: D瓜哥,https://www.diguage.com/
原文链接:https://wordpress.diguage.com/archives/80.html
版权声明:非特殊声明均为本站原创作品,转载时请注明作者和原文链接。

  1. D瓜哥
    2012年12月18日09:36 | #1

    特别感谢扣扣网友“谢安”!
    在原文中,我错把logab = logmb / logma写成了 logab = logma / logmb。感谢“谢安”的指正!有问题,请留言,D瓜哥会及时改正的。

  2. Cohlint
    2013年2月6日14:55 | #2

    Math.log(n),这个方法是以Math.E为底数,不是10为底数;
    Math.log(Math.E); // 1
    Math.log(10); //2.30+

  3. 2013年9月29日13:35 | #3

    学习了
    搜面向对象 搜过来的

    纠结了好久 格式化日期下面的 else 是在干嘛
    原来是手机号相关的
    写的好巧 都塞到了一起

  1. 2012年12月24日11:14 | #1