数据结构代码集训day16（适合考研、自学、期末和专升本）
本题来自B站up：白话拆解数据结构
今日题目就一个：约瑟夫环问题。
一个圈共有N个人（N为不确定的数字），第一个人的编号为0或者1（两个都可以，看你的程序如何编写），假设这边我将第一个人的编号设置为1号，那么第二个人的编号就为2号，第三个人的编号就为3号，第N个人的编号就为N号，现在提供一个数字M，第一个人开始从1报数，第二个人报的数就是2，依次类推，报到M这个数字的人出局，紧接着从出局的这个人的下一个人重新开始从1报数，和上面过程类似，报到M的人出局，直到N个人全部出局，请问，这个出局的顺序是什么？
这张图内圈代表元素，外圈代表出局的顺序。这里的元素有10个，报到三出局。出局就相当于从这个圈出去了，圈内元素减1。
这题有三种方法，第一个方法是用顺序表，用i记录出列下标，用count记录出列的个数，由于走完一圈后需要回到开头继续数，所以要i=i%L.length重置一下，删除的操作就是元素前移，前面已经说过了。
void fa1(SqList &L,int N,int M){
int count=0,i=0;
while(count!=N){
for(int k=0;k<M-1;k++,i++);
if(i>=L.length) i=i%L.length;
printf("%d ",L.data[i]);
for(int j = i; j < L.length - 1; j++) {
L.data[j] = L.data[j + 1];
}
count++;
L.length--;
}
}
实践：打印依次出队的元素
法二：用循环单链表，刚好类似于图上的结构，和上面一样，找M，然后删除，就是重置的时候注意一下就行了。
void fa2(Linklist &L,int N,int M){
if (L == NULL || L->next == L)
return; // 空链表或链表只有一个节点时，无需删除
Lnode *pre ,*p; // 删除的两个指针
pre=L;
p=L->next;
while(L!=L->next){
for(int i=0;i<M-1;i++){
pre=p;
p=p->next;
if(p==L){ // 重置
p=p->next;
pre=pre->next;
}
}
printf("%d ",p->data);
pre->next=p->next;
free(p);
p=pre->next;
}
}
实践：
法三：递归的做法，当 i == 1 时，表示只剩下一个人。这时，这个人的位置通过公式 (M - 1 + N) % N 来计算；函数通过调用自身，递归地减少人数（N-1）和索引（i-1），逐步缩小问题的规模；递归调用的结果会通过加上步长 M 并取模 N 来调整，确保计算的位置在当前圆圈中有效。
int fa3(int N,int M,int i){
if(i==1) return (M-1+N)%N;
else return (fa3(N-1,M,i-1)+M)%N;
}
实践：这里输出的是位序，换算出来和上面一样。
#include <iostream>
#include <cstdio>
#include <stack>
#include <ctime>
using namespace std;
typedef int ElemType;
struct SqList {
ElemType data[100];
int length;
};
typedef struct Lnode{
int data;
Lnode *next;
}Lnode,*Linklist;
Linklist list_insertbytail(Linklist &L) {
Lnode *s;
int x;
// 初始化头节点（哨兵节点），不存储实际数据
L = (Lnode*)malloc(sizeof(Lnode));
L->next = L; // 初始化为循环结构
Lnode *r = L; // r始终指向链表的尾节点
cin >> x;
while (x != 9999) {
s = (Lnode*)malloc(sizeof(Lnode)); // 为新节点分配空间
s->data = x; // 将数据存入新节点
s->next = L; // 新节点的next指向头节点，形成环
r->next = s; // 将新节点链接到尾部
r = s; // 更新尾节点指针为r
cin >> x; // 继续输入下一个数据
}
return L; // 返回循环链表
}
// 约瑟夫环问题,N个人报数，报到M的出列，从M的下一个开始报，报到M的再次出列，问剩下的那个是谁
class Solution{
public:
void fa1(SqList &L,int N,int M){ // 找M，删M，从下一个开始
int count=0,i=0; // count统计出列个数，到N-1就行了
while(count!=N){
for(int k=0;k<M-1;k++,i++);
if(i>=L.length) i=i%L.length;
printf("%d ",L.data[i]);
for(int j = i; j < L.length - 1; j++) {
L.data[j] = L.data[j + 1];
}
count++;
L.length--;
}
}
void fa2(Linklist &L,int N,int M){
if (L == NULL || L->next == L)
return; // 空链表或链表只有一个节点时，无需删除
Lnode *pre ,*p;
pre=L;
p=L->next;
while(L!=L->next){
for(int i=0;i<M-1;i++){
pre=p;
p=p->next;
if(p==L){
p=p->next;
pre=pre->next;
}
}
printf("%d ",p->data);
pre->next=p->next;
free(p);
p=pre->next;
}
}
int fa3(int N,int M,int i){
if(i==1) return (M-1+N)%N;
else return (fa3(N-1,M,i-1)+M)%N;
}
};
int main(){
// SqList L;
// L.length =10;
// // srand(static_cast<unsigned int>(time(nullptr)));
// // // 随机赋值
// for(int i =0;i<L.length;i++){
// L.data[i] = i+1;
// }
// Linklist L;
// list_insertbytail(L);
// Lnode *p = L->next;
int N,M;
cin>>N>>M;
printf("start:");
Solution a;
// a.fa1(L,10,3);
for(int i=1;i<=N;i++)
printf("%d ",a.fa3(N,M,i));
return 0;
}