棒棒糖将分给谁

news/2025/3/4 5:19:49/

棒棒糖将分给谁

附上PPT

问题：

​ 有8 个小朋友，但是只有一根棒棒糖，从第一个小朋友开始报数，报到5 的小朋友退出，然后下一个小朋友从1 开始重新报数，报到5的小朋友继续退出，如此下去，最后一个留下的小朋友将获得棒棒糖。你知道小朋友的退出的顺序吗？请利用所学过数据结构，设计算法解决以上问题。

第一种算法思路（循环队列）

​ 采用循环队列的数据结构，并且采取少用一个元素空间来区分队列满还是空，刚开始将八个小朋友依此入队，

然后移动队头指针，移到报数为5的小朋友出队，并且对该元素空间赋值为‘ ’，由于队头指针可能会移到元素空间

为‘ ’，但此时的位置并不是小朋友的位置，所以还需设置循环变量i，每当对头指针移到小朋友的位置时i++,当对头

指针移到‘ ’时，i值不变，直到i值为5时，此时对头指针指的小朋友出队。在移动的过程中，可能会出现两种情况：

第一种对头指针将报数为5的小朋友出队后，还要指向下一个小朋友，此时可能会出现下一个元素位置为‘ ’，这时

还需继续移动，直到下一个元素位置不为‘ ’。第二种队头指针可能会将队尾指针指的小朋友出队，这时队尾指针需

往前移动，移到元素空间不为‘ ’，即小朋友的位置。

1
2
H
rear
空
front
B
A
C
D
E
F
G
1
2
H
rear
B
A
C
D
空1
F
G
空
front
1
2
H
rear
空2
A
C
D
空1
F
G
空
front
1
2
G
rear
空2
A
C
D
空1
F
空3
空
front
1
2
F
rear
空2
A
C
D
空1
空4
空3
空
front
1
2
F
rear
空2
空5
C
D
空1
空4
空3
空
front
1
2
F
rear
空2
空5
C
空6
空1
空4
空3
空
front
1
2
C
rear
空2
空5
空6
空1
空7
空4
空3
空
front

代码：

//棒棒糖将分给谁
//作者：Second to none
//时间：2020年10月21日
#include<stdio.h>
#include<malloc.h>
#define Max_size 9
#define NULL 0
typedef struct
{char children[Max_size];int front, rear;
}SeQueue;
//初始化队列
int init(SeQueue*q)
{if(q==NULL)return 0;q->front = Max_size-1;q->rear = Max_size-1;q->children[q->front] = ' ';return 1;
}
//入队
int in_SeQueue(SeQueue* q, char x)
{if ((q->rear + 1) % Max_size == q->front){printf("队满！");return 0;}else {q->rear = (q->rear + 1) % Max_size;q->children[q->rear]=x;return 1;}
}
//出队
int out_SeQueue(SeQueue*q,char*x)
{*x = q->children[q->front];return 1;
}
//求队列中元素的个数
int length(SeQueue*q)
{int Length=0,i;for (i = 0;i < Max_size;i++)if (q->children[i] != ' ')Length++;return Length;
}
int main()
{SeQueue* q;q = (SeQueue*)malloc(sizeof(SeQueue));char x;char child;init(q);//初始化队列printf("输入小孩的代称：");child = getchar();//输入小朋友的代称:A,B,C,D,E,F,G,Hwhile (child != '\n'){in_SeQueue(q, child);child = getchar();}//开始抢棒棒糖q->front = (q->front + 1) % Max_size;while (length(q)!=1){int i ;for (i = 1;i <5;){if (q->children[(q->front + 1) % Max_size] != ' ')i = i + 1;q->front = (q->front + 1) % Max_size;}out_SeQueue(q,&x);printf("淘汰小孩%c\n", x);//若队头指针指向队尾指针时，这时队尾指针指向的小孩将被淘汰，并将队尾指针向前移动if (q->children[q->front] == q->children[q->rear]){int j = q->front - 1;while (q->children[j] == ' ')j--;q->rear = j;}q->children[q->front] = ' ';q->front = (q->front + 1)%Max_size;while (q->children[q->front] == ' ')q->front = (q->front + 1) % Max_size;}out_SeQueue(q, &x);printf("抢到棒棒糖的小孩是：%c",x);return 0;
}

运行截图：

在这里插入图片描述

算法效率分析：

由于在出队时，我做了如下处理，对某一元素出队后，并在该位置上赋值’ ‘,因此该算法的效率也是不怎么理想，首先定义控制变量i，在寻找报数为5的元素时，队头指针需要判断元素是否为’ ‘，若为’ ‘则i不变，队头指针继续往下移动；若不为’ '，i++，队头指针继续往下移动。该算法的时间复杂度不仅花在寻找报数为5的元素，还花在对元素的值进行判断，因此for循环执行了56次，高于前面算法for循环执行次数。

第二种算法思路（单循环链表）

​ 采用带头结点的尾指针单循环链表，先定义循环整形变量num，由于每个结点只能指向下一个结点，不能指向上一个结点，所以设置循环变量i=1&&i<4，每当i自增1时，已定义好的指针P，指向下一个结点。当i=4时，此时p指向报数为4的小孩结点，接下来分两种情况：第一种，当p->next==tail->next时，即p->next指向头结点，然而需要删除指针p指向头结点的下一个结点，即q=tail->next->next(另外定义指针变量q),然后头结点指向q->next,然后删除此时q所指向的结点，并num–，然后p->next指向头结点的下一个结点。第二种，当p->next!=tail->next时，即p->next不指向头结点。q=p->next，p->next=q->next,删除q指向的结点，并num–，当p->next= =tail->next,然后移动p=tail->next->next；当p->next!=tail->next时，移动p=p->next。直到num= =1时退出循环。
A
B
C
D
E
F
G
H
头结点
tail

代码：

//棒棒糖将分给谁
//作者：Second to none
//时间：2020年10月24日
#include<stdio.h>
#include<malloc.h>
typedef struct CNode
{char child;CNode* next;
}CLinkNode;
//创建链表
CLinkNode* creatList(int*num)
{char ch;CLinkNode* tail;CLinkNode* p;CLinkNode* q;tail = (CLinkNode*)malloc(sizeof(CLinkNode));tail->next = tail;printf("输入小孩代称:");ch = getchar();while (ch != '\n'){p = (CLinkNode*)malloc(sizeof(CLinkNode));p->child = ch;p->next = tail->next;tail->next = p;tail = p;ch = getchar();}tail = tail->next;return tail;
}
//删除结点
CLinkNode* DelLinklist(CLinkNode*tail,int*num)
{CLinkNode* p;CLinkNode* q;int i;p = tail->next;//指向头结点while (*num >1){for (i = 1;i <4;){if (p->next != tail){p = p->next;i++;}else if (p->next == tail){p = p->next->next;i++;}}if (p->next != tail){q = p->next;printf("淘汰%c\n", q->child);p->next = p->next->next;free(q);q = (CLinkNode*)malloc(sizeof(CLinkNode));(*num)--;if (p->next != tail){p = p->next;}else if (p->next == tail)p = tail->next;}//p->next指向尾结点else if (p->next == tail){q = p->next->next;//指向头结点printf("淘汰%c\n", q->child);tail->next = q->next;free(q);q = (CLinkNode*)malloc(sizeof(CLinkNode));(*num)--;p = tail->next;}}return tail;
}
void printlink(CLinkNode* tail)
{CLinkNode* p = tail;printf("获得棒棒糖的小朋友是:%c\n",p->next->child);
}
int main()
{CLinkNode* tail;int num=8;tail = creatList(&num);DelLinklist(tail,&num);printlink(tail);return 0;
}

运行截图：

在这里插入图片描述

算法效率分析：

该算法的效率比以上三种算法要高，主要是删除尾指针所指向的结点，没有其他冗余的结点，因此该算法的for循环执行了39次。

第三种算法思路（顺序表）

​ 采用顺序表的数据结构，L->length设置为8，用while判断L->length= =1？，然后设置变量j控制循环次数为5，在循环控制变量下，利用i=（i+1）%L->Length来自增i，当j=5时，删除顺序表中对应i的数组元素的值。直到L->length==1时，退出while循环，输出顺序表中数组元素的值。

代码:

//棒棒糖将分给谁
//作者：Second to none
//时间：2020年10月24日
#include<stdio.h>
#include<malloc.h>
#define Max_size 8
typedef struct 
{int length;char children[Max_size];
}SqList;
//顺序表的初始化
SqList* creatlist()
{SqList* L;L = (SqList*)malloc(sizeof(SqList));if (L == NULL)return NULL;elsereturn L;L->length = 0;
}
//输入小朋友代称
void InputList(SqList* L)
{int i;L->length = 8;//八个小朋友for (i = 0;i < L->length;i++)scanf_s("%c",&L->children[i],1);
}
//删除
void DelList(SqList*L,int i)
{int j;printf("退出小朋友：%c\n",L->children[i]);for (j = i;j < L->length-1;j++)L->children[j] = L->children[j+1];L->length--;
}
void printList(SqList*L)
{printf("获得棒棒糖的小朋友为：%c",L->children[L->length-1]);
}
int main()
{SqList* L;int j,i=-1;L = creatlist();printf("输出小孩代称：");InputList(L);while (L->length != 1){for (j = 0;j <5;j++)i = (i + 1) % L->length;DelList(L, i);i--;}printList(L);return 0;
}

运行截图：

在这里插入图片描述

算法效率分析：

采用顺序表来解决这个问题效率很低，在整个算法中for循环总共执行了50次，不仅要循环顺序表中的元素，而且还要对报数为5的小朋友进行删除，此时需要移动顺序表中的元素，大大增加了算法的时间复杂度。

第四种算法思路（双向链表）

利用双向链表的特点，已知一个结点，我们可以知道该结点的直接前驱和直接后继，定义计数变量count和控制变量i,每当i=5时，此时指针p所指向的结点为报数为5的小朋友，进行如下操作：p->prior->next = p->next;p->next->prior = p->prior;后，删除该结点。计数变量count最开始赋值为8，每当删除一个结点时，count–，当count==1时结束上述操作。

代码：

//棒棒糖将分给谁
//作者：Second to none
//时间：2020年10月24日
#include<stdio.h>
#include<malloc.h>
typedef struct DNode
{char child;struct DNode* prior, * next;}DLinkNode;
//初始化双向链表
DLinkNode* init()
{DLinkNode* L;L = (DLinkNode*)malloc(sizeof(DNode));L->prior = L;L->next = L;return L;
}
//创建链表
DLinkNode* CreatNode(DLinkNode*L)
{DLinkNode* p;DLinkNode* q;char ch;ch = getchar();q = L;q->child = ch;ch = getchar();while(ch!='\n'){p = (DLinkNode*)malloc(sizeof(DNode));p->child = ch;q->next = p;p->prior = q;q = p;ch = getchar();}q->next = L;L->prior = q;return L;
}
//输出链表
void PrintNode(DLinkNode* L, int count)
{DLinkNode* p;p = L;printf("获得棒棒糖的小朋友为：%c", p->child);
}
//删除链表结点
DLinkNode* DelNode(DLinkNode* L,int *count)
{int i;DLinkNode* p,*q;p = L;while (*count != 1){for (i = 1;i <5;i++){p = p->next;}printf("退出的小朋友为：%c\n", p->child);p->prior->next = p->next;p->next->prior = p->prior;q = p;p = q->next;free(q);q = (DLinkNode*)malloc(sizeof(DNode));(*count)--;}return p;
}
int main()
{DLinkNode* L;int count=8;L = init();printf("输入八个小朋友的代称：");L = CreatNode(L);L = DelNode(L,&count);PrintNode(L,count);return 0;
}

运行截图：

在这里插入图片描述

算法效率分析：

该算法效率最高，因为双向链表中的结点可以找到该结点的直接前驱和直接后继，在进行删除时，直接找到指定的结点，然后进行删除操作，无需判断。该算法的时间复杂度主要花在寻找报数为5的结点上，根据题目要求报数为5的小朋友退出，总共8 个小朋友，需要退出7个小朋友，因此该算法寻找报数为5的结点需要执行35次。
L
A
B
C
D
E
F

第五种算法思路（栈）

定义变量count来计数小朋友的数量，当满足count!=1时，进入while循环。定义控制变量i，每次i=5时，top所指的元素退出，count–,并对该位置赋值为 ’ '。由于top所指的元素可能为 ’ ‘，并不是每次top移向下一个元素，i都会自增。所以每次top移向下一个元素时，都要判断该位置的元素是否为’ ‘，若为’ ‘则i不变，若不为’ ',则i自增。这种处理方式与上一种采用循环队列的算法相似。注：这里top指针往下移采用条件表达式来进行判断，(S->top == 0) ? (S->top = Stack_size - 1) : (S->top–)。

代码：

//作者：Second to none
//时间：2020年10月24日
//棒棒糖将分给谁
#include<stdio.h>
#include<malloc.h>
#define Stack_size 8
typedef struct
{int elem[Stack_size];int top;
}SeqStack;
//初始化栈
void InitStack(SeqStack* S)
{S->top = -1;
}
//进栈
void Push(SeqStack* s, int x)
{if (s->top == Stack_size )printf("栈已满！\n");else s->elem[s->top] = x;
}
//出栈
void Pop(SeqStack* s, char* x)
{if (s->top == -1)printf("栈已空！\n");else*x = s->elem[s->top];
}
//判断栈空
int IsEmpty(SeqStack S)
{if (S.top == -1)return 1;elsereturn 0;
}
void Input(SeqStack* S)
{char child;child = getchar();while (child != '\n'){S->top++;Push(S, child);child = getchar();}
}
void PrintOut(SeqStack*S)
{char child;while (S->top != -1){Pop(S, &child);printf("%-3c",child);}
}
//删除栈中的元素
void DelStack(SeqStack*S,int count)
{char child;int i,j;j = S->top;while (count != 1){for (i = 1;i < 5;){(j == 0) ? (j = Stack_size - 1) : (j--);//printf("j=%d\n", j);if (S->elem[j] != ' ') i++;//printf("S->elem[(S->top == 0) ? (S->top = Stack_size - 1) : (S->top--)]=%c\n", S->elem[(S->top)]);//printf("i=%d\n",i);(S->top == 0) ? (S->top = Stack_size - 1) : (S->top--); }Pop(S, &child);//删除top所指向的元素printf("退出的小朋友为：%c\n",child);count--;Push(S, ' ');//printf("S->top_1=%d\n", S->top);(S->top == 0) ? (S->top = Stack_size - 1) : (S->top--);(j == 0) ? (j = Stack_size - 1) : (j--);while (S->elem[S->top] == ' '){(S->top == 0) ? (S->top = Stack_size - 1) : (S->top--);(j == 0) ? (j = Stack_size - 1) : (j--);}//printf("S->top_2=%d\n", S->top);}
}
int main()
{SeqStack* S;char child;S = (SeqStack*)malloc(sizeof(SeqStack));int count=8;//计数小朋友的数量InitStack(S);printf("输入小朋友的代称：");Input(S);DelStack(S, count);Pop(S, &child);printf("最后获得棒棒糖的小朋友为：%c\n",child);//PrintOut(S);return 0;
}

运行截图：

在这里插入图片描述

算法效率分析：

由于该算法的处理机制与循环队列相似，所以该算法的时间复杂度不仅花在寻找报数为5的元素，还花在对元素的值进行判断。该算法的for循环次数为54次，显然该算法的效率不怎么理想。


http://www.ppmy.cn/news/701779.html

相关文章

Python Turtle绘图[难度2星]：甜美棒棒糖（基础效果 / 加描边优化）

Python Turtle绘图[难度2星]：甜美棒棒糖（基础效果 / 加描边优化）

我喜欢turtle绘图&#xff0c;因为代码一点点的改动&#xff0c;总会带来意想不到的惊喜。 一些让我心动过的案例&#xff0c;分享给大家&#xff0c;也珍藏给自己。 ——Python教学路上的爬行者 案例1&#xff1a;棒棒糖&#xff08;基础效果&#xff09; 难度&#xff1a…
阅读更多...
python+tkinter一步步展示漂亮的棒棒糖和云朵

python+tkinter一步步展示漂亮的棒棒糖和云朵

作为专题的效果&#xff0c;也记录下这些代码&#xff0c;分享给大家&#xff0c;希望大家喜欢。 一、先上个效果图吧 换一个棒棒糖的图&#xff0c;生活甜蜜蜜。 好的&#xff0c;下面慢慢开始介绍整个实现过程。 二、准备图片素材 三、搭个框架&#xff0c;上个云朵图 im…
阅读更多...
跟着iMeta学做图｜ggplot2包绘制棒棒糖图展示变量间的相关性

跟着iMeta学做图｜ggplot2包绘制棒棒糖图展示变量间的相关性

如果你使用本代码&#xff0c;请引用&#xff1a;Changwu Wu. 2022. Pan-cancer analyses reveal molecular and clinical characteristics of cuproptosis regulators. iMeta 1: e68. https://doi.org/10.1002/imt2.68 代码编写及注释&#xff1a;农心生信工作室。 写在前面 …
阅读更多...
python+tkinter+canvas实现天降棒棒糖，生活甜甜蜜蜜

python+tkinter+canvas实现天降棒棒糖，生活甜甜蜜蜜

pythontkintercanvas实现天降棒棒糖&#xff0c;生活甜甜蜜蜜。 一、先看看效果吧。 直接开始介绍了吧。 二、准备资源图片 通过ps或者ppt软件把这个图片抠图干净&#xff0c;就会出来的效果好看些。 三、实现逻辑 &#xff08;一&#xff09;自定义棒棒糖类 class Ball:d…
阅读更多...
R语言绘制棒棒糖图（火柴杆图）

R语言绘制棒棒糖图（火柴杆图）

本博客介绍几种利用R语言绘制棒棒糖图&#xff08;火柴杆图&#xff09;的方法。 2. 使用原生ggplot方法 最容易也是最简单想到的方法是直接使用ggplot2包进行更新&#xff0c;这里需要使用ggplot本身的特性&#xff0c;通过图层叠加的方式&#xff0c;进行最终棒棒糖图的展现…
阅读更多...
Flink运行原理

Flink运行原理

Apache Flink是什么&#xff1f;对于这个问题&#xff0c;Apache软件基金会官方给出了定义&#xff1a;Flink是一种框架和分布式处理引擎&#xff0c;主要用于对无界和有界数据流进行有状态计算。 本文将从以下几个方面来了解flink运行原理&#xff1a; 【Flink运行时四大组件…
阅读更多...
R语言如何绘制棒棒糖图（22）

R语言如何绘制棒棒糖图（22）

1.什么是棒棒糖图&#xff1f; 棒棒糖图&#xff0c;顾名思义&#xff0c;由点棍组成&#xff0c;形似棒棒糖。 棒棒糖图&#xff08;lollipop chart&#xff09;&#xff1a;棒棒糖图传达了与柱形图或者条形图相同的信息&#xff0c;只是将矩形转变成线条&#xff0c;这样可…
阅读更多...
用Python绘制棒棒糖图表

用Python绘制棒棒糖图表

条形图在数据可视化里&#xff0c;是一个经常被使用到的图表。 虽然很好用&#xff0c;也还是存在着缺陷。比如条形图条目太多时&#xff0c;会显得臃肿&#xff0c;不够直观。 棒棒糖图表则是对条形图的改进&#xff0c;以一种小清新的设计&#xff0c;清晰明了表达了我们的数…
阅读更多...
最新文章

Copyright @ 2022~2023