“C++”环境下的算法探讨

2010-01-09王民川

科技传播 2010年13期

关键词：二分法指向零点

王民川

郑州广播电视大学，河南郑州 450007

“C++”环境下的算法探讨

王民川

郑州广播电视大学，河南郑州 450007

本文通过一个实例揭示如何将算法原理和程序设计相互结合；如何借助程序开发实践来进一步理解二分法求近似根算法的实质，从而深刻理解算法原理，增加学生成功建构数学概念、解决数学问题的可能性，进而使以学生发展为本的教育理念得以实现。

算法；二分算法；教学； C++

“现代意义上的‘算法’通常指可以用计算机来解决的某一类问题的程序或步骤，这些程序或步骤必须是明确和有效的，而且能够在有限步之内完成”[1]。算法实际上就是解决问题的一种程序性方法，它通常指向某一个或一类问题，而解决的过程是程序性和构造性的。计算机解决问题的过程就是对算法的执行过程，但这个算法必须是计算机能理解的语言描述，而我们采取“C++”这种程序设计语言就是计算机可以理解的语言。

C++是C的一个扩充版本。C是于1978年在贝尔实验室诞生的。开发C的目的是为了创造一种可以在多种平台上使用的简单语言（比汇编和机器代码简单…）。后来在80年代早期C被扩充为C++用于创造一种面向对象的语言。O（bject，对象）O（riented，基于）P（rogramming，编程）是一种用类来构造程序的编程方式。类型标识符用以区分main函数及后继类。OOP在方法上，C++在实现上使编写极为复杂的图形应用环境（例如Windows,Macintosh…）成为可能。

以下我们以一个二分查找法实例探讨如何在C++中应用算法教学：

二分法的概念：一般地，对于函数f(x),如果存在实数c,当x=c是f(c)=0,那么把x=c叫做函数f(x)的零点。解方程即要求f(x)的所有零点。先找到a、b，使f(a)，f(b)异号，说明在区间(a,b)内一定有零点，然后求f[(a+b)/2],现在假设f(a)＜0,f(b)>0,a＜b如果f[(a+b)/2]=0，该点就是零点，如果f[(a+b)/2]＜0，则在区间（(a+b)/2，b)内有零点，按上述方法在求该区间中点的函数值，这样就可以不断接近零点如果f[(a+b)/2]】>0，同上通过每次把f(x)的零点所在小区间收缩一半的方法，使区间的两个端点逐步迫近函数的零点，以求得零点的近似值，这种方法叫做二分法。由于计算过程的具体运算复杂，但每一步的方式相同，所以可通过编写程序来运算。

假如有一组数为3，12，24，36，55，68，75，88要查给定的值24.可设3个变量front，mid，end分别指向数据的上界，中间和下界，mid=（front+end）/2。

1）开始令front=0（指向3），end=7（指向88），则mid=3（指向36）。因为mid>x，故应在前半段中查找。

2）令新的end=mid-1=2，而front=0不变，则新的mid=1。此时x>mid，故确定应在后半段中查找。

3）令新的front=mid+1=2，而end=2不变，则新的mid=2，此时a[mid]=x，查找成功。

如果要查找的数不是数列中的数，例如x=25，当第三次判断时，x>a[mid]，按以上规律，令front=mid+1，即front=3，出现front>end的情况，表示查找不成功。

例：在有序的有N个元素的数组中查找用户输进去的数据x。

算法如下：

1）确定查找范围front=0，end=N-1，计算中项mid（front+end）/2。

2）若a[mid]=x或front>=end，则结束查找；否则，向下继续。

3）若a[mid]＜x,说明待查找的元素值只可能在比中项元素大的范围内，则把mid+1的值赋给front，并重新计算mid，转去执行步骤2；若a[mid]>x，说明待查找的元素值只可能在比中项元素小的范围内，则把mid-1的值赋给end，并重新计算mid，转去执行步骤2。

代码：