|
一、什么是约瑟夫环
? ? ? 有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再接着从1开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的编号。? ??
? ? ?OJ链接：OpenJudge - 1748:约瑟夫问题
二、循环链表实现
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
//在每一次循环中，都先处理核心功能部分的代码
struct node {
int data;
struct node* next;
};
int main() {
int n, m, i;
int answer[100];//猴王
int count = 0; //计数
struct node* head, * tail, * p, * q;
//虚拟头节点，数据域为-1
head = (struct node*)malloc(sizeof(node));
head->next = NULL; //指针域赋为空，这很重要
head->data = -1;
while (1) {
//通过输入样例我们看出来的：题目要求是可以多次输入n，m，因此我们要一直循环。
scanf("%d %d", &n, &m);
//如果n或m==0，释放head节点，然后退出循环
if (n == 0 || m == 0) { free(head); break; }
else {
tail = head;
//尾插法能保证顺序相同
for (i = 1; i <= n; i++) {
p = (struct node*)malloc(sizeof(node));
p->data = i; //给p赋值，是猴子的编号
tail->next = p; //尾插
p->next = head->next;//这里的head是一个虚拟头节点
tail = p;//更新尾指针
}
//链表创建完成
p = head->next;//更新p让他指向首元节点
q = tail;//报数的节点是要删除的，也就是说我们还是需要一个前驱节点，也就是我们熟悉的双指针法
i = 1;//报数的变量，从1开始
while (p != q) {
//这个循环是在干什么？是在寻找这一次输入的nm条件下的猴王
//循环结束条件是什么？也就是说最后只剩下一个猴子的时候结束，那个猴子就是猴王。此时p和q重合。
if (i == m) {
//找到了
q->next = p->next;//删除操作
free(p);//释放内存很重要
p = q->next;//p仍然应该指向q下一个节点，且从p开始重新报数
i = 1;//新一轮报数开始1
}
else {
//说明还没有找到
q = p;
p = p->next;
i++;
}
} //p!=q的这个循环在这里就应该结束了。
//当最后剩两个节点时，如果删除的是首元节点(p = head -> next)，此时会发现head和链表之间的链接断开了。如果需要维持这种链接，还需要对head的指针域进行赋值
head->next = q;
answer[count] = p->data;
free(p);
count++;
//p和q都指向这个最后的猴子，保存了结果之后，就可以直接释放这个节点了
//这个步骤很容易忘记，不能留下垃圾。
head->next = NULL;//链表这个时候已经清空了，要给head的指针域置空，让他恢复到初始的空链表状态，便于下一次循环。
}
}//直到输入00的时候，才会退出循环。上面的if语句会释放head节点，这样才不会留下垃圾
for (i = 0; i < count; i++) {
printf("%d", answer[i]);
}
return 0;
}
| 遇到的问题 | | | 总是显示访问地址冲突 | 妥妥大冤种 | | 删除元素操作那里，应该是q -> next = p -> next | 写成了q -> next = p -> next -> next。当p指向最后一个结点的时候，p->next都已经是NULL，哪里来的p->next ->next |
简约版没什么注释的代码：
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* next;
};
int main(void)
{
int n, m;
int i;
int answer[100];
int count = 0;
struct node* head, * tail, * p, * q;
head = (struct node*)malloc(sizeof(struct node));
head->next = NULL;
while (1) {
scanf("%d %d", &n, &m);
if (n == 0 || m == 0) {
free(head);
break;
}
else {
//尾插法，生成循环链表
tail = head;
for (i = 0; i < n; i++) {
p = (struct node*)malloc(sizeof(struct node));
p->data = i + 1;
tail->next = p;
p->next = head->next;
tail = p;
}
p = head->next; //后结点
q = tail; //前结点
i = 1;
while (p != q) {
if (i == m) {
q->next = p->next;
free(p);
p = q->next;
i = 1;
}
else {
q = p;
p = p->next;
i++;
}
}
answer[count] = p->data;
count++;
free(p);
head->next = NULL;
}
}
for (i = 0; i < count; i++) {
printf("%d\n", answer[i]);
}
return 0;
}
三、数组标志位实现
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
//数组标记法
int main()
{
int n, m;
int number; //记录剩余的猴子个数
int count = 1; //代表当前的报数
int i, pos;
while (~scanf("%d %d", &n, &m)) {//多组nm循环，输入0停止
if (n == 0 || m == 0) {
return 0;
}
number = n;
int monkey[301] = { -1 };//数组存储猴子的编号和状态
//退出的猴子数组值改为0，-1代表无效数组部分，1到n+1代表还没退出的猴子
for (i = 0; i < n; i++) {
monkey[i] = i + 1;
}
pos = 0;//pos用来控制当前处理的数组下标
while (number > 1) {
//剩余的猴子大于1时
//报数为m的猴子改为0
if (monkey[pos] > 0) {
//报数轮次变多，报数为m的越来越多，元素为0的越来越多，只有大于0的元素才需要继续报数操作
if (count != m) {
//不退出
count++;
pos = (pos + 1) % n; //为什么要取模呢？
//这是一个环形的结构。比如n = 10，那么10的下一个是1
}
else {
monkey[pos] = 0;//标记
count = 1;//重新开始报数
number--;//猴子数量减少
pos = (pos + 1) % n;//普通数组构成环状数组的核心语句
}
}
}
for (i = 0; i < n; i++) {
if (monkey[i] == 0)
printf("%d", monkey[i]);
}
}
return 0;
}
? ? ? ?但是OJ超时了。
四、数组模拟链表方式实现
| 怎样用数组模拟链表 | 让数组的元素值为next的下标，这样就连接起来了 | | 下标和猴子编号之间的关系 | 下标+1为猴子的编号，最后输出的时候别忘了下标+1 | | 双指针 | pos和prior一前一后，怎么移动才能有循环的效果呢？ |
//数组链接方式实现实现约瑟夫环
//用数组来模拟循环链表
//开拓思路
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main()
{
int n, m;
int number;//记录剩余猴子个数
int count;//代表当前的报数
int i, pos, prior;//pos当前下标，prior表示前一个下标。像不像我们链表里面的双指针？
while (~scanf("%d %d", &n, &m)) {
if (n == 0 || m == 0) return 0;
int monkey[301] = { 0 };//下标为-1的退出循环
for (i = 0; i < n - 1; i++) {
monkey[i] = i + 1;
}
//数组下标代表猴子编号，下标比猴子的实际编号小1
//下标为0的猴子的数组元素是1，即他的下一个猴子是下标为1的猴子。一共10个猴子的话，最后一个猴子的下标为9，它对应的数组元素是0，即他的下一个猴子是下标为0的猴子，也就是说最后一个猴子的下一个猴子是第一个猴子
monkey[i] = 0; //i = n-1的时候跳出循环，即最后一个猴子的数组元素值（编号）为0，形成循环链表
number = n;
pos = 0;//相当于单循环链表的p
prior = n - 1; //相当于单循环链表的q，他最开始再尾指针的位置
count = 1;//报数为1
while (number > 1) {//或者是pos != prior
if (count != m) {//没找到，移动
prior = pos;
pos = monkey[pos];
count++;
}
else {
monkey[prior] = monkey[pos];//数组值就是下一个猴子的下标
monkey[pos] = -1;//标记为退出
pos = monkey[prior];//当前猴子更新为下一个猴子
number--;
count = 1;
}
}
printf("%d", pos + 1);//猴子的下标+1为猴子的编号
}
return 0;
}
链接：数据结构与算法作业：带密码的约瑟夫环（数据结构与算法上机作业专栏里面的文章已经更新）
拓展、约瑟夫环数学方法，推导在课后完成
|