C语言中常见的几种算法浅析

孟小丁 白春霞

摘要：C语言是一门结构化的程序设计语言，在解决实际问题时，除了掌握扎实的基本语法知识，更重要的是要学习如何编写程序。本文针对C语言程序设计课程实践教学中存在的问题，从算法设计的角度，对常用的递归算法，排序算法，迭代法，“打擂台”法，辗转相除法等进行描述和分析。设计程序不仅保证算法的正确性，还要考虑算法的质量。所以如何编写高效且正确的程序是至关重要的。

关键词：C语言;算法;程序设计

中图分类号：G642        文献标识码：A        文章编号：1009-3044（2018）34-0215-02

著名计算机科学家Wirth提出“算法+数据结构=程序”。这一公式对于结构化设计语言是适用的[1]。算法是解决“做什么”和“怎么做”的问题，数据结构是加工对象。所以不了解算法就谈不上程序设计。随着教学内容的增加，程序设计的难度随之增大，对特定问题设计相应的算法尤为重要。利用C语言的知识在解决实际问题时，除了考虑算法和数据结构外，还应采用结构化程序设计的方法进行程序设计。

C语言程序设计作为大学生的一门基础必修课程，对提升大学生计算机编程能力至关重要，也是后续专业课程学习的先修课程。在C语言教学过程中，学生对程序设计往往显得力不从心，特别是在程序设计实验课上，对于一道程序难度不大的编程题，部分学生却不知道如何下手去做。在教学过程中，于清[2]建议以算法优先并结合案例教学的模式开展C语言的教学。屈婉玲[3]对算法课程的教学改革进行的总结。其他学者对C语言设计的递归算法[4，5]、排序算法[6]等分别进行了研究。

结合个人的实际教学情况，本文对常见的几种算法进行分析。

1 算法与分析

该课程教学中，涉及的典型算法有递归算法，排序算法，迭代法，“打擂台算法”，辗转相除法等。

1.1 递归算法

递归的概念是，在调用一个函数的过程中，直接或间接调用该函数本身。递归算法的执行过程分为回溯和递推两个阶段[1]。在第一个回溯阶段，把较复杂的问题求解到比原问题简单的一些问题。这个阶段，必须要有结束递归的条件。在第二个递推的阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂的解。

递归调用方式有直接递归调用和间接递归调用。常见应用于求解斐波那契数列[7]、汉诺塔问题[8，9]、树的遍历[10，11]、求阶乘（见示例1）等。

递归一般可以代替循环语句使用，虽然程序结构优美，但执行效率较低，耗费计算机内存资源，难以阅读和维护[12]。当效率处在第一位的时候，还须谨慎使用递归。

1.2 排序算法

排序方法按照排序的规律可分为“升序”和“降序”。排序的方法[13-15]有很多，如希尔排序、堆排序、快速排序、冒泡排序、选择法排序等。在C语言课程教学中，主要介绍的是冒泡法排序和简单选择法排序两种。

2 趣味性案例及求解算法

在学习过程中，常介绍一些趣味性的程序設计题目，例如猴子吃桃子、求解杨辉三角、n阶魔方阵的问题等。这些题目对提高学生的学习兴趣也起到了至关重要的作用。

还有一些实际应用题目也包含了相应的算法思想，比如：穷举法求解“百钱买百鸡”问题，回溯法求解“n皇后”问题等，KMP算法求解“字符串”匹配问题等。

3 结论与展望

上述主要介绍和分析了学生学习C语言过程中几种常用的算法，并给出了具体实例。另外简单介绍了C语言中的一些趣味性实例对应的求解算法。为了有效地解决实际问题，不仅需要保证算法的正确性，还要考虑算法的质量等要素，所以在编写程序的过程中，逐步教会或引导学生设计一个正确且有效的算法是至关重要的。

参考文献：

[1]谭浩强.C程序设计（第四版）[M].清华大学出版社.2010.

[2]于清，吐尔根·依布拉音，等.算法为先的C语言教学模式探讨[J].计算机教育，2009（20）：106-108+96.

[3]屈婉玲，王捍贫，段莉华.面向软件工程学科的算法课程建设[J].中国大学教学，2012（12）：55-57.

[4]任伟，任正云.C语言中递归调用的算法研究[J].襄阳职业技术学院学报，2014（1303）：27-30+34.

[5]李伟.浅析C语言递归算法[J].电脑知识与技术，2012（830）：7229-7235.

[6]闫鑫，王琴竹.循序渐进学习C语言选择排序算法[J].现代计算机（专业版），2018（14）：53-56.

[7]孙义欣，宋大伟.斐波那契数列问题的C语言教学实施探讨[J].电脑编程技巧与维护，2012（16）：151-152+154.

[8]白会波，高瑞平.汉诺塔问题的算法分析及C语言演示程序的实现[J].电脑知识与技术，2010（609）：2130-2131.

[9]肖桂云，袁亚丽.用C语言解决汉诺塔问题的方法及过程分析[J].河北北方学院学报（自然科学版），2006（03）：71-73.

[10]王敏，赵晓雷.基于遍历搜索二叉树中最长路径的算法研究[J].现代电子技术，2010（3308）：54-55+58.

[11]龚佳，袁赟，刘远军.一种二叉树非递归遍历算法的C语言实现[J].电脑知识与技术，2014（1001）：223-225.

[12]Stenphen Prata.C Primer Plus（第五版）中文版[M].人民邮电出版社.2005.

[13]宋美英.基于C语言的冒泡排序算法探讨[J].现代计算机（专业版），2011（29）：48-49+55.

[14]王敏.改进的双向选择排序算法[J].信息技术，2010（3409）：21-24+79.

[15]毛广敏.常用C语言排序算法解析[J].软件导刊，2012（1111）：51-54.

[16]李向军，杨花娥.求解一元三次方程近似根的几种算法的C语言实现[J].西安联合大学学报，1999（02）：65-69.

[17]马丽娟.常用计算机算法简介及C语言举例[J].电脑知识与技术，2010（611）：2655-2659+2662.

[18]柳小强.基于C语言最大公约数算法的设计与实现[J].现代计算机（专业版），2011（11）：53-56.

【通联编辑：王力】