خانه
گاما

درسنامه آموزشی دانش فنی پایه کلاس دهم شبکه و نرم افزار رایانه

پودمان 2: حل مسئله (الگوریتم و فلوچارت)

بازدید59/8 K
تاریخ بروزرسانی1400/05/14

دانا کنجکاو است که در مورد مریم میرزاخانی بداند. در حین جستجو به توصیف او از دستیابی به حل مسئله برمی‌‌خورد:

«گاهی مواقع احساس می‌کنم در یک جنگل بزرگ هستم و نمی‌دانم به کجا می‌روم؛ ولی به طریقی به بالای تپه‌ای می‌رسم و می‌توانم همه چیز را واضح‌تر ببینم. آنچه آن گاه رخ می‌دهد، واقعاً هیجان‌انگیز است.»

دانا دوست دارد در مورد این حس خوب و دستیابی به حل مسائل بداند.

حل مسئله

قرن‌ها توانایی حل مسئله را خلاقیت ذاتی افراد می‌دانستند. امروزه با استفاده از روش‌های حل مسئله و دسته‌بندی مسائل و با تکیه بر تمرین و تکرار می‌توان این مهارت را کسب و در حل مسائل روزمره از آن بهره گرفت. البته درحل مسائل تأثیر هوش و خلاقیت ذاتی افراد قابل انکار نیست در نظام‌های آموزشی موفق دنیا، حل مسئله به عنوان یک مهارت مهم به کودکان آموزش داده می‌شود. این مهارت به کودکان کمک می‌کند تا در رفع مشکلات خود تصمیم درست را اتخاذ کنند.

اما حل مسئله ابعادی گسترده‌تر از تصمیم‌گیری دارد. دانش حل مسئله با طرح نقشه‌ای، ما را از مبدأ به مقصد هدایت می‌کند. مهم‌ترین سؤالی که در برخورد با هر مسئله در ذهن نقش می‌بندد شناخت و چگونگی حل آن است.

دانا امروز دیر به هنرستان رسید. تأخیر ورود باعث شد که نتواند در کلاس دانش فنی پایه زنگ اول حاضر شود. این اولین بار نیست که او دیر می‌رسد. او در راهروی جلوی دفتر منتظر است تا خانواده و معاون مدرسه مشکل تأخیر را حل کنند. در زمان انتظار به این فکر کرد که آیا می‌تواند مشکل را خودش حل کند تا دیگر دچار چنین شرایطی نشود.

دانا سؤالات زیر و پاسخ آن‌ها را از ذهن گذراند:

- چرا دیر به مدرسه رسیدم؟ چون اتوبوس آهسته حرکت می‌کرد.
- چرا اتوبوس آهسته حرکت می‌کرد؟ چون ترافیک بود.
- چرا ترافیک بود؟ چون در این ساعت همه به سر کار می‌روند.
- چرا این ساعت را برای رفتن به مدرسه انتخاب کردم؟ چون از خانه دیر بیرون آمدم.
- چرا از خانه دیر بیرون آمدم؟ چون تا وسایلم را آماده کردم دیر شد.

دانا علت مشکل را پیدا کرد. اکنون مسئله دانا این است که صبح به موقع از خانه بیرون برود. اما راه حل چیست؟
حالا او می‌داند که راه حل این مسئله این است که هر شب پیش از خوابیدن وسایلش را آماده کند.

در اینجا روش حل، چراهایی بود که فرد را به ریشه مشکل هدایت می‌کرد. با دانستن ریشه اصلی مشکل می‌توان راه حلی برای مسئله آن به دست آورد.

ریشۀ اصلی مشکل

این روش حل مسئله «پنج چرا» نام دارد در این روش با هر «چرا» دامنه دلایلی که باعث مسئله یا مشکل است محدودتر می‌شود تا ریشه اصلی مشکل مشخص شود. تعداد چراها بستگی به پیچیدگی مسئله دارد و همواره 5 تا نیست.

فعالیت منزل (صفحهٔ 35 کتاب درسی)

 

یکی از مشکلات روزمره خود را با استفاده از روش بالا ریشه‌یابی کنید و مسئله مربوط به آن را حل کنید.

فعالیت کلاسی (صفحهٔ 36 کتاب درسی)

 

راه حل دیگری برای مسئله سریع‌ترین تایپیست پیشنهاد دهید.

فعالیت کلاسی (صفحهٔ 36 کتاب درسی)

 

1- اگر هنرآموز عدد 9 را صدا بزند کدام هنرجو باید پاسخ گو باشد؟

2- آیا هنرآموز روش درستی برای انتخاب هنرجو استفاده کرده است؟ چرا؟

مسائل مطرح شده برای دانا بسیار جالب بودند و او توانست به سادگی درستی راه حل آن‌ها را درک کند. اکنون از مهندس امیدزاده ، هنرآموز دانش فنی پایه خود می‌پرسد که چگونه می‌تواند چنین راه حل‌هایی را کشف کند؟ مهندس امیدزاده می‌گوید که با داشتن اعتماد به نفس و دانستن روش‌های حل مسئله می‌تواند به کشف راه‌حل‌ها بپردازد.

روش پولیا

حل مسئله فرایندی پیچیده از تفکر است. برای حل مسئله روش‌های مختلفی مانند روش پولیا، پنج چرا، تریز و… وجود دارد. در سال 1945 جورج پولیا برای اولین بار روش چهار مرحله ای را برای حل مسئله تدوین کرد. (شکل 2)

روش حل مسئله پولیا: 1- فهمیدن مسئله 2- طراحی نقشه 3- اجرای نقشه 4- بازنگری
شکل 2- روش حل مسئله پولیا

1- شناخت یا فهمیدن مسئله: شناخت و داشتن فهم درست از یک مسئله با مطالعه دقیق آن رخ می‌دهد. در این مرحله به سؤالات زیر پاسخ داده می‌شود:

- چه می‌خواهیم؟ مجهول‌ها چیست؟
- چه داریم؟ داده‌های مسئله چه هستند؟
- با چه شرایطی مواجه هستیم؟

2- طراحی نقشه: پیچیده‌ترین بخش حل مسئله است. در این بخش باید به سؤال زیر پاسخ داده شود:
با توجه به شرایط مسئله، ارتباط بین داده‌ها و مجهول‌ها چیست؟
پس از یافتن پاسخ، نقشه طرح شده در قالب الگوریتم یا روندنما بیان می‌شود.

3- اجرای نقشه: نقشه برای رسیدن به جواب اجرا می‌شود. برای افزایش دقت و سرعت می‌توان نقشه را با یک زبان برنامه‌نویسی نوشت و در یک رایانه اجرا کرد.

4- بازنگری: در این مرحله درستی جواب بررسی شده و در صورت امکان برای بهبود و توسعه الگوریتم تلاش می‌شود. بررس یدرستی الگوریتم‌ها موضوعی مهم است و نیاز به ابزارهای پیشرفته ریاضی دارد.

فعالیت کلاسی (صفحهٔ 38 کتاب درسی)

 

در مسئله سریع‌ترین تایپیست چهار مرحله پولیا را مشخص کنید.

مسئله محاسبه نمره پایانی: در پودمان حل مسئله، یک هنرجو نمره مستمر 4/5 و نمره شایستگی 2 را کسب کرده است. نمره پایانی پودمان هنرجو چند است؟ 

شناخت مسئله خروجی‌ها: نمره پایانی پودمان
ورودی‌ها: نمره مستمر 4/5، نمره شایستگی 2
شرایط: نمره شایستگی 5 برابر نمره مستمر ارزش دارد.
طراحی نقشه ارتباط: 5 برابر نمره شایستگی با نمره مستمر جمع می‌شود.
اجرای نقشه $2 \times 5 + 4/5 = 14/5$
بازنگری یک تعریف است و نیاز به بررسی درستی ندارد.

فعالیت کلاسی (صفحهٔ 38 کتاب درسی)

 

معمای زیر را به روش پولیا حل کنید.
«ما و ما و نصف ما و نیمه‌ای از نصف ما گر تو هم با ما شوی، جملگی صد می‌شویم.»

بارش فکری (Brainstroming)

ایده‌پردازی در روش پولیا به صورت فردی است. در این روش شخص روی ایده‌های خود فکر می‌کند و به راه‌حل می‌رسد. در بارش فکری یک گروه ایده‌پردازی می‌کنند و درنتیجه می‌توان به ایده‌های بیشتری دست یافت. اگر بخواهیم سرعت حل مسئله افزایش پیدا کند باید قوانین زیر اجرا شوند:

قضاوت ممنوع: در زمان ایده‌پردازی باید از داوری و قضاوت در مورد ایده‌ها پرهیز کرد تا ایده‌پردازان بدون نگرانی ایده خود را بیان کنند.

ارائه ایده‌های جسورانه: گاهی ایده‌های غیرعادی و عجیب باعث می‌شود مسئله از زاویه دیگری دیده شود و راه حل‌های بهتری به دست آید.

تمرکز بر کمیت: هرچه تعداد ایده‌ها بیشتر باشد احتمال دست یافتن به راه‌حل اساسی و مناسب بیشتر است.

ترکیب و بهبود ایده‌ها: می‌توان با غربال و ترکیب ایده‌ها به ایده‌های بهتری دست یافت که در حقیقت باعث کامل‌تر شدن ایده‌ها می‌شود.

به مسئله زیر دقت کنید:

گروهی از دانشمندان توانستند با تلاش و پشتکار مستمرخود، یک ماشین زمان بسازند. آنچه آن‌ها را به انجام این پروژه مصمم ساخته بود، حل مسئله بحران آب بود. سفر با تجهیزات پیشرفته آغاز شده است. هدف این است که با سفر به گذشته‌هایی که آب به وفور یافت می‌شد از وقوع بحران آب جلوگیری کنند. با رسیدن به مقصد اقدامات لازم با هدف تغییر آینده انجام خواهد شد. شما در زمان حال باید ایده برتر را برای مأموران این سفر بفرستید تا به محض رسیدن، آن را اجرایی کنند.

کنجکاوی (صفحهٔ 39 کتاب درسی)

 

با خانواده به مسئله بحران آب فکر کنید. راهکار شما برای حل این مسئله چیست؟

برای اجرای این روش ایجاد چند گروه کوچک از یک گروه بزرگ بهتر است. هرگروه یک مدیر و یک دبیر برای غربال و جمع‌بندی ایده‌ها دارد. مشخصات یک گروه بارش فکری در نمون برگ مشخصات ثبت می‌شود:

برای هر ایده مطرح شده در گروه نیز یک نمون برگ دانش تهیه می‌شود. این فرم بر اساس مدل پولیا طراحی و واجد تمام جزئیات ایدۀ مطرح شده است.

بارش فکری سریع ترین تایپیست‌: ایده دیگری برای حل مسئله سریع‌ترین تایپیست مورد مطالعه قرار گرفته است.

فعالیت گروهی (صفحهٔ 42 کتاب درسی)

 

1- با هم گروهی خود این ایده را اجرا کنید و از درستی آن اطمینان حاصل کنید.
2- با توجه به ایده قبلی درمسئله سریع‌ترین تایپیست کدام ایده بهتر است؟ در کلاس بحث کنید.

پژوهش (صفحهٔ 42 کتاب درسی)

 

در مورد استارت آپ ویکند (Startup Weekend) تحقیق کنید.

الگوریتم (Algorithm)

عکس پروفایل مهندس امیدزاده در یکی از شبکه‌های اجتماعی نظر دانا را جلب می‌کند. بعضی از خطوط در تصویر رنگی شده‌اند. دانا در مورد آن‌ها از هنرآموز خود سؤال می‌کند. مهندس امیدزاده توضیح می‌‌دهد که با کمی دقت می‌تواند کلمه "al-Khowarizmi" را در متون رنگی پیدا کند. کلمه‌ای که به دفعات در منابع علمی جهان تکرار شده است. او ابوجعفر محمد بن‌موسی خوارزمی، ریاضی‌دان، ستاره‌شناس و جغرافی‌دان نامی‌ایران است. واژه الگوریتم از نام او گرفته شده است. کتاب جبر و مقابله خوارزمی از کتاب‌های تأثیرگذار در زمینه ریاضیات است. شیوه حل مسئله در آن کتاب، امروزه الگوریتم نامیده می‌شود.

الگوریتم برای بیان حل مسئله به کار می‌رود. با ظهور نمادها در ریاضیات، استفاده از آن برای مدتی کنار گذاشته شد. اما با ظهور ماشین‌های محاسباتی دوباره مورد توجه قرار گرفت. اگر نتوان حل مسئله‌ای را با این شیوه بیان کرد، آن مسئله را محاسبه ناپذیر می‌گویند. الگوریتم‌ها متون دقیقی هستند که شروع و پایان و ترتیب و توالی جمله‌ها در آن‌ها از اهمیت بالایی برخوردار است.

در این پودمان بیشتر به فهمیدن مسئله و طراحی نقشه پرداخته می‌شود. بنابراین برای نوشتن الگوریتم می‌توان به طور خلاصه عمل کرد. از این رو سه‌گام زیر دنبال می‌شود:

گام اول: خروجی‌ها کدام‌اند؟
گام دوم: ورودی‌ها کدام‌اند؟
گام سوم: ارتباط ورودی‌ها با خروجی‌ها چیست؟ این ارتباط با توجه به شرایط مسئله شکل می‌گیرد. این گام شامل پردازش‌های یک الگوریتم یا روندنما است.

الگوریتم معمای گرگ و گوسفند و کلم: کشاورزی می‌خواهد یک گرگ، یک گوسفند و یک بسته کلم را از یک سمت رودخانه به سمت دیگر ببرد. قایق او گنجایش حمل یکی از این‌ها را دارد. اگر کلم را حمل کند و گرگ و گوسفند تنها بمانند، گرگ گوسفند را می‌خورد. اگر گرگ را حمل کند، گوسفند کلم را می‌خورد. چگونه این سه را به آن طرف رودخانه منتقل کند؟
شناخت مسئله خروجی‌ها: انتقال گرگ و گوسفند و کلم به طرف دیگر رودخانه
ورودی‌ها: گرگ و گوسفند و کلم در این سمت رودخانه
الگوریتم 1- شروع
2- گوسفند را با خود به آن طرف می‌برد و خالی بر می‌گردد.
3- گرگ را به آن طرف می‌برد و گوسفند را بر می‌گرداند.
4- کلم را به آن طرف می‌برد و خالی بر می‌گردد.
5- گوسفند را به آن طرف می‌برد.
6- پایان

الگوریتم روشی گام‌به‌گام برای حل مسئله (Step By Step)

- هر الگوریتم دارای شروع و پایان است و پس از تعداد محدودی گام یا مرحله خاتمه می‌یابد. هر چند ممکن است تعداد این مراحل بسیار زیاد باشد.

- هر گام از الگوریتم باید دارای تعریفی روشن و قابل انجام باشد.

- الگوریتم شامل هیچ یا چندین ورودی (Input) است.

- الگوریتم یک یا چندین خروجی (Output) دارد.

- الگوریتم باید با توجه به محدودیت‌های مجری آن طراحی شود تا قابل انجام باشد.

فعالیت کلاسی (صفحهٔ 44 کتاب درسی)

 

1- در راه حل معمای گرگ و گوسفند و کلم ویژگی‌های فوق را بررسی کنید. آیا یک الگوریتم است؟

2- الگوریتمی برای اجرا به دو تن کاغذ و صدها سال محاسبه نیاز دارد. با توجه به انسان بودن مجری آن، می‌توان آن را الگوریتم دانست؟ در مورد پاسخ خود توضیح دهید.

الگوریتم محاسبه نمره پایانی: در پودمان حل مسئله، یک هنرجو نمره مستمر 4/5 و نمره شایستگی 2 را کسب کرده است. نمره پایانی پودمان هنرجو چند است؟

شناخت مسئله خروجی‌ها: نمره پایانی پودمان
ورودی ها: نمره مستمر 4/5، نمره شایستگی 2
طراحی نقشه 1- شروع
2- نمره 2 را پنج برابر کن.
3- حاصل را با 4/5 جمع کن.
4- نتیجه محاسبه را در کارنامه درج کن.
5- پایان

در دنیای رایانه برای اعشار از نقطه استفاده می‌شود. علامت / نماد تقسیم است.
اگر بخواهیم این الگوریتم دو نمره مستمر و نمره شایستگی را از ورودی دریافت کند. باید به جای نمره 4/5 از عبارت «نمره مستمر» و به جای نمره 2 عبارت «نمره شایستگی» قرار گیرد.
این دو عبارت همان مفهوم متغیر است. متغیرها، نمادهایی برای بیان مقادیر معین هستند.

طراحی نقشه 1- شروع
2- نمره مستمر را دریافت کن.
3- نمره شایستگی را دریافت کن.
4- نمره شایستگی را پنج برابر کن.
5- حاصل را با نمره مستمر جمع کن.
6- نتیجه محاسبه را در کارنامه درج کن.
7- پایان

در الگوریتم صفحه قبل در هر مرحله یک عملیات انجام می‌شود. اما می‌توان چندین عملیات را در یک مرحله از الگوریتم قرار داد. باید دقت کرد که با این کار، انجام هیچ‌کدام از مراحل دچار اشکال نشود و نیز ترتیب عملیات در جمله‌بندی رعایت شود.

تقسیم طراحی یک الگوریتم به سه واحد ورودی، پردازش و خروجی، خوانایی آن را بالا برده و بهبود الگوریتم را نیز ساده‌تر می‌سازد.

طراحی نقشه 1- شروع
2- نمره مستمر و شایستگی را دریافت کن.                       $ \Leftarrow $  ورودی
3- نمره مستمر را با پنج برابر نمره شایستگی جمع کن.       $ \Leftarrow $  پردازش
4- نتیجه محاسبه را در کارنامه درج کن.                          $ \Leftarrow $   خروجی
5- پایان

برای نوشتن الگوریتم این نکات در نظر گرفته شود:‌

- برای ورودی‌ها و خروجی‌ها از متغیرها استفاده شود.
- برای جمع از نماد «+»، تفریق «-»، ضرب «*» و تقسیم «/» استفاده شود.
- برای بیان ترتیب اجرا در عملیات ریاضی از پرانتز استفاده شود.
- در جدول زیر نمادهایی معرفی شده است. با این نمادها الگوریتم‌های فارسی بازنویسی می‌شود.

کلمات کلیدی متغیرها نمادهای ریاضی
خروجی ورودی شروع پایان نمره نمره مستمر نمره شایستگی جمع ضرب تفریق تقسیم
Output Input Start End score middleScore meritScore + * - /

استفاده از موارد فوق در الگوریتم زیر مشاهده می‌شود. این الگوریتم شبیه کدهای برنامه است و اصطلاحاً به آن شبه کد (Pseudo code) گفته می‌شود.

طراحی نقشه 1- Start
2- Input middleScore , meritScore
3- score $ \leftarrow $ middleScore + 5* meritScore
4- Output score
5- End

فعالیت کلاسی (صفحهٔ 45 کتاب درسی)

 

در مرحله سوم چرا برای ضرب پرانتز گذاری انجام نشده است؟ ترتیب انجام عملیات کدام است؟

الگوریتم حدس کولاتز: الگوریتمی بنویسید که یک عدد طبیعی از ورودی را دریافت کند و براساس روش کولاتز عدد بعدی را مشخص نماید. 

شناخت مسئله خروجی‌ها: حدس عدد بعدی
ورودی‌ها: یک عدد طبیعی یا عدد صحیح مثبت
طراحی نقشه در حدس کولاتز اگر عدد ورودی زوج (Even) یا فرد (Odd) باشد، شیوه محاسبه عدد بعدی متفاوت است. پس بهتر است دو الگوریتم متفاوت داشته باشیم.
الگوریتم ورودی فرد الگوریتم ورودی زوج
 1- Start
2- Input number
3- nextNumber $ \leftarrow $ 3*number+1
4- Output nextNumber
5- End
1- Start
2- Input number
3- nextNumber $ \leftarrow $ number / 2
4- Output nextNumber
5- End

دستور شرطی دستوری است که با اگر (if) شروع می‌شود. درصورت یکه شرط برقرار باشد عملیات آن انجام می‌‌‌‌‌‌‌‌‌‌شود و در غیر این صورت (else) عملیات دیگری انجام می‌شود. با دستورات شرطی می‌‌‌‌‌توان چند الگوریتم با شرایط مختلف را به یک الگوریتم تبدیل کرد و تشخیص شرایط را به این دستور سپرد.

طراحی نقشه الگوریتم به زبان فارسی شبه کد
1- شروع
2- عددی طبیعی را دریافت کن.
3- اگر عدد بر دو بخش پذیر است
عدد را بر دو تقسیم کن
در غیر این صورت
به سه برابر عدد یکی اضافه کن
4- عدد حاصل را نمایش بده.
5- پایان
1- Start
2- Input number
3- if (number % 2 = 0)
nextNumber $ \leftarrow $ number / 2
else
nextNumber $ \leftarrow $ 3*number + 1
4- Output nextNumber
5- End

نماد «٪» باقی‌مانده را محاسبه می‌کند. اگر عددی به دو بخش پذیر (زوج) باشد باقی‌مانده آن صفر است و در غیر این صورت (فرد) باقی‌مانده یک است. نماد «=» برای سنجش مساوی بودن دو مقدار به کار می‌رود و از نماد «$ \leftarrow $» برای مقداردهی متغیرها استفاده می‌شود.

فعالیت کلاسی (صفحهٔ 47 کتاب درسی)

 

اگر در الگوریتم فوق عبارت «در غیر این صورت» حذف شود، چه تغییری در الگوریتم ایجاد می‌شود؟

روندنما (Flowchart)

روند نما نموداری برای نمایش یک الگوریتم است. این نمودار جریان کاری یک الگوریتم را به تصویر می‌کشد و به صورت بصری مسیر حرکت داده‌ها را نشان می‌دهد. در روندنما از نمادهای گرافیکی استاندارد استفاده می‌شود (شکل 3).

شکل 3- نمادهای گرافیکی روندنما (شروع و پایان، مسیر اجرا، عملیات، شرط، خروجی، ورودی)
شکل 3- نمادهای گرافیکی روندنما

روندنما و الگوریتم محاسبه نمره پایانی: 

طراحی نقشه

1- Start
2- Input middleScore , meritScore
3- score $ \leftarrow $ middleScore +5 * meritScore
4- Output score
5- End

روندنما و الگوریتم حدس کولاتز: 

طراحی نقشه

1- Start
2- Input number
3- if (number % 2 = 0)
nextNumber $ \leftarrow $ number / 2
else
nextNumber $ \leftarrow $ 3*number + 1
4- Output nextNumber
5- End

روندنمای حدس کولاتز دو مسیر اجرا دارد. مسیر نارنجی برای ورودی زوج و مسیر سبز برای ورودی فرد است. تصمیم‌گیری (شرط) برای انتخاب مسیر در لوزی انجام می‌شود. هر شرط یک مسیر به برنامه اضافه می‌کند و در اجرا به ازای هر ورودی یکی از مسیرها اجرا می‌شود.

پژوهش (صفحهٔ 49 کتاب درسی)

 

چگونه در رایانه می‌توان دو مجری برای اجرای روندنما داشت؟

روندنما و الگوریتم سریع‌ترین تایپیست: شرکتی قصد دارد یک تایپیست استخدام کند. ملاک استخدام سرعت تایپ (تعداد کلمه در دقیقه) است و دو متقاضی برای استخدام وجود دارد. روندنمایی برای تشخیص بیشترین سرعت تایپ رسم کنید. سرعت تایپیست اول a و سرعت تایپیست دوم b در نظرگرفته می‌شود. با توجه به روندنمای داده شده، الگوریتم را بنویسید. 

طراحی نقشه

1- Start
2-

فعالیت کلاسی (صفحهٔ 50 کتاب درسی)

 

در روندنمای صفحه قبل به چه دلیل از متغیر max استفاده می‌شود؟ آیا نمی‌توان مانند روندنمای زیر از متغیرهای a و b برای نمایش در خروجی استفاده کرد؟

فعالیت کلاسی (صفحهٔ 50 کتاب درسی)

 

روندنما و الگوریتم سریع‌ترین تایپیست را برای سه متقاضی بنویسید.

1- Start
2-

فعالیت منزل (صفحهٔ 51 کتاب درسی)

 

1- روندنمایی رسم کنید که سال تولد سه نفر را از ورودی بخواند و سن بزرگ‌ترین فرد را نمایش دهد. الگوریتم آن را نیز بنویسید.

1-

2- روندنما و الگوریتم سریع ترین تایپیست را برای چهار متقاضی بنویسید.

3- با توجه به روش دوم مسئله سریع ترین تایپیست، برای دو تایپیست، الگوریتم و روندنما طراحی کنید.
راهنمایی: برای پیاده سازی عبارت «او یکی از کارت‌ها را پیش خود نگه داشت» بهتر است مقدار نوشته شده روی یکی از کارت ها را در متغیر Max قرار دهید.

توسعه و تعمیم الگوریتم

برای طراحی یک الگوریتم پیچیده نیازی به پیچیده فکر کردن نیست. الگوریتم‌های پیچیده از کنار هم قرار دادن الگوریتم‌های ساده ایجاد می‌شوند. برنامه‌های بزرگ مانند یک جورچین هستند. ابتدا الگوریتم‌های کوچک‌تر (قطعات جورچین) طراحی می‌شوند. سپس این قطعات کنار هم قرارگرفته و برنامه اصلی را ایجاد می‌کنند.

مسئله سریع‌ترین تایپیست را به خاطر آورید. ابتدا مسئله برای دو تایپیست حل شد و سپس روندنما برای سه تایپیست رسم شد. اگر لازم باشد که برای تعداد تایپیست بیشتری روندنما رسم شود، کار بسیار پیچیده خواهد شد. برای حل این مسئله با تعداد متقاضی بیشتر به صورت زیر عمل می‌شود:

با در نظر گرفتن سه واحد ورودی، پردازش و خروجی مجزا در طراحی، امکان تعمیم الگوریتم فراهم می‌شود. روندنمای سریع‌ترین تایپیست برای دو متقاضی Max2 نامیده شد. با ترکیب دو Max2 می‌توان سریع‌ترین تایپیست را از میان سه متقاضی تشخیص داد.

فعالیت گروهی (صفحهٔ 53 کتاب درسی)

 

1- به کمک هنرآموز بررسی کنید اگر به جای max1 در روندنمای بالا همان max را قرار دهیم آیا روندنما درست است؟ در صورت تأیید این موضوع آیا می‌توان روندنما را ساده‌تر کرد؟

2- به چند گروه تقسیم شوید با استفاده از Max2، جمع و تفریق، یک روندنما برای محاسبه Min2 طراحی کنید. نباید در طراحی Max2 تغییری ایجاد شود زیرا با این روش طراحی Min2 ساده است.

توجه: گروه‌ها می‌توانند این فعالیت را در چند روز انجام دهند. پس از جمع‌بندی آن توسط مدیر و دبیر گروه آن را در کلاس به‌صورت مکتوب ارائه دهند. 

فعالیت منزل (صفحهٔ 53 کتاب درسی)

 

1- با روش بالا، سریع‌ترین تایپیست را از میان 4 متقاضی مشخص کنید. دو ایده برای حل این مسئله ارائه کنید سپس روندنمای آن را رسم کنید.

2- برای Max2 در منزل چند نمونه روندنما در کاغذهای مختلف رسم کنید. سپس با برش و چسباندن آن روی یک مقوا Max3 و Max4 و Max5 را طراحی کنید.

ساده سازی الگوریتم‌ها

مسئله اردوی هنرجویی: هنرستان فنی ایران تصمیم به برگزاری یک اردوی تفریحی دارد. شرط شرکت در اردو داشتن رضایت والدین است. مدیر مدرسه به هنرجویان گفته است در صورتی اردو برگزار خواهد شد که حداقل دو نفر از هنرآموزان در این اردو حضور داشته باشند و هوا نیز آفتابی باشد. برای برگزاری اردو باید هر سه شرط برقرار باشد.

شناخت مسئله

ورودی‌ها:
- رضایت والدین (parent): مقدار true به منزله داشتن رضایت والدین و false عدم رضایت والدین است.
- وضعیت هوا (sun): مقدار true هوای آفتابی و false هوای نامساعد را نشان می‌دهد.
- تعداد هنرآموزان (teacher): عددی صحیح مثبت است.

خروجی‌ها:
- وضعیت اردو (camp): مقدار true به معنی برگزاری اردو و false به معنی لغو اردو است.

شرایط:
- داشتن رضایت والدین (parent = true)
- هوای آفتابی (sun = true)
- همراهی حداقل دو هنرآموز (teacher>=2)

برای نمایش مفاهیمی که دو حالت دارند، می‌توانیم از yes/no و on/off یا true/false استفاده کنیم. در زبان‌های برنامه‌نویسی عموماً از true/false استفاده می‌شود. true به معنی درست و false به معنی نادرست است. متغیر حاوی true/False متغیر منطقی نام دارد که می‌توانیم مقدار اولیه آن را false در نظر بگیریم. بهتر است مقداردهی اولیه هر متغیری را به صورت صریح انجام دهیم.

فعالیت کلاسی (صفحهٔ 54 کتاب درسی)

 

1- جدول زیر را کامل کنید.

نمایش نمادین مفهوم به زبان فارسی
parent = true والدین رضایت دارند.
  والدین رضایت ندارند.
sun = false  
  هیچ همراهی ندارند.
teacher >= 3  
  دو همراه دارند.

نمایش نمادین «والدین رضایت دارند و هوا ابری است» چگونه است؟

طراحی نقشه (الگوریتم) 1- شروع
2- رضایت والدین، وضعیت هوا و تعداد هنرجویان را دریافت کن.
3- اگر والدین رضایت دارند.
        اگر هوا آفتابی است.
           اگر حداقل دو هنرآموز به اردو می‌آیند.
اردو برگزار می‌شود.
در غیر این صورت
اردو برگزار نمی شود.
در غیر این صورت
اردو برگزار نمی‌شود.
در غیر این صورت
اردو برگزار نمی‌شود.
4- پایان
1- Start
2- Input parent, sun, teacher
3- if (parent = true)
if ( )
if ( )
............................
else
............................
else
............................
else
camp $ \leftarrow $ false
4- Output camp
5- End
طراحی نقشه (روندنما)

فعالیت کلاسی (صفحهٔ 56 کتاب درسی)

 

1- الگوریتم و روندنمای اردوی دانش‌آموزی را کامل کنید.

2- بررسی کنید که چه تفاوتی بین الگوریتم فارسی و شبه کد وجود دارد.

3- نقشه دیگری برای این مسئله طرح کنید. (راهنمایی: به جای اینکه شرط بعدی به صورت تو در تو باشد هر شرط را پس از اتمام شرط دیگر قرار دهید.)

1- Start
2- Input parent, sun, teacher
3- if ( parent = true) camp $ \leftarrow $ true
4- if (………)
…..
……
7- End

4- الگوریتم بالا را به صورت فارسی بنویسید و روندنمای آن را ترسیم کنید.

برای حالتی که سه شرط (parent=true, sun=true, teacher=2) برقرار باشد مسیر حرکت با رنگ بنفش نشان داده شده است و نتیجه مطلوب یعنی برگزاری اردو حاصل می‌شود.

اجرای نقشه

بازنگری - آیا نقشه اوّل را تأیید می‌کنید؟ چرا؟
- آیا نقشه دوم را تأیید می‌کنید؟ چرا؟

فعالیت کلاسی (صفحهٔ 57 کتاب درسی)

 

1- برای حالات زیر نقشه صفحه قبل را بررسی کنید و مسیر آن را با یک رنگ مشخص کنید.‌

parent = false, sun = true, teacher = 3
parent = true, sun = true, teacher = 1

2- برای مسیر باقی مانده یک شرط طراحی کنید.

parent = ?, sun = ?, teacher = ?

فعالیت منزل (صفحهٔ 57 کتاب درسی)

 

حالات فوق را در نقشه‌ای که طراحی کرده‌اید بررسی کرده و نظر خود را در مورد این نقشه بگویید.

به نظر می‌رسد که برگزاری یک اردوی ساده به نقشه‌ای پیچیده نیاز دارد و اگر کمی شرایط اردو را پیچیده‌تر کنیم به نقشه پیچیده‌تری نیاز است. در زبان روزمره، ما به سادگی این شرایط را درک می‌کنیم اما درک آن در یک ماشین محاسباتی پیچیده است.

انسان‌ها برای ارتباط با یکدیگر از زبان مشترک استفاده می‌کنند. الگوریتم و روندنما زبان مشترک همه برنامه‌نویسان هستند. برای اینکه در انتقال مفاهیم در یک زبان ابهام ایجاد نشود از منطق استفاده می‌شود. با استفاده از منطق راه حل‌ها ساده‌تر در قالب الگوریتم و روندنما بیان می‌شوند.

به متن ساده زیر که بخشی از یک گفتگوی روزانه هر شخصی می‌تواند باشد دقت کنید:

دیروز دانا با پدرش به خرید رفت. او یک دفتر نقاشی نیاز داشت. درحین انتخاب دفتر نقاشی یک دفترچه خاطرات نیز توجه او را به خود جلب کرد. پدر متوجه این موضوع شد و گفت: هم دفتر نقاشی و هم دفترچه خاطرات را برای او می‌خرد. دانا بسیار خوشحال شد چون متوجه شد که پدر مثل همیشه اگر امکان داشته باشد
به خواسته‌های دانا احترام می‌گذارد.

چه چیزی در جمله پدر، دانا را متوجه خرید هردو دفتر کرد؟ حرف «وَ» این پیام را به دانا منتقل کرد. این نمونه‌ای از به کارگیری منطق است که در زبان انگلیسی به آن AND می‌گویند. زبان‌های برنامه‌نویسی نیز این عملگر را دارند. پس می‌توان از آن در بیان راه حل یک مسئله استفاده کرد.

به الگوریتم زیر دقت کنید:

طراحی نقشه (الگوریتم) 1- Start
2- Input parent, sun, teacher
3- camp $ \leftarrow $ (parent = true) AND (sun = true) AND (teacher >= 2)
4- Output camp
5- End

فعالیت کلاسی (صفحهٔ 58 کتاب درسی)

 

روندنمای الگوریتم صفحه قبل را رسم کنید.

شک ندارم که این راه حل شما را شگفت زده کرده است. بله! به سادگی این مسئله قابل حل بود به شرطی که بامنطق باشیم.

اگر پدر به دانا می‌گفت: دفتر نقاشی یا دفترچه خاطرات را برایش می‌خرد. مسئله فرق می‌کرد. دانا برای اینکه بداند پدر کدام را برایش می‌خرد باید تا زمان خرید صبر کند. ممکن است پدر دفتر نقاشی را بخرد. ممکن است دفترچه خاطرات را بخرد. این امکان نیز وجود دارد که هر دو را بخرد. این همه تفاوت به خاطر وجود «یا» است که در زبان انگلیسی به آن OR گفته می‌شود.

فعالیت منزل (صفحهٔ 58 کتاب درسی)

 

1- اگر پدر می‌گفت: یا دفتر نقاشی یا دفترچه خاطرات را می‌خرم، چه برداشتی داشتید؟

2- اگر پدر می‌گفت: دفتر نقاشی را می‌خرم و این طور نیست که بتوانم دفترچه خاطرات را هم بخرم. چه برداشتی داشتید؟

3- نقشه دوم را که در منزل برای رفتن به اردو کشیده‌اید به زبان منطقی بنویسید.

4- این مسئله را بدون استفاده از منطق و با استفاده از منطق حل کنید.
«هنرجویان هنرستان فنی ایران تصمیم گرفتند که به یک اردوی تفریحی بروند. اگر هنرجویی رضایت والدین را داشته باشد می‌تواند در این اردو شرکت کند. مدیر مدرسه به هنرجویان گفته است در صورتی اردو برگزار می‌شود که حداقل دو نفر از هنرآموزان شما را همراهی کرده و هوا آفتابی باشد یا دمای هوا کمتر از ده درجه نباشد.»

5- برای مسئله سه تایپیست با استفاده از منطق، الگوریتم نوشته و روندنمای آن را رسم کنید.

پودمان 2: حل مسئله (الگوریتم و فلوچارت)