【歐氏演算法】
<P align=center><STRONG><FONT size=5>【<FONT color=red>歐氏演算法</FONT>】</FONT></STRONG></P> <P><STRONG>英語翻譯：Euclid'salgorithm</STRONG></P><P><STRONG></STRONG> </P>
<P><STRONG>【辭書名稱】資訊與通信術語辭典</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>為一種求解二數之最大公約數（GCD）的演算法。</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>其方法是建立在如下的恆等式上。</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>gcd（a,b）＝gcd（a－b,b）即重複以小數減大數的結果取代大數，直到二數相等為止。</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>如求（99,36）最大公約數的過程可表示如：（99,36）→（63,36）→（27,36）→（27,9）→（18,9）→（9,9）。</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>故（99,36）最大公約數為9。</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>本演算法只需使用減法和比較兩種運算。</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>但其所需的工作步驟取決於二數的初始數（如gcd（1,2000）需要2000個步驟）。</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>經改良後，重複以小數除以大數的餘數取代大數，直到餘數為零，當時的除數即為最大公約數。</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>（99,36）→（27,36）→（27,9）→（0,9）。</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG>可有效縮減處理步驟。</STRONG></P>
<P><STRONG></STRONG> </P>
<P><STRONG></STRONG> </P>轉自:http://edic.nict.gov.tw/cgi-bin/tudic/gsweb.cgi?o=ddictionary
頁:
[1]