举个简单的例子，围圈问题的详细算法和程序 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);     /*释放节点*/ }

评论