题目描述
n 个人围成一圈，从第一个人开始报数,数到 m 的人出列，再由下一个人重新从 1开始报数，数到 m 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。
输入格式
输入两个整数 n,m。
输出格式
输出一行 n 个整数，按顺序输出每个出圈人的编号。
输入输出样例
输入
10 3
输出
3 6 9 2 7 1 8 5 10 4
说明/提示
1≤m,n≤100
1.动态单向链表实现的方法
动态链表需要临时分配链表节点，使用完毕后需要释放链表节点，动态链表的优点是能及时释放空间，不用使用多余的内存，缺点是需要管理空间，比较容易出错。
#define _CRT_SECURE_NO_WARNINGS #include<iostream> struct node { int data; node* next;//单向链表，一个next指针 }; int main() { int m, n; scanf("%d%d", &n, &m); node* head, * p, * now, * prev; head = new node; head->data = 1; head->next = NULL;//分配第一个节点,数据置为1 now = head; for (int i = 2; i <= n; i++) { p = new node; p->data = i; p->next = NULL;//把申请的新节点链接到前面的链表上 now->next = p; now = p; } now->next = head; //上面是建立链表。 now = head, prev = head; while ((n--) > 1) { for (int i = 1; i < m; i++)//数到m为止 { prev = now;//类似于单链表的元素删除，记录前一个位置，用于下面跳过第m个节点 now = now->next; } printf(" %d ", now->data); prev->next = now->next; delete now; now = prev->next; } printf(" %d", now->data);//最后一个节点的打印 delete now;//释放掉最后一个节点 return 0; }
为了方便大家理解思路，我做出了第一次while循环的图示 ，为了简便，节点就设置成了4个,m的值就设置为3。
2.用结构体数组实现单向静态链表实现的方法
静态链表较动态链表省去了动态分配和释放储存空间的麻烦。可以加快编码的速度。
#define _CRT_SECURE_NO_WARNINGS #include<iostream> const int N = 100;//定义静态链表的空间大小 struct node { int id, nextid; }nodes[N]; int main() { int n, m; scanf("%d%d", &n, &m); nodes[0].nextid = 1; for (int i = 1; i <= n; i++) { nodes[i].id = i, nodes[i].nextid = i + 1; } nodes[n].nextid = 1; int now = 1, prev = 1; while ((n--) > 1) { for (int i = 1; i < m; i++) { prev = now; now = nodes[now].nextid; } printf(" %d ", nodes[now].id); now = nodes[prev].nextid; } printf(" %d", nodes[now].nextid); return 0; }
同样是画了个简图方便理解（不要嫌弃我字丑🤗🤗🤗）
3.用结构体数组实现双向静态链表实现的方法
#define _CRT_SECURE_NO_WARNINGS #include<iostream> const int N = 100; struct node { int id; int preid, nextid;//前后节点 }nodes[N]; int main() { int n, m; scanf("%d%d", &n, &m); nodes[0].nextid = 1; for (int i = 1; i <= n; i++) { nodes[i].id = i; nodes[i].preid = i - 1; nodes[i].nextid = i + 1; } nodes[n].nextid = 1;//循环链表，尾指向头 nodes[1].preid = n;//循环链表，头指向尾 int now = 1;//从第一个节点开始 while ((n--) > 1) { for (int i = 1; i < m; i++) { now = nodes[now].nextid; } printf(" %d ", nodes[now].id); int prev = nodes[now].preid, next = nodes[now].nextid; nodes[prev].nextid = nodes[now].nextid; nodes[next].preid = nodes[now].preid; now = next;//新的开始 } printf(" %d", nodes[now].nextid); return 0; }
同样的，简图方便大家理解。
4.一维数组实现单向循环链表
这是最简单的实现方法。定义一个一维数组，数组的第i个节点的i就是节点的值。
#define _CRT_SECURE_NO_WARNINGS #include<iostream> int nodes[150]; int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 1; i <= n - 1; i++) { nodes[i] = i + 1;//nodes[i]的值就是下一个节点 } nodes[n] = 1; int now = 1, prev = 1; while ((n--) > 1) { for (int i = 1; i < m; i++) { prev = now; now = nodes[now]; } printf(" %d ", now); nodes[prev] = nodes[now];//跳过now节点 now = nodes[prev];//新的now节点 } printf(" %d", now); return 0; }
这个就不画图了。
现在我是在自学c++,还不是很熟练。
总结
感谢观看，本文到这里就结束了，如果觉得有帮助，请给文章点个赞吧，让更多的人看到。🌹 🌹 🌹
