辗转相除法
辗转相除法与最大公约数的关系
重要程度：9 分
<div>
<h2>辗转相除法与最大公约数的关系</h2>
<p>辗转相除法是一种用于求两个正整数最大公约数（Greatest Common Divisor, GCD）的有效方法。其基本思想是通过一系列的除法运算，逐步将问题简化。</p>
<p>假设我们要求两个正整数a和b的最大公约数，其中a > b。</p>
<ol>
<li>用a除以b，得到余数r。</li>
<li>如果r为0，则b即为所求的最大公约数。</li>
<li>如果r不为0，则将b赋值给a，将r赋值给b，重复步骤1。</li>
</ol>
<h3>例题说明</h3>
<p>例如，我们要求24和18的最大公约数：</p>
<pre>
24 ÷ 18 = 1 ... 6
18 ÷ 6 = 3 ... 0
</pre>
<p>因为最后的余数为0，所以此时的除数6就是24和18的最大公约数。</p>
<p>辗转相除法的关键在于，每次迭代后，问题的规模都会减小，直到找到一个余数为0的情况。</p>
</div>