【C语言】猴子选大王问题

PTA基础编程题目集 7-28
猴子选大王
题目简介：
一群猴子要选新猴王。新猴王的选择方法是：让N只候选猴子围成一圈，从某位置起顺序编号为1~N号。从第1号开始报数，每轮从1报到3，凡报到3的猴子即退出圈子，接着又从紧邻的下一只猴子开始同样的报数。如此不断循环，最后剩下的一只猴子就选为猴王。请问是原来第几号猴子当选猴王？

输入格式：
输入在一行中给一个正整数N（≤1000）。输出格式：
在一行中输出当选猴王的编号。输入样例：
11
输出样例：
7

题解思路：

第一步：
创建一个结构体：

typedef struct Node {int data;		//数据域int mark;		//标记int mark_end;	//标记结尾位置int mark_start;	//标记开始位置struct Node *next;	//指针域
} st, *pst;		//st等价于struct Node st；  *st等价于struct Node* st;

关于mark：
令没被去掉的猴子的 mark 值为 0 ；被去掉的猴子的 mark 值为 1 ；
关于mark_start：
令第一个结点的 mark_start 为 0 ；其余结点均为 1；
关于mark_end:
令最后一个结点的 mark_end 为 0 ；其余结点均为 1；

第二步：
创建一个循环链表

第三步：
根据题目要求对这个循环链表进行相对应的操作

操作其实也很简单，就是判断该链表内 mark==0 的个数，直到个数为1，跳出循环，然后遍历寻找这个mark为 0 的数据就可以了

需要注意的时，我们要对mark==0 的个数进行更新 ；

思路就是这样，代码如下；

//创建一个链表，用函数对链表进行遍历、插入、删除、排序
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>	//使用 bool 函数需要加这个头文件typedef struct Node {int data;			//数据域int mark;		//标记int mark_end;int mark_start;struct Node *next;	//指针域
} st, *pst;		//st等价于struct Node st；  *st等价于struct Node* st;pst creat_list(void) {	//创建链表int i;int len;pst end;pst New;pst pHead;pHead = (pst)malloc(sizeof(st));pHead->data = 1;pHead->mark_start = 0;		//初始位置标记为0pHead->mark_end = 1;		//末尾位置标记为1pHead->mark = 0;//pHead->next = NULL;		//头表内的指针指向为空end = pHead;			//因为此时只有一个表，所以尾指针和头指针指向相同的内容printf("请输入节点的个数：");scanf("%d", &len);/*利用for循环来存储数据*/for (i = 2; i <= len; i++) {New = (pst)malloc(sizeof(st));	//给新节点分配内存//printf("第 %d 个节点的值为:", i + 1);//scanf("%d", &new->data);New->data = i ;New->mark = 0;New->mark_start = 1;		//中间的初始位置标记为1；New->mark_end = 1;//New->next  = NULL;end->next = New;end = New;}end->mark_end = 0;//结尾的标志为0end->next = pHead;			//创建循环链表return pHead;
}int length_list(pst pHead) {	//通过计算链表mark_end=0 的位置,来计算该链表的长度		（这一部分的代码可以不看）int len = 0;	//长度pst p = pHead ;while (p->mark_end != 0) {len++;p = p->next;}if (p->mark_end == 0) {len++;}return len;
}int update_length(pst head) {	//更新当前链表的长度int len = 0;pst p = head;while (p->mark_end != 0) {	//标记不为结尾 if (p->mark_end == 0) {if (p->mark = 0) {len++;}} else {if (p->mark == 0) {len++;}p = p->next;}}return len;
}void delete_list(pst p) {	//删除（每3次去掉一个猴子）int i;pst q = p;pst temp = NULL;int len;pst r = NULL;while (update_length(p) != 1) {		//长度不为1for (i = 1; i <= 3; i++) {		//通过for循环来实现定点标记的功能if (update_length(p) == 1) {break;} else {if (i == 3) {		//3时更改一个1//printf("现在将要更换的数字%d \n", q->data);//len = update_length(p);//printf("当前链表的 长度 %d \n", len);q->mark = 1;}q = q->next;while (q->mark == 1 ) {//printf("\n当前标记为1的 %d ", q->data);q = q->next;//printf("下一个数字 %d \n", q->data);if (q->mark == 0) {break;}}}}}
}void search(pst p) {		//搜寻	（最后只需要搜寻mark=0的位置即可）	pst q = p ;while (q->mark_end != 0) {if (q->mark == 0) {printf("%d", q->data);break;} else {q = q->next;}if (q->mark_end == 0) {if (q->mark == 0) {printf("%d", q->data);} else {//		printf("error");}}}
}int main(void) {pst ptr = creat_list();//show_list(ptr);int len = length_list(ptr);if(len==1){printf("%d",ptr->data);}else{delete_list(ptr);search(ptr);}
}//printf("长度 %d", len);

评测：