تم إنشاء عرض تقديمي حول موضوع "الخوارزميات العودية" لإعداد الطلاب لامتحان الدولة الموحدة في علوم الكمبيوتر وتكنولوجيا المعلومات والاتصالات. يفحص العمل تعريف العودية ويقدم أمثلة على الكائنات الرسومية المحددة بشكل متكرر. يحتوي العرض التقديمي على طرق حل المهمة رقم 11 من مسودة النسخة التجريبية لامتحان الدولة الموحدة - 2015 في علوم الكمبيوتر. تتضمن الطريقة الأولى بناء شجرة استدعاء، أما الطريقة الثانية فتحل المشكلة باستخدام طريقة الاستبدال. يتم النظر في 4 أمثلة لحل المهام باستخدام كلتا الطريقتين. يحتوي العرض التقديمي التالي على 25 تمرينًا للتدريب مع إجابات من موقع كونستانتين بولياكوف.

تحميل:

معاينة:

لاستخدام معاينات العرض التقديمي، قم بإنشاء حساب Google وقم بتسجيل الدخول إليه: https://accounts.google.com

التسميات التوضيحية للشرائح:

المهمة رقم 11 امتحان الدولة الموحدة (المستوى الأساسي، الوقت - 5 دقائق) الخوارزميات العودية. المؤلف - كوروتون أو في، مدرس علوم الكمبيوتر، المؤسسة التعليمية البلدية "المدرسة الثانوية رقم 71"

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

في البرمجة، العودية هي استدعاء دالة من نفسها، مباشرة أو من خلال وظائف أخرى، على سبيل المثال، تستدعي الدالة A الدالة B، وتستدعي الدالة B الدالة A. ويسمى عدد الاستدعاءات المتداخلة لوظيفة أو إجراء بعمق العودية. مثال على التكرار: إذا كان لديك بقعة دهنية على فستانك، فلا تقلقي. تتم إزالة بقع الزيت بالبنزين. تتم إزالة بقع البنزين بمحلول قلوي.

مثال على المهمة: بالنظر إلى خوارزمية متكررة: الإجراء F(n: integer); ابدأ الكتابة (ن) ؛ إذا ن

مثال على التعيين: بالنظر إلى خوارزمية متكررة: الإجراء F(n: integer); ابدأ بالكتابة (ن) ؛ إذا ن

مثال على التعيين: بالنظر إلى خوارزمية متكررة: الإجراء F(n: integer); ابدأ الكتابة (ن) ؛ إذا ن الشريحة 9

مثال على التعيين: بالنظر إلى خوارزمية متكررة: الإجراء F(n: integer); ابدأ الكتابة (ن) ؛ إذا ن الشريحة 10

مثال على التعيين: بالنظر إلى خوارزمية متكررة: الإجراء F(n: integer); ابدأ الكتابة (ن) ؛ إذا ن الشريحة 11

15 المثال رقم 2: بالنظر إلى خوارزمية متكررة: الإجراء F(n: integer); ابدأ الكتابة (ن) ؛ إذا ن

المثال رقم 2: بالنظر إلى خوارزمية عودية: الإجراء F(n: integer); ابدأ الكتابة (ن) ؛ إذا ن الشريحة 13

المثال رقم 3: بالنظر إلى خوارزمية عودية: الإجراء F(n: integer); ابدأ writeln("*"); إذا كان n > 0، فابدأ بـ F(n-2); F(n div 2) نهاية النهاية؛ كم عدد العلامات النجمية التي سيتم طباعتها على الشاشة عند الاتصال بـ F(7)؟ 7 5 3 2 3 1 1 1 1 في هذا المثال، يتم عرض الرمز * -2 div 2 1 0 -1 0 -1 0 -1 -1 -1 0 0 0 على الشاشة بدلاً من قيم المعلمة ن .

المثال رقم 3: بالنظر إلى خوارزمية عودية: الإجراء F(n: integer); ابدأ الكتابة("*"); إذا كان n > 0، فابدأ بـ F(n-2); F(n div 2) نهاية النهاية؛ كم عدد العلامات النجمية التي سيتم طباعتها على الشاشة عند الاتصال بـ F(7)؟ * وبحساب عدد “النجوم” نحصل على 21. في هذا المثال، ليست قيم المعلمة n هي التي يتم عرضها على الشاشة، بل الرمز * * * * * * * * * * * * * * * * * * * * *

المثال رقم 3: بالنظر إلى خوارزمية عودية: الإجراء F(n: integer); ابدأ الكتابة("*"); إذا كان n > 0، فابدأ بـ F(n-2); F(n div 2) نهاية النهاية؛ كم عدد العلامات النجمية التي سيتم طباعتها على الشاشة عند الاتصال بـ F(7)؟ دعونا نحل المشكلة بدون شجرة. اجعل S(n) هو عدد "النجوم" التي سيتم طباعتها عند الاتصال بـ F(n). ثم 1+S(n-2)+ S(n div 2), n>0 1 , n نحن بحاجة إلى معرفة S(7). S(7)= 1 +S(5)+ S(3) S(5)= 1 +S(3)+S(2) S(3)= 1 +S(1)+S(1) S( 2)=1+S(0)+S(1)=1+1+S(1)=2+S(1) S(1)= 1+ S(-1)+S(0)=1+ 1+1=3 العكسي: S(2)=2+3=5 S(3)=1+3+3=7 S(5)=1+7+5=13 S(7)=1+ 13+ 7= 21 ق(ن)=

المثال رقم 4: الإجراء F(n: عدد صحيح)؛ ابدأ إذا ن الشريحة 18

المثال رقم 4: الإجراء F(n: عدد صحيح)؛ ابدأ إذا ن الشريحة 19

المثال رقم 4: الإجراء F(n: عدد صحيح)؛ تبدأ إذا ن

المثال رقم 4: الإجراء F(n: عدد صحيح)؛ تبدأ إذا ن

مهام التدريب

المشكلة 1: في ضوء خوارزمية عودية: الإجراء F(n: integer); ابدأ الكتابة("*"); إذا كان n > 0، فابدأ بـ F(n-2); F(ن شعبة 2); F(ن شعبة 2); نهاية النهاية؛ كم عدد العلامات النجمية التي سيتم طباعتها على الشاشة عند الاتصال بـ F(5)؟ الجواب: 34

المشكلة 2: في ضوء خوارزمية عودية: الإجراء F(n: integer); ابدأ الكتابة("*"); إذا كان n > 0، فابدأ بـ F(n-2); F(ن-2); F(ن شعبة 2); نهاية النهاية؛ كم عدد العلامات النجمية التي سيتم طباعتها على الشاشة عند الاتصال بـ F(6)؟ الجواب: 58

المشكلة 3: في ضوء خوارزمية متكررة: الإجراء F(n: integer); ابدأ الكتابة("*"); إذا كان n > 0 فابدأ بـ F(n-3); F(ن شعبة 2); نهاية النهاية؛ كم عدد العلامات النجمية التي سيتم طباعتها على الشاشة عند الاتصال بـ F(7)؟ الجواب: 15

المشكلة 4: في ضوء خوارزمية متكررة: الإجراء F(n: integer); ابدأ الكتابة("*"); إذا كان n > 0 فابدأ بـ F(n-3); F(ن-2); F(ن شعبة 2); نهاية النهاية؛ كم عدد العلامات النجمية التي سيتم طباعتها على الشاشة عند الاتصال بـ F(7)؟ الجواب: 55

المشكلة 5: في ضوء خوارزمية متكررة: الإجراء F(n: عدد صحيح)؛ ابدأ الكتابة("*"); إذا كان n > 0 فابدأ بـ F(n-3); F(ن-2); F(ن شعبة 2); F(ن شعبة 2); نهاية النهاية؛ كم عدد العلامات النجمية التي سيتم طباعتها على الشاشة عند الاتصال بـ F(6)؟ الجواب: 97

المشكلة 6: في ضوء خوارزمية متكررة: الإجراء F(n: integer); ابدأ الكتابة("*"); إذا كان n > 0 فابدأ writeln("*"); F(ن-2); F(ن شعبة 2); نهاية النهاية؛ كم عدد العلامات النجمية التي سيتم طباعتها على الشاشة عند الاتصال بـ F(7)؟ الجواب: 31

المشكلة 7: في ضوء خوارزمية متكررة: الإجراء F(n: عدد صحيح)؛ ابدأ الكتابة("*"); إذا كان n > 0 فابدأ writeln("*"); F(ن-2); F(ن شعبة 2); F(ن شعبة 2); نهاية النهاية؛ كم عدد العلامات النجمية التي سيتم طباعتها على الشاشة عند الاتصال بـ F(7)؟ الجواب: 81

المشكلة 8: بالنظر إلى خوارزمية عودية: الإجراء F(n: integer); ابدأ الكتابة("*"); إذا كان n > 0 فابدأ writeln("*"); F(ن-2); F(ن-2); F(ن شعبة 2); نهاية النهاية؛ كم عدد العلامات النجمية التي سيتم طباعتها على الشاشة عند الاتصال بـ F(6)؟ الجواب: 77

المشكلة 9: في ضوء خوارزمية متكررة: الإجراء F(n: عدد صحيح)؛ ابدأ إذا كان n > 0 ثم ابدأ F(n-2); F(ن-1); F(ن-1); نهاية؛ writeln("*"); نهاية ؛ كم عدد العلامات النجمية التي سيتم طباعتها على الشاشة عند الاتصال بـ F(5)؟ الجواب: 148

المشكلة 10: في ضوء خوارزمية متكررة: الإجراء F(n: عدد صحيح)؛ ابدأ إذا كان n > 0 ثم ابدأ writeln("*"); F(ن-2); F(ن-1); F(ن-1); نهاية؛ writeln("*"); نهاية؛ كم عدد العلامات النجمية التي سيتم طباعتها على الشاشة عند الاتصال بـ F(5)؟ الجواب: 197

المشكلة 11: في ضوء خوارزمية متكررة: الإجراء F(n: عدد صحيح)؛ ابدأ إذا كان n > 1 ثم ابدأ F(n-2); F(ن-1); F(ن شعبة 2); نهاية؛ writeln("*"); نهاية ؛ كم عدد العلامات النجمية التي سيتم طباعتها على الشاشة عند الاتصال بـ F(7)؟ الجواب: 88

المشكلة 12: في ضوء خوارزمية متكررة: الإجراء F(n: عدد صحيح)؛ ابدأ إذا كان n > 2 ثم ابدأ writeln("*"); F(ن-2); F(ن-1); F(ن شعبة 2); نهاية ؛ writeln("*"); نهاية؛ كم عدد العلامات النجمية التي سيتم طباعتها على الشاشة عند الاتصال بـ F(6)؟ الجواب: 33

المشكلة 13: في ضوء خوارزمية متكررة: الإجراء F (n: عدد صحيح)؛ ابدأ الكتابة (ن) ؛ إذا ن

المشكلة 14: في ضوء خوارزمية متكررة: الإجراء F (n: عدد صحيح)؛ ابدأ الكتابة (ن) ؛ إذا ن

المشكلة 15: في ضوء خوارزمية متكررة: الإجراء F (n: عدد صحيح)؛ ابدأ الكتابة (ن) ؛ إذا ن

المشكلة 16: في ضوء خوارزمية متكررة: الإجراء F (n: عدد صحيح)؛ ابدأ الكتابة (ن) ؛ إذا ن

المشكلة 17: في ضوء خوارزمية متكررة: الإجراء F (n: عدد صحيح)؛ ابدأ الكتابة (ن) ؛ إذا ن

المشكلة 18: في ضوء خوارزمية متكررة: الإجراء F (n: عدد صحيح)؛ ابدأ الكتابة (ن) ؛ إذا ن

المشكلة 19: في ضوء خوارزمية متكررة: الإجراء F (n: عدد صحيح)؛ ابدأ الكتابة (ن) ؛ إذا ن

المشكلة 20: في ضوء خوارزمية متكررة: الإجراء F (n: عدد صحيح)؛ ابدأ الكتابة (ن) ؛ إذا ن

المشكلة 21: في ضوء خوارزمية متكررة: الإجراء F (n: عدد صحيح)؛ ابدأ الكتابة (ن) ؛ إذا ن

المشكلة 22: في ضوء خوارزمية متكررة: الإجراء F (n: عدد صحيح)؛ ابدأ الكتابة (ن) ؛ إذا ن

المشكلة 23: في ضوء خوارزمية متكررة: الإجراء F (n: عدد صحيح)؛ ابدأ الكتابة (ن) ؛ إذا ن

المشكلة 24: في ضوء خوارزمية متكررة: الإجراء F (n: عدد صحيح)؛ ابدأ الكتابة (ن) ؛ إذا ن

المشكلة 25: في ضوء خوارزمية متكررة: الإجراء F (n: عدد صحيح)؛ ابدأ الكتابة (ن) ؛ إذا ن

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

1. جوهر العودية

قد يحتوي الإجراء أو الوظيفة على استدعاءات لإجراءات أو وظائف أخرى. يمكن للإجراء أيضًا أن يطلق على نفسه. لا توجد مفارقة هنا - فالكمبيوتر ينفذ فقط الأوامر التي يواجهها في البرنامج بشكل تسلسلي، وإذا واجه استدعاء إجراء، فإنه ببساطة يبدأ في تنفيذ هذا الإجراء. لا يهم الإجراء الذي أعطى الأمر للقيام بذلك.

مثال على الإجراء العودي:

توصية الإجراء (أ: عدد صحيح)؛ ابدأ إذا أ>

لنفكر فيما يحدث إذا تم إجراء استدعاء، على سبيل المثال، بالصيغة Rec(3) في البرنامج الرئيسي. يوجد أدناه مخطط انسيابي يوضح تسلسل تنفيذ البيانات.

أرز. 1. رسم تخطيطي للإجراء العودي.

يتم استدعاء الإجراء Rec مع المعلمة a = 3. ويحتوي على استدعاء الإجراء Rec مع المعلمة a = 2. لم يكتمل الاستدعاء السابق بعد، لذا يمكنك أن تتخيل أنه تم إنشاء إجراء آخر ولم يكمل الإجراء الأول عمله حتى انتهى. تنتهي عملية الاستدعاء عندما تكون المعلمة a = 0. عند هذه النقطة، يتم تنفيذ 4 مثيلات للإجراء في وقت واحد. يتم استدعاء عدد الإجراءات التي يتم تنفيذها في وقت واحد عمق العودية.

الإجراء الرابع المسمى (Rec(0)) سيطبع الرقم 0 وينهي عمله. بعد ذلك يعود التحكم إلى الإجراء المسمى (Rec(1)) ويتم طباعة الرقم 1 وهكذا حتى تنتهي كافة الإجراءات. ستتم طباعة المكالمة الأصلية بأربعة أرقام: 0، 1، 2، 3.

تظهر صورة مرئية أخرى لما يحدث في الشكل. 2.

أرز. 2. تنفيذ الإجراء Rec مع المعلمة 3 يتكون من تنفيذ الإجراء Rec مع المعلمة 2 وطباعة الرقم 3. بدوره، تنفيذ الإجراء Rec مع المعلمة 2 يتكون من تنفيذ الإجراء Rec مع المعلمة 1 وطباعة الرقم 2. إلخ .

كتمرين لوحدك، ضع في اعتبارك ما يحدث عندما تتصل بالتوصية (4). ضع في اعتبارك أيضًا ما سيحدث إذا قمت باستدعاء الإجراء Rec2(4) أدناه، مع عكس عوامل التشغيل.

الإجراء Rec2(a: عدد صحيح)؛ ابدأ الكتابة (أ) ؛ إذا كان a>0 ثم Rec2(a-1); نهاية؛

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

من الممكن وجود مخطط أكثر تعقيدًا بعض الشيء: تستدعي الوظيفة A الوظيفة B، والتي بدورها تستدعي A. وهذا ما يسمى العودية المعقدة. اتضح أن الإجراء الموصوف أولاً يجب أن يستدعي إجراءً لم يتم وصفه بعد. لكي يكون هذا ممكنًا، عليك استخدام .

الإجراء أ(ن: عدد صحيح)؛ (الوصف الأمامي (الرأس) للإجراء الأول) الإجراء B(n: عدد صحيح)؛ (الوصف الأمامي للإجراء الثاني) الإجراء A(n: عدد صحيح)؛ (وصف كامل للإجراء أ) ابدأ writeln(n); ب(ن-1); نهاية؛ الإجراء B(ن: عدد صحيح)؛ (وصف كامل للإجراء ب) ابدأ writeln(n); إذا ن

يسمح الإعلان الأمامي للإجراء B باستدعائه من الإجراء A. والإعلان الأمامي للإجراء A غير مطلوب في هذا المثال ويتم إضافته لأسباب جمالية.

إذا كان من الممكن تشبيه العودية العادية بالأوروبوروس (الشكل 3)، فيمكن استخلاص صورة العودية المعقدة من قصيدة الأطفال الشهيرة، حيث "كانت الذئاب خائفة وأكلت بعضها البعض". تخيل ذئبين يأكلان بعضهما البعض وسوف تفهم التكرار المعقد.

أرز. 3. أوروبوروس - ثعبان يلتهم ذيله. استخلاص من الأطروحة الخيميائية “سينوسيوس” لثيودور بيليكانوس (1478).

أرز. 4. العودية المعقدة.

3. محاكاة حلقة باستخدام العودية

إذا استدعى الإجراء نفسه، فإنه يؤدي بشكل أساسي إلى تنفيذ التعليمات التي يحتوي عليها مرة أخرى، على غرار الحلقة. بعض لغات البرمجة لا تحتوي على بنيات تكرارية على الإطلاق، مما يترك للمبرمجين تنظيم التكرارات باستخدام العودية (على سبيل المثال، Prolog، حيث العودية هي تقنية برمجة أساسية).

على سبيل المثال، دعونا نحاكي تشغيل حلقة for. للقيام بذلك، نحتاج إلى متغير عداد الخطوات، والذي يمكن تنفيذه، على سبيل المثال، كمعلمة إجراء.

مثال 1.

الإجراء LoopImitation(i, n: integer); (المعلمة الأولى هي عداد الخطوات، والمعلمة الثانية هي العدد الإجمالي للخطوات) begin writeln("Hello N ", i); // فيما يلي أي تعليمات سيتم تكرارها إذا i

نتيجة استدعاء النموذج LoopImitation(1, 10) ستكون تنفيذ التعليمات عشر مرات، مع تغيير العداد من 1 إلى 10. في هذه الحالة سيتم طباعة ما يلي:

مرحبا ن1
مرحبا ن2
…
مرحبا ن10

بشكل عام، ليس من الصعب أن نرى أن معلمات الإجراء هي حدود تغيير قيم العداد.

يمكنك تبديل المكالمة العودية والتعليمات المراد تكرارها، كما في المثال التالي.

مثال 2.

الإجراء LoopImitation2(i, n: integer); تبدأ إذا أنا

في هذه الحالة، سيحدث استدعاء إجراء عودي قبل بدء تنفيذ التعليمات. ستقوم النسخة الجديدة من الإجراء أيضًا، أولاً، باستدعاء مثيل آخر، وهكذا، حتى نصل إلى الحد الأقصى لقيمة العداد. فقط بعد ذلك سوف ينفذ آخر الإجراءات التي تم استدعاؤها تعليماتها، ثم ينفذ الإجراء الثاني قبل الأخير تعليماته، وما إلى ذلك. ستكون نتيجة استدعاء LoopImitation2(1, 10) هي طباعة التحيات بترتيب عكسي:

مرحبا ن10
…
مرحبا ن1

إذا تخيلنا سلسلة من الإجراءات التي تسمى بشكل متكرر، ففي المثال 1 ننتقل من الإجراءات التي تم استدعاؤها سابقًا إلى الإجراءات اللاحقة. في المثال 2، على العكس من ذلك، من الأحدث إلى الأقدم.

وأخيرًا، يمكن إجراء استدعاء متكرر بين كتلتين من التعليمات. على سبيل المثال:

الإجراء LoopImitation3(i, n: integer); ابدأ writeln("Hello N"، i); (قد تكون المجموعة الأولى من التعليمات موجودة هنا) إذا كنت

هنا، يتم تنفيذ التعليمات من الكتلة الأولى أولاً بشكل تسلسلي، ثم يتم تنفيذ التعليمات من الكتلة الثانية بترتيب عكسي. عند استدعاء LoopImitation3(1, 10) نحصل على:

مرحبا ن1
…
مرحبا ن10
مرحبا ن10
…
مرحبا ن1

سيستغرق الأمر حلقتين لفعل نفس الشيء دون التكرار.

يمكنك الاستفادة من حقيقة أن تنفيذ أجزاء من نفس الإجراء متباعد مع مرور الوقت. على سبيل المثال:

مثال 3: تحويل رقم إلى ثنائي.

الحصول على أرقام الرقم الثنائي كما هو معروف يتم عن طريق القسمة مع باقي على أساس نظام الأرقام 2. إذا كان هناك رقم فإن آخر رقم له في تمثيله الثنائي يساوي

أخذ الجزء الكامل من القسمة على 2:

نحصل على رقم له نفس التمثيل الثنائي، ولكن بدون الرقم الأخير. وبالتالي، يكفي تكرار العمليتين المذكورتين أعلاه حتى يتلقى حقل القسمة التالي جزءًا صحيحًا يساوي 0. وبدون التكرار سيبدو الأمر كما يلي:

بينما x>0 يبدأ c:=x mod 2; س:=س شعبة 2; اكتب (ج)؛ نهاية؛

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

باستخدام العودية، ليس من الصعب تحقيق الإخراج بالترتيب الصحيح بدون مصفوفة وحلقة ثانية. يسمى:

الإجراء BinaryRepresentation(x: integer); فار ج، س: عدد صحيح؛ ابدأ (الكتلة الأولى. يتم تنفيذها بترتيب استدعاءات الإجراء) c:= x mod 2; س:= س شعبة 2; (استدعاء متكرر) إذا كان x>0 ثم BinaryRepresentation(x); (الكتلة الثانية. يتم تنفيذها بترتيب عكسي) write(c); نهاية؛

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

4. علاقات التكرار. العودية والتكرار

يُقال إن تسلسل المتجهات يُعطى من خلال علاقة تكرارية إذا تم إعطاء المتجه الأولي والاعتماد الوظيفي للمتجه اللاحق على المتجه السابق

مثال بسيط لكمية محسوبة باستخدام علاقات التكرار هو المضروب

يمكن حساب العامل التالي من العامل السابق على النحو التالي:

وبإدخال الترميز نحصل على العلاقة:

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

س:= 1; لأني:= 2 إلى n do x:= x * i; writeln(x);

يتم استدعاء كل تحديث (x:= x * i). تكرار، وعملية تكرار التكرارات هي تكرار.

ومع ذلك، دعونا نلاحظ أن العلاقة (1) هي تعريف عودي بحت للتسلسل وحساب العنصر n هو في الواقع الأخذ المتكرر للدالة f من نفسها:

على وجه الخصوص، بالنسبة للمضروب يمكن كتابة:

مضروب الدالة (ن: عدد صحيح): عدد صحيح؛ ابدأ إذا كان n > 1 ثم المضروب:= n * المضروب(n-1) المضروب الآخر:= 1; نهاية؛

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

قبل الانتقال إلى المواقف التي يكون فيها التكرار مفيدًا، دعنا نلقي نظرة على مثال آخر حيث لا ينبغي استخدامه.

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

مع النهج "الأمامي"، يمكنك الكتابة:

وظيفة Fib(n: عدد صحيح): عدد صحيح؛ ابدأ إذا n > 1 ثم Fib:= Fib(n-1) + Fib(n-2) else Fib:= 1; نهاية؛

يقوم كل استدعاء Fib بإنشاء نسختين من نفسه، وكل نسخة تنشئ نسختين أخريين، وهكذا. عدد العمليات يزيد مع العدد نبشكل كبير، على الرغم من أن الحل التكراري خطي نعدد العمليات.

في الواقع، المثال أعلاه لا يعلمنا ذلك متىلا ينبغي أن تستخدم العودية، وإلا كيفلا ينبغي استخدامه. بعد كل شيء، إذا كان هناك حل تكراري سريع (يعتمد على الحلقة)، فيمكن تنفيذ نفس الحلقة باستخدام إجراء أو وظيفة متكررة. على سبيل المثال:

// x1, x2 - الشروط الأولية (1, 1) // n - رقم دالة أرقام فيبوناتشي المطلوبة Fib(x1, x2, n: integer): integer; فار x3: عدد صحيح؛ ابدأ إذا كان n > 1 ثم ابدأ x3:= x2 + x1; x1:= x2; x2:= x3; فيب:= فيب(x1, x2, n-1); end else Fib:= x2; نهاية؛

ومع ذلك، الحلول التكرارية هي الأفضل. السؤال هو متى يجب عليك استخدام التكرار في هذه الحالة؟

يمكن بسهولة استبدال أي إجراءات ووظائف متكررة تحتوي على استدعاء متكرر واحد لنفسها بحلقات تكرارية. للحصول على شيء ليس له نظير بسيط غير متكرر، تحتاج إلى اللجوء إلى الإجراءات والوظائف التي تسمي نفسها مرتين أو أكثر. في هذه الحالة، لم تعد مجموعة الإجراءات المطلوبة تشكل سلسلة، كما في الشكل 2. 1، بل شجرة كاملة. هناك فئات واسعة من المشاكل عندما يجب تنظيم العملية الحسابية بهذه الطريقة. بالنسبة لهم، سيكون التكرار هو الحل الأبسط والأكثر طبيعية.

5. الأشجار

الأساس النظري للوظائف العودية التي تطلق على نفسها أكثر من مرة هو فرع الرياضيات المنفصلة الذي يدرس الأشجار.

5.1. التعاريف الأساسية. طرق تصوير الأشجار

تعريف: سوف نسمي المجموعة المنتهية ت، تتكون من عقدة واحدة أو أكثر بحيث:
أ) هناك عقدة خاصة واحدة تسمى جذر هذه الشجرة.
ب) يتم تضمين العقد المتبقية (باستثناء الجذر) في مجموعات فرعية منفصلة زوجية، كل منها بدورها عبارة عن شجرة. تسمى الأشجار الأشجار الفرعيةمن هذه الشجرة.

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

أرز. 3. شجرة.

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

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

أرز. 4. طرق أخرى لتمثيل الهياكل الشجرية: (أ) المجموعات المتداخلة؛ (ب) الأقواس المتداخلة؛ (ج) قائمة الامتيازات.

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

يمكنك أيضًا إجراء تشبيه بين القائمة المتدرجة ومظهر جداول المحتويات في الكتب، حيث تحتوي الأقسام على أقسام فرعية، والتي بدورها تحتوي على أقسام فرعية، وما إلى ذلك. الطريقة التقليدية لترقيم هذه الأقسام (القسم 1، الأقسام الفرعية 1.1 و1.2، القسم الفرعي 1.1.2، وما إلى ذلك) تسمى نظام ديوي العشري. يتم تطبيقه على الشجرة في الشكل. 3 و 4 سيعطي هذا النظام:

1. أ؛ 1.1ب؛ 1.2 درجة مئوية؛ 1.2.1 د؛ 1.2.2 هـ؛ 1.2.3 ف؛ 1.2.3.1 جرام؛

5.2. تمرير الأشجار

في جميع الخوارزميات المتعلقة بالهياكل الشجرية، تظهر نفس الفكرة دائمًا، وهي الفكرة عابرأو اجتياز الشجرة. هذه طريقة لزيارة العقد الشجرية حيث يتم اجتياز كل عقدة مرة واحدة بالضبط. وينتج عن هذا ترتيب خطي لعقد الشجرة. على وجه الخصوص، هناك ثلاث طرق: يمكنك المرور عبر العقد بالترتيب الأمامي والخلفي والنهائي.

خوارزمية الاجتياز إلى الأمام:

• الوصول إلى الجذر
• انتقل عبر جميع الأشجار الفرعية من اليسار إلى اليمين بالترتيب المباشر.

هذه الخوارزمية متكررة، نظرًا لأن اجتياز الشجرة يحتوي على اجتياز الأشجار الفرعية، والتي بدورها يتم اجتيازها باستخدام نفس الخوارزمية.

على وجه الخصوص، بالنسبة للشجرة في الشكل. 3 و4، الاجتياز المباشر يعطي سلسلة من العقد: A، B، C، D، E، F، G.

يتوافق التسلسل الناتج مع تعداد العقد من اليسار إلى اليمين عند تمثيل شجرة باستخدام الأقواس المتداخلة وفي تدوين ديوي العشري، بالإضافة إلى ممر من أعلى إلى أسفل عند تمثيلها كقائمة متداخلة.

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

// اجتياز الطلب المسبق - الاسم الإنجليزي لإجراء الطلب المباشر PreorderTraversal((Arguments)); ابدأ // تمرير الجذر DoSomething((Arguments)); // انتقال الشجرة الفرعية اليسرى إذا (توجد شجرة فرعية يسرى) ثم PreorderTransversal((الوسائط 2)); // انتقال الشجرة الفرعية اليمنى إذا (توجد شجرة فرعية صحيحة) ثم PreorderTransversal((الوسائط 3)); نهاية؛

وهذا يعني أن الإجراء ينفذ أولاً جميع الإجراءات، وعندها فقط تحدث جميع الاستدعاءات العودية.

خوارزمية الاجتياز العكسي:

• انتقل من خلال الشجرة الفرعية اليسرى،
• الوصول إلى الجذر
• انتقل من خلال الشجرة الفرعية التالية إلى اليسار.
• الوصول إلى الجذر
• وما إلى ذلك حتى يتم اجتياز الشجرة الفرعية الموجودة في أقصى اليمين.

أي أنه يتم اجتياز جميع الأشجار الفرعية من اليسار إلى اليمين، وتقع العودة إلى الجذر بين عمليات الاجتياز هذه. بالنسبة للشجرة في الشكل 3 و 4 يعطي تسلسل العقد: B، A، D، C، E، G، F.

في الإجراء العودي المقابل، سيتم تحديد موقع الإجراءات في المسافات بين الاستدعاءات العودية. خصيصا لشجرة ثنائية:

// اجتياز الطلب – الاسم الإنجليزي لإجراء الطلب العكسي InorderTraversal((Arguments)); ابدأ // السفر إلى الشجرة الفرعية اليسرى إذا (توجد شجرة فرعية يسرى) ثم InorderTraversal((الوسائط 2)); // تمرير الجذر DoSomething((الحجج)); // اجتياز الشجرة الفرعية اليمنى إذا (توجد شجرة فرعية صحيحة) ثم InorderTraversal((الوسائط 3)); نهاية؛

خوارزمية اجتياز الطلب النهائي:

• انتقل من خلال جميع الأشجار الفرعية من اليسار إلى اليمين،
• الوصول إلى الجذر.

بالنسبة للشجرة في الشكل 3 و 4 سيعطي هذا تسلسل العقد: B، D، E، G، F، C، A.

في الإجراء العودي المقابل، سيتم تحديد موقع الإجراءات بعد الاستدعاءات العودية. خصيصا لشجرة ثنائية:

// اجتياز الطلب اللاحق – الاسم الإنجليزي لإجراء الأمر النهائي PostorderTraversal((Arguments)); ابدأ // السفر إلى الشجرة الفرعية اليسرى إذا (توجد شجرة فرعية يسرى) ثم PostorderTraversal((الوسائط 2)); // تجاوز الشجرة الفرعية اليمنى إذا (توجد شجرة فرعية صحيحة) ثم PostorderTraversal((الوسائط 3)); // تمرير الجذر DoSomething((الحجج)); نهاية؛

5.3. تمثيل شجرة في ذاكرة الكمبيوتر

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

اكتب PTree = ^TTree; TTree = سجل Inf: عدد صحيح؛ LeftSubTree، RightSubTree: PTree؛ نهاية؛

كل عقدة لها نوع PTree. هذا مؤشر، مما يعني أنه يجب إنشاء كل عقدة عن طريق استدعاء الإجراء الجديد عليها. إذا كانت العقدة عبارة عن عقدة طرفية، فسيتم تعيين القيمة لحقول LeftSubTree وRightSubTree لا شيء. بخلاف ذلك، يتم أيضًا إنشاء عقدتي LeftSubTree وRightSubTree بواسطة الإجراء الجديد.

يظهر أحد هذه السجلات بشكل تخطيطي في الشكل. 5.

أرز. 5. تمثيل تخطيطي لسجل نوع TTree. يحتوي السجل على ثلاثة حقول: Inf - رقم، وLeftSubTree، وRightSubTree - تشير إلى سجلات من نفس نوع TTree.

ويبين الشكل 6 مثالاً لشجرة مكونة من هذه السجلات.

أرز. 6. شجرة مكونة من سجلات من النوع TTree. يخزن كل إدخال رقمًا ومؤشرين يمكن أن يحتويا على أي منهما لا شيءأو عناوين السجلات الأخرى من نفس النوع.

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

6. أمثلة على الخوارزميات العودية

6.1. رسم شجرة

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

أرز. 6. شجرة.

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

ويرد أدناه مثال على هذا الإجراء، مكتوب في دلفي:

شجرة الإجراء (القماش: TCanvas؛ // القماش الذي سيتم رسم الشجرة عليه x، y: ممتد؛ // زاوية إحداثيات الجذر: ممتدة؛ // الزاوية التي تنمو فيها الشجرة TrunkLength: ممتد؛ // طول الجذع n: عدد صحيح // عدد الفروع (كم عدد // الاستدعاءات المتكررة التي لم يتم إجراؤها بعد)); فار x2, y2: ممتد; // بداية نهاية الجذع (نقطة الفرع) x2:= x + TrunkLength * cos(Angle); y2:= y - TrunkLength * sin(Angle); Canvas.MoveTo(round(x), round(y)); Canvas.LineTo(round(x2), round(y2)); إذا كان n > 1، فابدأ بـ Tree(Canvas, x2, y2, Angle+Pi/4, 0.55*TrunkLength, n-1); شجرة (قماش، x2، y2، زاوية-Pi/4، 0.55*TrunkLength، n-1)؛ نهاية؛ نهاية؛

للحصول على الشكل 6 تم استدعاء هذا الإجراء بالمعلمات التالية:

شجرة (Image1.Canvas، 175، 325، Pi/2، 120، 15)؛

لاحظ أن الرسم يتم قبل الاستدعاءات العودية، أي أنه يتم رسم الشجرة بترتيب مباشر.

6.2. أبراج هانوي

وفقًا للأسطورة الموجودة في معبد باناراس الكبير، يوجد تحت الكاتدرائية التي تشير إلى منتصف العالم، قرص برونزي مثبت عليه 3 قضبان من الماس، ارتفاعها ذراع واحدة وسميكة مثل النحلة. منذ زمن طويل، في بداية الزمن، ارتكب رهبان هذا الدير جريمة أمام الإله براهما. غاضبًا، أقام براهما ثلاثة قضبان عالية ووضع 64 قرصًا من الذهب الخالص على أحدها، بحيث يستقر كل قرص أصغر على قرص أكبر. بمجرد نقل جميع الأقراص الـ 64 من العصا التي وضعها الله براهما عليها عند خلق العالم، إلى قضيب آخر، سيتحول البرج مع المعبد إلى غبار وسيموت العالم تحت قصف الرعد.
تتطلب العملية ألا ينتهي الأمر بالقرص الأكبر حجمًا فوق القرص الأصغر أبدًا. الرهبان في مأزق: بأي ترتيب يجب أن يقوموا بالنوبات؟ مطلوب تزويدهم بالبرمجيات لحساب هذا التسلسل.

وبغض النظر عن براهما، فقد تم اقتراح هذا اللغز في نهاية القرن التاسع عشر من قبل عالم الرياضيات الفرنسي إدوارد لوكاس. تستخدم النسخة المباعة عادة 7-8 أقراص (الشكل 7).

أرز. 7. لغز "أبراج هانوي".

لنفترض أن هناك حل ل ن-1 قرص. ثم للتحول نالأقراص، اتبع ما يلي:

1) التحول ن-1 قرص.
2) التحول نالقرص على الدبوس الحر المتبقي.
3) نقوم بتحويل المكدس من ن-1 ورد القرص في النقطة (1) في الأعلى ن-القرص.

لأنه لهذه القضية ن= 1 خوارزمية إعادة الترتيب واضحة، ثم عن طريق الاستقراء، باستخدام الإجراءات (1) - (3)، يمكننا إعادة ترتيب عدد عشوائي من الأقراص.

لنقم بإنشاء إجراء عودي يطبع التسلسل الكامل للتحولات لعدد معين من الأقراص. في كل مرة يتم استدعاء مثل هذا الإجراء، يجب أن يطبع معلومات حول تحول واحد (من النقطة 2 من الخوارزمية). بالنسبة لعمليات إعادة الترتيب من النقطتين (1) و(3)، فإن الإجراء سوف يطلق على نفسه مع تقليل عدد الأقراص بمقدار واحد.

// ن - عدد الأقراص // أ، ب، ج - أرقام الدبوس. يتم التحويل من الدبوس a، // إلى الدبوس b مع الدبوس المساعد c. إجراء هانوي (ن، أ، ب، ج: عدد صحيح)؛ ابدأ إذا كان n > 1 ثم ابدأ هانوي(n-1, a, c, b); writeln(a, " -> ", b); هانوي(ن-1, ج, ب, أ); نهاية آخر writeln(a, " -> ", b); نهاية؛

لاحظ أن مجموعة الإجراءات التي يتم استدعاؤها بشكل متكرر في هذه الحالة تشكل شجرة يتم اجتيازها بترتيب عكسي.

6.3. تحليل التعبيرات الحسابية

تتمثل مهمة التحليل في حساب قيمة التعبير باستخدام سلسلة موجودة تحتوي على تعبير حسابي والقيم المعروفة للمتغيرات المضمنة فيه.

يمكن تمثيل عملية حساب التعبيرات الحسابية كشجرة ثنائية. في الواقع، يتطلب كل من العوامل الحسابية (+، -، *، /) معاملين، والذي سيكون أيضًا تعبيرات حسابية، وبالتالي يمكن اعتباره شجرتين فرعيتين. أرز. ويبين الشكل 8 مثالاً لشجرة مقابلة للتعبير:

أرز. 8. الشجرة النحوية المقابلة للتعبير الحسابي (6).

في مثل هذه الشجرة، ستكون العقد النهائية دائمًا متغيرة (هنا س) أو ثوابت رقمية، وستحتوي جميع العقد الداخلية على عوامل تشغيل حسابية. لتنفيذ عامل تشغيل، يجب عليك أولاً تقييم معاملاته. وبالتالي، يجب اجتياز الشجرة الموجودة في الشكل بترتيب نهائي. التسلسل المقابل للعقد

مُسَمًّى عكس التدوين البولنديالتعبير الحسابي.

عند إنشاء شجرة بناء الجملة، يجب عليك الانتباه إلى الميزة التالية. إذا، على سبيل المثال، هناك تعبير

وسنقرأ عمليات الجمع والطرح من اليسار إلى اليمين، ثم ستحتوي الشجرة النحوية الصحيحة على علامة الطرح بدلاً من علامة الجمع (الشكل 9أ). في جوهرها، تتوافق هذه الشجرة مع التعبير. من الممكن أن يكون إنشاء الشجرة أسهل إذا قمت بتحليل التعبير (8) في الاتجاه المعاكس، من اليمين إلى اليسار. في هذه الحالة، والنتيجة هي شجرة مع الشكل. 9ب، يعادل الشجرة 8أ، ولكن لا يتطلب استبدال العلامات.

وبالمثل، من اليمين إلى اليسار، تحتاج إلى تحليل التعبيرات التي تحتوي على عوامل الضرب والقسمة.

أرز. 9. أشجار بناء الجملة للتعبير أ – ب + جعند القراءة من اليسار إلى اليمين (أ) ومن اليمين إلى اليسار (ب).

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

7.3. تحديد عقدة الشجرة برقمها

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

على سبيل المثال، لنفترض أنك تريد أن تفعل كحلقات متداخلة نالخطوات في كل:

من أجل i1:= 0 إلى n-1 افعل من أجل i2:= 0 إلى n-1 افعل من أجل i3:= 0 إلى n-1 افعل ...

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

الإجراء NestedCycles(الفهارس: مجموعة من الأعداد الصحيحة؛ n، k، العمق: عدد صحيح)؛ فار ط: عدد صحيح؛ تبدأ إذا كان العمق

للتخلص من التكرار وتقليل كل شيء إلى دورة واحدة، لاحظ أنه إذا قمت بترقيم الخطوات في نظام أرقام الجذر ن، ثم تحتوي كل خطوة على رقم يتكون من الأرقام i1، i2، i3، ... أو القيم المقابلة من مصفوفة الفهارس. أي أن الأرقام تتوافق مع قيم عدادات الدورة. رقم الخطوة بالتدوين العشري العادي:

سيكون هناك مجموع الخطوات ن ك. من خلال مراجعة أرقامهم في نظام الأرقام العشرية وتحويل كل منهم إلى نظام الجذر ن، نحصل على قيم الفهرس:

M:= round(IntPower(n, k)); لأني:= 0 إلى M-1 لا تبدأ العدد:= i; بالنسبة لـ p:= 0 إلى k-1، ابدأ الفهارس:= Number mod n; الرقم:= الرقم div n; نهاية؛

DoSomething(Indexes); نهاية؛

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

أسئلة التحكم

1. حدد ما ستفعله الإجراءات والوظائف العودية التالية.

(أ) ما الذي سيطبعه الإجراء التالي عند استدعاء Rec(4)؟

توصية الإجراء (أ: عدد صحيح)؛ ابدأ الكتابة (أ) ؛ إذا كان a>0 ثم Rec(a-1); writeln(أ); نهاية؛

(ب) ما قيمة الدالة Nod(78, 26)؟

إيماءة الوظيفة (أ، ب: عدد صحيح): عدد صحيح؛ ابدأ إذا أ > ب ثم إيماءة:= إيماءة(أ – ب، ب) وإلا إذا ب > أ ثم إيماءة:= إيماءة(أ، ب – أ) إيماءة أخرى:= أ؛ نهاية؛

(ج) ما الذي سيتم طباعته من خلال الإجراءات أدناه عند استدعاء A(1)؟

الإجراء أ(ن: عدد صحيح)؛ الإجراء B(ن: عدد صحيح)؛ الإجراء أ(ن: عدد صحيح)؛ ابدأ الكتابة (ن) ؛ ب(ن-1); نهاية؛ الإجراء B(ن: عدد صحيح)؛ ابدأ الكتابة (ن) ؛ إذا ن

(د) ما هو الإجراء الموضح أدناه عند الاتصال بـ BT(0, 1, 3)؟

الإجراء BT(x: حقيقي؛ D، MaxD: عدد صحيح)؛ ابدأ إذا كان D = MaxD ثم اكتبln(x) وإلا ابدأ BT(x – 1, D + 1, MaxD); بت(س + 1، د + 1، ماكسد)؛ نهاية؛ نهاية؛ 2. Ouroboros - ثعبان يلتهم ذيله (الشكل 14) عند فرده له طولل ، قطر حول الرأسد ‎سمك جدار البطند

. حدد مقدار الذيل الذي يمكنه ضغطه داخل نفسه، وكم عدد الطبقات التي سيتم وضع الذيل فيها بعد ذلك؟

أرز. 14. توسيع Ouroboros.

3. بالنسبة للشجرة في الشكل. يشير الشكل 10 أ إلى تسلسل زيارة العقد بترتيب الاجتياز الأمامي والخلفي والنهائي.

5. قم بتصوير شجرة بناء الجملة بيانياً للتعبير الحسابي التالي:

اكتب هذا التعبير بالتدوين البولندي العكسي.

6. بالنسبة للرسم البياني أدناه (الشكل 15)، اكتب مصفوفة الجوار ومصفوفة الإصابة.

مهام

1. بعد حساب المضروب عددًا كبيرًا بما فيه الكفاية من المرات (مليون أو أكثر)، قارن بين فعالية الخوارزميات العودية والتكرارية. كم مرة سيختلف وقت التنفيذ وكيف ستعتمد هذه النسبة على الرقم الذي يتم حساب مضروبه؟

2. اكتب دالة عودية تتحقق من وضع الأقواس بشكل صحيح في السلسلة. فإذا كان الترتيب صحيحاً، توافرت الشروط التالية:

(أ) عدد أقواس الفتح والإغلاق متساوي.
(ب) يوجد داخل أي زوج فتحة - قوس إغلاق مناظر، ويتم وضع الأقواس بشكل صحيح.

أمثلة على الموضع غير الصحيح:)(، ())(، ())(()، وما إلى ذلك).

3. يمكن أن يحتوي السطر على قوسين دائريين ومربعة. كل قوس فتح له قوس إغلاق مناظر من نفس النوع (دائري - دائري، مربع - مربع). اكتب دالة عودية تتحقق من وضع الأقواس بشكل صحيح في هذه الحالة.

مثال على الموضع غير الصحيح: ([)].

4. عدد هياكل الأقواس العادية بطول 6 هو 5: ()()(), (())(), ()(()), ((())), (()()).
اكتب برنامجًا عوديًا لإنشاء جميع هياكل الأقواس المنتظمة ذات الطول 2 ن.

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

(أ) إذا تم وضع الهيكل الأصغر بين قوسين،
(ب) إذا تمت كتابة بنيتين أصغر بالتتابع.

5. قم بإنشاء إجراء يطبع جميع التباديل الممكنة للأعداد الصحيحة من 1 إلى N.

6. قم بإنشاء إجراء يطبع كافة المجموعات الفرعية للمجموعة (1، 2، ...، N).

7. قم بإنشاء إجراء يطبع كافة التمثيلات الممكنة للعدد الطبيعي N كمجموع الأعداد الطبيعية الأخرى.

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

تعليق: هذه الخوارزمية بديل. في حالة المصفوفات ذات القيمة الحقيقية، عادةً ما يسمح ذلك بأخطاء تقريب أصغر.

10. قم بإنشاء إجراء يرسم منحنى كوخ (الشكل 12).

11. إعادة إنتاج الشكل. 16. في الشكل، في كل تكرار تالٍ، تكون الدائرة أصغر بمقدار 2.5 مرة (يمكن جعل هذا المعامل معلمة).

الأدب

1. د. كنوث. فن برمجة الكمبيوتر. v. 1. (القسم 2.3. "الأشجار").
2. ن. ويرث. الخوارزميات وهياكل البيانات.