约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。
/** * 约瑟夫环: * 已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。 * Josephu(int n, int m) * @author arhaiyun * Date: 2013-09-26 **/ #include "stdafx.h" #include <iostream> #include <stdlib.h> using namespace std; typedef struct LinkNode{ int index; struct LinkNode* next; }JosephuNode; int Josephu(int n, int m) { //[1].Create a circulatory Link list JosephuNode *head, *tail; head = tail = (JosephuNode*) malloc(sizeof(JosephuNode));; for(int i = 1; i < n; i++) { tail->index = i; tail->next = (JosephuNode*)malloc(sizeof(JosephuNode)); tail = tail->next; } tail->index = n; tail->next = head; //[1].Count to the specific number and let him out for(int i = 1; tail != head; ++i) { for(int j = 1; j < m; ++j) { tail = head; head = head->next; } tail->next = head->next; cout<<"The "<<i<<" round "<<head->index<<" is out"<<endl; free(head); head = tail->next; } int winner = head->index; free(head); head = tail = NULL; return winner; } int main() { int winner = Josephu(5, 3); cout<<"Last winner is:"<<winner<<endl; system("pause"); return 0; }
顺便附上一个数学思想的约瑟夫环解法,要求有点不一样。就是一共n个人,查到m的人出圈,求最后圈里的人是几号。
int fun(int n, int m) { int i, r = 0; for (i = 2; i <= n; i++) r = (r + m) % i; return r+1; }