C语言如何求最大公约数

本篇内容介绍了“C语言如何求最大公约数”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

1. C语言简介

1.1 C语言发展史

C语言是一种广泛使用的面向过程的计算机程序设计语言，既适合于系统程序设计，又适合于应用程序设计。C语言的发展历程大致如图1-1所示：

图1-1 C语言的发展历程

1.2 C语言的特点

C语言是一种通用的程序设计语言，语言本身简洁、灵活、表达能力强，被广泛用于系统软件和应用软件的开发，并且具有良好的可移植性。

C语言的特点可概括如下：

（1）简洁、紧凑、灵活。C语言的核心内容很少，只有32个关键字，9种控制语句；程序书写格式自由，压缩了一切不必要的成分。

（2）表达方式简练、实用。C语言有一套强有力的运算符，达44种，可以构造出多种形式的表达式，用一个表达式就可以实现其他语言可能需要多条语句才能实现的功能。

（3）数据类型丰富。数据类型越多，数据的表达能力就越强。C语言具有多种数据类型，如字符型、整型、实型、数组、指针、结构体和共用体等，可以实现诸如链表、栈、队列、树等各种复杂的数据结构。其中的指针类型使得参数的传递简单并且迅速，同时节省内存空间。

（4）具有低级语言的特点。C语言具有与汇编语言相近的功能和描述方法，如地址运算和二进制数位运算等，还可以对硬件端口等资源进行直接操作，充分使用计算机的资源。C语言既具有高级语言便于学习和掌握的特点，又具有机器语言或汇编语言对硬件的操作能力。因此，C语言既可以作为系统描述语言，又可以作为通用的程序设计语言。

（5）C语言是一种结构化语言，适合于大型程序的模块化设计。C语言提供了编写结构化程序的基本控制语句，如if-else语句、switch语句、while语句和do-while语句等。C语言是函数的集合，函数是构成C语言程序的基本单位，每个函数具有独立的功能，函数之间通过参数传递数据。程序员可以编写自己的函数。同时，不同操作系统的编译器都为程序员提供了大量的标准库函数，如输入/输出函数、数学函数和字符串处理函数等。灵活地使用标准库函数可以简化程序设计，提高编写程序效率。

（6）各种版本的编译器都提供了预处理命令和预处理程序。预处理扩展了C语言的功能，提高了程序的可移植性，为大型程序的调试提供了方便。

（7）可移植性好。程序从一个环境不经改动或稍加改动就可以移植到另一个完全不同的环境中运行。这是因为标准库函数和预处理程序将可能出现的与机器有关的因素与源程序分割开来，使得针对不同的计算机硬件环境，可以重新定义有关的内容。

（8）生成的目标代码质量高。由C源程序编译和链接得到的目标代码的运行效率比用汇编语言编写的也不过只低10%~20%，可充分发挥机器的效率。

（9）C语言语法限制不严，程序设计自由度大。C语言程序在运行时不做诸如数组下标越界和变量类型兼容性等检查，而是由编程者自己保证程序的正确性。C语言几乎允许所有的数据类型的转换，字符型和整型可以自由混合使用，所有类型均可作逻辑型，可自己定义新的类型，还可以把某类型强制转换为指定的类型。实际上，这使编程者有了更大的自主性，能编写出灵活、优质的程序，同时也给初学者增加了一定的难度。所以，只有在熟练掌握C语言程序设计之后，才能体会到其灵活性。

C语言也存在以下缺点：

（1）程序的错误更隐蔽。C语言的灵活性使得用它编写程序时更容易出错，而且C的编译器不检查这样的错误。与汇编语言类似，需要程序运行时才能发现这些逻辑错误。C语言还会有一些隐患，如将比较的 “==” 写成赋值 “=” ，虽然语法上没错，但这样的逻辑错误往往不易发现，想要找出错误往往十分费时。

（2）C语言程序有时会难以理解。C语言语法成分相对简单，是一种小型语言。但是，其数据类型多，运算符丰富且结合性多样，使得对其理解有一定的难度。

（3）C语言程序有时会难以修改。考虑到程序规模的大型化或者巨型化，现在编程语言通常会提供 “类” 和 “包” 之类的语言特性，这样的特性可以将程序分解成更加易于管理的模块。然而C语言缺少这样的特性，维护大型程序显得比较困难。

1.3算法及其表示

C语言解题时，在程序中有两方面的描述，即数据描述和处理步骤（算法）描述，后者处理前者的数据。

算法具有以下特性：

• 有穷性：算法在执行了有限步骤后结束，并且每一步都可以在有穷的时间内完成。      

• 确定性：算法中每种操作必须有确切的含义，即无二义性。同时，无论如何算法只有唯一的一条执行路径，即相同的输入只能得出相同的输出。      

• 可行性：算法中描述的操作都可以通过已经实现的基本操作执行有限次数来实现。      

• 输入：有零个或多个输入，即算法需要的必要信息。      

• 输出：有一个或多个输出，输出的是与输入有某些特定关系的信息。没有输出的算法是无意义的。

算法的表示：

1.自然语言描述；    

2.传统流程图；    

3.N-S流程图；    

4.伪代码。

【例如】求两个正整数m和n的最大公约数（即同时能够整除m和n的最大正整数）。

1. 自然语言描述

欧几里得阐述了求两个数的最大公约数的过程——欧几里得算法

第一步：以n除m，并令r为所得余数（显然n>r0）。

第二步：若r=0,算法结束，n即为m和n的最大公约数。

第三步：置mn，nr，返回第一步。

2. 传统流程图

图1-2 求最大公约数的传统流程图

3. N-S流程图

图1-3 求最大公约数的N-S流程图

4. 伪代码

算法开始
输入m,n;
do{
    r←以n除m的余数；
    m←n;
    n←r;
}while(r≠0);
输出m;
算法结束

1.4常用算法介绍

1.枚举法

枚举法又称为穷举法。该方法通过逐一考察问题的所有可能解，找出问题真正的解。枚举法要求问题的可能解必须是有限的，而且这些可能解是已知的。

【例】给定一个正整数，确定它的整数立方根是否存在，若存在则找出这个立方根。

算法开始
输入一个正整数给n;
x←0;
while(x≤n 且 x*x*x≠n){
    x←x+1;
}
if(x≤n)
    找到n的整数立方根，输出x的值；
else
    输出n的整数立方根不存在信息；
算法结束

2.递推法

递推法是从已知的初始条件出发，逐次推出中间结果。在理想状态下，每递推一次，结果逐渐接近问题的最后解。递推法在数值算法中又称为迭代法。迭代法常用于求近似解的问题，根据对前一步结果的误差的不同处理方法，迭代法又有逼近迭代和试探迭代等不同方法。数值计算要注意解的稳定性问题，即在迭代中每一步的解越来越接近真正的解，否则迭代不会成功。

【例】计算一个正整数n的阶乘。

算法开始
输入一个正整数给n；
t←1;
i←1;
while(i≤n){
    t←t*i;
    i←i+1;
}
输出结果t
算法结束

3.递归法

一个直接或间接调用过程（或函数）自身的算法称为递归算法，一个函数如果调用自身进行计算则称该函数为递归函数。一些问题的算法描述中，递归法往往比非递归法更加简洁易懂。

【例】计算一个正整数N的阶乘。

阶乘函数f的递归定义为：
f(1)=1                (1!=1,N=1 时)
f(N)=N*f(N-1)         (N!=N*(N-1)!,如果N>1)

除了上面介绍的枚举法、递推法和递归法外，还有回溯法、贪婪法、分治法、动态规划法等

“C语言如何求最大公约数”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站，小编将为大家输出更多高质量的实用文章！