[C/C++ 演算法]- 約瑟夫問題（Josephus Problem）

[C/C++ 演算法]- 約瑟夫問題（Josephus Problem）

剛才找資料時發現一個C/C++的教學網站，趕快發揮(C/P)的長才將它備份來，有需要的同好，歡迎來(C/P)一下^^。

拷貝來源：
http://openhome.cc/Gossip/AlgorithmGossip/
http://openhome.cc/Gossip/AlgorithmGossip/JosephusProblem.htm

#include <stdio.h> #include <stdlib.h> #define LEN 41 #define STEP 3 void josephus(int*, int, int); int next(int*, int, int, int); int winner(int, int); int main(void) { int man[LEN] = {0}; josephus(man, LEN, STEP); printf("約琴夫排列："); int i; for(i = 0; i < LEN; i++) { printf("%d ", man[i]); } printf("\nWinner: %d", winner(LEN, STEP)); return 0; } void josephus(int* man, int len, int k) { int i, n; for(i = 1, n = -1; i <= len; i++) { n = next(man, len, k, n); man[n] = i; } } int next(int* man, int len, int k, int n) { int count = 0; while(count < k) { n = (n + 1) % len; if(man[n] == 0) { count++; } } return n; } int winner(int len, int k) { int g, n; for(g = 0, n = 1; n <= len; n++) { g = (g + k) % n; } return g + 1; }