搜尋的應用--貓咪猜數字大師

在前一個單元中我們讓貓咪想一個數字讓玩家猜,現在反過來,讓我們來出一個數字讓貓咪猜,那這樣的程式要如何寫呢?

之前要讓程式出題,所以我們一開始的時候使用隨機產生一個數字。現在是我們要出題,所以程式中就不需要使用隨機數的積木,而是馬上就進入猜數字的程序。因此,假設我們已經想好一個數字給貓咪,然後按下貓咪的角色,牠就開始猜數字了。

那麼,你覺得貓咪一開始要猜多少了?如果是亂猜的話,那麼也是要使用隨機數了。貓咪的猜數字(只猜一次)的程式積木如下:

由於是隨機猜測,只猜一次絕對是猜不到的,因此,我們需要再加上一個迴圈來不斷地猜測,直到我們說它猜到為止, 還記得之前的「重複直到」迴圈嗎?程式積木如下:

上面這段程式已經可以讓貓咪好好地猜數字了,但是牠都一直亂猜,這並不是有智慧的生物該有的樣子,所以,我們就使用一個比較有規則的猜法,就是二分搜尋法,方法如下:

二分搜尋法的主要特色就是先設定要猜測的最小值(min)和最大值(max),然後算出想要猜測的中間值myguess,公式如下:

myguess=floor(min+max2)myguess = floor(\frac{min+max}{2})

此時玩家要根據貓咪猜測的數字給它一個回饋,提示是bigger(要再大一點)或是smaller(要再小一點)。當貓咪收到提示之後,如果是要大一點,就把min設定為myguess,如果要小一點,就要把max設定為myguess,接著再重新計算上述的公式,使用此種方式,總有一天貓咪會猜到答案。

以下假設是要猜的數字是85,貓咪猜數字的過程:

有沒有可能,貓咪會猜不到你設定的數字呢?由於這個方法是使用二分的方式逐漸逼近答案,因此除非我們騙貓咪,不然是不會有猜不到的情形。那,貓咪如何得知我們故意騙牠呢?其實是有方法的,就是當max=min而且玩家還說不對的時候,程式修改如下:

以下是示範的影片:

有了以上的程式,同學們是否可以想想如何加上讓貓咪知道自己猜了幾次才猜對嗎?