约瑟夫环问题的两种解决方法

一、单循环链表法

 

 

#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
    int number;
    int mima;
    struct node * next;
}Node, *Link;
Link Init(void)
{
    Link L;
    L = (Link)malloc(sizeof(Node));
    L->next = L;
    return L;
}
void Insert(Link L, int e_mima, int e_number)
{
    Link p,q;
    p = (Link)malloc(sizeof(Node));
    p->mima = e_mima;
    p->number = e_number;
    q = L;
    while(q->next != L)q = q->next;
    p->next = q->next;
    q->next = p;
}
void Delete(Link L, int i)
{
    Link p,q;
    q = L;
    while(q->next != q && q->next->number != i)
        q = q->next;
    if(q->next->number == i)
    {
        p = q->next;
        q->next = p->next;
        free(p);
    }
}
void main()
{
    Link p,q,L;
    int i,m,n,mima;
    printf("intput the n,m
");
    scanf("%d%d",&n,&m);
    if(n<=0 || m<=0)return;
    L = Init();
    i=1;
    while(i<=n)
    {
        printf("pass %d:",i);
        scanf("%d",&mima);
        if(mima <= 0)continue;
            Insert(L, mima, i);
        i++;
    }
    i = 0;
    p = L;
    while(L->next != L)
    {
        q = p;
        p = p->next;
        if(p ==L)
        {
            q = p;
            p = p->next;
        }
        i++;
        if(i == m)
        {
            printf("%d\t",p->number);
            m = p->mima;
            Delete(L, p->number);
            p = q;
            i = 0;
        }
    }
    getch();
}

 

二、数组法

 

#define N 100
int yuesefu1(int data[],int sum,int k)
{
   int i=0,j=0,count=0;
   while(count<sum-1)
   {
     if(data[i]!=0)/*当前人在圈子里*/
         j++;
     if(j==k)/*若该人应该退出圈子*/
     {
         data[i]=0;/*0表示不在圈子里*/
         count++;/*退出的人数加1*/
         j=0;/*重新数数*/
     }
     i++;/*判断下一个人*/
     if(i==sum)/*围成一圈*/
         i=0;
   }
   for(i=0;i<sum;i++)
      if(data[i]!=0)
          return data[i];/*返回最后一个人的编号*/
}

void main()
{
   int data[N];
   int i,j,total,k;
   printf("\nPlease input the number of every people.\n");
   for(i=0;i<N;)/*为圈子里的人安排编号*/
   {
      int input;
      scanf("%d",&input);
      if(input==0)
           break;/*0表示输入结束*/
      for(j=0;j<i;j++)/*检查编号是否有重复*/
          if(data[j]==input)
              break;
      if(j>=i&&input>0)/*无重复,记录编号,继续输入*/
      {
          data[i]=input;
          i++;
      }
      else
           printf("\nData error.Re-input:");
   }
   total=i;
   printf("\nYou have input:\n");
   for(i=0;i<total;i++)
   {
     if(i%10==0)
            printf("\n");
     printf("%4d",data[i]);
   }
   printf("\nPlease input a number to count:");
   scanf("%d",&k);
   printf("\nThe last one's number is %d",yuesefu1(data,total,k));
}