HZNUOJ

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

Tags:
Time Limit:  1 s      Memory Limit:   128 MB
Submission:79     AC:20     Score:98.59

Description

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

nk

from 不知道什么百科


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


#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

input
2 3
output
1 2