文章目錄

• 前言
• 一、名稱定義
• • 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

while循環

int fun(int m,int n) {int r; //余數，當余數為0的時候，m即為最大公約數while(n!= 0)//先取余，再用余數對較小的數求余，直到余數為零 {r = m % n;m = n;n = r;}return m; //將結果返回 }

調用遞歸

int fun(int m,int n) {if(n！=0) return fun(n,m%n);return m; }

簡化遞歸

int fun(int m, int n) {return n ? fun(n, m % n) : m; }

3.更相減損法

定義：更相減損法是出自《九章算術》的一種求最大公約數的算法。

示例：求98與63的最大公約數。
98-63=35
63-35=28
35-28=7
28-7=21
21-7=14
14-7=7
7-7=0
當差為0時，除數即為最大公約數：7

---

while循環

int fun(int m,int n) {while(m!=n) //當差為0的時候，n即為最大公約數{if(m>n)m=m-n;elsen=n-m;}return n; }

二、ACM杭電入門題

先來看一個杭電的水題，看看有有沒有解題思路

ACM編程題（請根據下列各題目的描述、輸入和輸出要求，分別寫出相應正確的代碼）
----------------------------------第11題（hdu2503）--------------------------------
（1）題目
a/b + c/d
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Problem Description
給你2個分數，求他們的和，并要求和為最簡形式。
Input
輸入首先包含一個正整數T（T<=1000），表示有T組測試數據，然后是T行數據，每行包含四個正整數a,b,c,d（0<a,b,c,d<1000），表示兩個分數a/b 和 c/d。
Output
對于每組測試數據， 輸出兩個整數e和f，表示a/b + c/d的最簡化結果是e/f，每組輸出占一行。
Sample Input
2
1 2 1 3
4 3 2 3
Sample Output
5 6
2 1

• 本題在ACM中并不難，主要考察是否掌握最大公約數的求法

1.解題思路

• 先求解出未化簡的e,f
• 再求出最大公因數z（兩種方法）
• 最后輸出e=e/z, f=f/z

三、解題參考代碼(C語言，C++)

0.最優算法（C++）

一個優秀的acmer總是尋求最優算法（輾轉相除法時間復雜度優于更相減損法）

本段代碼為c++語言編寫，新手小白看不懂可以看下面的C語言解題

#include<iostream> //頭文件 using namespace std; int fun(int m,int n) //定義函數 輾轉相除法 {return n?fun(n,m%n):m; //求解最大公因數n,返回其值 } int main() { int n,a,b,c,d,e,f,z; //n行數，z最大公約數cin>>n;while(n--){ cin>>a>>b>>c>>d; e=a*d+b*c;f=b*d;z=fun(e,f); //調用函數返回最大公約數 cout<<e/z<<f/z; //輸出最簡答案}return 0; }

1.輾轉相除求解（C語言）

（1）參考代碼：

#include<stdio.h> int main() {int t,e,f,m,n,tmp,r;scanf("%d",&t);for(int i=0;i<t;i++){int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);e=a*d+b*c;f=b*d;///進行最大公約數的求解(f,e) <==> (m,n)m=f;n=e;///輾轉相除r=m%n;while(r!=0){m=n;n=r;r=m%n;}///經過上面的輾轉過程，所求的最大公約數就是n//printf("%d %d\n", e/n, f/n);}return 0; }

2.更相減損法求解（C語言）

（2）參考代碼：

#include<stdio.h> int main() {int t,e,f,m,n;scanf("%d",&t);for(int i=0;i<t;i++){int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);e=a*d+b*c;f=b*d;///進行最大公約數的求解(f,e) <==> (m,n)m=f;n=e;//輾轉相減while(m!=n){if(m>n)m=m-n;elsen=n-m;}///經過上面的輾轉過程，所求的最大公約數就是n//printf("%d %d\n",e/n,f/n);}return 0; }

總結

今天的分享就到這里啦，喜歡小編博客的可以點贊支持哦，覺得內容對你有用的可以收藏備用
最后，祝我們早日抗疫成功，摘下口罩和最想見面的人見面，齊心抗疫，眾志成城！

總結

以上是生活随笔為你收集整理的最详细最简单：最大公因数求法、辗转相除法、更相减损法，入门ACM，杭电水题，算法递归，初级算法题一看就懂的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。