2006年第2期
淄博师专学报
Jo urnal of Zibo N or mal Colleg e
总第4期
计算机算法中的数学方法研究
崔守梅1 郝 玲2
(1. 淄博师范高等专科学校数理科学系, 山东淄博255100; 2. 淄博师范高等专科学校附属中学, 山东淄博255100)
计算机算法是程序设计的核心部分, 数学方法是计算学科中最根本的研究方法。通过从计算机算法思想、摘要:
设计、分析三个方面与数学方法整合的论述, 不难看出数学理论对计算机解决问题具有重要的作用。
关键词:算法; 数学方法; 整合中图分类号:T P301. 6
文献标识码:A
文章编号:(2006) 02-0064-03
A bstract :Alg orithm is the key to computer prog ram design and m athematics m ethod is the mo st basically research method of num erical analy sis . This ar ticle mainly researches the combination of al -g orithm ideo logy , design and analysis of mathem atics m ethods . Examples pro ve the sig nificance of
Mathem atics me thod in reso lving the problem w ith com puter algo rithm s .
Key words :algo rithm s ; mathematics methods ; combination 计算机最原始的功能就是数字计算, 算法对学生来说并不陌生。小学的四则混合运算所遵循的先乘除、后加减的规则, 括号优先的处理规则, 都是学生最初接触到的算法实例。中学数学课程中的方程组解法、数列求和、质数判定、最大公约数和最小公倍数求法、定积分求值等, 都涉及到算法。算法(Algorithm ) 是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说, 就是计算机解题的过程。在这个过程中, 无论是形成解题思路还是编写程序, 都是在实施某种算法。一个算法应该具有五个重要的特征:有穷性、确切性、输入、输出、可行性。在计算机算法中经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等。
数学课程中很多问题都可以用程序设计的思维方法来解决。数学方法是指解决数学问题的途
收稿日期:200604
19
径和步骤, 它是计算学科中最根本的研究方法。
理论上凡能被计算机处理的问题均可以转换为一个数学问题。反之, 凡能以离散数学为代表的构造性数学方法描述的问题, 当该问题所涉及的论域为有穷或虽为无穷但存在有穷表示时, 这个问题也一定能用计算机来处理。
利用计算机解决科学计算等一系列问题, 应将实际问题转换为程序。这需要经过一个对问题抽象的过程, 建立起完善的数学模型。只有这样, 才能建立一个设计良好的程序。因此, 探讨数学方法对用计算机解决问题具有重要的作用。
一、计算机算法思想中整合数学方法数学方法是抽象地、模型化地分析问题, 比如分析法、综合法、归纳法、类比法、特殊法、数形结
作者简介:崔守梅(1968, 女, 山东桓台人, 硕士, 淄博师范高等专科学校数理科学系副教授, 主要从事数学与计算机教育研究。郝玲, 女, 硕士, 淄博师范高等专科学校附属中学教师。
合法等, 在演算能力和空间想象能力培养方面对学生有较高要求。近代数学的发展让数学实用性的特点更突出, 教改后的基础教育阶段的数学课程中也不同程度地加入了概率统计、逻辑推理等比较简单的现代数学思想。用数学思想和方法统率具体知识、具体问题的解决, 可以更好地培养和发展学生的思维方法和能力。学生掌握计算机算法的思想, 也是掌握一种方法。故在进行信息技术与数学教育整合过程中, 要认识到计算机算法与数学思维方法整合的重要性, 重视对数学思维与计算机算法的辨析, 找准数学思维与计算机算法的结合点。让两种思维方式、方法能够有机整合, 然后选择合适的软件, 制定合理的方案, 通过技术让思维发挥出更好的作用, 有效地促进整合的开展。
这里仅从三个方面来分析说明计算机算法思想中与数学方法的整合。
(一) 循环的思想
人们最怕机械重复, 因为重复枯燥乏味。而计算机则擅长重复。这种重复体现到程序中就是循环。不难想象, 如果没有循环, 计算机还能干什么! 计算机程序中的几个循环问题, 如二分法、数列求和、判定素数、辗转相除法、秦九韶算法等, 都包含了典型的数学方法。只是用手工计算时会因其过于繁琐而弃之不用。下列是用辗转相除法求两个正整数m 和n 的最大公约数的程序:
pro gram ex1;
var m , n , a , b , r :integer ; begin w rite (' Input m , n :' ) ; readln (m , n ) ;
a :=m ; b :=n ; r :=a mod b ; {求m /n 的余数r } w hile r 0do
beg in
a :=b ; b :=r ; {将n 的值放在m 中, 将r 的值放在n 中}
r :=a mod b ; end ;
w riteln (' The g reatest co mmo n divide is :' , b :8) ;
end .
(二) 递推的思想
10
怎么计算
∑i ! ? 这要设置一个变量S 记录
i =1
和, 还要设置一个变量n 记录项数。阶乘怎么办?
每一项都单独计算显然太麻烦。注意到每一项Tn 与前一项Tn -1的关系是Tn =n ×Tn -1。因此从第二项开始, 每一项都可以由前一项乘以n 得到。这就是递推。而这正是数学中的数列。程序中要实现递推, 只要用到n =n +1, S =S +T , T =T ＊n 等几个简单的语句。递推与数列两个概念, 使计算机算法与数学方法有机融合。
(三) 归纳的思想
用数学归纳法证明循环不变式(LOOP IN -VA RIANT ) , 并验证程序的功能(COM PU TES ) :
S UBROU TIN E COM P (X , Y ; Z ) (1) Z →X (2) W →Y
(3) W H ILE (W >0) a . Z →Z +Y b . W →W -1(4) RET URN
EN D OF SUBROU TINE COMP
COM PUTES :Z =X +Y LOOP INVARIAN T (Y ×W ) +Z =X +Y 2证明:令P (n ) 是谓词(Y ×W n ) +Z n =X +Y 2, n0=0。由归纳法证明, n ≥0P (n ) 。当n =0时, (Y ×W 0) +Z 0=X +Y 2, 由初值W 0=Y , Z 0=X , 显然为真。设k ≥0, P (k ) 为真, 即k ≥0(Y ×W k ) +Z k =X +Y 2。则经过一次循环后, Z k +1=Z k +Y , W k +1=W k -1。则
(Y ×W k +1) +Z k +1=(Y ×(W k -1) ) +(Z k
+Y ) =(Y ×W k ) +Z k =X +Y
这就是P (k +1) 为真。由上述两步, 结论得证。
当循环结束时, W n =0, 由(Y ×W n ) +Z n =X +Y 2, 则Z n =X +Y 2。
仅此三例可看到, 计算机算法思想与数学思维有较多的相同点。计算机算法是更加泛化了的数学方法。
二、计算机算法设计中的数学方法
程序设计中可采用多种数学方法, 恰如其分的数学方法可以大大减少程序运行的时间和所需空间, 起到优化程序的作用。来看一个计算定积
22
分的例子。
计算定积分:
I n =e
家, 将大量的时间花费在公式的计算与证明上会导致整个项目进度缓慢、成本过高。因此, 在算法设计中, 往往采用能近似表达性能的方法来展示某个算法的性能指标。例如, 计算机对n 和n +2n 的响应速度, 当n 比较大的时候几乎一样没什么区别, 便可直接认为后者算法的复杂度为n 2。在分析算法时, 隐藏细节的数学表示法可以简化算法复杂度的许多细节, 提取主要成分, 这也就是某些领域广泛使用的主成分分析思想。
基于算法复杂度简化表达的思想基础上, 通常会对算法进行最坏情况分析和平均情况分析。对于给定的算法, 如能保证最坏情况下的性能依然不错固然很好, 但是在某些情况下, 程序的最坏情况算法的运行时间和实际情况的运行时间相差很大。在实际应用中几乎不会碰到最坏情况下的输入, 此时可不进行最坏情况分析, 特别是分析最坏情况算法会花费大量精力的时候。利用数学方法的算法的平均情况分析, 可估计程序的性能, 作为算法分析的基本指标之一, 对于经典算法和反映出来的时间差几乎不会产生感觉的算法, 就没有必要去改进。例如程序进行1000次循环花费0. 1秒, 改进后为0. 01秒, 在实际应用中通常也只需要几千次循环, 此时就没有必要去研究了, 只要能正确完成任务即可。
数学方法在计算机算法中的合理运用, 可给编程带来很大方便, 现在越来越多的信息学竞赛题都用到数学推导。今后的计算机要向更加智能化的方向发展, 其出路仍然是数学的算法和数学的机械化, 对算法的研究日益成为数学教育的核心问题。
参考文献:
[1]董荣胜, 古天龙. 计算机科学与技术方法论[M ]. 人民
邮电出版社, 2002.
[2]曾范红. 注重数学思维与计算机算法的辨析[J ]. 中国
电脑教育报, 2005, (13) .
[3]王家廞. 离散数学结构[M ]. 北京:清华大学出版社,
2004.
[4]施吉林, 刘淑珍, 陈桂芝. 计算机数值方法[M ]. 北京:
高等教育出版社, 1999.
[5]李玉钊. 由二次方程的求根公式谈中学数学中算法的
稳定性[EB /O L ]. 中学学科网, 2005,(7) .
2
2
1
n x
x e d x i =0, 1, 2, L , 70
解:可有递推公式:I n =1-nI n -1
如果先计算I 0, 然后再计算I 1, I 2, …,I 7
假设计算出的近似值为I 0＊, 误差为E (I 0＊) =δ则I 1的近似值I 1＊的误差为E (I 1＊) =δ则I 2的近似值I 2＊的误差为E (I 2＊) =2! δ
则I 3的近似值I 3＊的误差为E (I 3＊) =3! δ……
则I 7的近似值I 7＊的误差为E (I 7＊) =7! δ=5040δ
至此, 误差放大了5千倍!
但如果利用递推公式:I n -1=(1-I n ) /n 先计算I 7, I 0的误差只有I 7的误差的5千分之一!
两者方法只是计算的顺序不同, 得出的结果相去甚远。无疑, 第二种方法具有非常明显的优点。正是这一变换计算次序, 却解决了此类数值计算的“稳定性”问题, 使之成为一个好算法。
为解决某个数值问题, 需要选择或设计一个算法。当现有的算法不能满足解题的需要, 就要设计一个新算法或改进现有算法。算法要有正确的理论基础、可行性、稳定性, 即计算结果误差对于初始数据的微小变动具有稳定性, 后者的微小变动不至于使前者产生极大误差而失真。为能保证算法稳定性, 可采用数学方法的推理和论证。
三、计算机算法分析中的数学方法
算法分析的任务是对设计出的每一个具体的算法, 讨论时间复杂度和空间复杂度, 以探讨某种具体算法适用于哪类问题, 或某类问题宜采用哪种算法。
通常我们可以利用实验对比分析、数学方法来分析算法。实验对比分析很简单, 两个算法相互比较。它们都能解决同一问题, 在相同环境下, 哪个算法的速度快就认为这个算法性能好。数学方法能将算法分析得更为细致, 能在严密的逻辑推理基础上判断算法的优劣。但在完成实际项目过程中, 很多时候都不能去做这种严密的论证与推断。因为不是在完成一道数学难题, 也不是数学领域的专(责任编辑:林美玉)
2006年第2期
淄博师专学报
Jo urnal of Zibo N or mal Colleg e
总第4期
计算机算法中的数学方法研究
崔守梅1 郝 玲2
(1. 淄博师范高等专科学校数理科学系, 山东淄博255100; 2. 淄博师范高等专科学校附属中学, 山东淄博255100)
计算机算法是程序设计的核心部分, 数学方法是计算学科中最根本的研究方法。通过从计算机算法思想、摘要:
设计、分析三个方面与数学方法整合的论述, 不难看出数学理论对计算机解决问题具有重要的作用。
关键词:算法; 数学方法; 整合中图分类号:T P301. 6
文献标识码:A
文章编号:(2006) 02-0064-03
A bstract :Alg orithm is the key to computer prog ram design and m athematics m ethod is the mo st basically research method of num erical analy sis . This ar ticle mainly researches the combination of al -g orithm ideo logy , design and analysis of mathem atics m ethods . Examples pro ve the sig nificance of
Mathem atics me thod in reso lving the problem w ith com puter algo rithm s .
Key words :algo rithm s ; mathematics methods ; combination 计算机最原始的功能就是数字计算, 算法对学生来说并不陌生。小学的四则混合运算所遵循的先乘除、后加减的规则, 括号优先的处理规则, 都是学生最初接触到的算法实例。中学数学课程中的方程组解法、数列求和、质数判定、最大公约数和最小公倍数求法、定积分求值等, 都涉及到算法。算法(Algorithm ) 是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说, 就是计算机解题的过程。在这个过程中, 无论是形成解题思路还是编写程序, 都是在实施某种算法。一个算法应该具有五个重要的特征:有穷性、确切性、输入、输出、可行性。在计算机算法中经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等。
数学课程中很多问题都可以用程序设计的思维方法来解决。数学方法是指解决数学问题的途
收稿日期:200604
19
径和步骤, 它是计算学科中最根本的研究方法。
理论上凡能被计算机处理的问题均可以转换为一个数学问题。反之, 凡能以离散数学为代表的构造性数学方法描述的问题, 当该问题所涉及的论域为有穷或虽为无穷但存在有穷表示时, 这个问题也一定能用计算机来处理。
利用计算机解决科学计算等一系列问题, 应将实际问题转换为程序。这需要经过一个对问题抽象的过程, 建立起完善的数学模型。只有这样, 才能建立一个设计良好的程序。因此, 探讨数学方法对用计算机解决问题具有重要的作用。
一、计算机算法思想中整合数学方法数学方法是抽象地、模型化地分析问题, 比如分析法、综合法、归纳法、类比法、特殊法、数形结
作者简介:崔守梅(1968, 女, 山东桓台人, 硕士, 淄博师范高等专科学校数理科学系副教授, 主要从事数学与计算机教育研究。郝玲, 女, 硕士, 淄博师范高等专科学校附属中学教师。
合法等, 在演算能力和空间想象能力培养方面对学生有较高要求。近代数学的发展让数学实用性的特点更突出, 教改后的基础教育阶段的数学课程中也不同程度地加入了概率统计、逻辑推理等比较简单的现代数学思想。用数学思想和方法统率具体知识、具体问题的解决, 可以更好地培养和发展学生的思维方法和能力。学生掌握计算机算法的思想, 也是掌握一种方法。故在进行信息技术与数学教育整合过程中, 要认识到计算机算法与数学思维方法整合的重要性, 重视对数学思维与计算机算法的辨析, 找准数学思维与计算机算法的结合点。让两种思维方式、方法能够有机整合, 然后选择合适的软件, 制定合理的方案, 通过技术让思维发挥出更好的作用, 有效地促进整合的开展。
这里仅从三个方面来分析说明计算机算法思想中与数学方法的整合。
(一) 循环的思想
人们最怕机械重复, 因为重复枯燥乏味。而计算机则擅长重复。这种重复体现到程序中就是循环。不难想象, 如果没有循环, 计算机还能干什么! 计算机程序中的几个循环问题, 如二分法、数列求和、判定素数、辗转相除法、秦九韶算法等, 都包含了典型的数学方法。只是用手工计算时会因其过于繁琐而弃之不用。下列是用辗转相除法求两个正整数m 和n 的最大公约数的程序:
pro gram ex1;
var m , n , a , b , r :integer ; begin w rite (' Input m , n :' ) ; readln (m , n ) ;
a :=m ; b :=n ; r :=a mod b ; {求m /n 的余数r } w hile r 0do
beg in
a :=b ; b :=r ; {将n 的值放在m 中, 将r 的值放在n 中}
r :=a mod b ; end ;
w riteln (' The g reatest co mmo n divide is :' , b :8) ;
end .
(二) 递推的思想
10
怎么计算
∑i ! ? 这要设置一个变量S 记录
i =1
和, 还要设置一个变量n 记录项数。阶乘怎么办?
每一项都单独计算显然太麻烦。注意到每一项Tn 与前一项Tn -1的关系是Tn =n ×Tn -1。因此从第二项开始, 每一项都可以由前一项乘以n 得到。这就是递推。而这正是数学中的数列。程序中要实现递推, 只要用到n =n +1, S =S +T , T =T ＊n 等几个简单的语句。递推与数列两个概念, 使计算机算法与数学方法有机融合。
(三) 归纳的思想
用数学归纳法证明循环不变式(LOOP IN -VA RIANT ) , 并验证程序的功能(COM PU TES ) :
S UBROU TIN E COM P (X , Y ; Z ) (1) Z →X (2) W →Y
(3) W H ILE (W >0) a . Z →Z +Y b . W →W -1(4) RET URN
EN D OF SUBROU TINE COMP
COM PUTES :Z =X +Y LOOP INVARIAN T (Y ×W ) +Z =X +Y 2证明:令P (n ) 是谓词(Y ×W n ) +Z n =X +Y 2, n0=0。由归纳法证明, n ≥0P (n ) 。当n =0时, (Y ×W 0) +Z 0=X +Y 2, 由初值W 0=Y , Z 0=X , 显然为真。设k ≥0, P (k ) 为真, 即k ≥0(Y ×W k ) +Z k =X +Y 2。则经过一次循环后, Z k +1=Z k +Y , W k +1=W k -1。则
(Y ×W k +1) +Z k +1=(Y ×(W k -1) ) +(Z k
+Y ) =(Y ×W k ) +Z k =X +Y
这就是P (k +1) 为真。由上述两步, 结论得证。
当循环结束时, W n =0, 由(Y ×W n ) +Z n =X +Y 2, 则Z n =X +Y 2。
仅此三例可看到, 计算机算法思想与数学思维有较多的相同点。计算机算法是更加泛化了的数学方法。
二、计算机算法设计中的数学方法
程序设计中可采用多种数学方法, 恰如其分的数学方法可以大大减少程序运行的时间和所需空间, 起到优化程序的作用。来看一个计算定积
22
分的例子。
计算定积分:
I n =e
家, 将大量的时间花费在公式的计算与证明上会导致整个项目进度缓慢、成本过高。因此, 在算法设计中, 往往采用能近似表达性能的方法来展示某个算法的性能指标。例如, 计算机对n 和n +2n 的响应速度, 当n 比较大的时候几乎一样没什么区别, 便可直接认为后者算法的复杂度为n 2。在分析算法时, 隐藏细节的数学表示法可以简化算法复杂度的许多细节, 提取主要成分, 这也就是某些领域广泛使用的主成分分析思想。
基于算法复杂度简化表达的思想基础上, 通常会对算法进行最坏情况分析和平均情况分析。对于给定的算法, 如能保证最坏情况下的性能依然不错固然很好, 但是在某些情况下, 程序的最坏情况算法的运行时间和实际情况的运行时间相差很大。在实际应用中几乎不会碰到最坏情况下的输入, 此时可不进行最坏情况分析, 特别是分析最坏情况算法会花费大量精力的时候。利用数学方法的算法的平均情况分析, 可估计程序的性能, 作为算法分析的基本指标之一, 对于经典算法和反映出来的时间差几乎不会产生感觉的算法, 就没有必要去改进。例如程序进行1000次循环花费0. 1秒, 改进后为0. 01秒, 在实际应用中通常也只需要几千次循环, 此时就没有必要去研究了, 只要能正确完成任务即可。
数学方法在计算机算法中的合理运用, 可给编程带来很大方便, 现在越来越多的信息学竞赛题都用到数学推导。今后的计算机要向更加智能化的方向发展, 其出路仍然是数学的算法和数学的机械化, 对算法的研究日益成为数学教育的核心问题。
参考文献:
[1]董荣胜, 古天龙. 计算机科学与技术方法论[M ]. 人民
邮电出版社, 2002.
[2]曾范红. 注重数学思维与计算机算法的辨析[J ]. 中国
电脑教育报, 2005, (13) .
[3]王家廞. 离散数学结构[M ]. 北京:清华大学出版社,
2004.
[4]施吉林, 刘淑珍, 陈桂芝. 计算机数值方法[M ]. 北京:
高等教育出版社, 1999.
[5]李玉钊. 由二次方程的求根公式谈中学数学中算法的
稳定性[EB /O L ]. 中学学科网, 2005,(7) .
2
2
1
n x
x e d x i =0, 1, 2, L , 70
解:可有递推公式:I n =1-nI n -1
如果先计算I 0, 然后再计算I 1, I 2, …,I 7
假设计算出的近似值为I 0＊, 误差为E (I 0＊) =δ则I 1的近似值I 1＊的误差为E (I 1＊) =δ则I 2的近似值I 2＊的误差为E (I 2＊) =2! δ
则I 3的近似值I 3＊的误差为E (I 3＊) =3! δ……
则I 7的近似值I 7＊的误差为E (I 7＊) =7! δ=5040δ
至此, 误差放大了5千倍!
但如果利用递推公式:I n -1=(1-I n ) /n 先计算I 7, I 0的误差只有I 7的误差的5千分之一!
两者方法只是计算的顺序不同, 得出的结果相去甚远。无疑, 第二种方法具有非常明显的优点。正是这一变换计算次序, 却解决了此类数值计算的“稳定性”问题, 使之成为一个好算法。
为解决某个数值问题, 需要选择或设计一个算法。当现有的算法不能满足解题的需要, 就要设计一个新算法或改进现有算法。算法要有正确的理论基础、可行性、稳定性, 即计算结果误差对于初始数据的微小变动具有稳定性, 后者的微小变动不至于使前者产生极大误差而失真。为能保证算法稳定性, 可采用数学方法的推理和论证。
三、计算机算法分析中的数学方法
算法分析的任务是对设计出的每一个具体的算法, 讨论时间复杂度和空间复杂度, 以探讨某种具体算法适用于哪类问题, 或某类问题宜采用哪种算法。
通常我们可以利用实验对比分析、数学方法来分析算法。实验对比分析很简单, 两个算法相互比较。它们都能解决同一问题, 在相同环境下, 哪个算法的速度快就认为这个算法性能好。数学方法能将算法分析得更为细致, 能在严密的逻辑推理基础上判断算法的优劣。但在完成实际项目过程中, 很多时候都不能去做这种严密的论证与推断。因为不是在完成一道数学难题, 也不是数学领域的专(责任编辑:林美玉)