38

اكواد ذكية: امثلة على دوال كتبت بطريقة مختصرة وذكية

تعجبني جداً الشفرة البرمجية المختصرة ذات الاسطر القليلة والمؤدية للغرض، قد لايهتم كثير من المبرمجين في شكل الشفرة البرمجية سواء كانت طويلة او قصيرة يهمه فقط انها تؤدي غرضها. بالنسبة لي اشبّه لغة البرمجة باللغة البشرية من ناحية كل ناطق بها له اسلوب مختلف عن الاخر، وانا احب الاسلوب المختصر الهادف. بالطبع لغة البرمجة ليست لتنطق ولكن هو مجرد تمثيل.

علماً بأن هناك فوائد عائدة على البرنامج من خلال الشفرة البرمجية المختصرة؛ فهي تتعامل بلطف أكثر مع الذاكرة والمعالج.

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

عموماً هذا الفصل اعجبني كثيراً فيه طرق لكتابة الشفرة البرمجية عجيبه احب ان اطرح لكم اشهرها واسهلها.

ذات مره طلب المحاضر برمجة دالة (الأسس) للاعداد الصحيحة الموجبة. فمت بكتابتها كا التالي:

    int pwr2(int b,int x){
    int c = b;

    for(x; x>1; x--)
        b *= c;

    return b;
}

وفرحت عندما كانت النتائج سليمة ولم اكن اتوقع ان هناك شفرة اكثر اختصاراً منها.

وتفاجأت بشفره اخرى واردة بالمنهج عجيبة وهي تستخدم اسلوب ريكيرجن (Recursion) الذي ذكرته سابقا وكانت بالشكل التالي:

int pwr(int b, int x){
    if(x != 1)
       return b*pwr(b,x-1);
}

برمجة هذه الدالة ذكية، صحيح ان الدالة ليست ذكيه فهي لاتتعامل مع الارقام الأقل من 1 ولكنها مجرد سطرين ! وبرمجتها ذكية ورائعة.

ايضاً هناك الفكتوريال ( مضروب العدد ): فـ 5! = 5 × 4 × 3 ×2 تساوي 120

هنا كان تخميني صحيحاً فهكذا ظهرت معي الدالة.

int fact(int n){
    if(n != 1)
        return n*fact(n-1);
}

حسناً سأشرح المثال السابق عملية Recursion هي مشابهة نوعاً ما لعمليات التكرار مثل while,for لكن عمليات التكرار تبداء من نقطة وتنتهي بنقطة اخرى بينما Recursion تبداء بنقطة وتنتهي بنفس النقطة التي بدأت منها. أي رحلة ذهاب واياب :))

في المثال السابق لنفترض ان المدخل كان 5 ستظهر لنا النتيجة 120 بالخطوات التالية:

  • ذهاب الخطوة الاولى: يضرب خمسة بناتج اياب الخطوة الثانية ويطرح واحد من الرقم خمسة ويرسله لـذهاب الخطوة الثانية.
  • ذهاب الخطوة الثانية: يضرب أربعة بناتج اياب الخطوة الثالثة ويطرح واحد من الرقم اربعة ويرسله لـذهاب الخطوة الثالثة.
  • ذهاب الخطوة الثالثة: يضرب ثلاثه بناتج اياب الخطوة الرابعة ويطرح واحد من الرقم ثلاثة ويرسله لـذهاب الخطوة الرابعة.
  • ذهاب الخطوة الرابعة: يضرب اثنين بناتج اياب الخطوة الخامسة ويطرح واحد من الرقم اثنين ويرسله لـذهاب الخطوة الخامسة
  • ذهاب الخطوة الخامسة: يجد ان الرقم واحد وهو لايستوفي الشرط لذلك لا يحجز لرحلة ذهاب اخرى :))
  • أياب الخطوة الرابعة: لايجد مردود من ذهاب الخطوة الخامسة ويعود برقم اثنين.
  • أياب الخطوة الثالثة: كان رقم ثلاثه في صالة الانتظار ! وتعود الخطوة الرابعة حاملة رقم اثنين وتضرب بـ 3 وتكون النتيجة 6
  • أياب الخطوة الثانية: كان رقم أربعه في صالة الانتظار وعادت الخطوة الثالثة تحمل الرقم 6. عندما نضرب رقم 6 بـ 4 تكون النتيجه 24
  • اياب الخطوة الأولى: كان رقم خمسة في صالة الانتظار وعادت الخطوة الثانية تحمل الرقم 24 لتضرب بالرقم خمسة وتكون النتيجه النهائيه 120

Tower Of Hanoi:

وعند بحثي ايضاً وجدت لعبة جميلة جداً وبسيطة ايضاً. قرأت عنها في كتاب محاضر اخر وكانت ممتعة ولكن هناك دالة Recursion ربما تكون افسدت متعة اللعبة. اللعبة اسمها Tower of Hanoi وهذا رابطاً لها هي ممتعه يمكنك تجربتهاً

http://www.mathsisfun.com/g...

اللعبة عبارة عن ثلاث أبراج وفي البرج الاول هناك عدد طبقات كل طبقة اكبر من الاخرى. مهمتك هي نقل الطبقات من البرج الاول الى البرج الثالث بنفس الترتيب بقوانين بسيطه وهي كا التالي: لا تستطيع نقل طبقة فوقها طبقة اخرى، ولا تضع طبقة فوق طبقة اصغر منها. الابداع هنا ان تنقل كل الطبقات الى البرج الثالث في خطوات اقل ووقت اقصر. والتحدي كل ما يزيد عدد الطبقات، فهي تبدأ من ثلاثة طبقات واتوقع ثلاثة طبقات سهله. تبداء صعوبتها عندما يكون عدد الطبقات اكثر من 5. الرابط السابق لايسمح لك باللعب بأكثر من 6 طبقات ولكن ستة طبقات ايضاً صعبة.

جرب اللعبة وقلي ما رأيك ؟ هل يمكن برمجة دالة تساعدك على معرفة نقل الـ 10 طبقات الى البرج الثالث بأقل خطوات ممكنة ؟ اذا كان الجواب نعم، كم تتوقع عدد الاسطر في هذه الدالة ؟ عدد الاسطر ! حسناً هي مجرد 7 اسطر.

void TowerOfHanoi(int n, string source, string temp, string destination, int& i){
    if(n ==1)
        cout << ++i << ": Move disk " << n << " from " << source << " to " << destination << endl;
    else{
        TowerOfHanoi(n - 1, source, destination, temp,i);
        cout << ++i << ": Move disk " << n << " from " << source << " to " << destination << endl;
        TowerOfHanoi(n - 1,temp , source, destination,i);
    }
}

واستخدامها يكون بالشكل التالي: int i = 0; TowerOfHanoi(3, "Tower1", "Tower2", "Tower3",i);

المدخلات التي تطلبها الدالة: 1. عدد الطبقات. 2. اسم افتراضي للبرج الاول 3. اسم افتراضي للبرج الثاني 4. اسم افتراضي للبرج الثالث 5. متغير رقمي تكون قيمته 0 ليظهر عدد الحركات

هذه الداله سترشدك كيف تحل لعبة Tower Of Hanoi بأقل خطوات ممكنة حتى لو كان عدد الطبقات 20 ! فكرة كتابة الدالة عظيمة. في بداية الموضوع مثّلت لغة البرمجة باللغة العادية ولكل مبرمج اسلوبه. مبرمج هذه الداله وصل لمرحلة الفلسفه :))

فلسفة هذه الدالة:

اذا استطعت ان تحل ذات الثلاث طبقات يعني انك تستطيع حل ذات الاربع. كذلك يمكنك حل ذات الخمس طالما تستطيع حل ذات الاربع .. الخ !

تحليل رياضي للعبة Tower Of Hanoi قد يفيدك لفهم واستيعاب عمل الدالة:

  • اذا كان هناك طبقة واحده على البرج، عدد الخطوات 1 سيكون كا التالي

    ((2^1) -1 )

  • اذا كانت هناك طبقتين على البرج، عدد الخطوات 3 تحسب كا التالي:

    ((2^2) -1)

  • اذا كانت ثلاث طبقات .... عدد الخطوات 7:

    ((2^3) -1)

  • اذا كان هناك n طبقات على البرج عدد الخطوات تحسب كا التالي:

    (2^n) - 1

ملاحظة: الشفرات السابقة كتبتها بلغة C++ ،ايضاً اعدت كتابة دالة Tower Of Hanoi مرة اخرى بلغة PHP وباللغة العربية ليستفيدوا الجميع.

  function TowerOfHanoi($n, $source, $temp, $destination, & $i){

  if($n == 1)
    echo ++$i.": حرك الطبقة ".$n." من ".$source." إلى ". $destination."<br>";
  else{
    TowerOfHanoi($n -1, $source, $destination, $temp, $i);
    echo ++$i.": حرك الطبقة ".$n." من ".$source." إلى ". $destination."<br>";
    TowerOfHanoi($n -1,$temp, $source, $destination, $i);
  }
}

استخدام الدالة كالتالي:

  $i = 0;
  echo TowerOfHanoi(3,"البرج الأول","البرج الثاني","البرج الثالث",$i)

المدخل الاول هو عدد الطبقات.

قد لايحب شخص النوع هذا من الدوال ويعتبره بلا فائدة، بالعكس هي مفيدة جداً وممارستها يحسن مهاراتنا في كتابة الشفرة البرمجية.

اتمنى تكون المشاركة مفيدة.

دمتم،؛

يرجى الدخول لحسابك أو تسجيل حساب لتستطيع إضافة تعليق
حساب جديد دخول

التعليقات

16
عبد الرحمن أحمد

هذه العملية نطلق عليها التعاودية أي أن الدالة تعيد استدعاء نفسها من داخلها و هناك شرط لتحقيق نقطة العودة خلفا لإنهاء التكديس

وهذه تستخدم في كثير من المجالات

منها التي ذكرتها بالأمثلة أعلاه

وتستخدم بكثرة في البنى الهرمية Structure Hierarchical مثل الأشجار Tree Structure والتي لها صفة تشابه الفروع مع الأصل

بمعنى أن كل فرع من الشجرة هو شجرة أيضا جذرها تلك العقدة التي وصلنا لها

ولهذا تستخدم التعاودية في مسح أو زيارة أفرع الشجرة

طبعا للتعاودية شروط صارمة حتى لا نقع في حلقة مفرغة أو حركة استدعاء دائرية ويحصل خطأ طفحان المكدس Stack Overflowبحيث يجب أن تكون السلسلة التي نعاود الاستدعاء من أجلها أن تكون منتهية

ويجب تضمين شرط الانتهاء بحيث تكون نقطة العودة من آخر استدعاء وصلنا إليه

ولاحظ في الأمثلة أعلاه شروط العودة إما وصول القيمة إلى 1 و طبيعة الدالة تضمن الوصول إلى هذه القيمة لأنها في كل مرة تنقص بمقدار واحد

وطبعا الشرط يجب أن يكون أصغر وليس يساوي فقط

لأنه لو أدخلنا عدد سالب لأصبحت السلسلة غير منتهية لأنها ستنقص إلا أن يمتلئ المكدس

في زيارة الشجرة يكون شرط الانتهاء هو عدم وجود أولاد أو أفرع للعقدة التي وصلنا إليها أي أنها ورقة وتمثل نهاية الفرع.

2
عبد الرحمن أحمد

بالمناسبة منذ أيام كتبت موضوع عن التعاودية الثنائية أي أن يكون أجراءات يتسدعيان بعضهما البعض بشكل تبادلي

وكيف يمكن الحماية من الاستدعاء غير المنتهي

في حال لم يكن هناك شرط عودة ضمني

طريقة : لحل مشكلة الاستدعاء التبادلي بين الإجراءات https://arabia.io/go/4771

2
راشد المري

احسنت اصغر من 2 افضل من يساوي 1

تحتوي الدوال المكتوبه بستخدام اسلوب Recursion الى عاملان اساسيان هما.

  • Base case: وهو الجزء الذي تتوقف عنده الداله ( تبداء رحلة العودة ) مثل الشرط الموجود.

  • Recursive case: وهو الجزء الذي فيه تكمل الدالة رحلة الذهاب.

14
billal em

شيء جميل بالفعل ... الأمثلة التي وضعتها كلها تدرس عادتا دروس مبادئ الخوارزميات ... لكن جعل الشيفرة مختصرة وغير سهلة القراءة في بعض الحالات قد يحدث لك مشاكل في ما بعد وبالخصوص إذا لم تضع تعليقات في الكود تصف وبشكل دقيد المهمة التي تقوم بها هذه الأكواد المختصرة ... وأن تكون مختصرة لا يعني أنها لا تستهلك موارد الجهاز عند تنفيذها .

15
راشد المري

احسنت نقطة التعليقات وتوضيح الداله مهمة جداً درسنا عن ذلك نقطتين مهمتان يفضل شرحهما بشكل تعليقات لكل داله هما:

  • pre-condition: وهو مدخلات الداله.

  • post-condition: الناتج الذي ترجعه الدالة.

مثال:

    /**
    * Pre-condition: base, exponent.
    * Post-condition: Result of base power exponent.
    *****/
    int pwr(int b, int x){
        if(x != 1)
           return b*pwr(b,x-1);
    }

شكراً لك

2
Ah_Asmar

ذكرتني بأيام الجامعة حيث درسنا عملية تحويل تابع عودي إلى تابع عادي باستخدام المكدسات stacks لكن رغم أن التابع الناتج أفضل من حيث التنفيذ إلا أن التابع العودي أوضح و أفضل من ناحية هندسة البرمجيات

2
راشد المري

احسنت هذا في قسم data structure،

هناك الـ queue و stack وكثير ماتوجد امثله على Recursion بها مثلا دالة Print

    void print(node* head){
        node* curr = head;
        if(curr != NULL)
        {
            cout << curr->info << endl;
            curr = curr->next;
            print(curr);
        }
    }

شكراً لك :))

2
wgh

علماً بأن هناك فوائد عائدة على البرنامج من خلال الشفرة البرمجية المختصرة؛ فهي تتعامل بلطف أكثر مع الذاكرة والمعالج.

حقيقةً هذه معلومة خاطئة, لكنها منتشرة عند كثير من المبرمجين :3

اي الكودين اخف على المعالج ؟ ويقوم بعمليات حسابية اقل ؟

// code 1
for(int i=0; i<=10; i++) {
    cout << "Hello";
}

// code 2
cout << "Hello";
cout << "Hello";
cout << "Hello";
cout << "Hello";
cout << "Hello";
cout << "Hello";
cout << "Hello";
cout << "Hello";
cout << "Hello";
cout << "Hello";

كما ان استخدام ال Recursion غير مفضل, لما يستهلكه من موارد ويسبب بطئ في التنفيذ

في اخر مشروع لي, استخدامي لل Recursion كان قاتلاً, واضررت الى استبداله بل Iteration

1
راشد المري

صدقت اخي WGH المعلومة التي سبق طرحتها في الموضوع كانت خاطئة ليتني استطعت استبدالها بايجابيات وسلبيات الاستدعاء الذاتي (recursion):

حسناً يمكنني طرحها هنا:

الإيجابيات:

  • بالرغم من أن في غالب الاحيان، تستطيع حل المشكلة البرمجية بدون Recursion (الاستدعاء الذاتي) ولكن في بعض الاحيان استخدام Recursion (الاستدعاء الذاتي) لابد منه. مثلاً، سوف تحتاج للاستدعاء الذاتي (Recursion) لصناعة برنامج يعرض قائمة من جميع ملفات النظام.

  • عملية الاستدعاء الذاتي (Recursion) هي جداً مرنة عند برمجة بنية بيانات (Data structure) مثل Stacks، Queue, Linked-list أو الفرز السريع (quick sort).

  • وبالتأكيد هو يقلل من عدد اسطر الشفرة البرمجية.

السلبيات:

  • يتطلب مساحة تخزين اضافية، يتم تخزين المتغيرات والاستدعاءات على المكدس، وفي كل رحلة ذهاب وإياب يتم تخصيص ذاكرة جديدة للمتغيرات ذات نفس الاسم.

  • إذا نسي المبرمج كتابة شرط الخروج (base/exit case) سوف تصبح رحلة الذهاب مستمره بلا عودة، ويضر ذلك بالذاكرة ويضطر المستخدم لمحاولة فورية لإيقاف البرنامج.

  • الاستدعاء الذاتي (Recursion) ليست سريعة في التنفيذ، أي لاينصح المبرمج بستخدامها إذا كانت هناك حلول اخرى.

المصدر:

http://my.safaribooksonline...

شكراً لك WGH افدتني واستفاد منك الجميع.

2
alsadi

الاستدعاء الذاتي Recursion يساهم في حل الكثير من المسائل المعقدة وأشهرها tower of Hanoi كما ذكرت وعيبه هو أنه يستهلك من المكدس stack ويمكن تحويل كل دالة من هذا الأسلوب إلى الحلقة العادية بعد فهم الطريقة (تذكر مبدأ المسطح أفضل من المتداخل flat is better than nested).

هناك الكثير من الأشياء الجميلة التي تسهل فهم الأشياء خصوصا في بايثون مثلا ال generators أو yield مثلا دالة cycle تعيد سلسلة لا نهائية ناتجة من تكرار المتسلسلة التي تعطيه إياها http://docs.python.org/2/li...

مثلا

itertools.cycle([1,10,2])

تعيد سلسلة لا نهائية عبارة عن 1 ثم 10 ثم 2 ثم تعود من جديد 1 ثم 10 ثم 2 ...

yield تعمل مثل return لكن لا تخرج من الدالة وتعود لتسير من حيث توقفت عندما يطلب العنصر التالي

يمكن استعمال الأمر السابق للحصول على سلسلة لا نهائية من الأعداد الأولية وكل ما نحصل على عدد نعمل له yield وليس return ومن يريد طباعتها يمكنه أن يعمل itertools.islice

http://www.macdevcenter.com...

أيضا من الأساليب الجميلة هي الدالة التي تعيد دالة أخرى وهو ما يعرف باسم higher order functions أو wrappers أو decorators

وهناك ما هو أجمل من ذلك مفهوم ال stackless أو ال co-routines وهي تشبه عملية yield لكن ليس بالضرورة أن تكون بين نفس الدالتين

أما أجمل ما رأيت لتبسيط الكود غير المتزامن هو ما يعرف بالوعود promise

https://arabia.io/webdev/4458

getJSON('story.json').then(function(story) {
  return getJSON(story.chapterUrls[0]);
}).then(function(chapter1) {
  addHtmlToPage(chapter1.html);
}).catch(function() {
  addTextToPage("Failed to show chapter");
}).then(function() {
  document.querySelector('.spinner').style.display = 'none';
});
1
ahmed.alshakh

من أجمل الخوارزميات. تبديل قيم متغيرين بدون تعريف متغير ثالث باستخدام العملية XOR. اسمها XOR swap algorithm.

ما أعرف كيف أضيف كود في الرد, أتمنى أنه يخرج واضح. الكود بلغة C++. على كل حال صفحة الخوارزمية في ويكيبيديا https://en.wikipedia.org/wi...

`

swap (int &a, int &b ) {

if (&a != &b ) {

a ^= b ;

b ^= a ;

a ^= b ;

} }

`

1
Yunus_ja

بما أنك تدرس Recursion فحتما سمعت ب The Fibonacci numbers ،

1
aseelassadi

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