这是以前发在"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);     /*释放节点*/}

评论