:::
歐氏演算法 - 教育百科
| 歐 | |
| 氏 | |
| 演 | |
| 算 | |
| 法 |
國家教育研究院辭書
基本資料
| 英文： | Euclid's algorithm |
| 日期： | 2003年6月 |
| 出處： | 資訊與通信術語辭典 |
辭書內容
|
名詞解釋： 為一種求解二數之最大公約數（GCD）的演算法。其方法是建立在如下的恆等式上。gcd（a,b）＝gcd（a－b,b）即重複以小數減大數的結果取代大數，直到二數相等為止。如求（99,36）最大公約數的過程可表示如：（99,36）→（63,36）→（27,36）→（27,9）→（18,9）→（9,9）。故（99,36）最大公約數為9。本演算法只需使用減法和比較兩種運算。但其所需的工作步驟取決於二數的初始數（如gcd（1,2000）需要2000個步驟）。經改良後，重複以小數除以大數的餘數取代大數，直到餘數為零，當時的除數即為最大公約數。（99,36）→（27,36）→（27,9）→（0,9）。可有效縮減處理步驟。 |
|
| 資料來源： | 國家教育研究院_歐氏演算法 |
| 授權資訊： | 資料採「 創用CC-姓名標示- 禁止改作 臺灣3.0版授權條款」釋出 |
貓頭鷹博士