【数据结构】约瑟夫环问题

Tags:

Description

约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

from 不知道什么百科

如题，对于给定的代码，完成slove(int n，int m)函数，使得它能够解决约瑟夫环问题。

Toggle Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct node node;
typedef struct node *ptr;

struct node
{
	int pos;
	ptr next;
};

ptr createSomething(int n)
{
	ptr res=NULL;
	res = (ptr)malloc(sizeof (node));
	res->pos = 1;
	res->next = res;
	res = res->next;
	int i;
	for (i = 2; i <= n; i++)
	{
		ptr tmp = (ptr)malloc(sizeof (node));
		tmp->pos = i;
		tmp->next = res->next;
		res->next = tmp;
		res = tmp;
	}
	return res->next;
}

void solveSomething(ptr p,int n, int m);

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	ptr head = createSomething(n);
	solveSomething(head, n, m);
} 

Input

输入只有两个数字 n，m (1<=n,m<=100)

表示总共有n个人，报到m的出列

最开始由标号为1的人开始喊

Output

输出只有一行整数，为出列的人的标号

Samples