الحساب العودي ل PGCD بلغة C

GCD (القاسم المشترك الأكبر)< / ب> لعددين صحيحين عندما لا يساوي أحدهما على الأقل صفرا هو أكبر عدد صحيح موجب مقسوم يقسم رقمين. على سبيل المثال ، GCD للعددين 45 و 30 هو 15.
1- ابحث عن GCD باستخدام Modulo
قم بتعيين قيمة b إلى a و b قيمة باقي قسمة a على b.< / li>
كرر حتى يصبح الباقي صفرا.< / li>< / ul >
< / a>< / div>

< / div>
مثال: < / div>< / div>
< / a>< / div>البرنامج المقابل في C:

< pre class = "prettyprint lang-c">#include< stdio.h>

int main()
{
int a,b,r,x,y;
do
scanf ("٪d" ، & a);
بينما (a< = 0) ؛
do
scanf ("٪d" ، & b);
بينما (b< = 0) ؛

إذا كان (أ> ب)
{
x=b;
r=a٪b;
}
else
{
x=a;
r=b٪a;
}

while(r!=0)
{
y=x;
x=r;
r=y٪x;
}
printf ("٪d"، x);
العودة 0 ؛
}
2- ابحث عن GCD بطريقة الطرح العودية
إذا كان a و b عددين صحيحين موجبين ، فلدينا الخصائص الحسابية التالية: < / div>
< / a>< / div>
مثال: < / div>
< / a>< / div>

< / div>
برنامج PGCD مع العودية.

< / div>
int PGCD (int a ، int b)
{
if (a = = b)
{
إرجاع a ؛
}
else
{
if (a> (ب) < BR / > إرجاع PGCD (أ - ب ، ب) ؛
else
إرجاع PGCD (أ ، ب - أ) ؛
}
}
المراجع:
ويكيبيديا: القاسم المشترك الأكبر
ويكيبيديا: خوارزمية إقليدس الموسعة