《计算思维导论》的算法选择与表现初探

《《计算思维导论》的算法选择与表现初探》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《计算思维导论》的算法选择与表现初探郭元辉西华师范大学实验中心摘要：随着计算机技术及应用的普及与提高，计算思维作为新一轮大学计算机基础教育的前沿课题和内容在理论与实践中讨论、尝试和渐进发展，《计算思维导论》单独开设或融合《大学计算机基础》已逐步在一些学校作为选修课、必修课展开。本文就实际教学中的算法选择与语言表现进行初步探讨并给出基本框架。.jyqkanujan(1887-1920)给出15位精度的公式：表现：1、VB、VC程序设计语言（本文选VB）；2、前导：数据类型、变量、常用函数；3、print命令求解。此一步，解决计算器的所有计算。算法2：数值算法（近似解）的级数计算公式

2、有多钟，1637年Leibniz给出的公式:表现：1、概念：近似解的截断误差[13]。2、前导：条件分支、循环概念及语句。3、难点：有限循环、无限循环（死循环）、空循环的处理。已知循环次数与未知循环次数（条件判断）的程序实例。当级数项符号一正一负交替出现时，用-1乘之的技巧。4、蕴含迭代与递归的形式。算法3：MonteCarlomethod（概率法）、1777年Buffon用投针实验计算了π，这是一种概率的方法。假设在单位正方形区域画上1/4的单位圆，往正方形里投针m（足够多）次，统计掉在圆内的数目n，那么根据概率的定义，针掉在圆内的概率p=n/m，也等于面积之比：由此：π≈4*

3、n/m表现：1、概念：随机数的产生及应用。2、利用VB的随机函数编程，圆内的关系为点（x,y）满足：x2+y2<=1。3、蕴含数学问题的求解，不仅仅依赖计算，也依赖于样本的分布。有的问题，例如成绩排序，本生就是处理和实现分布。问题二：迭代与递归迭代与递归本质上是与一个无穷序列0121,,,,,,nnsssss+??相关的两种计算方式，同一个关系：1()nnsFs+=，若取n=0,1,2,…则为迭代；取n=n,n-1,…,0则为递归。使用递归，由于函数的自身调用，在未得到初值时会占用内存空间。原则上两种方法可以转换，但对具体问题，有的迭代适合，有的递归适合。算法1：N!=N*

4、(N-1)*…2*1分别用迭代与递归求10！。表现：1、与S=1+2+…+n比较，迭代中初值的不同。2、概念：递归中内存的占用。3、N!的值：当N较大时是一个很大的数。由此加深对整形、长整型、双精度等数据类型的认识及处理。算法2：已知：f(x)=5.23?x2,a=2,b=3,f(a)*f(b)<0,用二分法求5.23的平方根，精确到10?6。（迭代进阶）表现：（程序化的二分法思想）1、c=(a+b)/2;2、计算f(c),如果

5、f(c)

6、<10?6那么结束否则下一步；3、如果f(a)*f(c)<0那么b=c否则a=c；4、转1。5、拓展：进一步牛顿迭代法进行计

7、算。将迭代次数两相比较，可以看到牛顿迭代法收敛速度快很多（平方收敛）。算法3：用欧几里得辗转相除法求（12,26）的最大公因子。(递归进阶)表现：1、设函数为gcd(m,n)，内容：2、计算m/n=q+r/n，q为商，r为余；（蕴含大量应用实例）3、如果r=0那么返回n，结束。否则下一步；4、m=n;n=r;递归调用gcd(m,n)。5、拓展：可以引申举例著名的汉罗塔递归，对汉罗塔问题，递归是最好的方法。问题三：整除与求模在《程序设计》的教科书里基本都会见到求水仙花数、数的拆分、求100以内的素数、十进制数转换成二进制数等，它们都属于整除与求模（余数）的问题，多用穷举法。算法1：

8、判断一个三位数X是否水仙花数？表现：1、所谓水仙花数是指一个三位数等于其每位数的立方之和。例：371=33+73+13；2、设x为abc三位，则：a=x100,b=(x-100*a),a=bmod10,b=b10;3、判断是否成立。4、拓展：x是否素数的判断归结为循环处理xmodp,(p=2,3,…,x-1),只要有一个为0便确定不是素数；x的二进制转换则是不断计算整除与求模：x=x2,iq=xmod2；i=0,1,2…n,至x=0结束。将nn1...10qqqq?记作二进制数。问题四：排序排序是计算机处理应用中最常见的工作之一，各国GDP排序，学生成绩排序，字典索引排序等

9、等，对已有数据排列位置根据某一关键字之值重新调整，其方法多样，效率不一，在算法研究中有重要地位。算法1：数组abc={23,41,6,7,12,9,8,30,34,12}元素排降序。表现：1、概念：数组的定义与使用；2、比较法：3、拓展：冒泡法：相邻两个元素比较，与比较法类似，但一轮比较完，如果没有出现一次数据交换，便可结束；插入法：假设前N个数据已经排好序，第n+1个数据逐一和前面的数据比较，放在相应位置，保持顺序一致。此算法涉及若干数据的移位问题。分治法：任选一个数，比之小的