二進(jìn)制在有限的遞歸教學(xué)中的一點(diǎn)巧用

◆摘 要：本文主要考慮二級制在有限的遞歸中的一點(diǎn)巧用，遞歸法一般是針對十進(jìn)制自然數(shù)，本文旨在給學(xué)生延拓思維。

◆關(guān)鍵詞：二進(jìn)制；遞歸；博弈策略

一、引言

我們將通過介紹一場人機(jī)博弈的方式來引入二進(jìn)制的一個(gè)應(yīng)用。關(guān)于二進(jìn)制的介紹可以在很多計(jì)算機(jī)入門課程中找到，例如[1-4]。以下我們先簡單介紹博弈規(guī)則。

假設(shè)計(jì)算機(jī)給出一串長度為n的0，1字符，博弈方式為玩家刪除最右端字符。當(dāng)玩家刪除的字符為0時(shí)，其它字符右移一位，且電腦將在字符串的左邊隨機(jī)生成一個(gè)字符0或者1；當(dāng)玩家刪除的字符為1時(shí)，其它字符右移一位，且玩家可自行選擇在左端添加0或者1。若在某一時(shí)刻所有的字符全為0，則玩家獲勝。

二、博弈策略及其分析

顯然，若在某一時(shí)刻所有的字符全為1，則在接下來的n次刪除字符后玩家均在左端添加0即可。

我們接下來將把每n次操作看作一組，則每一組操作后，實(shí)際上我們可以看作是直接對原有每個(gè)位置的字符進(jìn)行一次替換。當(dāng)原有字符為0時(shí)，由電腦隨機(jī)決定替換為0或者1；當(dāng)原有策略為1時(shí)，玩家可自行決定替換為0或者1。

我們可以將長度為n的0，1字符看作是二進(jìn)制表達(dá)下的一個(gè)數(shù)，該數(shù)的范圍在[0，2n-1]之間。每一組操作中，字符串的替換順序時(shí)從右向左。

我們的博弈策略如下：每一組操作中，我們觀察電腦的替換.此時(shí)有以下兩種情形：

情形一：若電腦始終將0替換為0，則我們也將1替換為0，這樣一組操作后自然得到所有字符全為0。

情形二：若在某個(gè)位置，電腦將0替換為1，則在該位置之后的操作中我們始終將1替換為1。

注意到，如果在某一組操作中出現(xiàn)情形一，則玩家已經(jīng)獲勝結(jié)束博弈過程。因此我們主要分析情形二。而實(shí)際上情形二出現(xiàn)時(shí)，我們一組操作后二進(jìn)制所表達(dá)的數(shù)字是嚴(yán)格遞增的。注意到長度為n的0，1字符看作是二進(jìn)制表達(dá)下數(shù)的范圍在[0，2n-1]之間，因此若持續(xù)出現(xiàn)情形二，則一定在經(jīng)過若干次操作后，我們可以得到全為1，此時(shí)下一組操作中玩家全替換為0即可獲勝。

三、小結(jié)

該策略中，我們比較核心的思想是通過遞歸的方法來得到嚴(yán)格遞增的字符串，然而字符串所表達(dá)的數(shù)有上界，故而必然可以達(dá)到。

參考文獻(xiàn)

[1]譚浩強(qiáng).C語言程序設(shè)計(jì)（第二版）[M].清華大學(xué)出版社，2009.

[2]胡泉，謝芳.C語言程序設(shè)計(jì)[M].華中科技大學(xué)出版社，2009.

作者簡介

錢文華，重慶師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，重慶市沙坪壩區(qū)大學(xué)城校區(qū)。