数据结构常见问题：12单元28 敢死队问题

《数据结构》课程常见问题

一一单元28敢死队问题

i.敢死队问题求解

解析：

问题描述

有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执

行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，

随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如

果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直

到任务完成为止。

排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后

一个留下来而不去执行任务。

要求：至少采用两种不同的数据结构的方法实现。

一、单循环链表数据结构

（-）需求分析

1,本程序任务是通过输入任意队伍人数n和报数上限m,输出使排长最后一个执行任务而开始记数的

初始位置。首先输入队伍人数n,然后输入报数上限m（m〈=n）,从1号开始报数，当达到报数上限时，那名

士兵出列执行任务，从下个人开始记数，再次循环，直到只剩一人，得到其在队伍中的位置，记下该位置

视为排长位置，则1号即可视为最先报数的人，通过数学计算即可获得所求。

2.功能模块和流程：

1）功能模块

该程序功能比较单一，主要是为解决敢死队问题而设计。通过输入队伍人数和报数上限即可获得

开始报数的位置。

2）程序流程

（1）构造链表（2）数据输入（3）执行删除（4）输出要求数值（5）结束

3.数据测试：

当n=10,m=5,输出结果为：要求的位置是：9。

（二）详细设计

1.算法设计：

本程序其实质是约瑟夫环问题。从排长位置即1号开始报数，共有n个人，达到报数上限m=5的战士

出列，继续进行报数，直到剩余最后一人，记下该位置为k。若将该位置视为排长位置，则原先的1号位

置即位所有的开始报数的位置Z。则z=n-k+2«

2.以单循环链表为存储结构，包含三个模块：

(1)主程序模块

(2)构造链表并初始化

(3)删除结点

3.结点类型和指针类型

typedefstructnode

(

intdata;

structnode*next;

}LNode;/*定义结点类型*/

LNode*p;

4.每个模块的分析

(1)主程序模块：

main()

(

LNode*p;

intm,n,z,y;

do

(

printfCPleaseinputthepeoplenumber:\n，z);

scanf&n);

)

while(n<=0);

do

(

printf(，zPleaseinputtheexcursion:、、)；

scanf&m);

)

while(m<=0);

if(n=l)

printf(，zthepositionis:1〃)；

else

(

p=CREAT(n);

y=DELETE(p,m);

z=n-y+2;

if(z%n==0)/*排除特殊情况*/

printf("thepositionis:\n%d\n〃，z);

else

printf(，zthepositionis:\n%d\nz，,(n-y+2)%n);

}/*通过数学思想求得实验要求情况下的数值*/

(2)构造单循环链表并初始化模块：

LNode*GREAT(intn)/*创建循环链表*/

(

LNode*s,*q,*t;

inti;

if(n!=0)

(

t=q=(LNode*)malloc(sizeof(LNode));

q->data=l;/*生成第一个结点并使其data值为1*/

for(i=2;i<=n;i++)

(

s=(LNode*)malloc(sizeof(LNode));/*自动生成结点*/

q->next=s;

口-〉1^*58@1。=:1;/*给第i个结点赋值i*/

q=q->next;

)

q->next=t;

}/*生成后续结点，并使其data值即为它所在链表(队伍)中的位置*/

returnt;

)

(3)删除结点模块：

DELETE(LNode*t,intm)/*链表的删除*/

(

LNode*a;inti;

while(t->next!=t)

(

for(i=l;i<m-l;i++)/*查找要删除结点的前一结点*/

t=t->next;

a=t->next;

t->next=a->next;

free(a);/*释放结点*/

t=t->next;

}/*while循环依次删除被点到的士兵*/

printf(〃\n〃)；

return(t->data);

)

(三)调试分析：

1.本程序运行后的结果应是如下提示：

Exitpleaseinput'O'OrGoon

Pleaseinputthetataloftheteam:

输入队伍总人数

Pleaseinputtheexcursion:

输入间隔人数

结果显示：Thewantedpositionis

选择的位置

2.在程序调试