QuickCalculators は、2 つの非負の整数に対して Euclid のアルゴリズムを実行し、最後の非ゼロの剰余として GCF が現れるまで、すべての商と剰余を出力します。いずれかの順序でペアを入力します。ステップ表には分割形式が表示されているので、各行を手で確認できます。
除算を繰り返してGCFを求めます
Euclid のアルゴリズムは、大きい数値を小さい数値で割り、大きい数値を余りで置き換えることを繰り返すことで最大公約数を見つけます。残りがゼロになった場合、そのステップの除数は GCF です。 Euclid のアルゴリズム計算機は各除算を記録するので、チェーンが監査可能になります。
816 と 2260 の場合は、2260 ÷ 816 から始めます。商は2、余りは628です。次に、816 ÷ 628 の余り 188 が残ります。残りがゼロになってチェーンが停止するまで続けます。ゼロ以外の最後の残りは、元のペアの GCF です。
ステップテーブルを読む
ステップ テーブルには、各ラウンドの被除数、除数、商、および剰余がリストされます。剰余列を読み進めると、ゼロで終わる縮小シーケンスが示されます。 QuickCalculators はこれらの列を整列させて、ノートブックのコピーで a × b + r が各行の以前の被除数に等しいことを検証できるようにします。
48 と 18 のコンパクトなスケッチ:
| 配当金 | 除数 | 商 | 残り |
|---|---|---|---|
| 48 | 18 | 2 | 12 |
| 18 | 12 | 1 | 6 |
| 12 | 6 | 2 | 0 |
ゼロ以外の最後の剰余は 6 であるため、 GCF(48, 18) = 6 となります。
このよくある間違いを避けてください
減算形式と除算形式は同じアルゴリズムです。割り算は引き算を繰り返して1つの商に圧縮します。学生はそれらを、異なる答えを持ったライバルのメソッドとして扱うことがあります。正しく適用された場合、両方とも同じ GCF で終了します。 48 から 18 を 2 回減算すると、12 に達します。これは、商 2 が 1 行にエンコードしたものとまったく同じです。
除算を優先すると、Euclid で説明された数学的パスを変更することなく、記述を節約できます。
アルゴリズムが常に終了する理由を理解する
各剰余は前の除数よりも厳密に小さい非負の整数であるため、剰余シーケンスは永久に下降することはできません。有限降下では、有限ステップ数の後に剰余がゼロになります。この保証は、ページが受け入れるすべての非負の整数入力に対して適用されます。
フィボナッチ数に関連する最悪のペアは、教室での典型的な例よりも多くの手順を必要としますが、それでも完了します。ステップ数は、通常のランダム ペアの入力の対数に応じておおよそ増加します。これが、Euclid のメソッドがリスト係数を超えてスケーリングする理由です。
よくある質問
Euclidのアルゴリズムとは何ですか?
ユークリッドのアルゴリズムは、剰余による除算を繰り返して、2 つの非負の整数の最大公約数を求める方法です。ゼロ以外の最後の残りは GCF です。電卓は、これらの各除算ステップを出力します。
Euclid のアルゴリズムはどのようにして GCF を見つけますか?
Euclid のアルゴリズムは、大きい数値を小さい数値で除算した余りで置き換えることによって GCF を求め、余りが 0 になるまで繰り返します。最後の非ゼロ剰余ステップで使用される除数は、GCF です。
816と2260のGCFとは何ですか？
816 と 2260 の GCF は、そのペアに対して Euclid のアルゴリズムを実行し、ステップ テーブルから最後の非ゼロの剰余を読み取ることによって検出されます。このページに両方の整数を入力すると、すべての商と余りが順番に表示されます。
Euclid のアルゴリズムはなぜ機能するのでしょうか?
Euclid のアルゴリズムが機能するのは、a と b の公約数は b と a mod b の公約数でもあるためです。ペアを小さい方の数字と剰余に置き換えると、剰余がゼロになるまで GCF が保持されます。
Euclid のアルゴリズムは何ステップかかりますか?
Euclid のアルゴリズムが実行するステップ数は入力によって異なります。各剰余は前の約数より小さいため、プロセスは有限です。フィボナッチのようなペアは平均よりも多くのステップを必要としますが、一般的な教室の数値はすぐに終了します。
引き算と割り算の違いは何ですか?
減算形式では、大きい方から小さい方を繰り返し減算します。除算形式は、商を使用して一括で減算します。どちらの形式でも同じ GCF が計算されます。割り算は引き算を繰り返すだけでコンパクトに書かれています。
まとめ
Euclid のアルゴリズム計算機は、除算を繰り返すことで GCF を見つけ、すべての商と剰余をステップ テーブルに表示します。 48 や 18 などのペアは、GCF(48, 18) と一致する残り 6 で終了します。減算と除算の形式は、異なる圧縮レベルでは同じアルゴリズムです。剰余は厳密に減少するため、プロセスは常に非負の整数で終了します。