有一堆人排成一圈,喊到一个数就出局,最后剩下的人,用c语言用动态链表编程

Answer 1

这个问题是有名的约瑟夫问题。

假设有n个人参加报数，依次编号1~n。从编号1开始依次报数，从1报到m，报到m的人出列，剩下来的人重新开始报数，报到m的人出列，如此重复直到所有人都出列为止。最后出列的人原来的编号是多少？

链表程序如下：

#include <stdio.h>
#include<stdlib.h>
struct node
{
int num;
struct node *next;
};
struct node *create(int n)
{
int i;
struct node *p,*head=NULL,*rear;
for(i=0;i<n;i++)
{
p=(struct node *)malloc(sizeof(struct node));
p->num=i+1;
if(head==NULL)
{
head=p;
rear=p;
}
else
{
rear->next=p;
rear=p;
}
}
rear->next=head;
return head;
}

void Del(struct node *head,int n,int m)
{
int i,j;
    struct node *p,*q=head,*front=head;
while(q->next!=head)
q=q->next;
for(j=0;j<n;j++)
{
for(i=1;i<m;i++)
{
q=front;
front=front->next;
}
        printf("%d\t",front->num);
p=front;
q->next=front->next;
front=front->next;
free(p);
}
}

void main()
{
int m,n;
    struct node *head;
printf("输入报到人数n:");
    scanf("%d",&n);
printf("输入报数终值m:");
    scanf("%d",&m);
head=create(n);
    if(n>0 && m>0)
{
Del(head,n,m);
head=0;
}
}

运行结果：

假设10个人参加报数，报到3的人出列，则出列顺序为

最后出列的是原来编号为4的人。