Algorithm Gossip (26) 约瑟夫环问题

前言

This Series aritcles are all based on the book 《经典算法大全》; 对于该书的所有案例进行一个探究和拓展，并且用python和C++进行实现; 目的是熟悉常用算法过程中的技巧和逻辑拓展。

提出问题

26.Algorithm Gossip: 约瑟夫问题 （Josephus Problem)

分析和解释

C语言 基础题， 一般书上都有示例

代码

#include <stdio.h>
#include <stdlib.h>
#define N 41
#define M 3
int main(void) {
	int man[N] = {0};
	int count = 1;
	int i = 0, pos = -1;
	int alive = 0;
	while(count <= N){
		do {
			pos = (pos+1)% N; // 环状处理
			if(man[pos] == 0)
				i++;
			if(i == M){ // 报数为3了
				i = 0;
				break;
				}
			} while(1);
		man[pos] = count;
		count++;
		}
	printf("
约琴夫排列：");
	for(i = 0; i < N;i++)
		printf("%d ", man[i]);
	printf("

您想要救多少人？");
	scanf("%d", &alive);
	printf("
L表示这%d人要放的位置：
", alive);
	for(i = 0; i < N;i++) {
		if(man[i] > alive) printf("D");
		else printf("L");
		if((i+1) % 5 == 0) printf(" ");
		}
	printf("
");
	return 0; }

拓展和关联

后记

参考书籍

• 《经典算法大全》
• 维基百科