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

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

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

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

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

二分查找算法

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

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

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

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

面向对象编程

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

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

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

查看源代码
打印帮助
01/**
02* numberScope 需要猜测的数字范围
03*/
04function GuessNumber(numberScope){
05    this._maxNumber = -1; // 猜测范围中，最大的数
06    this._minNumber = 0; // 猜测范围中，最小的数
07    this._nowNumber = -1; // 目前猜测出来的数
08    this._count = 0;  // 需要猜测的次数
09    this._times = 0;  // 猜测的次数
10    this._result = 0; // 猜测结果
11    this._complete = false; // 猜测是否完成
12    this._success = false; // 猜测是否成功。
13 
14    this.setNumberScope(numberScope); //设置猜数范围，这里默认从0开始.
15 
16}

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

查看源代码
打印帮助
1var guess = new GuessNumber(100);

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

查看源代码
打印帮助
1this.setNumberScope(numberScope); //设置猜数范围，这里默认从0开始.

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

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

查看源代码
打印帮助
01GuessNumber.prototype = {
02    constructor: GuessNumber,
03 
04    //设置数字范围
05    setNumberScope: function(numberScope){
06        if(numberScope < 0){
07            alert("数字范围不能小于0！");
08            return;
09        }
10        this._numberScope = numberScope;
11        this.start(this._minNumber, numberScope);
12    },
13 
14    //开始游戏，初始化一些必要的数据。主要是为方便重新设定最小值。所以将最小值作为第一个参数
15    start: function(minNumber, maxNumber) {
16        var inMinNum = this._minNumber;
17        var inMaxNum = this._numberScope;
18        this._minNumber = -1;
19        this._maxNumber = 1;
20 
21        // 当minNumber为0时，需要特殊处理一下。
22        var minNumberStr = minNumber + "";
23        if (minNumberStr != "") {
24            inMinNum = minNumber;
25        }
26 
27        if (maxNumber) {
28            inMaxNum = maxNumber;
29            this._numberScope = maxNumber;
30        }
31         
32        this._complete = false;
33        this._success = false;
34        this._times = 0;
35         
36        this.changeFields(inMaxNum, inMinNum);
37        this.setCount();
38    },
39 
40    // 计算所需猜测的次数
41    setCount: function() {
42        this._count = Math.ceil(Math.log(this._maxNumber - this._minNumber) / Math.log(2)) + 1;
43    },
44 
45    //猜测的数字太小，调大数字
46    toLarger: function(){
47        this.changeFields(this._maxNumber, this._nowNumber);
48    },
49 
50    //猜测的数字太大，调小数字
51    toSmaller: function(){
52        this.changeFields(this._nowNumber, this._minNumber);
53    },
54 
55    //计算数字大小，修改相应值
56    changeFields: function(maxNumber, minNumber){
57 
58        if(maxNumber <= minNumber || maxNumber == this._minNumber + 1) {
59            if(!this._complete) {
60                this.complete();
61            }              
62            return;
63        }
64        if(this._maxNumber !== maxNumber) {
65            this._maxNumber = maxNumber;
66        }
67 
68        if(this._minNumber !== minNumber) {
69            this._minNumber = minNumber;
70        }
71 
72        this._nowNumber = Math.round((this._maxNumber + this._minNumber) / 2);
73        this._times ++;
74    },
75    ……
76}

　　注意，这个的第二行。使用这种语法是非常方便。但是，却从本质上改变了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。不过，这样计算出来的结果还会有小数点，这是我们只需要来个“向上取整”就可以了。具体代码如下：

查看源代码
打印帮助
1// 计算所需猜测的次数
2setCount: function() {
3    this._count = Math.ceil(Math.log(this._maxNumber - this._minNumber) / Math.log(2)) + 1; //加1，确保次数肯定用。
4},

完整代码实现

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

查看源代码
打印帮助
001/**
002* numberScope 需要猜测的数字范围
003*/
004function GuessNumber(numberScope){
005    this._maxNumber = -1; // 猜测范围中，最大的数
006    this._minNumber = 0; // 猜测范围中，最小的数
007    this._nowNumber = -1; // 目前猜测出来的数
008    this._count = 0;  // 需要猜测的次数
009    this._times = 0;  // 猜测的次数
010    this._result = 0; // 猜测结果
011    this._complete = false; // 猜测是否完成
012    this._success = false; // 猜测是否成功。
013 
014    this.setNumberScope(numberScope); //设置猜数范围，这里默认从0开始.
015 
016}
017 
018GuessNumber.prototype = {
019    constructor: GuessNumber,
020 
021    //设置数字范围
022    setNumberScope: function(numberScope){
023        if(numberScope < 0){
024            alert("数字范围不能小于0！");
025            return;
026        }
027        this._numberScope = numberScope;
028        this.start(this._minNumber, numberScope);
029    },
030 
031    //根据数字长度，设定数字访问
032    setNumberScopeWithNumberLength: function(numLength){
033        this.setNumberScope(Math.pow(10, numLength));
034    },
035 
036    // 设置最小的数
037    setMinNumber: function(minNumber) {
038        this.start(minNumber);
039    },
040 
041    //开始游戏，初始化一些必要的数据。主要是为方便重新设定最小值。所以将最小值作为第一个参数
042    start: function(minNumber, maxNumber) {
043        var inMinNum = this._minNumber;
044        var inMaxNum = this._numberScope;
045        this._minNumber = -1;
046        this._maxNumber = 1;
047 
048        // 当minNumber为0时，需要特殊处理一下。
049        var minNumberStr = minNumber + "";
050        if (minNumberStr != "") {
051            inMinNum = minNumber;
052        }
053 
054        if (maxNumber) {
055            inMaxNum = maxNumber;
056            this._numberScope = maxNumber;
057        }
058         
059        this._complete = false;
060        this._success = false;
061        this._times = 0;
062         
063        this.changeFields(inMaxNum, inMinNum);
064        this.setCount();
065    },
066 
067    // 计算所需猜测的次数
068    setCount: function() {
069        this._count = Math.ceil(Math.log(this._maxNumber - this._minNumber) / Math.log(2)) + 1;
070    },
071 
072    // 获取总的猜测次数
073    getCount: function() {
074        if (this._count === 0) {
075            this.setCount();
076        }
077        return this._count;
078    },
079 
080    //猜测的数字太小，调大数字
081    toLarger: function(){
082        this.changeFields(this._maxNumber, this._nowNumber);
083    },
084 
085    //猜测的数字太大，调小数字
086    toSmaller: function(){
087        this.changeFields(this._nowNumber, this._minNumber);
088    },
089 
090    //计算数字大小，修改相应值
091    changeFields: function(maxNumber, minNumber){
092 
093        if(maxNumber <= minNumber || maxNumber == this._minNumber + 1) {
094            if(!this._complete) {
095                this.complete();
096            }              
097            return;
098        }
099        if(this._maxNumber !== maxNumber) {
100            this._maxNumber = maxNumber;
101        }
102 
103        if(this._minNumber !== minNumber) {
104            this._minNumber = minNumber;
105        }
106 
107        this._nowNumber = Math.round((this._maxNumber + this._minNumber) / 2);
108        this._times ++;
109    },
110 
111    //提前完成猜数
112    complete: function() {
113        this._complete = true;
114        if (this._maxNumber === this._minNumber) {
115            this._success = true;
116            this._result = this._maxNumber;
117        } else if (this._maxNumber < this._minNumber) {
118            this._success = false;
119            this._result = "Sorry! I failed.";
120        } else {
121            this._success = true;
122            this._result = this._nowNumber = Math.round((this._maxNumber + this._minNumber) / 2);
123            if (this._nowNumber == this._minNumber + 1) {
124                this._nowNumber = this._minNumber;
125            }
126        }
127    },
128 
129    //获取结果
130    getResult: function() {
131        if(!this._success) {
132            return "Sorrry! I failed.";
133        }
134        return this._result;
135    },
136 
137    // 获取猜测的数
138    getGuess: function() {
139        if(this._nowNumber == this._minNumber) {
140            return Math.round((this._maxNumber + this._minNumber) / 2);
141        }
142        return this._nowNumber;
143    },
144     
145    //获取猜测次数
146    getTimes: function() {
147        if(this._times === 0) {
148            this.start();
149        }
150        return this._times;
151    }
152     
153}

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

查看源代码
打印帮助
01$(document).ready(function(){
02    //格式化显示结果
03    function formatResult(num, type) {
04        if (type == 1) {
05            var tmp = new Date(num * 1000 * 3600 * 24);
06            return tmp.getFullYear()+"年"+(tmp.getMonth()+1)+"月"+tmp.getDate()+"日";
07        } else {
08            var numStr = num + "";
09            var strLeng = numStr.length;
10            var result = "";
11            for(var i = strLeng; i >= 0; i -= 4) {
12                var startIndex = i-4 > 0 ? i-4 : 0;
13                result = numStr.substring(startIndex, i) + result;
14                if(i > 4) {
15                    result = "-" + result;
16                }
17            }
18            return result;
19        }
20    }
21     
22    function showResult() {
23        if(guess._complete){
24            // 为了简化处理结果，把结果展示暂时写到这里。
25            if(guess._success) {
26                alert("您猜测的结果是：" + formatResult(guess.getGuess(), type));
27            } else {
28                alert("猜测失败。要不，咱试试其他的？");
29            }
30             
31            return;
32        }
33        document.getElementById("showNumber").value = formatResult(guess.getGuess(), type);
34        document.getElementById("showTimes").innerHTML = guess.getTimes();
35        document.getElementById("showCount").innerHTML = guess.getCount();
36    }
37 
38    var guess = new GuessNumber(100);
39 
40    // 定义个猜数范围数组
41    var scopeArr = [{min: 0, max: 100, tip: ""}, // 小试牛刀
42                    {min: Math.round(new Date(0).getTime() / (1000*3600*24)),
43                        max: Math.round(new Date().getTime() / (1000*3600*24)),
44                        tip: ""}, // 猜猜生日
45                    {min:Math.pow(10, 10), max: 2*Math.pow(10, 10),
46                        tip: ""} // 猜猜手机号
47                   ];
48 
49    var type = 0; //1 代表日期；其余代表数字
50 
51    guess.start(scopeArr[type].min, scopeArr[type].max);
52    showResult();
53 
54    $("#guessType").change(function(){
55        type = $(this).val();
56        guess.start(scopeArr[type].min, scopeArr[type].max);
57        showResult();
58    });
59    //alert("Scope："+guess._numberScope+"，Max："+guess._maxNumber+"，Min："+guess._minNumber+"，Now："+guess._nowNumber+"，Count："+guess._count);
60    $("#maxButton").click(function(){
61        guess.toSmaller();
62        showResult();
63    });
64 
65    $("#minButton").click(function(){
66        guess.toLarger();
67        showResult();
68    });
69     
70    $("#initButton").click(function(){
71        guess.start(scopeArr[type].min, scopeArr[type].max);
72        showResult();
73    });
74});

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

查看源代码
打印帮助
01<div style="background: #E6FAE6; padding-left: 15px; border: 1px dashed #E0E0E0;">
02<p>开始猜：最多需要<span id="showCount"></span>次</p>
03<p>　　选择一个类型：
04<select id="guessType">
05    <option value ="0">小试牛刀-猜一百以内的正整数</option>
06    <option value ="1">猜猜你的生日</option>
07    <option value="2">信不信，我能猜出你的手机号</option>
08</select></p>
09<p>　　　<input type="text" value="" size="24" maxlength="50" readonly="true" id="showNumber"  style="font-size:150%;"></p>
10<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>
11</div>

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

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

参考资料：

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


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

分类: Web开发, 挨踢(IT) 标签: , ,
  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. lake
    2013年9月29日13:35 | #3
    回复 | 引用

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

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

  1. 2012年12月24日11:14 | #1
    Javascript模块化编程（三）：模块化编程实战，试用SeaJS | 编程·早晨