数据结构报数问题（约瑟夫环单链表解法）

约瑟夫环&＃xff08;单向链表&＃xff09;

问题描述&＃xff1a;有n个小朋友围成一圈玩游戏&＃xff0c;小朋友从1至n编号&＃xff0c;2号小朋友坐在1号小朋友的顺时针方向&＃xff0c;3号小朋友坐在2号小朋友的顺时针方向&＃xff0c;……&＃xff0c;1号小朋友坐在n号小朋友的顺时针方向。
　　游戏开始&＃xff0c;从1号小朋友开始顺时针报数&＃xff0c;接下来每个小朋友的报数是上一个小朋友报的数加1。若一个小朋友报的数为k的倍数或其末位数&＃xff08;即数的个位&＃xff09;为k&＃xff0c;则该小朋友被淘汰出局&＃xff0c;不再参加以后的报数。当游戏中只剩下一个小朋友时&＃xff0c;该小朋友获胜。
　　例如&＃xff0c;当n&＃61;5, k&＃61;2时&＃xff1a;
　　1号小朋友报数1&＃xff1b;
　　2号小朋友报数2淘汰&＃xff1b;
　　3号小朋友报数3&＃xff1b;
　　4号小朋友报数4淘汰&＃xff1b;
　　5号小朋友报数5&＃xff1b;
　　1号小朋友报数6淘汰&＃xff1b;
　　3号小朋友报数7&＃xff1b;
　　5号小朋友报数8淘汰&＃xff1b;
　　3号小朋友获胜。
　　给定n和k&＃xff0c;请问最后获胜的小朋友编号为多少&＃xff1f;
输入格式
　　输入一行&＃xff0c;包括两个整数n和k&＃xff0c;意义如题目所述。
输出格式
　　输出一行&＃xff0c;包含一个整数&＃xff0c;表示获胜的小朋友编号。
样例输入
5 2
样例输出
3
样例输入
7 3
样例输出
4
数据规模和约定
对于所有评测用例&＃xff0c;1 ≤ n ≤ 1000&＃xff0c;1 ≤ k ≤ 9。
要求&＃xff1a;利用单向循环链表存储结构模拟此过程。

#include
#include
using namespace std;
typedef struct lnode
{int num;//编号int shu;//报数struct lnode *next;
}lnode,*link;void create(link &L,int m) //建造小朋友链表
{int i;L&＃61;new lnode;L->num&＃61;1;L->next&＃61;L;link q&＃61;new lnode;q&＃61;L;for(i&＃61;2;i<&＃61;m;i&＃43;&＃43;){link p&＃61;new lnode;p->num&＃61;i;p->next&＃61;q->next;q->next&＃61;p;q&＃61;p;}
}
link qianqu(link &L,link p) //找前驱
{link q&＃61;new lnode;q&＃61;L;while(q->next!&＃61;p)q&＃61;q->next;return q;
}void game(link &L,int n)
{link p&＃61;new lnode;p&＃61;L;int i&＃61;1;while(p->next!&＃61;p){p->shu&＃61;i;i&＃43;&＃43;;if(p->shu%n&＃61;&＃61;0||p->shu%10&＃61;&＃61;n) //{link q&＃61;new lnode;q&＃61;p; //q记住pp&＃61;qianqu(L,p); //p指向p的前驱p->next&＃61;q->next;delete(q);}p&＃61;p->next;}printf("%d",p->num);
}int main()
{int m,n;link L;scanf("%d %d",&m,&n);create(L,m);game(L,n);
}

类似的约瑟夫环问题可以在game函数里if语句进行修改。