摘  要: 本文主要介绍几种经典的C语言算法,主要有最大公因数算法、老鼠走迷宫算法、快速排序算法等. 主要是根据问题的思路与解题流程，将这些算法与具体问题相结合，用C语言尽可能简洁准确的给出算法求得答案，并讨论各个算法的一些优缺点与可改进之处.63122

毕业论文关键词: 经典算法，最大公因数，老鼠走迷宫，快速排序

Abstract:Several classic C language algorithms are introduced in this paper, including the greatest common factor algorithm, maze algorithm, quick sort algorithm, etc. Mainly according to the problem thought and the problem solving process, the algorithm combined with concrete problems, using C language as far as possible concise and accurate algorithm for the answer, and discuss some of the advantages and disadvantages of each algorithm and the improvements. 

Keywords: classical algorithm, greatest common pisor, rats run maze, quick sort

目  录

0 引言 4

1 C语言简介4

2几个经典算法研究4

2.1最大公因数算法4

2.2 老鼠走迷宫算法7

2.3 快速排序算法13

结论16

参考文献17

致谢18 

0  引言

C语言中的经典算法在现代社会中有着广泛的应用, 算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。同一个问题不同的算法都可以解决，但是它们的时间复杂度、空间复杂度不同，算法分析可以优化程序，使运行时占用更少的时间和空间。及时地归纳总结各种类型的题目算法，尤其是一题多解的方法，对拓宽思维、加深对题目的理解更加有助[1]。

1  C语言简介

C语言简洁紧凑，使用方便灵活，运算功能丰富，数据类型丰富，表达能力强，具有结构化的控制语句，程序设计自由度大，能实现汇编语言的大部分功能，可以直接对硬件进行操作，可移植性好，生成目标代码质量高，程序执行效率高，应用面广，既具有高级语言的优点，又具有低级语言的很多特点[2]。因此很适合用其中的经典算法编写出简便的解题方法。

2  几个经典算法研究

2.1  最大公因数算法

    在C语言的循环结构程序设计的过程中，求两个数的最大公因数是一个经典的案例。常用的有以下两种算法：

（1）辗转相除法

辗转相除法简介：辗转相除法，又称欧几里德算法(Euclidean algorithm)，是求两个正整数的最大公因数的算法，它是已知最古老的算法，可追溯至3000年前。其原理是用两数中的较大数除以较小数，若余数为0，则除数就是这两个数的最大公因数。若余数不为0，则以除数作为新的被除数，以余数作为新的除数，继续相除，直到能整除为止，最后一个非零除数即为这两数的最大公因数[3]。

算法思想：设两数为m、n(m>n),求m和n最大公因数(m,n)的步骤如下：用m除以n=q......r1,若r1=0,则(m,n)=b;若r1≠0，则再用n除以r1，得n&pide;r1=q......r2,若r2=0,则(m,n)=r1,若r2≠0,则继续用r1除以r2，如此下去，直到余数为0为止，最后一个非0除数即为(m,n)。

例1：m=40，n=15，求m和n的最大公因数。按照此算法计算如下：文献综述

40%15的得数为10，不为0；15%10的得数为5，不为0；10%5的得数为0，所以num1和num2的最大公约数是5。

程序如下：

#include<stdio.h>

int main()

{

    int x,y,num1,num2,t;

    scanf("%d,%d",&x,&y);