離散課上第一次接觸歐幾里得算法，課上并無多講，知識了解一個大概，隨后幾天學(xué)習(xí)C語言過程中遇到，看一本算法入門雜志中有提到，突然有興趣，開始尋找關(guān)于歐幾里得算法的一些簡單知識，下文文章僅是初學(xué)的我關(guān)于歐幾里得算法的搜集和一些自己的看法
一：歐幾里得算法：
想到歐幾里得算法最本質(zhì)的想法就是算最大公因數(shù)gcd(a,b) = gcd(b,a mod b)，之前大一初學(xué)python的時候老師給我們的最初求最大公因數(shù)的問題是我那個時候（初學(xué)編程）（使用python）
現(xiàn)在使用歐幾里得算法進(jìn)行求最大公約數(shù)
def findemax(x,y):
? ? while y!= 0:
? ? ? ? t = x%y
? ? ? ? x = y
? ? ? ? y = t
? ? return x
print(findemax(24,36))
歐幾里得算法體現(xiàn)出高效，下面是分析兩個代碼的算法復(fù)雜度，從算法復(fù)雜度來直觀看其高效
代碼1：復(fù)雜度很簡單：O（n）
歐幾里得算法復(fù)雜度為O（lgn）
下面是歐幾里得算法復(fù)雜度的解析（非原創(chuàng)，是根據(jù)一個博客得到的，加上一點自己的理解）算是比較能理解的一種解釋
所以歐幾里算法比較高效
下面是歐幾里算法的數(shù)學(xué)證明（非原創(chuàng)，比較好理解）
歐幾里得算法的應(yīng)用
倒水問題解析
有兩個容器，容積分別為A升和B升，有無限多的水，現(xiàn)在需要C升水。 我們還有一個足夠大的水缸，足夠容納C升水。起初它是空的，我們只能往水缸里倒入水，而不能倒出。 可以進(jìn)行的操作是： 把一個容器灌滿； 把一個容器清空（容器里剩余的水全部倒掉，或者倒入水缸）； 用一個容器的水倒入另外一個容器，直到倒出水的容器空或者倒入水的容器滿。 ? ? 問是否能夠通過有限次操作，使得水缸最后恰好有C升水。
#include <stdio.h>\\C語言進(jìn)行編寫（原創(chuàng)）
int main()
{
? ? int a,b,c;
? ? int t;
? ? scanf("%d%d",&a,&b,&c);
? ? while (b!=0){
? ? ? ? t = a%b;
? ? ? ? a = b;
? ? ? ? b = t;
? ? }
? ? if (b%c == 0){
? ? ? ? printf("yes");
? ? }else
? ? {
? ? ? ? printf("no");
? ? }
? ? return 0;
}
歐幾里得是我第一學(xué)習(xí)的算法，算法真神奇，這個算法讓我知道了為什么要好好學(xué)算法了，繼續(xù)努力吧~每天學(xué)習(xí)一個算法
