QuickCalculators menjalankan algoritma Euclid pada dua integer bukan negatif, mencetak setiap hasil bagi dan baki sehingga PBB muncul sebagai baki bukan sifar terakhir. Masukkan pasangan dalam mana-mana tertib; jadual langkah menunjukkan bentuk pembahagian supaya setiap baris boleh disemak dengan tangan.
Cari PBB dengan pembahagian berulang
Algoritma Euclid mencari faktor sepunya terbesar dengan membahagikan nombor yang lebih besar dengan yang lebih kecil dan menggantikan yang lebih besar dengan baki, kemudian mengulangi. Apabila baki sifar muncul, pembahagi daripada langkah itu ialah PBB. Kalkulator Algoritma Euclid merekodkan setiap bahagian supaya rantaian boleh diaudit.
Untuk 816 dan 2260, mulakan dengan 2260 ÷ 816. Hasil bagi ialah 2 dan bakinya ialah 628. Seterusnya, 816 ÷ 628 meninggalkan baki 188. Teruskan sehingga baki sifar menghentikan rantai. Baki bukan sifar akhir ialah PBB bagi pasangan asal.
Baca jadual langkah
Jadual langkah menyenaraikan dividen, pembahagi, hasil bagi dan baki untuk setiap pusingan. Membaca ke bawah lajur baki menunjukkan urutan pengecutan yang berakhir pada sifar. QuickCalculators menjajarkan lajur tersebut supaya salinan buku nota boleh mengesahkan × b + r sama dengan dividen terdahulu pada setiap baris.
Lakaran padat untuk 48 dan 18: | Dividen | Pembahagi | Quotient | Baki | | --- | --- | --- | --- | | 48 | 18 | 2 | 12 | | 18 | 12 | 1 | 6 | | 12 | 6 | 2 | 0 |
Baki bukan sifar terakhir ialah 6, jadi PBB(48, 18) = 6.
Elakkan kesilapan biasa ini
Bentuk tolak dan bentuk bahagi adalah algoritma yang sama. Pembahagian ialah penolakan berulang yang dimampatkan menjadi satu hasil bahagi. Pelajar kadangkala menganggap mereka sebagai kaedah saingan dengan jawapan yang berbeza. Kedua-duanya ditamatkan pada PBB yang sama apabila digunakan dengan betul. Menolak 18 daripada 48 dua kali mencapai 12, iaitu betul-betul apa yang dikodkan oleh 2 dalam satu baris.
Mengutamakan bahagian menjimatkan penulisan tanpa mengubah laluan matematik yang diterangkan oleh Euclid.
Fahami mengapa algoritma sentiasa ditamatkan
Setiap baki ialah integer bukan negatif yang lebih kecil daripada pembahagi sebelumnya, jadi jujukan baki tidak boleh turun selama-lamanya. Turun terhingga memaksa baki sifar selepas banyak langkah terhingga. Jaminan itu berlaku untuk semua input integer bukan negatif yang diterima oleh halaman.
Pasangan kes terburuk yang berkaitan dengan nombor Fibonacci memerlukan lebih banyak langkah daripada contoh bilik darjah biasa, namun masih selesai. Kiraan langkah berkembang secara kasar dengan logaritma input untuk pasangan rawak biasa, itulah sebabnya kaedah Euclid menskalakan faktor penyenaraian yang lalu.
Soalan lazim
Apakah algoritma Euclid?
Algoritma Euclid ialah kaedah untuk mencari faktor sepunya terbesar bagi dua integer bukan negatif dengan pembahagian berulang dengan baki. Baki bukan sifar terakhir ialah PBB. Kalkulator mencetak setiap langkah pembahagian tersebut.
Bagaimanakah algoritma Euclid mencari PBB?
Algoritma Euclid mencari PBB dengan menggantikan nombor yang lebih besar dengan baki selepas pembahagian dengan nombor yang lebih kecil, berulang sehingga bakinya adalah sifar. Pembahagi yang digunakan dalam langkah bukan-sifar terakhir ialah PBB.
Apakah PBB bagi 816 dan 2260?
PBB bagi 816 dan 2260 ditemui dengan menjalankan algoritma Euclid pada pasangan itu dan membaca baki bukan sifar terakhir daripada jadual langkah. Masukkan kedua-dua integer pada halaman ini untuk melihat setiap hasil bagi dan baki mengikut urutan.
Mengapa algoritma Euclid berfungsi?
Algoritma Euclid berfungsi kerana mana-mana pembahagi sepunya a dan b juga merupakan pembahagi sepunya bagi b dan mod b. Menggantikan pasangan dengan nombor yang lebih kecil dan bakinya mengekalkan PBB sehingga bakinya mencecah sifar.
Berapa banyak langkah yang diambil oleh algoritma Euclid?
Bilangan langkah yang diambil oleh algoritma Euclid bergantung pada input; setiap baki adalah lebih kecil daripada pembahagi sebelumnya, jadi prosesnya adalah terhingga. Pasangan seperti Fibonacci memerlukan lebih banyak langkah daripada purata, tetapi nombor bilik darjah biasa selesai dengan cepat.
Apakah perbezaan antara bentuk tolak dan bahagi?
Bentuk penolakan berulang kali menolak yang lebih kecil daripada yang lebih besar; bentuk bahagi menolak secara pukal menggunakan hasil bahagi. Kedua-dua borang mengira PBB yang sama. Pembahagian hanyalah penolakan berulang yang ditulis padat.
Ringkasan
Kalkulator Algoritma Euclid mencari PBB dengan pembahagian berulang dan menunjukkan setiap hasil bagi dan baki dalam jadual langkah. Pasangan seperti 48 dan 18 berakhir pada baki 6, sepadan dengan PBB(48, 18). Bentuk penolakan dan pembahagian adalah algoritma yang sama pada tahap pemampatan yang berbeza. Baki berkurangan dengan ketat, jadi proses sentiasa ditamatkan untuk integer bukan negatif.