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