正文

求围圈问题的详细算法和程序集锦2006-06-24 21:57:00

【评论】 【打印】 【字体：大 中 小】 本文链接：http://blog.pfan.cn/goal00001111/16162.html

分享到：

这是以前发在"c语言之家"的一篇文章,今天把它收集到一起来.
17人围成一圈，编号为1，2，3，……，17，从1开始报数，报到3的倍数的人离开，
一直下去，直到最后剩下1人，求此人的编号。
这个题目的解法很多，我原来就总结了5种，但都不如用数组队列来的简明。
算法如下：
/*求围圈问题的详细算法和程序*/
/*17人围成一圈，编号为1，2，3，……，17，从1开始报数，报到3的倍数的人离开，
一直下去，直到最后剩下1人，求此人的编号  */

#include <stdio.h>
#include <stdlib.h>

int main(void)
{

       int a[17]={0};
       int front=0, rear=16;  //因为数据较小，可令队头元素也占一个实用（有数据域）的空间
       int i, count=0; //计数器

       for (i = 0;i < 17;i++)
              a[i] = i + 1;    /* 填空数组，编号是下标加一，注意C语言中的数组下标从0开始 */

       while ((front%17) != (rear%17))//当队列元素还有一个，注意这里不需要队列为空，而是留一个元素
       {
            if(++count <  3)//若元素非3的倍数，往前移
                  a[++rear%17] = a[front++%17];
            else    //否则将该元素从队列中删除，并打印
            {
                  printf("%d\n",a[front++%17]);    /* 把这个家伙打印出来 */
                  count = 0;
            }
      }

      printf("最后一个是：%d\n",a[rear%17]);
      system("pause");
      return 0;
}


另，附上几个不同的算法：（多数是我自己写的，部分是收集别人的 ）
一：
int main(void)
{
      int a[17]={0};
      int i, count, s;
     
      for (i = 0;i < 17;i++)
      {
            a[i] = i + 1;    /* 填空数组，编号是下标加一，注意C语言中的数组下标从0开始 */
      }
      i=0;
      s=17;  //用来记录退出圈外的人的数目
      count=0;  //计数器
      while (s > 1)
      {
            for (i=0; i<17; i++)
                  if (a[i] != 0)
                  {
                        count++;    //报一次数
                        if(count == 3)  //每报到一次3，该人退出
                        {
                              printf("%d\n",a[i]);    /* 把这个家伙打印出来 */
                              a[i] = 0;
                              count = 0;  //计数器归零
                              s--;
                        }
                  }
      }

      for(i=0; i<17; i++)
            if(a[i] != 0)
                  printf("最后一个是：%d\n",a[i]);

      system("pause");
      return 0;
}

二：
int main(void)
{
      int* arr;    /* 用于存储“那些人” */
      int n;        /* “那些人”的总数 */
      int s;        /* 开始的编号 */
      int m;        /* 间隔多少个人出列一个 */
      int i,j;

      printf("请输入多少个人：\n");
      scanf("%d",&n);
      printf("请输入开始的序号：\n");
      scanf("%d",&s);
      printf("请输入间隔的人数：\n");
      scanf("%d",&m);

      arr = (int*)(malloc(sizeof(int) * n));    /* 申请一个数组，以存储“那些人” */
      if (arr == NULL)    /* 并非一定分配成功的 */
      {
            printf("空间不足，程序退出。\n");
            return 1;
      }
    for (i = 0;i < n;i++)
    {
        arr[i] = i + 1;    /* 填空数组，编号是下标加一，注意C语言中的数组下标从0开始 */
    }
    printf("出列顺序：\n");
    j = s + m - 2;    /* 这是第一个要出列的人的下标 */

    while (n > 1)    /* 当队列中还有不止一个人的时候，要就进行出列的动作 */
    {
        printf("%d\n",arr[j]);    /* 把这个家伙打印出来 */
        /* 这个家伙走了以后，后面的人应该依次顶上来 */
        for (i = j;i < n - 1;i++)
        {
            arr[i] = arr[i + 1];
        }
        n--;    /* 并且整个队列的人少了一个，也就是长度要减掉一 */
        /* 这是下一个要出列的人 */
        j = (j + m - 1) % n;
    }
     /* 现在只有一个人了，就是arr[0] */
    printf("最后一个是：%d\n",arr[0]);
    free(arr);    /* 记得要释放申请的空间 */
      system("pause");
    return 0;
}

三：
int main(void)
{
      int a[17]={0};
      int i, j, s;

      for (i = 0;i < 17;i++)
    {
        a[i] = i + 1;    /* 填空数组，编号是下标加一，注意C语言中的数组下标从0开始 */
    }
    i=0;
    s=17;
    j=0;
    while(s > 1)
    {
        if(a[i%17] != 0)
        {
            if((i+1-j)%3 == 0)
            {
                printf("%d\n",a[i%17]);    /* 把这个家伙打印出来 */
                a[i%17] = 0;
                s--;
            }
        }
        else
            j++;
        i++;
        }
        for(i=0; i<17; i++)
               if(a[i] != 0)
                     printf("最后一个是：%d\n",a[i]);

    system("pause");
    return 0;
}

四：
int main(void)
{
    int n, m;
    int* a;    /* 用于存储“那些人” */
    int i, j, s;

    printf("请输入多少个人：\n");
    scanf("%d",&n);
    printf("请输入是哪个数字的倍数：\n");
    scanf("%d",&m);
   a = (int*)(malloc(sizeof(int) * n));    /* 申请一个数组，以存储“那些人” */
   if (a == NULL)    /* 并非一定分配成功的 */
   {
      printf("空间不足，程序退出。\n");
      return 1;
   }

   for (i = 0; i < n; i++)
   {
      a[i] = i + 1;    /* 填空数组，编号是下标加一，注意C语言中的数组下标从0开始 */
   }
    i = 0;   //从下标为 i%n 的元素开始数数
    j = 0;   //记录已经退出的元素的个数
    s = n;   //记录尚未退出的元素的个数

    while(s > 1)
   {
        if(a[i%n] != 0) //如果元素值不为0，则表示其尚未退出
        {
            if((i+1-j)%m == 0) //判断当前报数(i+1-j)是否为m的倍数，（-j）表示跳过j个元素
            {
                printf("第%d号出列\n",a[i%n]);    /* 把这个家伙打印出来 */
                a[i%n] = 0;   //已经退出的元素赋值为0
                s--;    //退出一个元素
            }
        }
        else   //如果元素值为0，则表示其已经退出
            j++; //此时i值仍然会累加，但我们记下这个已经退出的元素 ，以便报数时跳过它
        i++;
    }
        for(i=0; i<n; i++)
            if(a[i] != 0)
                printf("最后一个是：%d\n",a[i]);
    free(a);    /* 记得要释放申请的空间 */
    system("pause");
   return 0;
}

 五：
 /*此算法我看不懂*/
void fun(int m, int n);
int main(void)
{
       int n, m;
       int* a;    /* 用于存储“那些人” */
       int i, j, s;

       printf("请输入多少个人：\n");
   scanf("%d",&n);
   printf("请输入是哪个数字的倍数：\n");
   scanf("%d",&m);
   fun(n, m);
  
   system("pause");
   return 0;
}

void fun(int m, int n)
{

    int *pos;
    int i, p = m-1;
    pos = (int*)malloc(m*sizeof(int));
    pos[m-1] = 0;
    for (i=0; i<m-1; i++)
    {
        pos[i] = i+1;
    }
    do{
        //  printf("\np=%d\t", p);
        for (i=0; i<n-1; i++)
            p = pos[p];
     // printf("%d ",pos[p]+1);
      pos[p] = pos[pos[p>;
    } while(p != pos[p]);

    printf("%d", p+1);
}

六：
int main(void)
{
       int n, m;
       int* a;    /* 用于存储“那些人” */
       int i, j, s;

       printf("请输入多少个人：\n");
   scanf("%d",&n);
   printf("请输入是哪个数字的倍数：\n");
   scanf("%d",&m);

   a = (int*)(malloc(sizeof(int) * n));    /* 申请一个数组，以存储“那些人” */
   if (a == NULL)    /* 并非一定分配成功的 */
   {
      printf("空间不足，程序退出。\n");
      return 1;
   }

   for (i = 0; i < n; i++)
   {
      a[i] = i + 1;    /* 填空数组，编号是下标加一，注意C语言中的数组下标从0开始 */
   }
    i = 0;
    j = 0;   //报数
    s = n;   //记录尚未退出的元素的个数
    while(s > 1)
   {
        if(a[i%n] != 0) //如果元素值不为0，则表示其尚未退出
        {
            j++;
            if(j%m == 0) //判断当前报数是否为m的倍数
            {
                printf("第%d号出列\n",a[i%n]);    /* 把这个家伙打印出来 */
                a[i%n] = 0;   //已经退出的元素赋值为0
                s--;    //退出一个元素
            }
        }
        i++;
    }
    for(i=0; i<n; i++)
        if(a[i] != 0)
            printf("最后一个是：%d\n",a[i]);
    free(a);    /* 记得要释放申请的空间 */
    system("pause");
   return 0;
}

七：
typedef struct List
{
    int Number;
    struct List *Next;
}Node,*Link;

Link Create_List(int n) ;   /*建立循环链表*/
void Print_List(Link Head)  ;     /*遍历打印链表*/
void Kick(Link Head, int m, int s);       /*设置函数,将数据逐个踢出队列*/

int main(void)
{
    Link ysf;   /* 用于存储“那些人” */
    int n;        /* “那些人”的总数 */
    int s;        /* 开始的编号 */
    int m;        /* 间隔多少个人出列一个 */

    printf("请输入多少个人：\n");
    scanf("%d",&n);
    ysf = Create_List(n);
    Print_List(ysf);

    printf("请输入开始的序号：\n");
    scanf("%d",&s);
    printf("请输入间隔的人数：\n");
    scanf("%d",&m);

    Kick(ysf,m,s);
    printf ("\n");
   
    system("pause");
    return 0;

}

Link Create_List(int n)    /*建立循环链表*/
{
    Link Head;
    Link New;
    Link Pointer;

    Head=(Link)malloc(sizeof(Node));    /*申请头节点*/
    if( Head == NULL)    /* 并非一定分配成功的 */
    {
        printf("空间不足，程序退出。\n");
        exit(1);
    }
    Head->Number = 1;
    Head->Next = NULL;
    Pointer = Head;
    for (int i=1;i<n;i++)           /*对中点节点进行赋值并连接链表*/
    {
        New=(Link)malloc(sizeof(Node));
        if (New == NULL)    /* 并非一定分配成功的 */
        {
             printf("空间不足，程序退出。\n");
             exit(1);
          }
      New->Number = i+1;
      New->Next = NULL;
      Pointer->Next = New;
      Pointer = New;
    }
    Pointer->Next = Head;

    return Head;
}

void Print_List(Link Head)       /*遍历打印链表*/
{
    Link Pointer;
    Pointer = Head;
    while (Pointer->Next != Head)
    {
        printf ("%d ",Pointer->Number);
        Pointer=Pointer->Next;
    }

    printf ("%d ",Pointer->Number);
    printf ("\n");
}

void Kick(Link Head, int m, int s)       /*设置函数,将数据逐个踢出队列*/
{
    Link NEW_HEAD;     /*被踢出节点的直接前驱*/
    Link PrePointer;     /*被踢出节点的直接前驱*/
    Link Pointer;     /*被踢出队列的节点*/
    int j=1;

    NEW_HEAD = Head;
    while(NEW_HEAD->Number != s)
        NEW_HEAD = NEW_HEAD->Next;
    PrePointer = NEW_HEAD;

    while (1)
    {
        j = 1;  printf ("\nj=%d \n",j);
        while (j++ < m)
            PrePointer = PrePointer->Next;

        Pointer = PrePointer->Next;
        PrePointer->Next = Pointer->Next;    /*前驱与后继相连,将节点踢出*/
        PrePointer = PrePointer->Next;
        printf ("tizou %d ",Pointer->Number);
        free(Pointer);

        if (PrePointer->Next==PrePointer)
            break;
    }

    printf ("shengxia %d",PrePointer->Number);
    free (PrePointer);     /*释放节点*/
}

阅读(3661) | 评论(1)


版权声明：编程爱好者网站为此博客服务提供商，如本文牵涉到版权问题，编程爱好者网站不承担相关责任，如有版权问题请直接与本文作者联系解决。谢谢！

评论

loading...
您需要登录后才能评论，请 登录 或者 注册