عرض خطي للخوارزمية. أنواع الخوارزميات: خطية ، متفرعة ، دورية. طرق لوصف الخوارزميات

حلقة مع شرط مسبق

في إطار برمجة منظمةيمكن وصف مشاكل الحل الحسابي باستخدام ما يلي الهياكل الحسابية:

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

وصف الهياكل الخوارزمية المختلفة بلغة المخططات الكتل

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

المتفرعة if-else
إذا أرجع تعبير الشرط صحيحًا (صواب) ، فسيتم تنفيذ الخوارزمية على طول فرع "نعم" ، وإذا لم يتم استيفاء الشرط (خطأ) ، فسيتم التنفيذ على طول فرع "لا". لأي نتيجة للتعبير الشرطي ، من المستحيل العودة إلى الفرع الرئيسي للبرنامج ، وتجاوز خطوات إضافية.

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

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

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

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

>> أنواع الخوارزميات

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

الخوارزميات الخطية
الخوارزميات المتفرعة
خوارزميات مع التكرار.

الخوارزميات الخطية

التي يتم فيها تنفيذ الأوامر بالترتيب الذي تم كتابتها فيه ، أي بالتسلسل الواحد تلو الآخر ، يسمى الخطي.

على سبيل المثال ، خوارزمية غرس الأشجار التالية خطية:

1) حفر حفرة في الأرض.
2) أنزل الشتلات في الحفرة ؛
3) ملء الحفرة بالشتلات بالأرض ؛
4) سقي الشتلات بالماء.

باستخدام مخطط كتلة ، يمكن وصف هذه الخوارزمية على النحو التالي:

الخوارزميات المتفرعة

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

يمكن وصف منطق اتخاذ القرار على النحو التالي:

لو<условие>من ثم<действия 1>خلاف ذلك<действия 2>

أمثلة:

إذا أردت أن تكون صحيبعد ذلك استلقِ على الأريكة طوال اليوم.
إذا طارت طيور السنونو على ارتفاع منخفض ، فسوف تمطر ، وإلا فلن تمطر ؛
إذا تم تعلم الدروس ، ثم اذهب في نزهة ، وتعلم ELSE الدروس.

في بعض الحالات<действия 2>قد يكون غائبا

لو<условие>من ثم<действия 1>

مثال:

إذا أطلق على نفسه حمولة ، صعد إلى الخلف.

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

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

وهكذا ، بمساعدة مخطط الكتلة ، يمكنك تمثيل المنطق بوضوح شديد عند حل المشكلة التالية.

من بين ثلاث عملات من نفس الفئة ، واحدة مزيفة (أخف). كيف أجده باستخدام ميزان بدون أوزان؟

خوارزميات التكرار

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

تحتوي خوارزمية دوراتيسمى جولة روبن أو خوارزمية متكررة.

يُطلق على الموقف الذي لا ينتهي فيه تنفيذ الحلقة أبدًا حلقة لا نهاية لها. يجب تطوير الخوارزميات لتجنب مثل هذه المواقف.

لنلق نظرة على مثال من الرياضيات.

يُطلق على العدد الطبيعي اسم "أولي" إذا كان يحتوي على قسومتين فقط: واحد والرقم نفسه 1.

2 ، 3 ، 5 ، 7 - الأعداد الأولية ؛ 4 ، 6 ، 8 - لا. في القرن الثالث قبل الميلاد ، اقترح عالم الرياضيات اليوناني إراتوستينس الخوارزمية التالية للعثور على جميع الأعداد الأولية الأقل من رقم معين ن:

1) اكتب جميع الأعداد الطبيعية من 1 إلى n ؛
2) حذف 1 ؛
3) ضع خط تحت أصغر الأرقام غير المميزة ؛
4) اشطب جميع الأرقام التي هي مضاعفات ما تحته خط في الخطوة السابقة ؛
5) إذا كانت القائمة تحتوي على أرقام غير محددة ، فانتقل إلى الخطوة 3 ، وإلا فإن جميع الأرقام التي تحتها خط أولية.

هذه خوارزمية دورية. عند تنفيذه ، تتكرر الخطوات من 3-5 حتى توجد أرقام غير مميزة في القائمة الأصلية.

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

تذكر أن الرقم 1 ليس رقمًا مركبًا (يحتوي على أكثر من مقسومين) ولا عددًا أوليًا.

أهم شيء

يمكن تمييز ثلاثة أنواع من الخوارزميات بناءً على ترتيب تنفيذ الأمر:

> الخوارزميات الخطية.
> الخوارزميات المتفرعة.
> خوارزميات التكرار.

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

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

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

أسئلة ومهام

1. ما الخوارزميات تسمى الخطية؟
2. أعط مثالاً لخوارزمية خطية ،
3. يمكن لـ "الآلة الحاسبة" المؤدية تنفيذ أمرين فقط: الضرب في 2. ثم الجمع. ابتكر أقصر خطة للحصول على الرقم 50 من O.
4. ما هو شكل من أشكال تنظيم الأعمال يسمى المتفرعة؟
5. ما هي الشروط التي يجب على بطلة قصة "الإوز البجع" أن تستوفيها؟
6. أعط مثالاً على خوارزمية تحتوي على تفريع "
7. اقرأ مقتطفًا من قصيدة جيه روداري "ما هي رائحة الحرف اليدوية؟":

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

إعادة الصياغةحول المهن باستخدام عبارة "إذا ... ثم" /

8. تذكر الأبطال الذين تتخذ الحكايات الشعبية الروسية قرارات تحدد مصيرهم.
9. من أصل 9 عملات من نفس الفئة ، هناك واحدة زائفة (أفتح). كم عدد الأوزان على الميزان بدون أوزان يمكنك تحديدها؟
10. ما هو شكل تنظيم الأعمال يسمى التكرار؟
11. أعط مثالاً لخوارزمية تحتوي على التكرار.
12. في أي أعمال أدبية تعرفها ، يتم إجراء شكل دوري لتنظيم الأعمال؟
13. أين سيكون المؤدي الذي أكمل مجموعة الفرق التالية 16 مرة على التوالي؟

أمشي 10 أمتار للأمام

تدوير 90 درجة في اتجاه عقارب الساعة

14. ما مجموعة الإجراءات وكم مرة يجب تكرارها عند حل المشكلة التالية؟

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

15. تذكر مشكلة الآلة الحاسبة التي يمكنها فقط الضرب في 2 وإضافة 1. سيكون من الأسهل بكثير تطوير خوارزميات منطقية لها إذا استخدمت مخطط الكتلة التالي:

باستخدام هذا المخطط الانسيابي ، طور خوارزميات منطقية للحصول على الأرقام 1024 و 500 من الرقم 0.

Bosova L. L. المعلوماتية: كتاب مدرسي للصف 6 / L.L. Bosova. - الطبعة الثالثة ، القس. و أضف. - م: BINOM. معمل المعرفة 2005. - 208 ص: مريض.

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

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

يتم تقسيم جميع الخوارزميات حسب هيكلها إلى ثلاث مجموعات:

خطي؛

المتفرعة

دوري.

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

أرز. 8. رسم تخطيطي للخوارزمية الخطية

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

يمكن أن تحتوي هذه الخوارزمية على خيارين:

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

2. هناك صيغتان من العمليات الحسابية ، وتعمل الخوارزمية وفقًا للمبدأ المنطقي التالي: IF (الشرط) - ثم (الصيغة 1) ، ELSE (الصيغة 2).

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

الشكل 9. مخططات انسيابية لخوارزميات التفرع

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

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

مع عدد معروف من التكرارات (الدورات)

الخوارزميات التكرارية التي لا يكون فيها عدد الدورات معروفًا مسبقًا ويتم تحديد نهاية الدورة من خلال بعض الشروط (بشكل أساسي دقة حسابية معينة).

دعونا ننظر في كلا النوعين من الخوارزميات.