约瑟夫环

1.问题描述：n个人（编号1~n)，从1开始报数，报到m的退出，剩下的人继续从1开始报数。按顺序输出列者编号

模拟过程，使用循环链表或者数组，但是链表便于删除，效率更高。使用循环链表的C代码如下:

#include <stdio.h>
#include <stdlib.h>

struct node
{
	int value;
	struct node *next;
};
typedef struct node list;

int main()
{
	int n, m;
	int i;
	while(scanf("%d%d", &n, &m) != EOF)
	{
		list *head, *tmp, *pre;
		head = (list*)malloc(sizeof(list));
		head -> value = 1;
		head -> next = NULL;
		tmp = head;
		for(i=2; i<=n; i++)
		{
			list *node = (list*)malloc(sizeof(list));
			node -> value = i;
			node -> next =NULL;
			tmp -> next = node;
			tmp = node; 
		}
		tmp -> next = head;	//link the last to the head
		
		pre = tmp;
		tmp = head;
		while(tmp -> next != tmp)
		{
			for(i=1; i<m; i++)
			{
				pre = tmp;
				tmp = tmp -> next;
			}
			//delete the node to which tmp point to
			pre -> next = tmp -> next;
			printf("%d ", tmp -> value);
			free(tmp);
			tmp = pre -> next;
		}
		printf("%d\n", tmp -> value);
		free(tmp);
	}
	return 0;
}

另一种方法是使用数学方法计算，C代码如下：

#include <stdio.h>
#include <stdlib.h>

int main()
{
	int n, m;
	int i , p;
	int *array, counter;
	while(scanf("%d%d", &n, &m) != EOF)
	{
		i = 0;
		array = (int*)malloc(sizeof(int)*n);
		counter = 0;
		while(++i <= n)
		{
			p = i * m;
			while(p > n)
				p = p - n + (p - n -1)/(m - 1);
			array[counter] = p;
			counter++;
		}
		
		if(counter == 1)
			printf("%d\n", array[0]);
		else
		{
			for(i=0; i<counter-1; i++)
				printf("%d ", array[i]);
			printf("%d\n", array[i]);
		}
		free(array);
	}
	return 0;
}

两种方法的时间复杂度都是O(n)