Program C++ untuk mengira faktor sepunya terbesar

Faktor sepunya tertinggi atau pembahagi sepunya terbesar ialah faktor yang boleh membahagi dua atau lebih nilai secara serentak tanpa menghasilkan sebarang baki. Dalam artikel ini, kita akan membincangkan beberapa cara untuk melaksanakan HCF/GCD bagi dua nombor dalam C++.

Ini hanyalah penyelesaian matematik, terdapat beberapa algoritma untuk mencari pembahagi sepunya yang paling hebat. Kaedah Euclidean ialah cara biasa untuk mencari pembahagi sepunya terbesar. Kami akan menggunakan algoritma yang sama dalam mod berulang dan rekursif.

Gunakan kaedah berulang

Penyelesaian lelaran Euclidean untuk mencari pembahagi sepunya terhebat ditunjukkan dalam bahagian algoritma.

Algoritma

• Ambil dua nombor a dan b sebagai input.
• Jika a sama dengan 0, kembalikan b.
• Jika b ialah 0, kembalikan a.
• Apabila a dan b tidak sama, lakukan operasi.
  • Jika a > maka a := a – b.
  • Jika tidak b := b - a.
• Tamatkan gelung.
• Kembalikan faktor sepunya terbesar sebagai pembolehubah a.

Contoh

#include <iostream>
using namespace std;

int solve( int x, int y) {
   if (x == 0)
      return y;
   else if (y == 0)
      return x;
   while (x != y) {
      if (x > y)
         x = x - y;
      else
         y = y - x;
   }
   return x;
}

int main( int argc, char* argv[] ) {
   cout << "HCF of two numbers 12 and 72 is: " << solve(12, 72) << endl;
   cout << "HCF of two numbers 18 and 13 is: " << solve(18, 13) <<   endl;
   cout << "HCF of two numbers 117 and 96 is: " << solve(117, 96) << endl;
   cout << "HCF of two numbers 85 and 15 is: " << solve(85, 15) << endl;
}

Output

HCF of two numbers 12 and 72 is: 12
HCF of two numbers 18 and 13 is: 1
HCF of two numbers 117 and 96 is: 3
HCF of two numbers 85 and 15 is: 5

Gunakan kaedah berulang

Kaedah Euclidean yang sama boleh dilaksanakan menggunakan kaedah rekursif. Di bawah ini kami menerangkan definisi kaedah rekursif, algoritma yang ditunjukkan di bawah.

Algoritma

• Tentukan fungsi yang dipanggil HCF yang menerima dua nombor a dan b.
• Jika a ialah 0, kembalikan b
• Jika tidak, kembalikan HCF( b mod a, a)

Contoh

#include <iostream>
using namespace std;

int solve( int x, int y) {
   if (x == 0)
      return y;
   return solve( y % x, x );
}

int main( int argc, char* argv[] ) {
   cout << "HCF of two numbers 12 and 72 is: " << solve(12, 72) << endl;
   cout << "HCF of two numbers 18 and 13 is: " << solve(18, 13) << endl;
   cout << "HCF of two numbers 117 and 96 is: " << solve(117, 96) << endl;
   cout << "HCF of two numbers 85 and 15 is: " << solve(85, 15) << endl;
}

Output

HCF of two numbers 12 and 72 is: 12
HCF of two numbers 18 and 13 is: 1
HCF of two numbers 117 and 96 is: 3
HCF of two numbers 85 and 15 is: 5

Kesimpulan

Mencari faktor sepunya terbesar atau pembahagi sepunya terbesar adalah sangat berguna apabila menyelesaikan masalah matematik yang berbeza. Ia boleh dikira menggunakan kaedah Euclidean. Kaedah ini boleh digunakan secara berulang atau rekursif. Di sini kami menunjukkan dua kaedah. Sebaliknya, kita boleh mengira GCD/HCF melalui gandaan sepunya terkecil (LCM). GCD dan LCM bagi dua nombor adalah sama dengan hasil darab dua nombor itu. Jadi, mengikut prinsip ini, jika kita mengetahui LCM dan hasil darab kedua-dua nombor ini, kita boleh mengira GCD dengan mudah.

Atas ialah kandungan terperinci Program C++ untuk mengira faktor sepunya terbesar. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!