逢N退出的圖形化算法設(shè)計

衛(wèi)洪春，蒲國林，王安志

（四川文理學(xué)院 計算機(jī)學(xué)院，四川 達(dá)州635000）

1 提出問題

問題描述：有n個人圍成一圈，從編號1開始順序排號，一直到n.從第1個人開始，順次以1，2，…，N循環(huán)報數(shù)（從1到N報數(shù)），凡報到數(shù)字N的人退出圈子，問最后留下的人的編號是多少？[1]如圖1所示.

圖1 初始狀態(tài)

2 求解方式

該問題是一個古老而經(jīng)典的游戲，會在很多場合用到.在計算機(jī)環(huán)境下，也可以有很多處理辦法，如數(shù)組，單向循環(huán)鏈表等.例如在C＋＋環(huán)境中以數(shù)組方式實現(xiàn)的代碼如下：

＃include＜iostream＞

＃define NUM 13 ／／總?cè)藬?shù)

using namespace std；

void main（）｛ int num ＝ NUM，flag＝1，numArray[NUM＋1]；

for（int i＝0；i＜ NUM＋1；i＋＋）numArray[i]＝i；／／初始化一維數(shù)組的元素

while（num ！＝1）｛ ／／若當(dāng)前狀態(tài)下剩余的人數(shù)num大于1.

for（i＝1；i＜ NUM＋1；i＋＋）｛

if（numArray[i]！＝0）｛／／若數(shù)組的第i個元素不為零

if（flag＝＝3）｛flag＝0；numArray[i]＝0；num--；｝

flag＋＋；｝｝ ｝

for（i＝1；i＜ NUM＋1；i＋＋）

if（numArray[i]！＝0）cout＜＜"最后剩下的人的編號是："＜＜numArray[i]＜＜"＼n＼n"；

｝

求解結(jié)果：最后剩下的人的編號是：13

上述算法是利用C＋＋的一維數(shù)組實現(xiàn).由于是n個人圍成一圈，可利用單向鏈表來完成.但在控制臺模式下對該問題的求解過程不直觀.本文探討圖形模式下該問題運(yùn)算過程的動態(tài)演示.在圖形模式下對該算法實現(xiàn)過程，關(guān)鍵是將控制臺下的輸出語句轉(zhuǎn)換為圖形繪制.下面分析利用面向?qū)ο蠹夹g(shù)，[2]結(jié)合鏈表的相關(guān)知識[3]實現(xiàn)該問題在圖形模式下的運(yùn)算過程.

3 設(shè)計類

3.1 Cperson人員類的設(shè)計

CPerson類是問題中每個人所共有的屬性和方法.數(shù)據(jù)成員包括人員編號，是否繪制該人員編號的標(biāo)識，人員占位所需的坐標(biāo)與寬度；成員函數(shù)包括構(gòu)造函數(shù)、析構(gòu)函數(shù)、繪制某個人員的繪圖函數(shù)、相關(guān)的設(shè)置函數(shù)等.所有成員均設(shè)計成public，見表1.

類Cperson的實現(xiàn)：

CPerson：：～CPerson（）｛ ｝ Person：：CPerson（）｛flag＝FALSE；｝／／所有標(biāo)識為假

CPerson：：CPerson（int x，int y，int halfw，int number）｛／／初始化該對象的相關(guān)數(shù)據(jù)成員

this-＞x＝x；this-＞y＝y(tǒng)；this-＞halfw＝halfw；his-＞number＝number；flag＝TRUE；｝

表1 類CPerson的結(jié)構(gòu)

voidCPerson：：DrawPerson（bool flg，CDC＊pDC）｛

／／繪制占位；標(biāo)識為真則繪制該對象的編號，否則繪不繪制

if（flg）｛char a[2]；itoa（number，a，10）；pDC-＞TextOut（x-8，y-5，a）；｝

else pDC- ＞TextOut（x-8，y-5，""）； ｝

voidCPerson：：SetFlag（bool flag）｛this- ＞flag＝flag；｝

voidCPerson：：setNum（int i）｛this-＞number＝0；｝

3.2 結(jié)點Node類的設(shè)計

節(jié)點類Node中定義了兩個數(shù)據(jù)成員，一個是保存Cperson類的對象數(shù)據(jù)的m＿Data，另一個是指向下一節(jié)點的指針域Node＊m＿Next.對Node類的操作有如下函數(shù)來完成.為操作方便，所有成員均設(shè)計為public，見表2.

表2 類Node的結(jié)構(gòu)

類Node的實現(xiàn)：

Node：：Node（）｛m＿Next＝ NULL；｝／／無參構(gòu)造函數(shù)，指針域不指向任何結(jié)點

Node：：～Node（）｛if（m＿Next）delete m＿Next；｝

Node：：Node（CPerson data）｛m＿Data＝da-ta；m＿Next＝ NULL； ｝

Node：：Node（CPerson data，Node＊next）｛m＿Data＝data；m＿Next＝next； ｝

void Node：：setData（CPerson data）｛m＿Data＝data；｝

CPerson Node：：getData（）｛return m＿Data；｝

voidNode：：setNext（Node＊next）｛m＿Next＝next；｝

Node＊Node：：getNext（）｛return m＿Next；｝

3.3 單向循環(huán)鏈表LinkList類的設(shè)計

鏈表與數(shù)組相似，一個鏈表代表一個線性數(shù)據(jù)序列，但是這兩種數(shù)據(jù)結(jié)構(gòu)存在不同之處.創(chuàng)建數(shù)組是一次性開辟一整塊內(nèi)存空間.創(chuàng)建鏈表則可以先只創(chuàng)建一個鏈表頭，鏈表中的其他結(jié)點可在需要時動態(tài)創(chuàng)建并加入到鏈表中.鏈表是由節(jié)點組成的非連續(xù)的動態(tài)線性數(shù)據(jù)結(jié)構(gòu)，適合于處理數(shù)據(jù)序列中數(shù)據(jù)數(shù)目不定，且插入和刪除較多的問題.

由此問題的描述，很自然想到用單向循環(huán)鏈表來實現(xiàn).在結(jié)點類Node的基礎(chǔ)上，設(shè)計單向循環(huán)鏈表類LinkList，其數(shù)據(jù)成員為鏈表的頭結(jié)點m＿FirstNode及最后一個結(jié)點m＿LastNode.其操作如表3所示.

表3 類LinkList的結(jié)構(gòu)

類LinkList的實現(xiàn)：

＃define RADIUS 100

LinkList：：LinkList（）｛m＿FirstNode ＝NULL；m＿LastNode＝ NULL；｝／／建立空鏈表

LinkList：：LinkList（CPerson data）｛m ＿FirstNode＝new Node（data）；

m＿FirstNode-＞m＿Next＝m＿FirstNode；m＿LastNode＝m＿FirstNode；

｝／／建立只有一個節(jié)點的鏈表

LinkList：：～LinkList（）｛／／析構(gòu)函數(shù)，刪除指向頭、尾結(jié)點的指針

if（m＿FirstNode！＝ NULL）｛delete m＿FirstNode；m＿FirstNode＝ NULL；｝

if（m＿LastNode！＝ NULL）｛delete m＿LastNode；delete m＿LastNode；｝ ｝

voidLinkList：：insertAtBegin（CPerson data）｛／／生成數(shù)據(jù)節(jié)點并插到鏈表的開頭

if（m＿FirstNode＝＝ NULL）｛／／若是空鏈表，直接插入

m＿FirstNode＝ new Node（data）；m＿First-Node-＞m＿Next＝ m＿FirstNode；

m＿LastNode＝m＿FirstNode； ／／尾結(jié)點指向第一個生成的結(jié)點

｝else｛／／把新節(jié)點插在第一個節(jié)點前，并指向原來的第一節(jié)點

m＿FirstNode＝ new Node（data，m＿First-Node）；／／生成新的結(jié)點

m＿LastNode-＞m＿Next＝ m＿First-Node；／／尾結(jié)點的指針域指向頭結(jié)點

｝ ｝

voidLinkList：：remove（）｛／／刪除鏈表中的某個節(jié)點

m＿FirstNode-＞m＿Next＝ m＿FirstNode-＞m＿Next-＞m＿Next；

m＿FirstNode＝ m＿FirstNode-＞m＿Next；

｝

voidLinkList：：removeAll（）｛／／刪除所有的節(jié)點，使鏈表為空

if（m＿FirstNode！＝ NULL）｛delete m＿FirstNode；m＿FirstNode＝ NULL；｝

if（m＿LastNode！＝ NULL）｛delete m＿LastNode；delete m＿LastNode；｝ ｝

voidLinkList：：Move（CRect rect，CDC ＊pDC）｛

int cx，cy，i； int m＿PersonNum ＝13；／／待報數(shù)的總?cè)藬?shù)

double theta，radius；／／人員占位所需的圓的半徑及單位圓心角

theta＝ 2＊3.1415926／m＿PersonNum；／／單位角度

radius＝RADIUS；int meetN＝3；／／逢3退出

cx＝ （rect.right-rect.left）／2；／／當(dāng)前客戶區(qū)的中間位置坐標(biāo)

cy＝ （rect.bottom-rect.top）／2；

for（i＝ m＿PersonNum；i＞＝1；i--）｛／／向空鏈表中插入m＿PersonNum個節(jié)點

CPerson person（ ／／生成編號為i的Cperson對象

cx＋int（RADIUS＊sin（（i-1）＊theta）），cy＋int（RADIUS＊cos（（i-1）＊theta）），16，i）；

insertAtBegin（person）；／／新生成的對象加入到鏈表中

｝

Node＊pn＝ m＿FirstNode；／／初始狀態(tài)，繪制所有結(jié)點

pn- ＞getData（）.DrawPerson（TRUE，pDC）；

for（i＝0；i＜ m＿PersonNum；i＋＋）｛pn＝pn-＞m＿Next；

pn- ＞getData（）.DrawPerson（TRUE，pDC）；

｝Sleep（2000）；

int p＝ m＿PersonNum； ／／當(dāng)前鏈表中的人數(shù)p

i＝0； ／／計數(shù)器i用于報數(shù)

if（p！＝0）｛ ／／當(dāng)鏈表中當(dāng)前的人數(shù)p不等于0時

while（p＞1）｛i＋＋；

if（i＜ meetN ）｛

if（i＝＝meetN-1）｛若報數(shù)達(dá)到N，則不繪制該結(jié)點，并刪除它，人數(shù)p減1

m＿FirstNode-＞m＿Next-＞getData（）.DrawPerson（false，pDC）；

remove（）；p--；i＝0；Sleep（1500）；｝

elsem＿FirstNode＝m＿FirstNode-＞m＿Next；

｝｝｝｝

4 集成與實現(xiàn)

在VC6.0環(huán)境下，創(chuàng)建基于單文檔的 MFC工程CMeetNOut＿M(jìn)FC，在該工程中加入已設(shè)計的Cperson類、Node類及LinkList類.在菜單上添加標(biāo)識為ID＿BEGIN的命令，在視圖類中添加該命令的響應(yīng)函數(shù)OnBegin（），在該函數(shù)中完成對所給問題的處理，[4-5]其過程如下：

voidCMeetNOut＿M(jìn)FCView：：OnBegin（）｛ RedrawWindow（）；

CDC＊pDC ＝ GetDC（）；CRect rect；Get-ClientRect（＆rect）；

LinkList plist；plist.Move（rect，pDC）；ReleaseDC（pDC）； ｝

編譯運(yùn)行后，可在窗口中看到每次報數(shù)過程中被移出的人的編號，從而達(dá)到可視化演示的目的.運(yùn)算過程如圖2-圖4所示，圖4是運(yùn)算的最后結(jié)果.

圖2 退出狀態(tài)1

圖3 退出狀態(tài)2

圖4 結(jié)束

5 結(jié)語

本文探討并實現(xiàn)了“循環(huán)報數(shù)、逢N退出”問題的圖形化求解過程.它綜合運(yùn)用了面向?qū)ο蠹夹g(shù)設(shè)計類，利用數(shù)據(jù)結(jié)構(gòu)的知識設(shè)計單向循環(huán)鏈表，利用VC6.0的MFC技術(shù)對圖形環(huán)境的支持，使實際問題的處理過程以圖形化形式表現(xiàn)出來，達(dá)到了求解過程的可視化效果.

[1]譚浩強(qiáng)，張基溫.C語言程序設(shè)計教程：第3版[M].北京：高等教育出版社，2008：188.

[2]鄭 莉，董 淵，何江舟.C＋＋語言程序設(shè)計：第4版[M].北京：清華大學(xué)出版社，2011：98-122.

[3]王曉東.數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計[M].北京：機(jī)械工業(yè)出版社，2012：32-34.

[4]衛(wèi)洪春.掃描線多邊形區(qū)域填充算法研究[J].四川文理學(xué)院學(xué)報，2012（5）：77-82.

[5]沈 榮，廖 婷.圖形對象拾取技術(shù)在開發(fā)CAD系統(tǒng)中的應(yīng)用[J].四川文理學(xué)院學(xué)報，2012（5）：76-77.