تمرين حلو، لكن ألا ترى لو تجعل العضو يبحث عن أفضل طريقة لحل النشاط بدلا من وضع الطرق؟ البحث يحسّن من قدرة العضو على تحليل أفضل طريقة و تطبيقها. و من خلالها يستطيع الوصول لمصادر جيّدة تساعده في حل مشاكل شبيهه.

بالنسبة لحلي، استخدمت Scala. لغة أتمنى تعلمها بسبب Actors ((خارج نطاق النشاط :) )

object arabia {

  def gcd(x: Int, y: Int): Int = {

    require(x >= 0, "X must be greater than 0")
    require(y >= 0, "Y must be greater than 0")

    def loop(x: Int, y: Int): Int = {
            if ( x == y ) x
            else if ( x > y ) loop(x - y, y)
            else                            loop(x, y - x)
    }

    if ( x.min(y) == 0 ) x.max(y)
    loop(x,y)

  }                                               //> gcd: (x: Int, y: Int)Int

    gcd(198,252)                              //> res0: Int = 18
}

السطر

gcd(198,252) 

ينفذ الدالة

  def gcd(x: Int, y: Int): Int = {

تستقبل x و y و كلهم من نوع Int. و الدالة ترجع قيمة من نوع Int

require(x >= 0, "X must be greater than 0")
require(y >= 0, "Y must be greater than 0")

تتأكد من إن القيمتين دائما أكبر من أو تساوي 0. و تقوم بإرجاع خطأ في حالة أقل من صفر. و هذه دالة موفّرة من نفس اللغة

و الدالة الداخلية

def loop(x: Int, y: Int): Int = {
        if ( x == y ) x
        else if ( x > y ) loop(x - y, y)
        else                            loop(x, y - x)
}

لا تنفذ إلا إذا استدعيت من داخل الدالة gcd. قبل استدعائها، نتأكد من أن القيم لا تساوي الصفر.

if ( x.min(y) == 0 ) x.max(y)

في لغة Scala كل شئ object حتى int. ال class من نوع int يوفر دالة اسمها min و max و ترجع القيمة الأقل و الأعلى. في حالة أحدهم صفر، الدالة gcd سترجع الأعلى. لم أأخذ حالة القيمتين صفر و لكنها وضعها سهل.

إذا القيمتين لم تكن اصفارا، دالة gcd ستستدعي دالة loop الداخلية بإرسال قيم x و y.

دالة loop ستتحقق في كل مرة من شروط اقليدس و هي ثلاث شروط

لغة Scala لا تحتاج إلى return لإرجاع القيمة. لغة Scala تسترجع آخر قيمة تم ذكرها.

احتجت لوضع بعض الشروط خارج loop لأن لا حاجة لها في كل مرة loop تنفذ. بعض حلولكم يمكن تحسينها بفصل بعض الشروط لتنفيذها مرة واحدة بدلا من كل مرة تستدعي فيها دالة gcd

مشاركتي بالجافاسكربت

function gcd(a, b) {
  if (isNaN(a) && isNaN(b)  ) {
    return alert("أدخل رقام من فضلك!");
  }

  if (b === 0) {
    return alert("القاسم المشترك الأكبر هو" + a);
  }
  else if (a === 0) {
    return alert("القاسم المشترك الأكبر هو" + b);
  }
  else if (a > b) {
    remind = a - b;
  }

  else {
    remind = b - a;
  }

  if (b > remind) {
    return gcd(b, remind);
  }
  else {
    return gcd(remind, b);
  }
}

var a = prompt('أدخل الرقم الأول');

var b = prompt('أدخل الرقم الثاني الآ،');

gcd(a,b);

تقوم بإدخال القيم عبر prompt ثم يتأكد الكود من أنّ ما أدخلته هو رقم وليس حرفا، ثم يحسب، لقد استخدمت طريقة الطرح هنا، وقد كتبت هذا الكود منذ وقت طويل عندما كنت أتعلم الجافاسكربت

مثال حي هنا

نشاط جميل، وهذه مشاركتي البسيطة لكن بدون استخدام أحد الطريقتين المذكورتين.

اللغة المستخدمة Java

public static void main(String[] args) {

    int a,b,k;
    a = 252;
    b = 198;

    k = a;
    if(a > b) k = b;

    while(k > 0){
        if(a % k == 0 && b % k == 0){
            System.out.println(k);
            break;
        }
        k--;
    }               
}

هذه هي الطريقة التي اتبعتها، باستعمال C++ واعتقد انه بسيط كفاية.

int GCD(int &m, int &n)

{

int r;
if (m < 0 || n < 0)
{
    cout << "No Negative numbers allowed!" << endl;
    return -1;  // indicates failure.
}

else if (m == 0 && n != 0)
{
    return n;
}

else if (n == 0 && m != 0)
{
    return m;
}

else if (m == 0 && n == 0)
{
    cout << "Math Error" << endl;
    return -1;
}

else if (m == n)
{
    return m;
}

else if (n > m)      // checks if n is larger than m.
{
    int temp = n;
    n = m;
    m = temp;
}

while (n != 0)
{
    r = (m%n);
    m = n;
    n = r;
}
return m;

}

قد يكون هنالك مساحة كبيرة من التحسين او تسريع الكود لكني لم افعل ذلك حينها.

أنظر ياعزيزي لست جيداً بالرياضيات ابداً، ولكن بعد ما ابيضّت اخر شعرة سوداء في رأسي خرجت بهذا الناتج، قم بتجربته واخبرني اذا كان صالحاً او لا اذا كان صالحاً سوف اشرحه. انا اختبرته على المدخلات السابقة وكان الناتج صحيحاً واذا احببت ان اترجمة لأي لغة برمجة اخرى أعرفها سأفعل، قمت بعمل الدالة بلغة C++

    int commonDenominator(int x,int y){

        if(((x>y)?x:y) - ((x>y)?y:x) == 0)
            return (x<y)?x:y;
        else
            return commonDenominator(((x>y)?y:x), ((x>y)?x:y) - ((x>y)?y:x));
    }

الخوارزميتين بلغة بايثون

أسهل ما يكون

def gcd1(a, b):
    while b !=0:
        t = b
        b = a % b
        a = t
    return a

def gcd2(a, b):
    while a != b:
        if a>b: a=a-b
        else: b=b-a
    return a


print gcd2(100, 150)

يمكن صياغة طريقة اقليدس كما يلي

القاسم المشترك الأكبر : بتكرار قسمة المقسوم عليه على باقي القسمة ... قبل الوصول للصفر

مثال 252 و 198

فتقسم العدد الأول ولا يهم ان كان الاكبر [1] ولكن سنسخدمه اي 252

نقسمه 252 على الثاني 198 يكون الباقي 54

ثم نقسم المقسوم عليه السابق اي 198 على الباقي السابق 54 فيكون الباقي 36

ثم نقسم المقسوم عليه السابق اي 54 على الباقي السابق 36 فيكون الباقي 18

ثم نقسم المقسوم عليه السابق اي 36 على الباقي السابق 18 فيكون الباقي 0

اذا القاسم المشترك الأكبر : 18

فدائما ما نحتاج المقسوم عليه مرتين مرة مقسوما عليه ومره هو نفسه مقسوم على باقي سابق فاذا سمينا المقسوم divided و المقسوم عليه reminder

فيمكننا كتابة التالي

divided=252  reminder=198 ->
divided=198  reminder=54 ->
divided=54  reminder=36 ->
divided=36  reminder=18 ->
divided=18  reminder=0 

أو

gcd(x, y):
  divided = x
  reminder = y
  while reminder not equal 0:
    temp = reminder
    reminder = divided % reminder
    divided = temp

فيكون الكود بالبايثون

def gcd(divided, reminder):
    while reminder: 
        temp = reminder
        reminder = divided % reminder
        divided = temp
    return divided

و يمكن اختصاره للتالي

def gcd(divided, reminder):
    while reminder:
        divided, reminder = reminder, divided % reminder
    return abs(divided)

لماذا اضيفت دالة القيمة المطلقة؟ لانه بالنهاية ان امكنك القسمة على رقم سالب بدون باقي فيمكنك القسمة على نفس الرقم بالموجب واي رقم موجب اكبر من اي رقم سالب

[1] لماذا لا يهم اسخدام الرقم الاكبر كبداية؟

لانه حين تقسم العدد الاصغر على الاكبر سيكون باقي القسمة هو الرقم نفسه. وفي الخطوة التالية ستقسم المقسوم عليه وهو في هذه الحالة الرقم الاكبر على الباقي اي الرقم الأصغر :) كما لو كنت بدأت بقسمة الاكبر

recursive approach

int gcd(int p, int q) {
    if (q>0)
        return gcd(q, p%q);

    return p;
}