Question

编程：用带头节点（或不带头节点）的单循环链表解决约瑟夫环问题（c++,c）。要能运行，最好有截图

Answer 1

/*
   C- Program to implement josephus problem
*/
#include<stdio.h>
#include<stdlib.h>

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

typedef struct node node;

int josephus(int,int, node *);

node *head=NULL,*h=NULL;


void main()
{
        int count=1,n,m,s;//改动
        node *new;
        printf("请输入玩游戏的人数 n:"); 
        scanf("%d",&n);
        while(n < 1)//改动
        {
            printf("\n玩这个游戏至少也要1个人吧？请重新输入n: ");
            scanf("%d",&n);
        }
        printf("请输入点到则出局的数字 m （小于 %d）: ",n); 
        scanf("%d",&m);
        while(m > n || m <1)
        {
            printf("\n请确认点到则出局的数字 m在1到%d内 重新输入m: ",n);
            scanf("%d",&m);
        }
        printf("从哪个开始数？：");
        scanf("%d",&s);
        while(s > n || s <1)
        {
            printf("\n从序号为s的人开始数，请确认输入的数在1到%d内,请重新输入s: ",n);
            scanf("%d",&s);
        }
        while(count<=n)
        {
                new=(node*)malloc(sizeof(node));
                new->data=count++;
                if(head==NULL)
                {
                        head=new;
                        new->next=head;
                }
                else
                {
                        h=head;
                        while(h->next!=head)
                                h=h->next;
                        h->next=new;
                        new->next=head;
                }
        }
        printf("排成圈子的顺序是:\n");
        h=head;
        while(h->next!=head)
        {
         printf("%d->",h->data);
                h=h->next;
        }
        printf("%d",h->data);
        printf("\n");
        
        printf("\n\n共%d个人进行游戏，从第%d个人开始数，每数到%d的那个人就出局。\n游戏出局的顺序是：\n",n,s,m);
        josephus(m,s,head); 
}

int josephus(int m,int s,node *front)
{
        node *f;
        int c=1;
        
        for(; s>1; s--)
        {
            front=front->next; //让front指向第s个。
        }
        
        
        while(front->next!=front)
        {
                c=1;
                while(c!=m)
                {
                        f=front;
                        front=front->next;
                        c++;
                }
                f->next=front->next;
                printf("%d->",front->data); //打印出局者
                front=f->next;
        }
        printf("\n");
        printf("胜出者是:%d\n",front->data);  //打印“最后出局”胜利的人
        return 0;
}