狐狸逮兔子问题

2023-08-23 00:03| 来源: 网络整理| 查看: 265

问题描述：围绕着山顶有10个圆形排列的洞，狐狸要吃兔子，兔子说：“可以，但是必须找到我，我就在这10个洞中，你先找到1号洞口，第二次隔1个洞找（即3号洞），第三次隔2个洞找（即6号洞），以此类推，次数不限。”但狐狸从早到晚进进出出了1000次，仍没有找到兔子。问兔子究竟藏在哪个洞里？数据结构顺序表实现算法分析： 1.首先构造空的顺序表。因为有10个洞，所以可以用具有10个元素的顺序表来表示这10个洞。下标即为洞的编号。 2.构造抓兔子算法。可以先将顺序表中所有元素设置为1，然后通过1000次循环，对每一次查找到的洞修改标志为0，最后输出标志为1的洞即为兔子所藏之处。

参考代码：

#define _CRT_SECURE_NO_WARNINGS 1 #include #include #define OK 1 #define OVERFLOW -2 typedef int status; typedef int ElemType; #define LIST_INIT_SIZE 10 //线性表空间的初始分配量 typedef struct { ElemType *elem; //存储空间基址 int length; //当前长度 int listsize; //当前分配的存储容量 }SqList; //构造线性表L status InitList_Sq(SqList *L) { (*L).elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if (!((*L).elem)) //空间分配失败 return OVERFLOW; (*L).length = 0; //空表长度为0 (*L).listsize = LIST_INIT_SIZE; //初始存储容量 return OK; } //逮兔子函数 status Rabbit(SqList *L) { int i = 0; int current = 0; for (i = 0; i current = (current + i) % LIST_INIT_SIZE; //实现顺序表的循环引用 (*L).elem[current] = 0; //标记进过的洞为0 } printf("\n可能藏的洞："); for (i = 0; i SqList L; InitList_Sq(&L); Rabbit(&L); printf("\n"); system("pause"); }

打印结果：在这里插入图片描述

【本文地址】

公司简介

联系我们