问题描述
围绕着山顶有10个圆形排列的洞,狐狸要吃兔子,兔子说:”可以,但必须找到我,我就藏于这10个洞中,你先到1号洞找,第二次隔1个洞(即3号洞)找,第二次隔2个洞(即6号洞)找,以后如此类推,次数不限.”但狐狸从早到晚进进出出了1000次,仍没有找到兔子.问:兔子究竟藏在那个洞里?
问题要求
- 设计一种存储方式用于存储山洞,元素的下标表示山洞的编号,元素的值为1表示狐狸没有进过山洞,为0表示狐狸进过该山洞.
- 为保持程序的通用性,山洞的数目和狐狸进出山洞的次数不一定为题设的10和1000,可由用户从键盘输入.
- 要求编写函数模拟狐狸逮兔子的过程,并输出兔子可能的藏身之处.
注:实验报告中要求说明采用了什么存储结构。
问题分析
这实际上是一个反复查找线性表的过程.
定义一个顺序表,用具有10个元素的顺序表来表示这10个洞.每个元素表示围绕山顶的一个洞,下标为洞的编号.对所有洞设置初始标志为1,然后通过1000次循环,对每次所进之洞修改标志为0,最后输出标志为1的洞,即兔子藏身的洞.
定义了一个单链表,将其转换为循环链表,利用循环链表来解决了这个问题。
代码
#include<bits/stdc++.h> using namespace std; typedef struct LNode { int data; int flag; struct LNode *next; }Lnode, *LinkList; int main() { LinkList L; L = new LNode; L->data = 1; L->flag = 1; L->next = NULL; for (int i = 1; i < 10;i++) { LinkList p; p = new LNode; p->data = 11-i; p->flag = 1; p->next = L->next; L->next = p; if (i == 1){ p->next = L; } } LinkList s; s = new LNode; s = L; for (int i = 0; i < 1000;i++) { s->flag = 0; for (int j = 0; j < i+2;j++) { s = s->next; } } cout << "最终结果:"<< "\n"; for (int i = 0; i < 10;i++){ cout << L->data <<"洞"<< " " << L->flag << "\n"; L = L->next; } }
评论区