软考真题
第10题
【说明】
约瑟夫问题是一个经典的问题,其描述是:有n个人(编号为1〜n)围成一圈,从第1个人开始,按照顺时针方向从1开始计数到m (即数到第m个人),让其出圈,然后再从其顺时针方向的下一个人开始,依次计数到m并让其出圈,重复这个过程,直到所有人都出圈,试给出出圈者的顺序。

以n=5,m=3为例,其出圈顺序为3,1,5,2,4,过程如图4-1所示。



下面的函数Joseph()在单向循环链表表示的基础上模拟上述出圈过程。

n为5时的单向循环链表结构如图4-2所示。



链表的结点类型定义如下:

typedef struct Node{

int no;

struct Node *next;

}Node, *LinkList;

函数Joseph(LinkList tail, int n, int m)的处理思路如下:

(1) .用k计数,每次都从0开始,当计数到m-1时结束本次计数;

(2) .通过指针p查找出圈者所对应的结点,当k的值等于m-1时,p应指向出圈者对应结点的前驱结点;

(3) .通过删除结点表示出圈处理;

(4) .当m大于圈中剩余人数时,为了避免重复计数,用模运算修改m的值:

(5) .计数和删除操作完成后再恢复m的原值。

【C函数】

【问题:4.1】阅读说明和C函数,填补C函数中的空缺(1)〜(5)。
第9章C程序设计
正确答案:
你的答案:
请先在App中激活(应用市场搜“软考真题”)
知识点:
试卷:
2011年 下半年 下午试卷 案例

笔记

答题卡
加油