n個人(編號為0,1,...,n-1)圍成一個圈子，從0號開始依次報數(shù)昭雌，每數(shù)到第m個人，這個人就得自殺健田，之后從下個人開始繼續(xù)報數(shù)烛卧，直到所有人都死亡為止。問最后一個死的人的編號(其實看到別人都死了之后最后剩下的人可以選擇不自殺……)妓局。
約瑟夫環(huán).jpg
問題主要有兩種問法
- 問具體的自殺流程
- 問最后留下的那個人的編號
下面分別針對兩種問法來說明：
1总放、自殺的流程
可以利用循環(huán)鏈表模擬整個流程
c++實現(xiàn)循環(huán)鏈表實現(xiàn)
#include <iostream>
/*
* 約瑟夫問題利用循環(huán)鏈表進行模擬
*/
typedef struct node{
int data;
struct node* next;
} node;
//初始化循環(huán)鏈表
node* create(int n) {
node *head, *p,*s;
head = (node *) malloc(sizeof(node)); // 空頭節(jié)點，僅提供一個鏈表初始化的入口
p = head;
if (0 != n) {
for (int i = 1; i <= n; i++) {
s = (node *) malloc(sizeof(node));
s->data = i;
p->next = s;
p = s;
}
s->next = head->next; //尾節(jié)點指向第一個存有數(shù)據(jù)的節(jié)點
}
free(head);
return s->next;
}
void Josephus_Process(int n, int m, node* p){
node* temp;
while ( p->next != p ){
for(int i = 1; i < m-1 ; i++){
p = p->next;
}
std::cout<<p->next->data<<"->";
temp = p->next;
p->next = temp->next;
free(temp);
p = p->next;
}
std::cout<<p->data<<std::endl;
}
int main() {
int n = 10;
int m = 4;
node* p = create(n);
Josephus_Process(n,m,p);
return 0;
}
2好爬、最后留下存活的人
這時可以利用遞歸方法和數(shù)學推導得到最后留下的人
#include <iostream>
#include <list>
using std::cout;
using std::endl;
using std::cin;
using std::list;
int main()
{
int total = 0;
cout << "Please input total number of people : ";
cin >> total;
int number = 0;
cout << "Please input selected number : ";
cin >> number;
/* If number = 3
* f(1) = 0
* f(2) = 1 = (f(1) + 3) % 2
* f(3) = 1 = (f(2) + 3) % 3
* f(4) = 0 = (f(3) + 3) % 4
* f(5) = 3 = (f(4) + 3) % 5
* ...
* f(n) = x = (f(n-1) + 3) % n
* */
int last = 0; // f(1) = 0
for(int i = 2; i <= total; ++i)
{
last = (last + number) % i;
}
cout << "The last one is : " << last + 1 << endl;
return 0;
}
