همه انسانها روزانه اعمال بسیاری را طبق یک روال خاص انجام می دهند تا به نتیجه مشخصی برسند. بعنوان مثال خود شما ممکن است روش مشخصی برای آمدن به دانشگاه داشته باشید، مانند :
از منزل بیرون آمده و به ابتدای خیابان اصلی بیا، سوار تاکسی شده و به میدان ... برو و سپس از آنجا با اتوبوس به دانشگاه بیا.
به تشریح دقیق مراحل مختلف انجام یک کار بخصوص الگوریتم می گوییم. این کلمه از نام الخوارزمی ریاضیدان و منجم ایرانی گرفته شده است.
نکته مهم آنستکه انسانها بسیاری ازجزئیات را بطور ذاتی می دانند و نیازی به بیان آنها نیست. بطور مثال نیازی نیست نحوه سوار شدن به تاکسی را برای آنها بیان کرد. اما در مورد کامپیوترها این مسئله صادق نیست و باید کلیه جزئیات کار بطور دقیق به آنها داده شود. علاوه براین انسانها می توانند در موقعیتهای خاص با قدرت تعقل خود، الگوریتم را متناسب با نیازها تغییر دهند. مثلا درصورتیکه بر اثر برف، اتوبوسها نیامده باشند بلافاصله از راه حل دیگری استفاده خواهیم کرد. اما درمورد کامپیوتر این مسئله برقرار نیست و باید از قبل حالتهای خاص پیش بینی شده و روشهای برخورد با آنها تشریح شده باشد. بطور کلی تعریف دقیق الگوریتم بشرح زیر است :
الگوریتم : مجموعه محدودی از دستورالعملها است که اگر به ترتیب دنبال شوند موجب انجام کار خاصی می گردند. هر الگوریتم باید دارای شرایط زیر باشد :
1- ورودی : یک الگوریتم می تواند صفر یا چند ورودی داشته باشد که از محیط خارج تامین می گردد.
2- خروجی : الگوریتم باید یک یا چند کمیت خروجی داشته باشد.
3- قطعیت : هر دستورالعمل باید واضح و بدون ابهام باشد.
4- کارایی : هر دستورالعمل باید قابل اجرا باشد.
5- محدودیت : در تمام حالات، الگوریتم باید پس از طی مراحل محدودی خاتمه یابد.
الگوریتم می تواند داده هایی را از دنیای خارج دریافت کند و یا نکند. مثلا در مثال فوق ممکن است وضعیت هوا را بعنوان ورودی به الگوریتم برای تصمیم گیری در مورد نحوه رفتن به دانشگاه در نظر بگیریم. اما درهر صورت الگوریتم باید خروجی تولید کند و گرنه هیچ عمل مفیدی انجام نداده است.
دستورالعملها باید کاملا واضح باشند. مثلا دستور زیر واضح نیست :
"صبر کن تا یک ماشین بزرگ (منظور اتوبوس) از راه برسد و سوار آن بشو"
چرا که بزرگ بودن از دید افراد مختلف، مفهوم متفاوتی است. همینطور دستورالعمل "اگر عدد مورد نظر به اندازه کافی کوچک است." یا دستورالعمل " a = b #c" نیز واضح نیستند.
دستورالعملها باید قابل اجرا باشند و نمی توانیم دستوراتی مثل "از روی ساختمان 10 طبقه روبرو پرواز کن" و یا "a = b / 0" داشته باشیم.
در نهایت الگوریتم حتما باید تحت هر شرایطی خاتمه یابد. مثلا نمی توان الگوریتمی نوشت که تمام اعداد طبیعی را چاپ کند. البته معمولا الگوریتمهایی که این شرط را ندارند، دارای مشکلی هستند که در بعضی شرایط خاص در حلقه بینهایت قرار می گیرند.
در علم کامپیوتر، ما معمولا با یک مسئله مواجهیم که باید آن را حل کنیم. این مسئله می تواند در زمینه های مختلفی همچون علمی، اقتصادی، ریاضی، فنی و ... باشد. معمولا برای حل یک مسئله، مراحل زیر طی می گردد:
- تعریف مسئله بصورت جامع و دقیق (شامل تعریف ورودیها و خروجیها)
- بررسی راه حلهای مختلف برای حل مسئله
- انتخاب مناسبترین راه حل و تهیه یک الگوریتم برای آن
- آزمایش الگوریتم با داده های ورودی و اشکالزدایی آن
- تبدیل الگوریتم به یک زبان برنامه نویسی کامپیوتری (مانند C یا Pascal)
- وارد کردن برنامه به کامپیوتر و تست و اشکالزدایی آن
- استفاده از برنامه
اولین گام تعریف دقیق مسئله شامل کلیه خواسته ها ونیازها و همچنین ورودیها و خروجیهای مسئله است. هرگونه اشکالی در این مرحله، باعث بروز مشکلات اساسی در مراحل نهایی و حتی غیرکاربردی شدن برنامه خواهد شد.
گام بعدی بررسی راه حلهای متفاوت است. برای حل مسئله به یک راه حل نیاز است که همان الگوریتم مورد نظر ما است. بعنوان مثال همه ما با الگوریتم حل یک معادله درجه دوم آشنا هستیم. سخت ترین قسمت کار یک برنامه نویس کامپیوتر، تبدیل مسئله به یک الگوریتم است. چرا که چنانچه این کار به درستی صورت پذیرد، تبدیل الگوریتم به یک زبان برنامه نویسی بسیار ساده بوده و طبق قواعد خاصی صورت می پذیرد. اما متاسفانه برای تبدیل صورت مساله به یک الگوریتم هیچ روش خاصی وجود ندارد و همه چیز به خلاقیت و تجربه طراح الگوریتم مربوط می شود. بهمین دلیل عده ای طراحی الگوریتمها را بیشتر یک هنر می دانند تا یک علم. این جمله تا حدی درست است، چرا که اصولا بعضی از افراد ذاتا قدرت بسیار بالایی برای طراحی الگوریتمها دارند و براحتی می توانند الگوریتمهایی برای حل مسائل مشکل طراحی کنند. اما با این وجود تجربه و تمرین نیز در طراحی الگوریتمها نقش مهمی دارد و افراد می توانند با دیدن مسائل مختلف و راه حل آنها، قدرت حل مسائل را در خود بالا ببرند.
با توجه به آنچه گفته شد، متاسفانه هیچ روش مشخصی برای تبدیل مسئله به الگوریتم وجود ندارد. بهمین دلیل ما در بخش اول درس، سعی می کنیم با طرح مسائل مختلف و ارائه راه حلهایی برای آنها، قدرت طراحی الگوریتم را در شما بالا ببریم. سعی شده است مسائل بگونه ای انتخاب گردد که اکثر موارد مهم را پوشش دهد، با این وجود طراحی الگوریتم نیاز به تمرین بسیار زیاد دارد. در بخش دوم درس نیز به نحوه تبدیل الگوریتمها به زبان برنامه نویسی C خواهیم پرداخت که کار چندان مشکلی نیست و چنانچه الگوریتم به درستی نوشته شده باشد، برنامه آن نیز درست عمل خواهد کرد.
در این بخش کار خودرا با یک الگوریتم ساده شروع می کنیم.
مثال1) الگوریتمی بنویسید که ضرایب یک معادله درجه دوم بصورت زیر را دریافت و ریشه های آن را محاسبه و چاپ کند.
a x2 + b x + c = 0
برای حل این مسئله ابتدا باید ضرائب a ، b و c از کاربر دریافت و در خانه های حافظه ذخیره گردند. برای اینکه بتوانیم بعدا به این خانه های حافظه مراجعه کنیم، به هریک از آنها یک نام نسبت می دهیم. به هریک از این نامها یک متغیر گفته می شود. دلیل این نامگذاری آنستکه مقادیر ذخیره شده در هریک از این خانه های حافظه می تواند تغییر کند. گرچه انتخاب نام بعهده خودشماست و می تواند هر چیزی باشد، ولی توصیه می گردد از اسامی بامعنی و متناسب استفاده گردد. این کار سبب می شود که خواندن و درک الگوریتم شما برای سایر افراد نیز ساده گردد. اکنون به قراردادهای زیر توجه کنید :
- برای دریافت اطلاعات از کاربر از دستور بخوان استفاده می گردد.
- برای نوشتن اطلاعات در خروجی از دستور چاپ کن استفاده می گردد.
- برای انتساب یک مقدار به یک متغیر از علامت -> استفاده می شود.
اکنون به حل مثال 1 توجه کنید :
a, b, c : ضرایب معادله درجه دوم
delta : مقدار دلتا در فرمول حل معادله درجه 2 x1 , x2 : ریشه های معادله
1- a و b و c را بخوان
2- delta ← b2 – 4ac
3- ? و ?
4- x1 و x2 را چاپ کن
5- توقف کن
همانگونه که می بینید الگوریتم فوق در حالت کلی درست عمل می کند و می تواند ریشه های یک معادله درجه دوم را محاسبه و چاپ کند. اما اگر حالات خاصی همچون منفی بودن delta رخ دهد، الگوریتم دچار مشکل خواهد شد. همانطور که قبلا نیز گفته شد، طراح الگوریتم باید پیش بینی همه موارد خاص را کرده باشد. برای حل این مشکل نیاز به مکانیزمی داریم که بتواند منفی بودن delta را بررسی نماید. این مکانیزم در قسمت بعد توضیح داده شده است.
چگونه می توانیم الگوریتمها را بیان کنیم؟ مسلما الگوریتمها باید برای انسانها قابل فهم و درک باشند و همه بتوانند به راحتی منظور نویسنده الگوریتم را درک کنند (البته در مرحله بعد این الگوریتم باید به یک زبان قابل درک توسط کامپیوتر تبدیل شود). بهمین دلیل معمولا الگوریتمها به یک زبان طبیعی مانند فارسی یا انگلیسی نوشته می شود. البته متاسفانه این مسئله باعث می شود که بعضی ابهامات در درک الگوریتمها پیش آید. لذا معمولا یکسری از توافقات و تعریفها از قبل بین طراح و خواننده الگوریتم برقرار می گردد. از آنجا که زبانهای برنامه نویسی مانند C به زبان انگلیسی خیلی نزدیک هستند، بعض از طراحان از ترکیب زبان C و انگلیسی (که به آن کد شبه C می گویند) برای بیان الگوریتم استفاده می کنند تا نه تنها ابهامی پیش نیاید بلکه تبدیل آن به یک برنامه واقعی نیز ساده باشد. این کار بسیار مفید است و شما می توانید در آینده از این روش استفاده کنید، ولی از آنجا که هنوز با زبان C آشنا نشده ایم، از زبان فارسی بعلاوه برخی علائم ریاضی برای بیان الگوریتمها استفاده خواهیم کرد.
لازم بذکر است که در گذشته از نمودار گردشی (Flowchart) نیز برای بیان الگوریتمها با استفاده از شکلهای استاندارد استفاده می شد، که تنها برای الگوریتمهای کوچک مناسب بود. ما در این درس از نمودارهای گردشی استفاده نخواهیم کرد.
مکانیزم شرط هنگامی استفاده می شود که قصد داریم درستی یا نادرستی یک عبارت رابررسی کرده و متناسب با نتیجه بررسی شرط، عملیات خاصی را انجام دهیم و یا از انجام بعضی عملیات صرفنظر کنیم. شکل کلی این دستور به شکل زیر است :
اگر (عبارت شرطی) آنگاه دستورات
درصورتیکه عبارت شرطی درست ارزیابی شود آنگاه قسمت دستورات اجرا خواهد شد. اما در غیر اینصورت به دستور بعدی خواهد رفت. این دستور به شکل زیر نیز استفاده می شود:
اگر (عبارت شرطی) آنگاه دستورات1
درغیر اینصورت دستورات 2
که در اینحالت چنانچه شرط درست ارزیابی نشود، دستورات 2 اجرا خواهد شد.اکنون به حل درست مثال 1 توجه کنید.
1- a و b و c را بخوان
2- اگر ( 0 = a ) آنگاه چاپ کن "معادله درجه دو نیست" و توقف کن
3- delta ← b2 – 4ac
4- اگر ( 0 > delta ) آنگاه چاپ کن "معادله جواب ندارد"
درغیراینصورت ? و ? و x1 و x2 را چاپ کن
5- توقف کن
مثالهایی که تاکنون بیان شد، بگونه ای بود که نیاز به تکرار دستورات نداشت. اما بعضی موارد لازم است که عملیات مشخصی چندین بار تکرار شوند. بعنوان مثال فرض کنید قصد داریم میانگین معدلهای 100 دانشجو را محاسبه کنیم. قطعا 100 بار دستور خواندن و جمع کردن راه حل چندان مناسبی نیست. راه حل بهتر آنستکه بگونه ای به مجری الگوریتم بگوییم بنحوی عمل خواندن معدل و جمع زدن آنها را 100 بار تکرار کند.
حلقه تکرار مکانیزمی است که مجموعه ای از دستوزات را تا زمانیکه شرط خاصی برقرار باشد تکرار می کند. حلقه تکرار به دو شکل مورد استفاده قرار می گیرد :
- شرط در ابتدای حلقه که مکانیزم کلی آن به شکل زیر است :
تا زمانیکه (شرط مورد نظر) دستورات a تا b را تکرارکن
…(a
.
.
.
… (b
در این حالت ابتدا شرط موردنظر بررسی می گردد؛ درصورتیکه شرط برقرار نباشد به اولین دستور پس از b می رود. اما در صورتیکه شرط درست ارزیابی شود، دستورات شماره a تا b انجام می شوند و سپس مجددا به ابتدای حلقه بازگشته و عملیات فوق را مجددا تکرار می کند.
- شرط در انتهای حلقه که مکانیزم کلی آن به شکل زیر است :
تکرار کن
…(a
.
.
.
… (b
تا زمانیکه (شرط مورد نظر)
در این روش ابتدا دستورات حلقه یکبار انجام می شوند و در پایان حلقه شرط بررسی می گردد. چنانچه شرط برقرار نبود به دستور بعدی می رود و در صورت برقرار بودن شرط، مجددا به ابتدای حلقه باز می گردد.
برای روشن شدن موضوع، بحث را با یک مثال ادامه می دهیم.
مثال2) الگوریتمی بنویسید که یک عدد را دریافت و فاکتوریال آن را محاسبه و چاپ کند.
N! = 1 × 2 × 3 × … × (N-1) × N
حل)
n : عدد ورودی برای محسبه فاکتوریال آن
i : شمارنده حلقه fact : مقدار فاکتوریال
1- n را بخوان
2- 1 ← i و 1 ← fact
3- تا زمانیکه ( i ≤ n ) دستورات 5-4 را تکرار کن
4- fact ← fact × i
5- i ← i + 1
6- fact را چاپ کن
7- توقف کن
در این قسمت برای آشنایی بیشتر شما با طراحی الگوریتمها به ذکر چند نمونه دیگر می پردازیم.
مثال 3) الگوریتمی بنویسید که n عدد را دریافت و حداکثر و حداقل آنها را چاپ کند.
حل) برای حل مسائل حداکثر یا حداقل ابتدا باید یک متغیر برای نگهداری آنها درنظر بگیریم. نکته مهم مقدار اولیه این متغیر است. دو روش کلی وجود دارد :
- اولین مقدار را دریافت و آن را بعنوان مقدار اولیه درنظر بگیریم.
- مقدار اولیه متغیر حداکثر را برابر کمترین عدد ممکن و متغیر حداقل را برابر بیشترین عدد ممکن درنظر بگیریم.
در حل زیر از روش اول استفاده شده است.
n : تعداد اعداد i : شمارنده حلقه adad : عدد دریافت شده در هر مرحله
max : بزرگترین عدد min : کوچکترین عدد
1- n را بخوان
2- adad را بخوان
3- min ← adad و max ← adad
4- i ← 2
5- تا زمانیکه ( i ≤ n ) دستورات 6 تا 8 را تکرار کن
6- adad را بخوان
7- اگر ( adad > max ) آنگاه max ← adad
در غیر اینصورت اگر ( adad < min ) آنگاه min ← adad
8- i ← i + 1
9- max و min را چاپ کن
10- توقف کن
..............................
