|
第五单元 排序与查找 第1课时 数组与数组变量  思考与讨论视频 关于数组,我们应该知道的知识: 1.数组是一组顺序存放的变量、数组的下标表示该元素的位置，下标是可计算、可索引的整数。 2.数组作为一种特殊并且很有用的变量，数组的下标表示该元素的位置。 3.数组需要先定义，后使用。数组变量的定义和一般变量的定义类似，在VB中我们采用“Dim 数组名(1 to n) as 数据类型”的形式定义数组，在VB环境中，要求一个数组中存放的数据必须是同一类型的数据。 4.数组名和一般变量命名规则相同。可由字母、数字、下划线组成，且须字母开头，规避保留字符。 5.因为数组下标连续性的特点，经常用循环结构来处理用数组存储的批量数据。 拓展阅读：《斐波那契数列》 斐波那契数列，又被称为黄金分割数列，是指这样一个数列：1、1、2、3、5、8、13、21……，即后一个数字是前两个数字之和。在数学中，该数列直接被以递归的形式定义：f(1)=1，f(2)=1，f(n)=f(n-1)+f(n-2)(n>2,n∈N)。这个数列与大自然中植物的关系非常密切，几乎所有花朵的花瓣都来自于这个数列中的一项数字（如向日葵花盘、菠萝表皮方块形鳞苞形成的两组旋向相反的螺线等），它形成了一种自然规律。更为有趣的是，随着数列项数的增加，前一项与后一项之比越来越逼近黄金分割的数值0.6180339887。也许正是由于此数列的这些特性，在教学实践中，以它为具体案例，可以引起学生的探究兴趣。所以在教学实践中，笔者发现很多一线教师都会用到“斐波那契数列（Fiboncci Sequence）”来作为教学实例，通过求解该数列第n项的问题设计算法。下面以求“斐波那契数列的第20项数值”为例，分别用递归和迭代算法表示。 （一）用递归算法实现 递归算法是反复调用“自身”的过程，因此我们可以先定义一个函数（如f(n)），然后在算法执行中，反复调用这个函数。基于VB语言，可以这样实现： 图1 用递归算法实现求斐波那契数列的第20项数值的程序代码（1） 当然，用递归的方式解决该问题，也可以采用不定义函数，而用数组变量的方式实现： 图2用递归算法实现求斐波那契数列的第20项数值的程序代码（2） 以上两种方式，其实质是一样的，都是根据该数列的数学定义，从第三项开始，对前两项求和的反复使用。 （二）用迭代算法实现 虽然斐波那契数列的数学定义是采用递归的形式，但用迭代算法一样能够解决，解决方案是先定义三个变量（如f1、f2、f3），然后对变量进行更新赋值，同时利用循环控制执行过程。基于VB语言，采用迭代算法解决这个问题可以表示如下： 图3 用迭代算法实现求斐波那契数列的第20项数值的程序代码 当然，针对这个问题，也可以只采用两个变量实现，只需要将“图3”循环体内代码换为“f1 = f1 + f2: f2 = f1 - f2”，同时将输出的内容换为“Str(f1)”。 （三）递归与迭代算法的简单对比 就“求斐波那契数列的第20项数值”问题而言，由以上分析我们可以看到，用递归算法和迭代算法都能实现，但从算法执行效率方面考虑，二者还是存在一定的差别的。 从“图1”解决该问题的描述来说，在程序主语句中，对于n>3 ，每调用一次函数f，其实都会引起两次该函数的调用。因此，如果求解的项数值比较大，调用函数f的总次数按指数增长，如此例中求第20项，函数f被调用次数近百万次，显然这样的一个程序是不太实用的。而“图3”中采用迭代算法实现该问题，就避免了同一值的重复计算问题，循环体内只是执行了54（((20-3)+1)*3）次的赋值运算，显然效率更高。当用计算机解决一个问题时，一般存在多种不同的方法。对于较小的问题，只要管用，方法的不同并没有什么关系。但对于大型问题（或者需要解决大量小型问题的集合），我们就需要考虑算法的效率问题了。 在解决实际问题中，递归算法可以和迭代算法之间转换，但它们的计算机执行效率也并不是都和上例一样：迭代优于递归，而要具体问题具体分析。比如另一个经典算法案例“汉诺塔问题”，其递归算法中有两处递归调用，并且其中一处的调用语句后面还有其它的非递归调用语句，要把这样的问题用迭代的方式实现，相对比较复杂，并且它们并不会明显提高程序的执行效率，反而会使程序“不易读”。 递归和迭代在算法和程序设计中，作为特别有用的工具，可以帮助我们解决一些表面看起来非常复杂的问题。在教学实践中，通过选择合适的实例，并分析设计算法最终实现，可以帮助学生更好的理解其基本思想，培养算法思维。同时在分析中如果对比算法执行效率的问题，其实也是算法不断优化思想的体现，这些都是发展学生计算思维的要义所在。 ——节选自论文《从计算思维的视角辨析算法中的递归与迭代》
|
|
|
来自： 木舟u2497sll0j > 《待分类》
