逢N退出的图形化算法设计

卫洪春，蒲国林，王安志

（四川文理学院 计算机学院，四川 达州635000）

1 提出问题

问题描述：有n个人围成一圈，从编号1开始顺序排号，一直到n.从第1个人开始，顺次以1，2，…，N循环报数（从1到N报数），凡报到数字N的人退出圈子，问最后留下的人的编号是多少？[1]如图1所示.

图1 初始状态

2 求解方式

该问题是一个古老而经典的游戏，会在很多场合用到.在计算机环境下，也可以有很多处理办法，如数组，单向循环链表等.例如在C＋＋环境中以数组方式实现的代码如下：

＃include＜iostream＞

＃define NUM 13 ／／总人数

using namespace std；

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

for（int i＝0；i＜ NUM＋1；i＋＋）numArray[i]＝i；／／初始化一维数组的元素

while（num ！＝1）｛ ／／若当前状态下剩余的人数num大于1.

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

if（numArray[i]！＝0）｛／／若数组的第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"；

｝

求解结果：最后剩下的人的编号是：13

上述算法是利用C＋＋的一维数组实现.由于是n个人围成一圈，可利用单向链表来完成.但在控制台模式下对该问题的求解过程不直观.本文探讨图形模式下该问题运算过程的动态演示.在图形模式下对该算法实现过程，关键是将控制台下的输出语句转换为图形绘制.下面分析利用面向对象技术，[2]结合链表的相关知识[3]实现该问题在图形模式下的运算过程.

3 设计类

3.1 Cperson人员类的设计

CPerson类是问题中每个人所共有的属性和方法.数据成员包括人员编号，是否绘制该人员编号的标识，人员占位所需的坐标与宽度；成员函数包括构造函数、析构函数、绘制某个人员的绘图函数、相关的设置函数等.所有成员均设计成public，见表1.

类Cperson的实现：

CPerson：：～CPerson（）｛ ｝ Person：：CPerson（）｛flag＝FALSE；｝／／所有标识为假

CPerson：：CPerson（int x，int y，int halfw，int number）｛／／初始化该对象的相关数据成员

this-＞x＝x；this-＞y＝y；this-＞halfw＝halfw；his-＞number＝number；flag＝TRUE；｝

表1 类CPerson的结构

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

／／绘制占位；标识为真则绘制该对象的编号，否则绘不绘制

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 结点Node类的设计

节点类Node中定义了两个数据成员，一个是保存Cperson类的对象数据的m＿Data，另一个是指向下一节点的指针域Node＊m＿Next.对Node类的操作有如下函数来完成.为操作方便，所有成员均设计为public，见表2.

表2 类Node的结构

类Node的实现：

Node：：Node（）｛m＿Next＝ NULL；｝／／无参构造函数，指针域不指向任何结点

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 单向循环链表LinkList类的设计

链表与数组相似，一个链表代表一个线性数据序列，但是这两种数据结构存在不同之处.创建数组是一次性开辟一整块内存空间.创建链表则可以先只创建一个链表头，链表中的其他结点可在需要时动态创建并加入到链表中.链表是由节点组成的非连续的动态线性数据结构，适合于处理数据序列中数据数目不定，且插入和删除较多的问题.

由此问题的描述，很自然想到用单向循环链表来实现.在结点类Node的基础上，设计单向循环链表类LinkList，其数据成员为链表的头结点m＿FirstNode及最后一个结点m＿LastNode.其操作如表3所示.

表3 类LinkList的结构

类LinkList的实现：

＃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；

｝／／建立只有一个节点的链表

LinkList：：～LinkList（）｛／／析构函数，删除指向头、尾结点的指针

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

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

voidLinkList：：insertAtBegin（CPerson data）｛／／生成数据节点并插到链表的开头

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

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

m＿LastNode＝m＿FirstNode； ／／尾结点指向第一个生成的结点

｝else｛／／把新节点插在第一个节点前，并指向原来的第一节点

m＿FirstNode＝ new Node（data，m＿First-Node）；／／生成新的结点

m＿LastNode-＞m＿Next＝ m＿First-Node；／／尾结点的指针域指向头结点

｝ ｝

voidLinkList：：remove（）｛／／删除链表中的某个节点

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

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

｝

voidLinkList：：removeAll（）｛／／删除所有的节点，使链表为空

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；／／待报数的总人数

double theta，radius；／／人员占位所需的圆的半径及单位圆心角

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

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

cx＝ （rect.right-rect.left）／2；／／当前客户区的中间位置坐标

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

for（i＝ m＿PersonNum；i＞＝1；i--）｛／／向空链表中插入m＿PersonNum个节点

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；／／初始状态，绘制所有结点

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； ／／当前链表中的人数p

i＝0； ／／计数器i用于报数

if（p！＝0）｛ ／／当链表中当前的人数p不等于0时

while（p＞1）｛i＋＋；

if（i＜ meetN ）｛

if（i＝＝meetN-1）｛若报数达到N，则不绘制该结点，并删除它，人数p减1

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

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

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

｝｝｝｝

4 集成与实现

在VC6.0环境下，创建基于单文档的 MFC工程CMeetNOut＿MFC，在该工程中加入已设计的Cperson类、Node类及LinkList类.在菜单上添加标识为ID＿BEGIN的命令，在视图类中添加该命令的响应函数OnBegin（），在该函数中完成对所给问题的处理，[4-5]其过程如下：

voidCMeetNOut＿MFCView：：OnBegin（）｛ RedrawWindow（）；

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

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

编译运行后，可在窗口中看到每次报数过程中被移出的人的编号，从而达到可视化演示的目的.运算过程如图2-图4所示，图4是运算的最后结果.

图2 退出状态1

图3 退出状态2

图4 结束

5 结语

本文探讨并实现了“循环报数、逢N退出”问题的图形化求解过程.它综合运用了面向对象技术设计类，利用数据结构的知识设计单向循环链表，利用VC6.0的MFC技术对图形环境的支持，使实际问题的处理过程以图形化形式表现出来，达到了求解过程的可视化效果.

[1]谭浩强，张基温.C语言程序设计教程：第3版[M].北京：高等教育出版社，2008：188.

[2]郑 莉，董 渊，何江舟.C＋＋语言程序设计：第4版[M].北京：清华大学出版社，2011：98-122.

[3]王晓东.数据结构与算法设计[M].北京：机械工业出版社，2012：32-34.

[4]卫洪春.扫描线多边形区域填充算法研究[J].四川文理学院学报，2012（5）：77-82.

[5]沈 荣，廖 婷.图形对象拾取技术在开发CAD系统中的应用[J].四川文理学院学报，2012（5）：76-77.