浅谈C语言中的数学文化

1、浅谈c语言中的数学文化学院英才学院学号 6120610306姓名 李策2013.12浅谈c语言中的数学文化摘要：数学是知识的工具，亦是其它知识工具的泉源。所有研究顺序和 度量的科学均和数学有关。当然，数学文化更是体现在学习、生活中 的各个方面。由于阅历与知识储备有限，本文是根据作者学习c语 言的经历以及学习数学竞赛时了解的知识，结合几个个人认为蕴含深 刻数学思想的经典问题，简单的谈谈对数学以及数学文化的理解。c语言；数学文化；优化i. c语言中的数学文化程序设计是一门非常重要的计算机课程，其重要性不仅仅体现在 一般意义上的程序编制，更体现在引导学习者实现问题求解思维方式 的转换培养人们的计算思

2、维能力。从这一点来看，计算机程序 设计与数学有着密不可分的关系。c语言是一种计算机程序设计语言，它既具有高级语言的特点， 又具有汇编语言的特点，是目前应用最广泛的计算机语言之一。而对 于任何一种计算机语言，其本质是将解决实际问题的一种特定的算法 用计算机可以识别的语言进行叙述。而算法就是问题的解决流程，在 一定意义上说，c语言是一种针对计算机的数学语言，其中蕴含的数 学思维就不言而喻了。下面将根据在学习c语言过程中遇到的些问题來讨论c语言中蕴含的数学文化与数学思想。2.数学文化在c语言中的具体体现2.1约瑟夫问题数学在程序优化中有着重要的作用，其中函数迭代和递归便是数 学在程序设计优化中的经典

3、应用。我们以著名的约瑟夫问题为例，讨论递归中蕴含的数学文化。约 瑟夫问题可以简单地叙述为：让n个人围成一圈，从某一个人（不妨 编号为1）开始从1报数，报到m的人出圈，然后从下一个人开始， 再从1报数，报到m者出圈，重复至只剩下最后一个人，求此人的 编号叫首先，我们可以通过编译程序，构建链表将上述过程进行模拟。 建立一个含n个节点的循环链表表示n个人围成圈，节点的数据域存 放n个人的编号指针域存放下一个节点的位置，从第一个节点开始, 找到第m个节点，删除该节点，依次继续下去，直到队列仅剩一个 节点。算法：1定义数据；2.建立单项循环链表，节点的数据域记录编号；3模拟循环报数的过程（通过链表的删除

4、操作实现），由 于链表构成的是环，所以当头尾相连时（由一个节点指 向下一个节点时，指向其本身）表示报数过程完毕；4.输出该节点数据域中的编号即可。虽然运用链表法（或者数组）可以形象直观的将约瑟夫问题展示 岀来，但是也可以想象代码的复杂以及时间复杂度。下面我们用数学方法解决此问题。我们知道，第一个出列的人编号为k = m % n,剩卜'的人组成了 一个新的约瑟夫环(以编号为k+1开始)：k+l, k+2,n-1, n, 1,k-l, 并且从1开始报数。我们近将编号进改变:1,2,，n-k-1, n-k, n-k+1,，n-1,变换后就变成了 ml个人报数的子问题，如果我们知道ml个人报数

5、的子问题的解f(n-l),那么我们将其变换冋去就可 以找到n个人报数问题的解(因为当n>l时，首先被排除掉的人不会是最后出列的人，因此两种情况最后出圈的人位置相同)。利用表2.1-1,归纳递归关系:n人k+1k+2 n-1n1 k-1n-1人12 n-k-1n-kn-k+1 n-1递归关系f(n)=f(n-1 )+k%n(将 k 替换后 f(n)=f(n-1 )+m%n%n)表2.11显然，基线情况f(l)=l，此时我们可以用递归解决约瑟夫问题了。 评价解决某一问题的程序，可靠性与运算效率是至关重要的因索。下面我们从运算效率的角度对两种方法进行比较分析。无论是用 链表实现还是用数组实现都

6、有一个共同点：要模拟整个游戏过程，时 间复杂度高达o(nm),当n, m非常大(例如上百万，上千万)的时候, 几乎是没有办法在短时间内出结果的。对于递归法，每次运行都会调 用下一级函数，相对而言会损耗更多的时间，但是我们可以将递归形 式稍作修改，利用循环结构和所得关系式逐级计算每一个函数值，这 时的时间复杂度仅为0(n)。对于代码复杂程度的比较，见附录。小公倍数通过编程实现：输入两个正整数m和n,输出m和n的最小公 倍数d。思路：从m和n中较人的开始递增，枚举法找到第一个数d, 满足d是m和n的公倍数即可。用例:100 101,大约要循环100x101-101=9999次我们已知辗转相除法是比

7、较高效地求两个止整数m和n的最大 公约数的方法，那么对于求这两个数的最小公倍数是否有类似的高效 方法。如果我们已知最大公约数与最小公倍数之间的等式关系，那么 我们便可以通过最大公约数来间接地求解两个数的最小公倍数。在数论中有这样的关于最大公约数与最小公倍数的简单数学性 质：若m和n的最大公约数和最小公倍数分别为d和d,则有 mxn=dxdf3o事实上，m=dxm, n=dxnp则m】和m互质，所以d= dxniixn!， 即 mxn=dxdo上述性质说明求解最大公约数与最小公倍数没有太大的差别，已 知其中的一个便可以求得另一个。明显的，我们有优化思路：利用辗 转相除法求出最大公约数，然后计算最

8、小公倍数，减少循环次数。2.3素数的判别编程实现：输入正整数m判断n是否为素数。思路：根据素数的定义，枚举法判断是否为素数，对素数求和。 我们可以用2到ml z间的数逐个去除n,若均不可以整除n,则n 为素数。用例：n=10000,需要进行9999次循环。同样的，运用数学方法分析，我们有若d是n的约数，设n/d=d, 则d也为n的约数，dxd=rio如果d和d均 小于 眉,贝0 d><d<n； 如果均 大于眉,则dxd>no即除了 n的平方根外，n的约数成对出 现，且在数轴上分布在n的平方根两侧。经过上述分析，只需用2到 丽+1z间的数判断n是否为素数。当n= 1000

9、0时，只需循环100次 左右。2.4水仙花数水仙花数是指一个n位数（nn3）,它的每个位上的数字的n次 幕之和等于它本身。由于当时对水仙花数的定义不了解，将题目错 误的理解为如下形式。编程实现：输出所有满足它的每个位上的数字的3次幕之和等于 它木身的正整数，不妨称为“伪水仙花数”。思路：只需要从1开始枚举，验证后输出结果即可。但是在进行程序编写的过程中发现，循环体没有终止循环的条 件。因此我们需要确定一个上限n,这个上限满足任何大于n的正整 数均不是“伪水仙花数”。运用数学方法分析：假设n是一个五位数, nloooo,其各个数位上的和sum5x9a3=3645,此吋n>sum,即任 意一

10、个五位数都不是“伪水仙花数”。此时位数每增加一位，n至少 在10000的基础上增加的值最小为90000,而sum至多增加9人3=729, 仍有n>sum,即任何一个位数不小于五位的正整数不是“伪水仙花 数”。若n是一个四位数，sum4x9a3=2916,因此n$2916时，一 定不是“伪水仙花数”。至此，我们可以给出一个不是很严密的上限n=3000o通过上述讨论，我们可以初步体会到数学在程序设计中的应用与 作用。计算机技术的发展极大地促进了各个学科的进步，但是我们必 须注意到数学是所有学科的基础，因此不能够忽视各个学科中的数学 文化和数学思维。仅就c语言而言，数学方法虽然不能形象的将求

11、解问题的过程展示岀来，而且思维量大，但是数学更能够从本质上分 析问题，其解法不仅能够对程序进行优化，也更加具有普适性。当然，由于个人水平有限，掌握的数学知识也只是一些皮毛，分 析的不甚透彻。但是，数学的重要性是无法否认的，而数学文化在学 习、生活中的体现也是可见一斑。参考文献1 苏小红，王宇颖，孙志刚等c语言程序设计.高等教育出版社.2011.4, 1-12 李开友，方廷刚.约瑟夫问题：递推模型与一类新数列.攀枝花大学学报. 14(4), 1997刘诗雄，熊斌.高中竞赛数学教程.武汉大学岀版社.2003.1, 49-504林宣治.水仙花数的计算机解法临沂师范学院学报12(6), 2006附录:

12、链表法、递归法解约瑟夫问题代码1.链表法#include <stdio.h>#include <stdio.h>#include <stdlib.h>#define n 41#define m 3#define start 0stmct linklist int data;struct linklist *link; lnoden;typedef struct linklist link;int main(void)inti;link *p, *head;for (i = 0; i < n; i+) lnodei.data = i + 1; if(i&

13、lt;n-l)lnodei.link=& lnodei+l;elselnodei.link = lnode;head = p = & lnodestart; while(p -> link != p) for(i = l;i<m- l;i+) p = p -> link;printf(m%d commit suicidenf p -> link -> data);p -> link = p -> link -> link; p = p -> link;if(p>link = p)printf(h%d commit su

14、iciden! p -> link -> data);printf(nlink list");return 0;乙递归法include <stdio.h>#define n 41int main()int i,a=l;for(i=2;i<=n;i+)a=(a+3)%i;if(a=o)a=a+i;printf("%d comit suiciden",a);printf("r e c u r s i o rt);return 0;数学以及数学文化的定义1. 数学我认为数学不仅仅是一门研究数量、空间等概念的一门学科，还 是一门为其他学科取得进步而奠定基础的工具学科，更是一种锻炼学 习者思维，提高逻辑推理能力的最有效的方式（让人变聪明的方式）。2. 数学文化由于我对数学很感兴趣，从小就接受各种数学竞赛培训。通过阅 读