admin 管理员组文章数量: 1184232
【约瑟夫环】
【约瑟夫环】
- 问题描述
- 通过链表解决
- 通过数组模拟解决
- 通过数学推导公式解决
- 思路
- 代码1：
- 代码2
问题描述
约瑟夫问题是个著名的问题：N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。
通过链表解决
通过链表的思路比较简单，只需写一个循环链表，然后数个数删除节点，直到最后一个节点。
#include <iostream>
using namespace std;
struct Node {int num;Node *next;
};
//插入节点
Node* insert(Node* head, Node* tail, int x)
{Node* n = (Node *)malloc(sizeof(Node));n->num = x;n->next = head;tail->next = n;return n;
}
int main()
{int n, m;cout << "请输入总共人数:";cin >> n;cout << "请输入m,确定第几个人:";cin >> m;Node* head = (Node *)malloc(sizeof(Node));Node* tail = NULL;head->num = 1;tail = head;head->next = tail;for (int i = 1; i < n; i++){insert(head, tail, i + 1);tail = tail->next;}int num = 0;Node* p = tail;Node* q = NULL;while (p->next != p){q = p->next;num++;if (num > m){num = 1;}if (num == m){p->next = q->next;free(q);//删除节点，q是p后面一个节点continue;}p = p->next;}cout << "最终存活的是：" <<p->num << endl;return 0;
}
运行结果如下：
通过数组模拟解决
- 思路:
标记已经杀死的，依次数未标记的，最终只剩下一个人。 - 代码演示:
#include <iostream>
using namespace std;
int main()
{int n, m;cout << "请输入总共人数:";cin >> n;cout << "请输入m,确定第几个人:";cin >> m;int* arr = (int *)malloc(n * sizeof(int));int* arr2 = (int *)malloc(n * sizeof(int));memset(arr, 0, n * sizeof(int));for (int i = 0; i < n; i++){arr[i] = i + 1;}int num = 0;//标记已标记的人数int i = -1;int j = 0;while (num < n){i = (i + 1) % n;if (arr[i] != -1){j++;if (j > m){j = 1;}if (j == m){arr2[num++] = arr[i];arr[i] = -1;}}}cout << "最终存活的是：" << arr2[n-1] << endl;return 0;
}
运行结果如下：
通过数学推导公式解决
思路
首先，我先剧透一下推导公式：
- f(N,M)f(N,M)表示，N个人报数，每报到M时杀掉那个人，最终胜利者的编号
- f(N−1,M)f(N−1,M)表示，N-1个人报数，每报到M时杀掉那个人，最终胜利者的编号
下面我们来模拟一下n=7,m=3时的场景：
表示7个人，他们先排成一排，假设每报到3的人被杀掉。
刚开始时，头一个人编号是1，从他开始报数，第一轮被杀掉的是编号3的人。
编号4的人从1开始重新报数，这时候我们可以认为编号4这个人是队伍的头。第二轮被杀掉的是编号6的人。
……
第六轮时，编号1的人开始重新报数，这时候我们可以认为编号1这个人是队伍的头。这轮被杀掉的是编号5的人。
下一个人还是编号为1的人，他从1开始报数，不幸的是他在这轮被杀掉了。
最后的胜利者是编号为4的人。
将表格当成数组，并翻译后：
- f(1,3)f(1,3) ：只有1个人了，那个人就是获胜者，他的下标位置是0
- f(2,3)=(f(1,3)+3)%2=3%2=1f(2,3)=(f(1,3)+3)%2=3%2=1：在有2个人的时候，胜利者的下标位置为1
- f(3,3)=(f(2,3)+3)%3=4%3=1f(3,3)=(f(2,3)+3)%3=4%3=1：在有3个人的时候，胜利者的下标位置为1
- f(4,3)=(f(3,3)+3)%4=4%4=0f(4,3)=(f(3,3)+3)%4=4%4=0：在有4个人的时候，胜利者的下标位置为0
。。。 - f(7,3)=4;
通过上面的推导我们发现了很多共同点，总结起来就是f(N,M)=(f(N−1,M)+M)%N（N个人报数，每报到M时杀掉那个人，最终胜利者的编号）。
好了，公式也推的差不多了。没时间多说了，上代码：
- 代码演示
代码1：
#include <iostream>
using namespace std;
int main()
{int n, k, x = 0;cout << "请输入总共人数:";cin >> n;cout << "请输入k,确定第几个人:";cin >> k;for (int i = 2; i <= n; i++){x = (x + k) % i;}cout << "最后的幸存者是：" << x + 1 << endl;return 0;
}
运行结果如下：
代码2
#include<iostream>
#include<stdio.h>
using namespace std;int yuesefu(int n, int m)
{if(n == 1){ //这里返回下标,从0开始，只有一个元素就是剩余的元素0return 0;}else{return (yuesefu(n - 1, m) + m) % n; }
}
int main()
{int n, m;cout << "请输入总共人数:";cin >> n;cout << "请输入k,确定第几个人:";cin >> m;cout << "最后的幸存者是：" << yuesefu(n, m) + 1 << endl;return 0;
}
运行结果如下：
本文标签： 约瑟夫环
版权声明：本文标题：【约瑟夫环】 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1687109292a64792.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论