Page 123 - 高中 信息技术 选择性必修1 数据与数据结构
P. 123
5.2 查找
例4：斐波那契数列（Fibonacci），又称黄金分割数列，指的是由这样一组数组成的
数列：1，1，2，3，5，8，13，21，34，55，89，144，233，…
斐波那契数列的第一项是1，第二项也是1，从第三项开始，每一项的值都等于前两
项之和。在前面例2中，我们用迭代算法实现了对兔子繁殖数量组成的斐波那契数列的求
解。同样，斐波那契数列也可以用递归算法实现求解，其核心代码如下：
int fib(int n) //定义递归函数fib，参数n是指数列的第几项
{
if(n==1||n==2) return 1; //当n=1或n=2时，返回1，结束递归
return fib(n-1)+fib(n-2);
广东教育出版社
//当n>2时，本项的值等于前两项之和，调用函数fib来计算前两项fib(n-1)
//和fib(n-2)
}
交 流
分组交流，在日常学习、生活和工作中，有哪些活动或流程能体现递归的思想？
5.2 查找
在日常生活和学习中，我们经常要进行查找工作，例如从字典中查找汉字、单词，
从电话号码本中查找电话，在图书馆中查找图书，高考查询成绩等。其实，“电话号码
本”“字典”等都可以看作一张表，查找则是在一个含有众多数据元素（或记录）的表中
找出某个特定的数据元素（或记录）。在信息时代，由于信息量巨大，人工查找是非常困
难的，甚至是无法办到的，所以必须依靠计算机才能快速、准确地查找信息。
5.2.1 顺序查找
顺序表是指采用顺序存储的方式存储的集合或线性表。在本章，我们主要探讨一维数
组这种顺序表的顺序查找和二分查找方法。
顺序查找也称为线性查找，它的基本思想是：从顺序表的一端开始，将每个元素的关
键字与给定值k进行比较，如果相同，则表明查找成功，返回该元素的下标；如果在所有
元素都进行了比较后，仍找不到关键字为k的元素，则表明查找失败，返回特定值-1。
在超市中，要实现查询某商品在哪个货架，我们可以用数组存储商品的编号、存放的
货架等信息。程序运行时，输入需查询商品的编号，然后在数组中依次查找编号，就可查
115115
21X2204.indd 115 2019/10/6 17:17:04
