第二章：程序的算法设计

1.实验目的

a.明确算法的概念和特点。

b.通过对问题的分析，设计合理的算法解决问题；

c.在原有算法的基础上做更进一步的改进

2.题目描述

求n个数的最大公约数和最小公倍数，用C或C++或java或python语言实现程序解决问题。

1.程序风格良好(使用自定义注释模板)

2.提供友好的输入输出，并进行输入数据的正确性验证。

 

3.需求分析

通过上一节求最大公约数的四种算法的比较，可以得出辗转相除法（欧几里得算法）更为适用，所以这一节决定采用该算法进行计算。计算步骤如下：

1. 利用辗转相除法求得两个数的最大公约数
2. 通过对gcd函数的调用，实现求得n个数的最大公约数
3. 同理，利用所得最大公约数求的最小公倍数
4. 通过对lcm函数的调用，实现求的n个数的最小公倍数

4.算法设计

4.1辗转相除法求最大公约数

辗转相除法，又称欧几里得算法，其算法原理是：首先用两个正整数中较大的数作为被除数，用较小的数做除数进行除法运算，若余数不为0，再把上次的除数作为被除数，把上次的余数作为下次的除数，直到余数是0为止，此时的除数即为两数的最大公约数。

4.1.1算法分析

(1).大数放a中、小数放b中；

(2).求a/b的余数；

(3).若a%b=0则b为最大公约数；

(4).如果a%b!=0则递归调用gcd函数；

(5).直至a%b=0，得到a和b最大公约数。

4.1.2算法实现

int gcd(int a,int b)

 {

if(a%b==0)

     return b;

         else;

         return gcd(b,a%b);

 }

4.1.3流程图

4.2 求N个数最大公约数

     先求前两个数的最大公约数，随后用所得公约数与下一个数求最大公约数，以此类推。

4.2.1算法实现

   int ngcd(int *a, int n)//个数n，实际坐标n-1数

{

    if(n==1)

       return *a;

    return gcd(a[n-1],ngcd(a, n-1));//坐标n-1数与前面数的公约数

}

4.3求两个数的最小公倍数

用两数之积除以两数最大公约数

4.3.1算法实现

    int lcm(int a,int b)

{

    return a*b/gcd(a, b);

}

4.3.2流程图

 

4.4 求N个数的最小公倍数

先求前两个数的最小公倍数，随后用所得公倍数与下一个数求最小公倍数，以此类推。

 

4.4.1算法实现

int nlcm(int *a, int n)

{

    if (n==1)

       return *a;

    else

       return lcm(a[n-1],nlcm(a,n-1));

}

5.调试及测试  

5.1调试界面

5.2数据测试