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

الخوارزمية الموضحة في الشكل 12 تسمى خوارزمية الشروط الدورية، حيث يتم فحص الحالة في بداية الحلقة أو عند مدخل الحلقة. > x عند مدخل الحلقة. إذا تم استيفاء الشرط ، فانتقل إلى المربع 4 ، وإلا فانتقل إلى المربع 6.

في الكتلة الرابعة ، يتم حساب قيمة المتغير في أنا= أنا+1 .

يعرض المربع الخامس النتيجة:

قيمة المتغير في,

أنا.

مثال : قم بعمل رسم تخطيطي لمثال (الشكل 12) ، والتحقق من حالة الخروج من الحلقة. في هذا المثال ، لا يتغير شرط المهمة ، والإخراج هو نفسه ، لكن المخطط الانسيابي سيكون مختلفًا.

حل : في هذه الحالة ، يتم التحقق من شرط الخروج من الحلقة: ذ<=x ... في ظل هذا الشرط ، لا يتم تنفيذ الحلقة. يجب نقل الحالة في مخطط الكتلة إلى نهاية الدورة ، بعد طباعتها. يتم تنفيذ الدورة طالما تم استيفاء الشرط ص> س.

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

تقدم الكتلة الثانية ذ=30 , x=4 .

الكتلة الثالثة تحسب قيمة المتغير في ، يتم حساب عدد الدورات المكتملة أنا= أنا+1 .

تعرض الكتلة الرابعة النتيجة:

قيمة المتغير في,

عدد الدورات المنجزة أنا.

الكتلة الخامسة تتحقق من الحالة ذ <= x للخروج من الحلقة. إذا تم استيفاء الشرط ، فسيتم الانتقال إلى الكتلة 6 ، وإلا ، إلى الكتلة 3 وتتكرر الدورة.

الشكل 13. خوارزمية حلقة ما بعد الشرط

أسئلة التحكم

1. مفهوم الخوارزمية.

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

3. الهياكل الأساسية الخوارزمية.

4. الكتل الرئيسية لخوارزمية الرسوم.

5. الهيكل الحسابي الخطي. مثال.

6. المتفرعة. مثال.

7. الهياكل الحسابية الدورية. مثال.

من الناحية العملية ، تعد الأشكال التالية لعرض الخوارزميات هي الأكثر شيوعًا:

· شفهي (محاضر في اللغة الطبيعية) ؛

· رسوم بيانية (صور من رموز بيانية) ؛

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

· البرمجيات (نصوص بلغات البرمجة).

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

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

· تعيين رقمين.

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

خلاف ذلك ، استمر في تنفيذ الخوارزمية ؛

· تحديد أكبر الأرقام.

· استبدل الأرقام الأكبر بالفرق بين الأرقام الأكبر والأصغر.

· كرر الخوارزمية من الخطوة 2.

الخوارزمية الموصوفة قابلة للتطبيق على أي أعداد طبيعية ويجب أن تؤدي إلى حل المشكلة.

الطريقة اللفظيةلا يستخدم على نطاق واسع للأسباب التالية:

· لم يتم صياغة مثل هذه الأوصاف بشكل صارم.

· المعاناة من الإسهاب في السجلات ؛

· السماح بالغموض في تفسير الأنظمة الفردية.

طريقة رسوميةعرض الخوارزميات أكثر إحكاما ومرئية مقارنة بالخوارزميات اللفظية.

هذا التمثيل الرسومي يسمى مخطط الخوارزميةأو مخطط كتلة.

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

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

1) كتلة البداية والنهاية

يعرض العنصر الإخراج إلى البيئة الخارجية والمدخلات من البيئة الخارجية (الاستخدام الأكثر شيوعًا هو بداية البرنامج ونهايته). يتم تسجيل الإجراء المقابل داخل الشكل.

2) كتلة العمل

القيام بعملية أو أكثر ومعالجة البيانات من أي نوع (تغيير قيمة البيانات ، نموذج العرض ، الموقع). داخل الشكل ، تتم كتابة العمليات نفسها مباشرةً ، على سبيل المثال ، عملية الإسناد: أ = 10 * ب + ج

3) كتلة المنطق

يعرض حل أو وظيفة من نوع التبديل بإدخال واحد ومخرجين بديلين أو أكثر ، يمكن تحديد واحد منها فقط بعد تقييم الشروط المحددة داخل هذا العنصر. يُشار إلى دخول عنصر ما بخط ، وعادةً ما يدخل في قمة رأس العنصر. إذا كان هناك مخارجان أو ثلاثة ، فعادةً ما يُشار إلى كل مخرج بخط يخرج من القمم المتبقية (الجانب والسفلي). إذا كان هناك أكثر من ثلاثة مخرجات ، فيجب إظهارها كسطر واحد يخرج من أعلى (غالبًا من أسفل) العنصر ، والذي يتفرع بعد ذلك. يمكن كتابة نتائج الحساب المقابلة بجوار الأسطر التي تمثل هذه المسارات. أمثلة الحل: بشكل عام - المقارنة (ثلاثة نواتج:> ،<, =); в программировании − условные операторы if (два выхода: true, false) и case (множество выходов).

تحويل البيانات إلى نموذج مناسب للمعالجة (الإدخال) أو عرض نتائج المعالجة (المخرجات). لا يُعرّف هذا الرمز حامل البيانات (تُستخدم رموز محددة للإشارة إلى نوع حامل البيانات).

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

خوارزمية Forking - خوارزمية تحتوي على شرط واحد على الأقل ، ونتيجة للتحقق يمكن إجراء التقسيم إلى عدة فروع متوازية للخوارزمية.

الخوارزمية الخطية هي مجموعة من الأوامر (التعليمات) تنفذ بالتتابع في وقت واحد تلو الآخر.

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

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

الخوارزمية

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

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

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

مفهوم الخوارزمية

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

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

1. اختر حلاً.
2. ادرس كل تفاصيل الطريقة المختارة.
3. اشرح النقطتين الأوليين لفناني الأداء المستقبلي بلغة يفهمها.

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

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

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

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

الخصائص الأساسية للخوارزمية

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

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

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

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

قدرات الكمبيوتر

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

الأرقام الثابتة تعني جميع الأرقام: 3،15 ، 100 ، 105 ، ميزتها هي الثبات أثناء تشغيل البرنامج بالكامل. تغير المتغيرات قيمتها أثناء تنفيذ الكود وعادة ما يتم الإشارة إليها بالحروف: x ، y ، max ، min ، إلخ.

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

العمليات التي يستطيع الكمبيوتر القيام بها:

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

هذه هي العمليات الأساسية التي يمكن أن تقوم بها معظم لغات البرمجة.

طرق لوصف الخوارزميات

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

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

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

أجور Alg (int ST، real ZP) arg ST res ZP start if ST

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

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

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

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

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

سيتم وصف مزيد من التفاصيل حول كل خوارزمية حسابية مع أمثلة أدناه.

مبادئ الخوارزمية

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

تصحيح الخوارزمية

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

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

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

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

مفتاح حل هذه المشكلة هو قفص مؤقت إضافي يجب استخدامه لمبادلة الحيوانات.

خوارزميات التشعب

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

دعنا نعطي مثالاً عن خوارزمية لحل مشكلة إيجاد الأكبر بين ثلاثة أعداد.

خوارزمية دورية

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

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

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

دعونا نبني خوارزمية دورية باستخدام مثال إيجاد عامل العدد N.

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

هناك عدد من الخوارزميات الأخرى التي تختلف في التصنيف أو الأصل.

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

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

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

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

أرز. 1. لعبة اللوح ()

تعتبر اللعبة المعروفة "Monopoly" أو "Manager" نموذجًا أكثر تعقيدًا لتنفيذ الخوارزمية (الشكل 2).

أرز. 2. لعبة "مونوبولي" ()

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

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

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

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

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

"الاحتكار"

Monopoly هي واحدة من أكثر ألعاب الطاولة شعبية. قواعدها بسيطة للغاية ومفهومة لكل من لعبها مرة واحدة على الأقل (الشكل 4).

أرز. 4. لعبة "مونوبولي" ()

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

وفقًا لمصادر رسمية - Parker Brothers ، التي تنتج Monopoly منذ عام 1935 حتى يومنا هذا - ولدت لعبة اللوحة الأسطورية على النحو التالي. في عام 1934 ، عرض مهندس عاطل عن العمل تشارلز دارو (الشكل 5) المكتب أعلاه لإطلاق لعبة اخترعها حول تجارة العقارات.

أرز. 5 - تشارلز دارو ()

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

ومع ذلك ، في الوقت نفسه ، هناك أيضًا ألعاب سابقة معروفة تذكرنا بشكل لافت للنظر بـ "الاحتكار". اتضح أن دارو كان فقط أول من أسرع وحصل على براءة اختراع للمتعة "الشعبية"؟ نعم و لا. ألقت التحقيقات في السنوات الأخيرة الضوء على الغموض الكامن وراء أصول لعبة Monopoly.

في النصف الثاني من القرن التاسع عشر ، عاش الاقتصادي السياسي هنري جورج وعمل في الولايات المتحدة. اقترح استبدال جميع الرسوم بضريبة واحدة - على الأرض. مشبع بأفكاره ، في يناير 1904 ، حصل ماجي على براءة اختراع للعبة اللوح The Landlord’s Game ، والتي تشبه "الاحتكار" الحالي من حيث القواعد والمظهر. يُعتقد أن "لعبة مالك الأرض" لها نوعان مختلفان من القواعد: بعد أن لعبوا لعبة وفقًا لقوانين الضرائب الحالية ، تحول اللاعبون إلى النموذج الذي اقترحه جورج - ومن المفترض أنهم أصبحوا مقتنعين بضرورته. مزايا. وهكذا ، فإن اللعبة لم تكن ترفيهية ، بل كانت أداة للصراع الأيديولوجي.

لم يأت إلى الإنتاج الضخم ، ولكن The Landlord’s Game انتشرت تدريجيًا في جميع أنحاء أمريكا الشمالية في نسخ الحرف اليدوية. تراجعت زيادة الاهتمام بلعبة اللوح في سنوات الكساد الكبير: كان الآلاف من العاطلين عن العمل سعداء بتخيل أنفسهم كأكياس نقود على طاولة القمار على الأقل. استغرق ظهور رجل مغامر مثل تشارلز دارو بضعة أشهر - وقد جاء على مدى عقود عديدة بعد أن اكتسب شهرة المخترع الوحيد لـ "الاحتكار".

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

أرز. 6. لعبة "مدير" ()

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

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

أرز. 3. المصباح الكهربائي ()

على سبيل المثال ، الخوارزمية التالية لاستبدال المصباح المحترق تكون خطية (الشكل 3):

1. قم بإيقاف تشغيل مفتاح الضوء.

2. فكّ المصباح الكهربائي المحترق ؛

3. المسمار في لمبة جديدة.

4. قم بتشغيل المفتاح للتحقق من أن الضوء مضاء.

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

(مخطط كتلة (الشكل 7.) انظر نهاية الملخص)

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

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

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

خلاف ذلك<действия 2>

إذا كان لديك مال ، فاشترِ الخبز ، ولا تشتريه بعد ذلك.

إذا كنت ستكون في المركز اليوم ، فاتصل بي ، ELSE لا تفعل ذلك.

إذا تم تعلم الدروس ، ثم اذهب في نزهة ، وتعلم ELSE الدروس.

في بعض الحالات<действия 2>قد يكون غائبا. قد يكون هذا بسبب وضوحها (على سبيل المثال ، في المثال الأول - من الواضح أنه إذا لم يكن لديك مال ، فلا يمكنك ببساطة شراء الخبز) ، وعدم الحاجة إليه.

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

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

إذا كنت تريد أن تكون بصحة جيدة ، ثم أعصابك.

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

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

(مخطط انسيابي (الشكل 8.) انظر في نهاية الملخص)

الشروط اللازمة والكافية

لقد ناقشنا معك بالفعل أن هناك شروطًا ضرورية وكافية.

مثال على شرط مسبق سيكون:

لكي تصبح طبيباً ، يجب أن تكمل شهادة الطب.

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

مثال على شرط كاف سيكون:

للحصول على برودة ، فقط قم بتشغيل مكيف الهواء.

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

بالطبع ، هناك شروط ضرورية وكافية في نفس الوقت (تسمى هذه الشروط يعادل). على سبيل المثال:

لفصل الصيف القادم ، من الضروري والكافي أن ينتهي الربيع.

في الواقع ، إذا انتهى الربيع ، يأتي الصيف ، وإذا لم ينته الربيع ، فلا يمكن للصيف أن يأتي. أي أن شروط نهاية الربيع وبداية الصيف متكافئة.

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

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

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

1. خذ تفاحة.

2. معرفة ما إذا كانت فاسدة.

3. إذا كانت فاسدة - قم برميها بعيدًا ، إذا لم تكن كذلك - قم بنقلها إلى صندوق آخر.

من الضروري تنفيذ هذه المجموعة من الإجراءات حتى نفاد التفاح الموجود في الصندوق.

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

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

يجب تطوير الخوارزميات لتجنب مثل هذه المواقف.

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

في هذه الحالة ، يبدو مخطط الكتلة الخاص بها كما يلي: (مخطط الكتلة (الشكل 9.) انظر في نهاية الملخص)

ناقشنا في هذا الدرس ثلاثة أنواع من الخوارزميات - الخوارزميات الخطية ، والخوارزميات المتفرعة ، والخوارزميات المتكررة.

في الدرس التالي ، سنناقش كيفية كتابة الخوارزميات عمليًا.

منخل إراتوستينس

لنتذكر تعريف العدد الطبيعي الأولي.

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

أمثلة على الأعداد الأولية: 2 ، 3 ، 5 ، 7.

أمثلة على الأرقام المركبة: 4 ، 6 ، 8.

في القرن الثالث قبل الميلاد ، اقترح عالم الرياضيات اليوناني إراتوس فين الخوارزمية التالية للعثور على جميع الأعداد الأولية الأقل من رقم معين NS:

1- اكتب كل الأعداد الطبيعية من 1 إلى ن;

2. حذف 1 ؛

3. وضع خط تحت أصغر الأرقام غير المميزة ؛

4. اشطب جميع الأرقام التي هي من مضاعفات الرقم المسطر في الخطوة السابقة ؛

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

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

لنفكر في نتيجة هذه الخوارزمية. لنكتب جميع الأعداد الأولية من 1 إلى 25.

لنكتب الأعداد من 1 إلى 25.

دعنا نحذف 1. الآن سوف نؤكد على الاثنين. اشطب جميع الأرقام الزوجية.

نظرًا لأنه لا يتم تمييز جميع الأرقام ، ضع خطًا تحت 3. اشطب الآن جميع الأرقام التي تقبل القسمة على 3.

بما أنه لم يتم وضع علامة على جميع الأرقام ، ضع خط 5. الآن ، اشطب الرقم 25.

نظرًا لأنه لا يتم تمييز جميع الأرقام ، فإننا نشدد على 7.

لا يمكنك شطب أي شيء ، ولكن لا يتم تمييز جميع الأرقام ، لذلك نؤكد على 11.

لا يمكنك شطب أي شيء ، ولكن لا يتم تمييز جميع الأرقام ، لذلك نؤكد على 13. مرة أخرى ، لا يمكننا حذف أي شيء - نضع خط تحت 17 ، ثم 19 و 23.

تم وضع علامة على جميع الأرقام الآن.

نحصل على الأعداد الأولية: 2 ، 3 ، 5 ، 7 ، 11 ، 13 ، 17 ، 19 ، 23.

أرز. 7.مخطط كتلة لتغيير المصباح الكهربائي

أرز. 8. مخطط انسيابي لأعمال طالب الصف السادس

أرز. 9. كتلة الرسم البياني للمنبه

فهرس

1. Bosova L.L. المعلوماتية وتكنولوجيا المعلومات والاتصالات: كتاب مدرسي للصف السادس. - م: BINOM. معمل المعرفة 2012.

2. Bosova L.L. المعلوماتية: مصنف للصف السادس. - م: BINOM. معمل المعرفة 2010.

3. Bosova L.L.، Bosova A.Yu. دروس المعلوماتية في الصفوف 5-6: دليل منهجي. - م: BINOM. معمل المعرفة 2010.

1. بوابة الإنترنت "شبكتنا" ()

2. بوابة الإنترنت "سوق المعرفة هايبر ماركت" ()

3. بوابة الإنترنت "kaz.docdat.com" ()

واجب منزلي

1. §3.4 (Bosova L.L. المعلوماتية وتكنولوجيا المعلومات والاتصالات: كتاب مدرسي للصف السادس).

2. الصفحة 81 مهمة 2 ، 6 (Bosova L.L. المعلوماتية وتكنولوجيا المعلومات والاتصالات: كتاب مدرسي للصف السادس).

3. الصفحة 82 مهمة 9 ، 11 ، 13 ، 14 (Bosova L.L. المعلوماتية وتكنولوجيا المعلومات والاتصالات: كتاب مدرسي للصف السادس).

4. * الصفحة 83 مهمة 15 (Bosova L.L. المعلوماتية وتكنولوجيا المعلومات والاتصالات: كتاب مدرسي للصف السادس).