约瑟夫问题的源程序？

Answer 1

#include <cstdio>

struct Node
{
int data;
Node * next;
};

Node* make_list(int n)//建立一个循环链表
{
Node *p = new Node, *q;
int i;

p->data = 1;//先建立一个只有一个节点的循环链表
p->next = p;

for(i = 2; i <= n; i++)//再向其中插入剩下的n－1个节点
{
q = new Node;
q -> data = i;
q -> next = p -> next;
p -> next = q;
p = q;
}
return p;
}

void Joseph(int n, int m)
{
Node *p = make_list(n), *q = p;//p指向最后一个节点，保证下一个是第一个节点
int i, j;
for(i = 0; i < n; i++)
{
p = q;
p = p -> next;
for(j = 1; j < m; j++)
{
p = p -> next;
q = q -> next;
}
printf("%d ", p -> data);
q -> next = p -> next;
delete p;
}
printf("\n");
}

int main()
{
int n, m;
while(scanf("%d%d", &n, &m) == 2 && m > 0 && n > 0)//输入两个数,n表示一共n个人，m表示每次从1数到m
Joseph(n, m);
return 0;
}