文章目录

  • 前言
  • 一、名称定义
    • 1.最大公约数
    • 2.辗转相除法
    • 3.更相减损法
  • 二、ACM杭电入门题
    • 1.解题思路
  • 三、解题参考代码(C语言,C++)
    • 0.最优算法(C++)
    • 1.辗转相除求解(C语言)
    • 2.更相减损法求解(C语言)
  • 总结

前言

本篇博客对:最大公因数,辗转相除法,更相减损法等专有名词进行了详细的介绍,分享了两种求解最大公因数的算法代码,以杭州电子科技大学的ACM入门题作为索引,借助实际代码,对上面介绍的两种算法求解最大公因数进行初级应用,粗略地介绍了递归思想对算法的优化。

一、名称定义

1.最大公约数

定义:最大公因数是指两个或多个整数共有约数中最大的一个。

示例:12、16的公约数有1、2、4,其中最大的一个是4,4是12与16的最大公约数。

2.辗转相除法

定义:辗转相除法是求两个自然数的最大公约数的一种方法。

示例:求319,377的最大公约数
319÷377=0(余319)
377÷319=1(余58)
319÷58=5(余29)
58÷29=2(余0)
当余数为0时,除数即为最大公约数:29

  1. while循环
int fun(int m,int n){ int r;//余数,当余数为0的时候,m即为最大公约数while(n!= 0)//先取余,再用余数对较小的数求余,直到余数为零 { r = m % n;m = n;n = r;}return m;//将结果返回}
  1. 调用递归
int fun(int m,int n){ if(n!=0) return fun