SSOJ1197约瑟夫问题链表实现
2713+
作者:crxis 发布:2017-08-09 分类:链表
题目大意:约瑟夫问题,n个人围成一圈,依次报数,报到m出列,出列后不再报数,输出出列顺序。
题目描述
有n个人围坐在一个圆桌周围,把这n个人一次编号为1,2,…,n。从编号是1 的人开始报数,数到第m个人就出列,然后从出列的下一个人重新开始报数,数到第m个人又出列……..如此反复,直到只所有人都出列为止。给出n和m的值,输出出列顺序。
输入
第一行两个数n和m(n,m<1000)
输出
出列顺序
样例输入
6 5
样例输出
5 4 6 2 3 1
解题思路
用结构体存储每个人的编号和下一个报数的人是谁;建立一个循环链表,这样报到最后一个会回到第一个。
1、预处理:n个人,分配n个结构体的空间,分别存下编号可以下一个报数编号的地址。
2、报数出列:从“头”开始报数,报m-1次后,到第m个时输出,并让他出列——出列者的前一个的下一个报数的人是出列者的下一个报数的人,下一次有出列者的下一个人开始报数。