مرحبا وأهلا بكم،
في الأسبوع الماضي طرحت نشاط صنع خوارزمية، وبعد طرح النشاط بدقائق، اكتشفت أني ارتكبت بعض الأخطاء الجسيمة
https://arabia.io/go/4733منها، النشاط كان صعبا جدا، كتابة خوارزمية الميراث امر معقد جدا، ويحتاج دقة بالغة وعددا كبيرا من المدخلات، وأيضا، كان من المفروض أن نبدأ بشيء بسيط
والثاني هو أني لم أوفر شرحا عن كيف ستعمل الخوارزمية
لذا هذه المرة قررت عمل شيء أكثر بساطة، مع توفير شرح بالطبع
القاسم المشترك الأكبر
هو شيء تعلمناه في الرياضيات، وعادة يستعمل لصنع خوارزميات، الهدف من النشاط هو إيجاد القاسم المشترك الأكبر انطلاقا من مُدخلين
مما يعني أن الدالة تقبل 2 input وتطرح 1 output
لحساب القاسم المشترك هناك طريقتين
الأول باستعمال خوارزمية اقليدس
في حال نسيتم كيف يتم حسابه، فالأمر كالتالي
(سأشرح مثال ويكيبيديا)
لدينا عدد ما، فنقل 252 وعدد آخر 198، ونريد أن نحسب القاسم المشترك الأكبر لهما،
نقوم أولا بقسم 252 على 198 لنجد باقي القسمة، ولنسمه العدد c، ثم نقوم مجددا بقسم العدد الأصغر من مدخلات البداية (وهو 198) على باقي القسمة الجديدة لنجد عدد آخر، ثم نقسم هذا العدد أيضا على العدد السابق (c) ونستمر بالأمر حتى نجد باقي القسمة يساوي 0، بهذا، فإن باقي القسمة التي أتى قبله هو القاسم المشترك الأكبر
مثال ويكي
القاسم المشترك الأكبر للعددين 252 و 198:
252 = 198 * 1 + 54 ‘ أربع وخمسون هو باقي قسمة 252 على 198
فنجد القاسم المشترك للعددين 198 و 54
198 = 54 * 3 + 36 ‘ ست وثلاثون هو باقي القسمة.
نكرر العملية هذه المرة مع : 54 و 36
54 = 36 * 1 + 18
مرة أخرى : 36 = 18 * 2 + 0
هنا وصلنا للصفر فيكون العدد الثاني 18 هو القاسم المشترك الأكبر.
الطريقة الثانية
طريقة الطرح
وهي أن تقوم بطرح العدد الأصغر من الأكبر لتحصل على ناتج، ثم تطرحه من العدد الأصغر في البداية وتقوم بالأمر حتى تجد النتيجة صفر، أي عندما يساوي a = b وعندها ذلك هو القاسم المشترك
252 - 198 = 54
198 - 54 = 144
144 - 54 = 90
90 - 54 = 36
36 - 18 = 18
18 - 18 = 0
والقاسم المشترك هو 18
تستطيعون استعمال أيّ طريقة تريدونها ما دامت النتيجة ستكون واضحة،
وبالطبع بأي لغة محببة لكم،
سأطرح أنا مثالي في الرد الأول وهو باستخدام الجافاسكربت
بالتوفيق
هذه هي الطريقة التي اتبعتها، باستعمال 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#:
public static double GCD(double m,double n)
{
double r;
if (m == 0 || n == 0)
{
if (m == n)
{
return -1;
}
else if (n != 0)
{ return n; }
else if (m != 0)
{ return m; }
}
else if (m < 0 || n < 0)
{
return -1;
}
else if (n > m)
{
double temp = n;
n = m;
m = temp;
}
while (n != 0)
{
if (m == n)
{ break; }
r = (m % n);
m = n;
n = r;
}
return m;
}
بهذه الطريقة لن يضيع وقته (ان صح التعبير) في المقارنة بعكس مثالي للـ C++ فمثلاً ان كان كلا الرقمين صفر فسيضطر سابقاً للمقارنة مرتين اضافيتين، بينما ان لم يكن صفراً من الاساس فلديه طريق طويل قليلاً من المقارنات، ما فعلته في هذا التحديث البسيط قد لا يكون بالكثير، لكني دائماً احاول تحسين اداء البرنامج بقدر ما تسمح لي خبرتي المتواضعة (مازلت مبتدئاً). وشكراً لطرحك النشاط المسلي، كنت افضل ان تدع لنا البحث عن افضل طريقة ممكنة.
قد لا افهم تماماً ما تقصد (لاني لست محترفاً)، لكن في الC# (سي شارب، ليس سي) القواعد محكمة قليلاً فيما يتعلق بأنواع البيانات، فلا يمكنني اعادة False لأي نوع غير الـ bool (في ضوء ما تعلمته حتى الآن)، فأعادة قيمة مثلاً مثل -1 كنوع من التنبيه او التحذير والتي من خلالها سأعلم ان هنالك مشكلة في المدخلات، -1 ببساطة وكما اعتقد انك تعرف وهذا من سؤالك، هي مجرد قيمة مستحيل ان تظهر في الظروف الصحيحة، لا يوجد عددين قاسمهم المشترك -1(على حد علمي)، لكني لا استعملها لكونها تعني false في لغة الـ C، مجرد قيمة مميزة.
التعليقات