一、辗转相除法

1、简介

辗转相除法又叫欧几里得算法。

假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法，是这样进行的：

1997 / 615 = 3 (余 152)

615 / 152 = 4(余7)

152 / 7 = 21(余5)

7 / 5 = 1 (余2)

5 / 2 = 2 (余1)

2 / 1 = 2 (余0)

至此，最大公约数为1

以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1。

2、代码 

#include<stdio.h>

int gcd(int a, int b) {
     int t;
     while(b!=0) {
         t=a%b;
         a=b;
         b=t;
     }
     return a;
}

二、更相减损术

1、简介

更相减损术是出自《九章算术》的一种求最大公约数的算法。

求98与63的最大公约数：

98-63=35

63-35=28

35-28=7

28-7=21

21-7=14

14-7=7

所以，98和63的最大公约数等于7。

2、代码

#include<stdio.h>

int gcd(int a, int b) {
    while (a != b) {
        if (a > b)
            a = a - b;
        else
            b = b - a;
    }
    return b;
}

三、秦九韶算法

1、简介

秦九韶算法是中国南宋时期的数学家秦九韶提出的一种多项式算法。

在西方被称作霍纳算法。

         

一般地，一元n次多项式的求值需要经过(n+1)*n/2次乘法和n次加法，而秦九韶算法只需要n次乘法和n次加法。

2、算法描述

• 用一个数组去描述该多项式，数组的最大下标就是最大幂，下标对应的值就是对应的系数
• 输入多项式信息，x的值和各系数（看作是的系数）
• 以加法为连接点

3、代码 

#include<stdio.h>

/*秦九韶算法*/
int Qinjiushao(int x,int*a,int n)//x x的值  *a 包含系数信息的数组  n 最高幂+1
{
	int result = a[n-1];
	for(int i=n-2;i>=0;i--)
		result = x*result+a[i];
	return result;
}

int main()
{
	int x,n;
	printf("x的值：\n");
	scanf("%d",&x);
	printf("最高幂：\n");
	scanf("%d",&n);
	int a[n];
	for(int i=0;i<n+1;i++)
	{
		printf("系数%d：\n",i);
		scanf("%d",&a[i]);
	}
	printf("由秦九韶算法得出结果：%d",Qinjiushao(x,a,n+1));
}

4、举例说明 

求的值