ورود / ثبت نام
به جلسه سوم خوش اومدید، این نوشته با اصول و قواعد طراحی ساختار تکرار در فلوچارتها آشنا می‌شوید و مثالهای کاربردی و مفیدی بیان میشود.
گاهی اوقات در نوشتن الگوریتم، باید عملیاتی را به صورت تکراری انجام دهیم. به طور مثال برنامه‌ای را در نظر بگیرید که 10 عدد را از ورودی دریافت کند و پس از دریافت هر عدد، مجذور آن عدد را چاپ کند. برای رسم این فلوچارت باید این 3 دستور، 10 بار در برنامه تکرار شود:
قابل تصور است که اگر به جای 10 عدد، بخواهیم 1000 عدد از ورودی دریافت کنیم و مجذور آنها را چاپ کنیم کشیدن فلوچارت مساله غیر ممکن است! برای حل این مشکل باید با ساختار تکرار آشنا شوید.
ساختار تکرار در فلوچارت
همانطور که از اسم آن مشخص است قرار است ساختاری درست کنیم که به تعداد دفعاتی که برای آن مشخص میکنیم تکرار شود (مثلا 1000 بار) اما فلوچارت از کجا باید بفهمد که این ساختار 1000 بار تکرار شده است یا نه؟ از جلسه قبل مثال تعداد هواداران یا تعداد اعداد زوج را به یاد بیاورید. در آن مثالها از ایده شمارنده (counter) استفاده کردیم و گفتیم هر بار طرفدار پرسپولیس دیدی یکی به counter اضافه کن. در ساختار تکرار هم دقیقا از همین ایده استفاده میکنیم. متغیری به اسم i تعریف میکنیم و هر بار که ساختار مورد نظر اجرا شد یکی به i اضافه میکنیم.
فلوچارت زیر را ببینید تا بیشتر در مورد ساختار تکرار صحبت کنیم.
در فلوچارت بالا اندیس i به 1 مقداردهی اولیه میشود. شرط i<=1000 همان شرطی است که کنترل میکند آیا 1000 عدد دریافت شده است یا خیر. درصورتی که i کوچکتر از 1000 باشد X دریافت میشود و توان دوم آن چاپ میشود و یکی به i اضافه میشود. این کار تا زمانی ادامه پیدا میکند که مقدار i از 1000 بزرگتر شود
نکته مهم در مورد ساختار تکرار
در نوشتن و استفاده از ساختار تکرار همیشه این نکته را مد نظر داشته باشید که یک ساختار تکرار از 4 قسمت تشکیل شده است.
- مقداردهی اولیه به شمارنده
- شرط
- قالب تکرار شونده
- به‌روز رسانی اندیس شمارنده
به عنوان مثال در فلوچارت روبرو اندیس شمارنده ( که i نام دارد) با یک مقدار دهی اولیه شده است. شرط i<=1000 وجود دارد، دستورات مربوط به خواندن عدد و مجذور آن وجود دارد و در انتهای ساختار تکرار با دستور i=i+1 شمارنده به روزرسانی میشود.
نکته دیگری که باید در نظر داشته باشید این است که اگر هرکدام از این ها را فراموش کنید که در فلوچارت ذکر کنید، فلوچارت شما با اشکال جدی روبرو میشود:
- اگر فراموش کنید که اندیس شمارنده را مقدار دهی اولیه کنید، در به‌روز رسانی اندیس با مشکل مواجه می‌شوید. چون در به‌روز رسانی اندیس شما می‌خواهید یکی به اندیس اضافه کنید. حال اگر اندیس شما مقداری نداشته باشد چگونه یک واحد به آن اضافه شود؟
- قسمت اصلی ساختار تکرار شرط است. مثلا در فلوچارت قبلی شرط این جمله را بیان میکرد که تا I از 10 کو چکتر است دستورات را انجام بده. حال اگر شرط وجو نداشته باشد دستورات فقط یک بار انجام میشود.
- اگر به‌روز رسانی اندیس صورت نگیرد ساختار تکرار تا بی‌نهایت ادامه پیدا خواهد کرد و الگوریتم هیچگاه متوقف نمی‌شود. (چرا؟)
مثال: فلوچارت برنامه‌ای را رسم کنید که با دریافت N، مجموع 1+2+…+Nرا چاپ کند
توجه داشته باشید که این مساله را بدون حلقه و با استفاده از فرمول به راحتی میتوان محاسبه کرد. ولی ما در این مثال برای اینکه چگونگی استفاده از ساختار تکرار را نمایش دهیم از این فرمول استفاده نمی‌کنیم.
(بد نیست قبل از نگاه کردن به جواب، به این سوال فکر کنید.)
قبل از اینکه فلوچارت این مساله را رسم کنید در ذهنتان مجموع 1 تا 10 (بدون استفاده از فرمول) را محاسبه کنید. احتمالا شما هم در ذهنتان به این شکل جمع میکنید:
1 به اضافه 2 میشه 3، 3 به اضافه 3 میشه 6، 4 به اضافه 6 میشه 10، 5 به اضافه 10 میشه 15 …
اگر به مسیری که در ذهنتان دنبال شده است دقت کنید میبینید که یک متغیر در نظر گرفتید که مجموع اعداد را در آن آپدیت میکنید. (3، 6، 10، 15 …)
ما هم از همین ایده میتوانیم استفاده کنیم. اسم متغیر را sum در نظر میگیریم، با صفر مقدار دهی میکنی و به ترتیب اعداد 1، 2، 3، 4، 5، 6، 7، 8، 9، 10 را به sum اضافه میکنیم:
در ابتدا sum =0 است، وقتی 1 به sum اضافه می شود مقدار sum برابر 1 میشود.
وقتی 2 به sum اضافه میشود مقدار sum برابر 3 می شود
وقتی 3 به sum اضافه میشود مقدار sum برابر 6 می شود
وقتی 4 به sum اضافه میشود مقدار sum برابر 10 می شود
وقتی 5 …
با این توضیحات فلوچارت زیر را ببینید:
در فلوچارت بالا از ساختار تکرار استفاده شده است. همانظور که میبینید ساختار تکرار مقدار I را از 1 تا N تغییر میکند و هر بار I به sum اضافه می شود. یعنی در تکرار اول 1 به sum اضافه میشود، در تکرار دوم 2 به sum اضافه میشود، تکرار بعدی 3 اضافه می شود و …
این مثال را با دقت زیاد بخوانید. در مثالهای بعد از ایده‌ی این مثال به وفور استفاده میشود!
مثال: فلوچارت برنامه‌ای را رسم کنید که مجموع اعداد طبیعی ضریب 7 کوچکتر از N را حساب کند.
به طور مثال اگر N برابر 40 باشد، عدد 105 را چاپ کند (حاصل 35+28+21+14+7)
این مساله را به دو روش میتوان حل کرد. حتما قبل از دیدن فلوچارت این مساله سعی کنید خودتان مساله را حل کنید:
روش اول:
در روش اول شبیه به مساله قبلی عمل کردیم با این تفاوت که هر iای به sum اضافه نمی‌شود،i هایی به sum اضافه میکنیم که بر 7 بخشپذیر باشد. اما روش دوم:
در این روش هوشمندانه تر عمل کردیم. در روش اول همه اعداد 1 تا N تولید شد و فقط اعداد ضریب 7 به sum اضافه شد. اما در روش دوم فقط اعدای تولید شد که نیاز داشتیم! اگر 2 فلوچارت را به خوبی متوجه شده باشید جواب این سوال برایتان ساده است: کدام روش سریعتر است؟
تمرین: فلوچارت برنامه ای رسم کنید که از ورودی عدد N را دریافت کند و مقدار N! را چاپ کند.
مثال: فلوچارت برنامه‌ای رسم کنید که بزرگترین عدد را بین 100 عددی که کاربر وارد میکند چاپ کند
برای اینکه ایده حل این مساله را متوجه شوید اول بگویید بزرگترین عدد بین این 3 عدد چند است؟ 10، 13، 11
شما بدون فکر کردن و به صورت چشمی 13 را انتخاب کردید. اینبار تعداد اعداد را بیشتر میکنیم. بزرگترین عدد بین این اعداد چند است:
(اعداد را از راست به چپ بخوانید)
20 7 13 15 25 24 12 101 14 13 12 11 45 55 102 35 110 32 11 7 14 201 33 19 27 44 200 133 98 85 77 111 37 99 112 111 22 170
احتمالا برای پیدا کردن بزرگترین عدد اعداد را یکی یکی بررسی کردید و در ذهنتان بزرگترین عدد تا آن لحظه را به خاطر سپردید. مثلا اگر اعداد را از سمت چپ و با عدد 20 شروع کنید یکی یکی اعداد را جلو میرویم و به 25 که میرسیم در ذهنمان 25 را نگه میداریم و میگوییم تا اینجا 25 بزرگترین است، به همین ترتیب جلو میرویم و به 101 که رسیدیم 101 را جایگزین 25 در ذهنمان میکنیم و به همین شکل ادامه میدهیم تا 201 به عنوان بزرگترین عدد انتخاب شود.
در فلوچارت این مساله هم دقیقا به همین شکل عمل میکنیم و از متغیری به اسم max استفاده میکنیم و در ابتدا فرض میکنیم max = 20 (که همان اولین عددمان است) و اعداد را یکی یکی از ورودی میخوانیم و با max مقایسه میکنیم…
فلوچارت این مساله را ببینید:
تمرین:
- فلوچارت برنامه ای رسم کنید که بزرگترین و دومین بزرگترین عدد ( عددی که فقط از بزرگترین عدد کوچکتر و از بقیه اعداد بزرگتر است.) را بین 100 عددی که کاربر وارد میکند چاپ نماید.
- فلوچارت برنامه‌ای را رسم کنید که یک عدد مثبت را دریافت و تعداد ارقام آن را چاپ کند.
- فلوچارت برنامه‌ای رسم کنید که معکوس یک عدد مثبت را چاپ کند. (توجه کنید که معکوس 2400 برابر 42 می‌باشد نه 0042)
- فلوچارتی رسم کنید که با دریافت x از ورودی، بررسی کند که آیا x یک عدد اول است یا خیر.
کتاب الگوریتم و فلوچارت
دوره آموزشی الگوریتم و فلوچارت
نمونه سوال و تمرینهای بیشتری میخواهی؟
39 تمرین از سرفصلهای مختلف الگوریتم و فلوچارت که میتونید به عنوان نمونه سوالات امتحانی هم بهش نگاه کنید