حل مسئله و الگوریتم ها

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

مشکلات ، راه حل ها و ابزارها

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

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

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

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

یک برنامه رایانه ای مجموعه ای از دستورالعمل ها برای رایانه است. این دستورالعمل ها مراحلی را که رایانه باید برای اجرای یک طرح دنبال کند ، توصیف می کند.

الگوریتم طرحی برای حل یک مشکل است.

شخص باید یک الگوریتم را طراحی کند.

شخص باید یک الگوریتم را به یک برنامه رایانه ای ترجمه کند.

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

یک فرآیند توسعه الگوریتم

هر راه حل مشکل با یک برنامه شروع می شود. این طرح الگوریتم نامیده می شود.

روش های زیادی برای نوشتن الگوریتم وجود دارد. برخی از آنها بسیار غیررسمی هستند ، برخی از آنها کاملاً رسمی و ریاضی هستند و برخی دیگر کاملاً گرافیکی هستند. دستورالعمل اتصال یک پخش کننده DVD به تلویزیون یک الگوریتم است. یک فرمول ریاضی مانند πr 2 یک مورد خاص از الگوریتم است. این فرم تا زمانی که روش خوبی برای توصیف و بررسی منطق برنامه فراهم کند ، از اهمیت ویژه ای برخوردار نیست.

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

مرحله 1: توضیحات مربوط به مشکل را بدست آورید.

مرحله 2: مشکل را تجزیه و تحلیل کنید.

مرحله 3: یک الگوریتم سطح بالا را توسعه دهید.

مرحله 4: با افزودن جزئیات بیشتر ، الگوریتم را اصلاح کنید.

مرحله 5: الگوریتم را مرور کنید.

مرحله 1: توضیحات مربوط به مشکل را بدست آورید.

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

مشتری وظیفه ایجاد توضیحی از مشکل را بر عهده دارد ، اما این اغلب ضعیف ترین بخش فرآیند است. کاملاً متداول است که توضیحات مشکل از یک یا چند نوع نقص زیر رنج ببرد: (1) توضیحات به فرضیات غیرمستقیم متکی است ، (2) توضیحات مبهم است ، (3) توضیحات ناقص است ، یا (4)توضیحات دارای تضادهای داخلی است. این نقص ها به ندرت ناشی از بی دقتی مشتری است. در عوض ، آنها به این دلیل هستند که زبانهای طبیعی (انگلیسی ، فرانسوی ، کره ای و غیره) نسبتاً نادرست هستند. بخشی از مسئولیت توسعه دهنده شناسایی نقص در توصیف یک مشکل و همکاری با مشتری برای اصلاح این نقص ها است.

مرحله 2: مشکل را تجزیه و تحلیل کنید.

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

هنگام تعیین نقطه شروع ، باید با جستجوی پاسخ به سؤالات زیر شروع کنیم:

چه داده هایی در دسترس است؟

آن داده ها کجاست؟

چه فرمول هایی مربوط به مشکل هستند؟

چه قوانینی برای کار با داده ها وجود دارد؟

چه روابطی بین مقادیر داده وجود دارد؟

هنگام تعیین نقطه پایان، باید ویژگی های یک راه حل را توصیف کنیم. به عبارت دیگر، چگونه متوجه خواهیم شد که کارمان تمام شده است؟پرسیدن سوالات زیر اغلب به تعیین نقطه پایان کمک می کند.

چه حقایق جدیدی خواهیم داشت؟

چه مواردی تغییر خواهد کرد؟

چه تغییراتی در آن موارد ایجاد خواهد شد؟

چه چیزهایی دیگر وجود نخواهند داشت؟

مرحله 3: یک الگوریتم سطح بالا را توسعه دهید.

الگوریتم طرحی برای حل یک مسئله است، اما طرح ها در سطوح مختلفی از جزئیات ارائه می شوند. معمولاً بهتر است با یک الگوریتم سطح بالا شروع کنید که بخش اصلی یک راه حل را شامل می شود، اما جزئیات را به بعد واگذار می کند. ما می توانیم از یک مثال روزمره برای نشان دادن یک الگوریتم سطح بالا استفاده کنیم.

مشکل: من به یک کارت تولد برای برادرم، مارک، نیاز دارم.

تحلیل: من کارت ندارم. ترجیح می دهم کارت بخرم تا اینکه خودم کارت بخرم.

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

"به کدام فروشگاه مراجعه کنم؟"

چگونه به آنجا برسم: پیاده روی، رانندگی، دوچرخه سواری، اتوبوس؟

"مارک چه نوع کارتی را دوست دارد: طنز، احساساتی، خطرناک؟"

این نوع جزئیات در مرحله بعدی فرآیند ما در نظر گرفته می شود.

مرحله 4: با افزودن جزئیات بیشتر ، الگوریتم را اصلاح کنید.

یک الگوریتم سطح بالا مراحل اصلی را نشان می دهد که برای حل یک مشکل باید دنبال شود. اکنون باید جزئیات را به این مراحل اضافه کنیم، اما چقدر جزئیات را باید اضافه کنیم؟متأسفانه پاسخ به این سوال بستگی به شرایط دارد. ما باید در نظر بگیریم که چه کسی (یا چه چیزی) قرار است الگوریتم را پیاده سازی کند و آن شخص (یا چیز) چقدر از قبل می داند چگونه باید انجام دهد. اگر کسی قرار است از طرف من کارت تولد مارک را بخرد، دستورالعمل های من باید مطابق با این باشد که آیا آن شخص با فروشگاه های موجود در جامعه آشنایی دارد یا نه و اینکه خریدار چقدر سلیقه برادرم را در کارت های تبریک می شناسد.

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

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

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

مرحله 5: الگوریتم را مرور کنید.

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

آیا این الگوریتم یک مشکل بسیار خاص را حل می کند یا یک مشکل کلی تر را حل می کند؟اگر یک مشکل بسیار خاص را حل می کند ، آیا باید آن را تعمیم داد؟

به عنوان مثال ، یک الگوریتم که مساحت یک دایره را با شعاع 5. 2 متر محاسبه می کند (فرمول π*5. 2 2) یک مشکل بسیار خاص را حل می کند ، اما یک الگوریتم که مساحت هر دایره را محاسبه می کند (فرمول π*r 2) کلی تر را حل می کندمسئله.

آیا می توان این الگوریتم را ساده کرد؟

یک فرمول برای محاسبه محیط مستطیل:

یک فرمول ساده تر خواهد بود:

آیا این راه حل شبیه به راه حل مشکل دیگر است؟چگونه آنها یکسان هستند؟اونها چجوری متفاوت هستن؟

به عنوان مثال ، دو فرمول زیر را در نظر بگیرید:

شباهت ها: هر یک منطقه را محاسبه می کند. هر کدام دو اندازه گیری را ضرب می کنند.

تفاوت ها: از اندازه گیری های مختلف استفاده می شود. فرمول مثلث حاوی 0. 5 است.

فرضیه: شاید هر فرمول منطقه شامل ضرب دو اندازه گیری باشد.

مثال 4. 1: انتخاب و گیاه

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

بیانیه مشکل (مرحله 1)

جرو از (0، 0) رو به شرق و بدون گل در کیسه خود شروع می شود. یک گل در محل (3، 0) وجود دارد. برنامه ای بنویسید که جرو را به چیدن گل و کاشت آن در محل (3، 2) هدایت کند. پس از کاشت گل، جرو باید یک فاصله به شرق بپرد و متوقف شود. هیچ توری، گل یا جروس دیگری در جزیره وجود ندارد.

شروع کنید	پایان

تجزیه و تحلیل مسئله (مرحله 2)

گل دقیقاً سه فاصله جلوتر از جرو قرار دارد.

قرار است گل دقیقاً در دو فضای جنوب محل فعلی کاشته شود.

جرو قرار است رو به شرق یک فضای شرقی گل کاشته شده را به پایان برساند.

هیچ شبکه ای برای نگرانی وجود ندارد.

الگوریتم سطح بالا (مرحله 3)

بیایید نام جرو بابی را بگذاریم. بابی باید کارهای زیر را انجام دهد:

الگوریتم تفصیلی (مرحله 4)

بیایید نام جرو بابی را بگذاریم. بابی باید کارهای زیر را انجام دهد:

الگوریتم را مرور کنید (مرحله 5)

الگوریتم سطح بالا مسئله را به سه زیرمسئله نسبتا آسان تقسیم کرد. این تکنیک خوبی به نظر می رسد.

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

این الگوریتم در واقع راه حلی برای یک مسئله کمی کلی تر است که در آن جرو از هر جایی شروع می شود و گل مستقیماً 3 فاصله جلوتر از جرو قرار دارد.

کد جاوا برای "Pick and Plant"

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

یک برنامه نویس خوب به صورت تدریجی کار می کند، تکه های کوچک را یکی یکی اضافه می کند و دائماً کار را بررسی می کند.

اولین ساخت

برای مشاهده عملی این راه حل، یک سناریوی جدید Greenfoot4Sofia ایجاد کنید و از دستور منوی Edit Palettes Jeroo برای قابل مشاهده کردن کلاس های Jeroo استفاده کنید. بر روی کلاس Island کلیک راست کرده و یک زیر کلاس جدید با نام دلخواه خود ایجاد کنید. این زیر کلاس کد جدید شما را نگه می دارد.

اولین ساخت پیشنهادی شامل سه چیز است:

متد اصلی (در اینجا myProgram() در زیر کلاس جزیره شما).

اعلامیه و نمونه هر جرو که مورد استفاده قرار خواهد گرفت.

الگوریتم سطح بالا در قالب نظرات.

نمونه در ابتدای myProgram() بابی را در (0، 0)، رو به شرق، بدون گل قرار می دهد.

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

ساخت دوم

این ساخت منطق را به "گرفتن گل" اضافه می کند ، که در الگوریتم مفصل (مرحله 4 در بالا) شامل 3 بار پریدن و سپس چیدن گل است. کد جدید توسط نظرات نشان داده شده است که در اصل ظاهر نمی شوند (آنها فقط در اینجا هستند تا توجه به اضافات را جلب کنند). خطوط خالی به نشان دادن سازماندهی منطق کمک می کند.

با لحظه ای برای اجرای کار تا کنون ، می توانید تأیید کنید که آیا این مرحله در الگوریتم برنامه ریزی شده همانطور که انتظار می رود کار می کند یا خیر.

سومین ساخت

این ساخت منطق را به "قرار دادن گل" می افزاید. کد جدید توسط نظرات ارائه شده در اینجا برای علامت گذاری موارد اضافی نشان داده شده است.

ساخت چهارم (نهایی)

این ساخت منطق را به "هاپ شرق" اضافه می کند.

مثال 4. 2: خالص را با گل جایگزین کنید

این بخش شامل یک مثال دوم است که نشان دهنده فرآیند توسعه الگوریتم است.

بیانیه مشکل (مرحله 1)

دو Jeroos وجود دارد. یک جرو از (0 ، 0) رو به شمال با یک گل در کیسه خود شروع می شود. دوم از (0 ، 2) رو به شرق با یک گل در کیسه خود شروع می شود. یک شبکه در مکان وجود دارد (3 ، 2). برنامه ای را بنویسید که اولین جرو را هدایت کند تا گل خود را به دومین بار بدهد. پس از دریافت گل ، جرو دوم باید شبکه را غیرفعال کند و یک گل را در جای خود کاشت. بعد از کاشت گل ، جرو باید به سمت جنوب بچرخد و رو به رو شود. در این جزیره هیچ شبکه ، گل یا جروئوس دیگری وجود ندارد.

شروع کنید	پایان

تجزیه و تحلیل مسئله (مرحله 2)

jeroo_2 دقیقاً دو فاصله از Jeroo_1 است.

تنها شبکه دقیقاً سه فاصله از Jeroo_2 است.

هر جرو دقیقاً یک گل دارد.

jeroo_2 پس از دریافت یکی از jeroo_1 دو گل خواهد داشت. برای غیرفعال کردن شبکه باید از یک گل استفاده شود. گل دیگر باید در محل شبکه کاشته شود ، یعنی (3 ، 2).

Jeroo_1 در (0 ، 1) رو به جنوب به پایان می رسد.

Jeroo_2 قرار است در (3 ، 2) رو به جنوب به پایان برسد.

هر جرو با 0 گل در کیسه خود به پایان می رسد. از یک گل برای غیرفعال کردن شبکه استفاده شد و دیگری کاشته شد.

الگوریتم سطح بالا (مرحله 3)

بیایید نام اول جرو آن و دوم اندی را نام ببریم.

شبکه را پیدا کنید (اما روی آن پرش نکنید) گیاه خالص را یک گل در محل NET Face South غیرفعال کنید

الگوریتم تفصیلی (مرحله 4)

بیایید نام اول جرو آن و دوم اندی را نام ببریم.

الگوریتم را مرور کنید (مرحله 5)

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

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

کد جاوا برای "جایگزین کردن خالص با گل"

مانند گذشته ، کد باید به صورت تدریجی به عنوان یک سری ساختها نوشته شود. چهار ساخت برای این مشکل مناسب خواهد بود. طبق معمول ، ساخت اول شامل روش اصلی ، اعلامیه و فوری اشیاء Jeroo و الگوریتم سطح بالا در قالب نظرات خواهد بود. ساخت دوم آن گل خود را به اندی می دهد. ساخت سوم اندی دارای شبکه است و شبکه را غیرفعال می کند. در ساخت نهایی ، اندی گل را قرار می دهد و به سمت شرق می چرخد.

اولین ساخت

این ساخت روش اصلی را ایجاد می کند ، Jeroos را فوراً می کند و الگوریتم سطح بالا را تشریح می کند. در این مثال ، روش اصلی MyProgram () موجود در زیر کلاس جزیره است.

ساخت دوم

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

سومین ساخت

این ساخت منطقی را برای اندی برای یافتن و غیرفعال کردن شبکه اضافه می کند.

ساخت چهارم (نهایی)

این ساخت منطق را برای اندی اضافه می کند تا یک گل را در (3 ، 2) قرار دهد و به سمت جنوب بپیچد.