歐幾里得演算法
① 歐幾里得演算法（輾轉相除法）
就是把上一輪有餘數的除法計算中， 除數變為下一輪計算的被除數， 余數變為下一輪計算的除數， 一直這樣計算下去， 直到最後一次計算余數為零， 在最後一輪計算中的被除數，即為所求的最大公約數。
舉例： 105和85的最大公約數
第一輪計算 105÷85=1...20
第二輪計算 85÷20=4...5
第三輪計算 20÷5=4
第三輪沒有餘數， 因此 105和85的最大公約數就是第三輪計算的被除數 5.
至於C語言編程，下邊是我自己寫的G函數(思想就是輾轉相除法求最大公約數)
int G(int x,int y)
{ int t;
while(y!=0)
{ t=x%y ;
x=y;
y=t;
}
return x;
}
② 擴展歐幾里得演算法 好懂一點
歐幾里德演算法又稱輾轉相除法，用於計算兩個整數a,b的最大公約數。其計算原理依賴於下面的定理：
定理：gcd(a,b) = gcd(b,a
mod b)
證明：a可以表示成a = kb +
r，則r = a mod b
假設d是a,b的一個公約數，則有
d|a,
d|b，而r = a - kb，因此d|r
因此d是(b,a
mod b)的公約數
假設d 是(b,a
mod b)的公約數，則
d | b , d
|r ，但是a = kb +r
因此d也是(a,b)的公約數
因此(a,b)和(b,a mod
b)的公約數是一樣的，其最大公約數也必然相等，得證
歐幾里德演算法就是根據這個原理來做的，其演算法用C++語言描述為：
int
Gcd(int a, int b)
{
if(b ==
0)
return a;
return
Gcd(b, a % b);
}
當然你也可以寫成迭代形式：
int
Gcd(int a, int b)
{
while(b !=
0)
{
int r = b;
b = a % b;
a =
r;
}
return
a;
}
本質上都是用的上面那個原理。
補充:
擴展歐幾里德演算法是用來在已知a,
b求解一組x，y使得a*x+b*y=Gcd(a,b)(解一定存在，根據數論中的相關定理)。擴展歐幾里德常用在求解模線性方程及方程組中。下面是一個使
用C++的實現：
int
exGcd(int a, int b, int &x, int
&y)
{
if(b ==
0)
{
x = 1;
y = 0;
return a;
}
int r =
exGcd(b, a % b, x, y);
int t =
x;
x =
y;
y = t - a
/ b * y;
return
r;
}
把這個實現和Gcd的遞歸實現相比，發現多了下面的x,y賦值過程，這就是擴展歐幾里德演算法的精髓。
可以這樣思考:
對於a' = b,
b' = a % b 而言，我們求得 x, y使得 a'x + b'y = Gcd(a', b')
由於b' = a
% b = a - a / b * b (註：這里的/是程序設計語言中的除法)
那麼可以得到:
a'x + b'y
= Gcd(a', b') ===>
bx + (a - a / b * b)y = Gcd(a', b') = Gcd(a, b)
===>
ay +b(x - a / b*y) = Gcd(a, b)
因此對於a和b而言，他們的相對應的p，q分別是
y和(x-a/b*y).
在網上看了很多關於不定方程方程求解的問題，可都沒有說全，都只說了一部分，看了好多之後才真正弄清楚不定方程的求解全過程，步驟如下：
求a * x
+ b * y = n的整數解。
1、先計算Gcd(a,b)，若n不能被Gcd(a,b)整除，則方程無整數解；否則，在方程兩邊同時除以Gcd(a,b)，得到新的不定方程a'
* x + b' * y = n'，此時Gcd(a',b')=1;
2、利用上面所說的歐幾里德演算法求出方程a' * x + b' * y = 1的一組整數解x0,y0，則n' * x0,n' *
y0是方程a' * x + b' * y = n'的一組整數解；
3、根據數論中的相關定理，可得方程a'
* x + b' * y = n'的所有整數解為：
x = n' * x0 + b' * t
y = n' * y0 - a' * t
(t為整數)
上面的解也就是a * x + b * y = n 的全部整數解。
步驟如下：
擴展歐幾里德演算法－求解不定方程，線性同餘方程：
解不定方程ax + by = n的步驟如下:
(1)計算gcd(a, b). 若gcd(a, b)不能整除n，則方程無整數解；否則，在方程的兩邊同除以gcd(a, b)，
得到新的不定方程a'x + b'y = n'，此時gcd(a', b') = 1
(2)求出不定方程a'x + b'y = 1的一組整數解x0, y0，則n'x0，n'y0是方程a'x + b'y = n'的一組整數解。
(3)根據&@^%W#&定理，可得方程a'x + b'y = n'的所有整數解為：
x = n'x0 + b't
y = n'y0 - a't
(t為整數)
這也就是方程ax + by = n的所有整數解
利用擴展的歐幾里德演算法，計算gcd(a, b)和滿足d = gcd(a, b) = ax0 + by0的x0和y0，
也就是求出了滿足a'x0 + b'y0 = 1的一組整數解。因此可得：
x = n/d * x0 + b/d * t
y = n/d * y0 - a/d * t
(t是整數)
program oujilide;
var i,j,a,b,c,d,x,y:longint;
function gcd(a,b:longint):longint;
var i:longint;
begin
if a=0 then exit(b);
if b=0 then exit(a);
gcd:=gcd(b,a mod b);
end;
procere extend_gcd(a,b:longint;var x,y:longint);
var i,j:longint;
begin
if b=0 then
begin
x:=1;
y:=0;
exit
end;
extend_gcd(b,a mod b,x,y);
i:=x;
x:=y;
y:=i-(a div b)*x;
end;
begin
assign(input,'oujilide.in');
reset(input);
assign(output,'oujilide.out');
rewrite(output);
read(a,b,c);
d:=gcd(a,b);
if c mod d=0 then begin a:=a div d; b:=b div d; c:=c div d; end
else begin writeln('No answer!'); exit; end;
extend_gcd(a,b,x,y);
x:=c*x;
y:=c*y;
writeln(x,' ',y);
end.
③ 歐幾里得演算法
計算過程一模一樣，只是最後對1001取模：
1 = 167 - 166
= 167 - (834 - 4 * 167)
= 5 * 167 - 834
= 5 *(1001 - 834) - 834
= 5 * 1001 - 6 *834
= 5 * 1001 - 6 * (3837 -3 *1001)
= 23 * 1001 - 6 *3837
然後對等式兩端同時除以模1001得
6 * 3837 = 1 (mod 1001)
於是 x ＝ 6
④ 擴展歐幾里得演算法
//歐幾米德演算法 //演算法描述：給定兩個正整數m和n,求他們的最大公因子。 //1.[求余數]用m除以n並令r為所得余數 //2.[余數為0]若r=0,則演算法結束，n即為所求答案 //3.[互換]置m←n,n←r,並返回步驟1。 #include <cstdlib> #include <iostream> using namespace std; int main(int argc, char *argv[]) { int n,m; int r; cout << "輸入兩個數（M，N）："; cin >> m >> n; cout << m << "和" << n << "的最大公約數為"; while(r!=0) { r=m %n; m=n; n=r; } cout << m<< endl; system("PAUSE"); return EXIT_SUCCESS; }
麻煩採納，謝謝!
⑤ 用java實現歐幾里得演算法🌝
publicstaticvoidmain(String[]args){
Scannerscanner=newScanner(System.in);
inta,b;
a=scanner.nextInt();
b=scanner.nextInt();
System.out.printf("%d和%d的最大公約數為：%d",a,b,Gcd(a,b));
}
privatestaticintGcd(intM,intN){
intRem;
while(N>0){
Rem=M%N;
M=N;
N=Rem;
}
returnM;
}
⑥ 關於歐幾里得演算法，主要是看不懂。請高手指點迷津。。。。
1、 歐幾里德演算法：給定兩個正整數m和n，求他們的最大公因子，即能夠同時整除m和n的最大的正整數。
E1：【求余數】以n除m並令r為所得余數（我們將有0<=r<n）。
E2：【余數為0？】若r=0，演算法結束；n即為答案。
E3：【互換】置mßn,nßr,並返回步驟E1.
證明：
我們將兩個正整數m和n的最大公因子表示為：t = gcd（m，n）；
重復應用等式：gcd（m，n）= gcd（n，m mod n）直到m mod n 等於0；
m可以表示成m = kn + r；則 r = m mod n ， 假設 d是 m 和 n的一個公約數，則有：
d|m 和 d|m 而 r =m – kn ，因此 d|r ，因此 d 是 (n,m mod n) 的公約數；假設 d 是 (n,m mod n) 的公約數，
則 d|n ，d|r ，但是 m=kn+r ，因此 d 也是 (a,b) 的公約數；因此 (a,b) 和
(b,a mod b) 的公約數是一樣的，其最大公約數也必然相等，得證。
具體步驟描述如下：
第一步：如果 n=0 ，返回 m 的值作為結果，同時過程結束；否則，進入第二步。
第二步：用 n 去除 m ，將余數賦給 r 。
第三步：將 n 的值賦給 m，將 r的值賦給 n，返回第一步。
偽代碼描述如下：
Euclid(m,n)
// 使用歐幾里得演算法計算gcd(m,n)
// 輸入：兩個不全為0的非負整數m，n
// 輸出：m，n的最大公約數
while n≠0 do
r ← m mod n
m ← n
n ← r
註：(a,b) 是 a,b的最大公因數
(a,b)|c 是指 a,b的最大公因數 可以被c整除。
java實現：
package algorithm;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class GreatestCommonDivisor {
int a,b,temp = 0;
public static void main(String args[]) throws IOException {
GreatestCommonDivisor gcd = new GreatestCommonDivisor();
gcd.readNum();
gcd.MaxNum();
System.out.print(gcd.a+"和"+gcd.b+"的最大公約數是:");
while (gcd.b != 0) {
gcd.temp = gcd.b;
gcd.b = gcd.a % gcd.b;
gcd.a = gcd.temp;
}
System.out.println(gcd.temp);
}
//輸入兩個正整數,中間用空格分開.
public void readNum() throws IOException{
BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
String str = buf.readLine();
for(int i = 0;i<str.length();i++){
if(str.charAt(i)==' ' && temp == 0){
a = Integer.parseInt(str.substring(temp,i));
temp = i;
b = Integer.parseInt(str.substring(temp+1,str.length()));
break;
}
}
}
public void MaxNum(){
if (a < b) {
temp = b;
b = a;
a = temp;
}
}
}
⑦ 用歐幾里得演算法找x和y!!
就是8=144*1-1(1000-144*6)
=144*1-1000+144*6（分配律）
=144*（6+1）-1000（結合律）
⑧ 什麼是歐幾里得演算法，它有什麼意義
歐幾里得演算法即輾轉相除法，用以求兩個數的最大公約數（或者最小公倍數）
證明如下
假設x,y的最大公約數為d
且設x=k1*d，y=k2*d;
則有z=x-y=(k1-k2)*d;
也必定能被d整除，所以通過兩個數不斷輾轉，直到其中一個變為0為止，以此最終快速得出兩個數的最大公約數。
在演算法的應用上是用求余以加速運算的速度。
總的來說，歐幾里得演算法的意義就是快速求得兩個數的最大公約數。
⑨ 歐幾里得演算法是什麼
歐幾里得演算法又稱輾轉相除法，是指用於計算兩個非負整數a，b的最大公約數。應用領域有數學和計算機兩個方面。計算公式gcd(a,b) = gcd(b,a mod b)。
輾轉相除法的演算法步驟為，兩個數中用較大數除以較小數，再用出現的余數除除數。
再用出現的余數（第二餘數）去除第一餘數，如此反復，直到最後余數是0為止。
輾轉相除法是利用以下性質來確定兩個正整數a和b的最大公因子的：
1、若r是a ÷ b的余數，且r不為0，則gcd(a,b) = gcd(b,r)。
⒉、a和其倍數之最大公因子為a。
另一種寫法是：
⒈、令r為a/b所得余數（0≤r），若r= 0，演算法結束；b即為答案。
⒉、互換：置a←b，b←r，並返回第一步。
⑩ 歐幾里得演算法求過程
就是把上一輪有餘數的除法計算中， 除數變為下一輪計算的被除數， 余數變為下一輪計算的除數， 一直這樣計算下去， 直到最後一次計算余數為零， 在最後一輪計算中的被除數，即為所求的最大公約數。