۹-۴ فرموله کردن الگوریتمها: مراقبت-کنترل تکرار
فرموله کردن الگوریتمها: مراقبت-کنترل تکرار ، اجازه دهید تا به مسئله میانگین کلاس بازگردیم و آنرا مجدداً و اینبار بصورت زیر و کلی تر تعریف کنیم:
“برنامه محاسبه میانگین کلاس را به نحوی توسعه دهید تا در هر بار اجرای برنامه، به تعداد اختیاری نمره دریافت کرده و محاسبه میانگین بر روی آنها اعمال شود.”
در برنامه قبلی، تعداد نمرات از همان ابتدا مشخص بود (۱۰ نمره). در این برنامه، تعداد نمراتی که بعنوان ورودی وارد خواهند شد مشخص نیستند. برنامه باید بر روی تعداد نمرات وارد شده کار کند. چگونه برنامه تشخیص می دهد که به گرفتن نمره پایان دهد؟ محاسبات به چه صورتی باید انجام گرفته و میانگین کلاس به نمایش درآید؟
مراقبت-کنترل تکرار
یک راهحل برای رفع این مشکل، استفاده از یک مقدار ویژه بنام مقدار مراقبتی (sentinel value) است که پایان ورود دادهها را مشخص می کند (همچنین به این مقدار، مقدار سیگنال، مقدار ساختگی یا پرچم نیز می گویند). در این روش کاربر اقدام به وارد کردن نمرهها کرده و در پایان مقدار مراقبتی تعیین شده را به عنوان اینکه دادههای ورودی به اتمام رسیدهاند، وارد می سازد. روش مراقبت-کنترل تکرار، روش تکرار-تعریفنشده نیز نامیده می شود چرا که تعداد دفعات تکرار قبل از اجرای حلقه مشخص نیست.
واضح است که مقدار مراقبتی باید به نحوی انتخاب شود که به عنوان یک ورودی معتبر مورد قبول واقع نشود. بدلیل اینکه نمرات امتحان معمولاً منفی نیستند، می توانیم از مقدار -۱ به عنوان مقدار مراقبتی در این برنامه استفاده کنیم. بنابراین به هنگام اجرای برنامه، نمرات کلاس، می توانند ترتیبی مانند -۱ و ۸۴، ۷۴، ۷۵، ۹۶، ۹۳ داشته باشند. برنامه باید نمره میانگین کلاس را با استفاده از مقادیر ۹۳، ۹۶، ۷۵، ۷۴ و ۸۴ محاسبه کرده و به نمایش درآورد (-۱ یک مقدار مراقبتی است و نباید در محاسبه میانگین وارد شود).
الگوریتم شبهکد به روش مراقبت کنترل تکرار به روش از بالا به پایین، اصلاح گامبهگام: اولین اصلاح
به هنگام بررسی مسائل پیچیدهای همانند این برنامه، عرضه الگوریتم شبهکد به آسانی امکان پذیر نمی باشد. از اینرو به برنامه میانگین کلاس با استفاده از تکنیکی بنام، از بالا به پایین، اصلاح گامبهگام نزدیک می شویم که برای ساخت و توسعه برنامههای ساختیافته مناسب و ضروری است. شبهکدی که در بالاترین سطح (top) ارائه می شود، عبارت است از:
Determine the class average for the quiz.
این عبارت تابع و هدف اصلی برنامه است که در واقع کاری که باید برنامه انجام دهد را در بردارد. عبارت top جزئیات ناکافی در مورد اینکه برنامه چگونه بایستی نوشته شود در خود دارد. بنابر این به طرف جزئیات برنامه و اصلاح گام به گام پیش می رویم. ابتدا عبارت top به قسمتهای کوچکی تقسیم می شود که هر یک به ترتیب وظایفی در برنامه ایفا می کنند. نتیجه این تقسیمات در اولین گام می تواند چنین باشد:
Initialize Variables
Input, sum and count the quiz grades
Calculate and print the total of all student grades and the class average
در اینجا، با توجه به اینکه فقط از عبارت توالی استفاده شده، لیست انجام مراحل فقط شامل عبارتهای اجرائی است که به ترتیب یکی پس از دیگری اجرا می شوند.
اصلاح گامبهگام مرحله دوم
مرحله بعدی تجزیه برنامه به جزئیات بیشتر (مرحله دوم)، در ارتباط با متغیرها می باشد به یک متغیر بنام total نیاز است که مجموع اعداد را در خود نگهداری کند و به یک متغیر دیگر بنام count که نشان دهد، چه تعدادی از این اعداد مورد پردازش قرار گرفتهاند. یک متغیر برای دریافت هر نمره از طریق ورودی و یک متغیر برای نگهداری میانگین محاسبه شده مورد نیاز است. عبارت شبهکد:
Initialize variable
را می توان به عبارات جزئی تر زیر تقسیم کرد:
Initialize total to zero
Initialize counter to zero
توجه کنید که فقط متغیرهای total و counter نیاز به مقداردهی اولیه قبل از بکارگیری دارند. متغیرهای average و grade (این متغیرها برای محاسبه میانگین و ورودی کاربر استفاده شده است)، نیازی به مقداردهی اولیه ندارند. عبارت شبهکد:
Input, sum and count the quiz grades
نیازمند یک عبارت تکرار (حلقه) است که نمرات را دریافت کند. چون بطور دقیق نمیدانیم که چه تعداد نمره به عنوان ورودی دریافت خواهیم کرد، از روش مراقبت-کنترل تکرار استفاده می کنیم. کاربر در هر زمان یک مقدار معتبر وارد می کند و پس از اینکه آخرین مقدار مورد نظر را وارد کرد، مقدار مراقبتی را وارد می کند تا از حلقه ورود نمرات خارج شود. برنامه در هر بار که داده وارد می شود مقدار آنرا با مقدار مراقبتی مقایسه می کند. دومین اصلاح بر روی عبارت شبهکد قبلی می تواند بصورت زیر باشد:
Prompt the user to enter the first grade
Input the first grade (possibly the sentinel)
While the user has not yet entered the sentinel
Add this grade to the running total
Add one to the grade counter
Input the next grade (possibly the sentinel)
عبارت شبهکد زیر
Calculate and print the total of all student grades and the class average
می تواند به صورت عبارات جزئی تر زیر نوشته شود:
If the counter is not equal to zero
Set the average to the total divided by the counter
Print the total of all student grades in the class
Print the average
Else
Print “No grades were entered”
توجه کنید که در این قسمت برای جلوگیری از بروز خطای منطقی تقسیم بر صفر، یک تست بکار برده شده است که اگر در برنامه تشخیص داده نشود، می تواند مشکل ساز شود. شبهکد کامل برنامه میانگین در شکل ۱۱-۴ آورده شده است.
به هنگام اجرای یک عمل تقسیم بر عبارتی که ممکن است مقدار آن صفر باشد، باید تستی به همین منظور و رسیدگی به آن در برنامه تدارک دیده شود. رسیدگی به این امر می تواند چاپ یک پیغام ساده خطا باشد. گاهی اوقات انجام عملیات پیچیده مورد نیاز است.
Initialize total to zero
Initialize counter to zero
Input the first grade (possibly the sentinel)
While the user has not as yet entered the sentinel
Add this grade to the running total
Add one to the grade counter
Input the next grade (possibly the sentinel)
If the counter is not equal to zero
Set the average to the total divided by the counter
Print the average
Else
Print “No grades were entered”
شکل ۱۱-۴ | الگوریتم شبهکد با استفاده از روش مراقبت-کنترل تکرار برای حل مسئله میانگین کلاس.
الگوریتم شبهکد ۱۱-۴ مسئله میانگین کلاس را که در ابتدای این بخش بصورت کلی بیان شده بود، برطرف می کند. این الگوریتم فقط پس از طی دو مرحله اصلاح گام به گام توسعه یافت، در حالیکه گاهی اوقات به انجام مراحل بیشتر نیاز است.
پیادهسازی کلاس GradeBook به روش مراقبت-کنترل تکرار
شکلهای ۱۲-۴ و ۱۳-۴ کلاس GradeBook را به نحوی نشان می دهند که حاوی تابع عضو determineClassAverage است که الگوریتم شبه کد شکل ۱۱-۴ را پیادهسازی می کند (این کلاس در شکل ۱۴-۴ توصیف شده است). اگر چه هر نمره وارد شده یک عدد صحیح است، امکان تولید یک عدد اعشاری به هنگام محاسبه میانگین وجود دارد، به عبارتی یک عدد حقیقی یا عدد با نقطه اعشار (همانند ۷.۳۳، ۰.۰۹۷۵ یا ۱۰۰۰.۱۲۳۴۵). نوع داده int نمی تواند چنین اعدادی را عرضه کند، از اینرو این کلاس باید از نوع داده دیگری استفاده کند. زبان C++ دارای چندین نوع داده برای ذخیرهسازی اعداد اعشاری در حافظه است، نوعهای همانند float و double. تفاوت اصلی مابین این نوع در این است که در مقایسه با متغیرهای float، متغیرهای double قادر به نگهداری اعداد بزرگتر و دقیقتر در سمت نقطه اعشار هستند، در نتیجه دقت عدد بیشتر خواهد بود. این برنامه مبادرت به معرفی یک عملگر ویژه بنام عملگر cast است که محاسبه میانگین را مجبور می کند تا نتیجه را بصورت عدد اعشاری تولید کند. این ویژگی به هنگام بررسی برنامه توضیح داده خواهد شد.
در این مثال مشاهده می کنید که عبارات کنترلی می توانند به صورت پشته یکی بر روی دیگری قرار داده شوند (بصورت متوالی). عبارت while در خطوط ۶۷-۷۵ از شکل۱۳-۴ بلافاصله پس از عبارات if..else قرار گرفته است و حالت توالی دارد. قسمت اعظم کد بکار رفته در این مثال با کد برنامه ۹-۴ یکسان است، از اینرو تمرکز خود را بر روی ویژگی ها و مباحث جدید متمرکز می کنیم.
شکل ۱۲-۴ | برنامه میانگین کلاس با روش مراقبت-کنترل تکرار: فایل سرآیند GradeBook
شکل ۱۳-۴ | برنامه میانگین کلاس با روش مراقبت–کنترل تکرار: فایل کد منبع GradeBook
شکل۱۴-۴|برنامه میانگین کلاس با روش مراقبت-کنترل تکرار: ایجاد یک شی از کلاس GradeBook(شکل۱۲-۴ و ۱۳-۴) و فراخوانی تابع عضو determineClassAverage.
در خط ۵۵ متغیر average از نوع double اعلان شده است. این نوع به محاسبه میانگین امکان می دهد تا بصورت یک عدد اعشاری در متغیر ذخیره گردد. در خط ۵۹ متغیر gradeCounter با صفر مقداردهی شده چرا که هنوز نمرهای وارد نشده است، به یاد داشته باشید که این برنامه از روش مراقبت-کنترل تکرار استفاده می کند. به منظور ثبت دقیق تعداد نمرات وارد شده، متغیر gradeCounter فقط به هنگام وارد شدن یک نمره معتبر بعنوان ورودی، افزایش می یابد.
تفاوتهای موجود مابین روشهای مراقبت-کنترل تکرار و شمارنده-کنترل تکرار
به تفاوتهای موجود میان روش مراقبت-کنترل تکرار در این برنامه و شمارنده-کنترل تکرار در برنامه ۹-۴ توجه کنید. در روش شمارنده-کنترل تکرار، در هر بار تکرار عبارت while (خطوط ۵۷-۶۳ از شکل ۹-۴) یک مقدار از سوی کاربر دریافت می گردید. در روش مراقبت-کنترل تکرار، قبل از اینکه برنامه به عبارت while برسد، یک مقدار (خطوط ۶۳-۶۴ از شکل ۱۳-۴)) دریافت می شود. این مقدار تعیین می کند که آیا جریان کنترل برنامه وارد بدنه عبارت while شود یا خیر. اگر شرط عبارت while برقرار نباشد (کاربر مقدار مراقبتی وارد کرده باشد)، بدنه عبارت while اجرا نخواهد شد (هیچ نمرهای وارد نمی شود). از سوی دیگر، اگر شرط برقرار شود، بدنه اجرا شده و مقدار وارد شده کاربر بکار گرفته می شود (به total افزوده می شود، خط ۶۹). پس از پردازش مقدار، مقدار بعدی قبل از اینکه برنامه به انتهای بدنه عبارت while برسد توسط کاربر وارد می شود (خطوط ۷۳-۷۴). زمانیکه برنامه به }در خط ۷۵ می رسد، اجرا با تست بعدی در شرط عبارت while ادامه می یابد (خط ۶۷). مقدار جدید وارد شده تعیین می کند که آیا عبارت بدنه while مجدداً اجرا شود یا خیر. دقت کنید که مقدار بعدی همیشه قبل از اینکه شرط عبارت while ارزیابی شود، بلافاصله توسط کاربر وارد می شود. در اینحالت برنامه می تواند قبل از اینکه اقدام به پردازش مقداری نماید، تعیین کند که آیا آن مقدار، مقدار مراقبتی است یا خیر. اگر مقدار مراقبتی باشد، عبارت while خاتمه می یابد و مقدار به total افزوده نمی شود.
پس از خاتمه حلقه، عبارت if..else در خطوط ۷۸-۹۰ اجرا می شود. شرط موجود در خط ۷۸ تعیین می کند که آیا نمرهای وارده شده است یا خیر. اگر نمرهای وارد نشده باشد، بخش else (خطوط ۸۹-۹۰) از عبارت if..else اجرا شده و پیغام “No grades were entered” را به نمایش درآورده و تابع عضو کنترل را به تابع فراخوان برگشت می دهد.
به بلوک موجود در حلقه while شکل ۱۳-۴ دقت کنید. بدون حضور براکتها، سه عبارت آخر در بدنه حلقه در خارج از حلقه جای می گرفتند و این سبب می شد که کامپیوتر این کد را بصورت زیر و نادرست تفسیر کند:
// loop until sentinel value read from user
while ( grade != -1 )
total = total + grade; // add grade to total
gradeCounter = gradeCounter + 1; // increment counter
// prompt for input and read next grade from user
cout << “Enter grade or -1 to quit: “;
cin >> grade;
در این حالت برنامه دچار یک حلقه بی نهایت می شود در صورتیکه کاربر ۱- را به عنوان اولین نمره وارد نکند (خط ۶۴).
دقت اعداد اعشاری و نیاز حافظه
متغیرهایی از نوع float عرضهکننده اعداد با دقت منفرد در نقطه اعشار هستند و دارای هفت رقم معنی دار در سیستمهای ۳۲ بیتی می باشند. متغیرهای از نوع double عرضهکننده دقت مضاعف در نقطه اعشار هستند. این دقت مستلزم دو برابر حافظه مورد نیاز برای یک متغیر float است و دارای ۱۵ رقم معنی دار در سیستمهای ۳۲ بیتی است (تقریباً دو برابر دقیقتر از متغیرهایfloat). برای اکثر محاسبات صورت گرفته در برنامهها نوع float می تواند کافی باشد، اما می توانید با استفاده از double دقت را تضمین کنید. در برخی از برنامهها، حتی متغیرهای از نوع double هم کافی نیستند، برنامههایی که خارج از قلمرو بحث این کتاب هستند. اکثر برنامهنویسان برای عرضه اعداد اعشاری از نوع double استفاده می کنند. در واقع C++ بطور پیشفرض با تمام اعداد اعشاری که در کد منبع برنامه تایپ می کنید (همانند ۷.۳۳ و ۰.۰۹۷۵) همانند مقادیر double رفتار می کند. چنین مقادیری در کد منبع بعنوان ثابتهای اعشاری شناخته می شوند.
غالبا اعداد اعشاری در انجام عملیات تقسیم گسترش زیادی پیدا می کنند. برای مثال با تقسیم ۱۰ بر ۳، نتیجه ۳.۳۳۳۳۳۳… با دنبالهای از ۳های نامتناهی خواهد بود. کامپیوتر فضای ثابتی برای نگهداری چنین مقادیری در اختیار دارد، از اینرو ذخیره سازی مقادیر اعشاری فقط بصورت تخمینی صورت می گیرد.
علیرغم اینکه اعداد اعشاری همیشه ۱۰۰ درصد دقیق نیستند، اما کاربردهای بسیاری دارند. برای مثال، هنگامی که در مورد حرارت عادی بدن یعنی ۹۸.۶ صحبت می کنیم، نیازی نیست تا دقت اعشاری آنرا بسیار دقیق بیان کنیم. زمانیکه به درجه حرارت در یک دماسنج نگاه می کنیم و آنرا ۹۸.۶ می خوانیم، ممکن است مقدار دقیق آن ۹۸.۵۹۹۹۴۷۳۲۱۰۶۴۳ باشد. اما استفاده از مقدار ۹۸.۶ به صورت تخمینی در بسیاری از موارد می تواند مناسب و کاربردی باشد.
تبدیل مابین نوعهای بنیادین بصورت صریح و ضمنی
متغیر average بصورت double (خط ۵۵ از شکل ۱۳-۴) اعلان شده تا نتیجه اعشاری محاسبه انجام گرفته را در خود ذخیره سازد. با این همه، متغیرهای total و gradeCounter هر دو از نوع صحیح می باشند. بخاطر دارید که نتیجه تقسیم دو عدد صحیح یک عدد صحیح است که در آن بخش اعشاری جواب از بین میرود (قطع م شود). در عبارت زیر
average = total / gradeCounter;
ابتدا تقسیم انجام می شود، از اینرو بخش اعشاری نتیجه قبل از تخصیص به average از بین می رود. برای انجام یک محاسبه اعشاری با مقادیر صحیح، بایستی مقادیر موقتی که اعداد اعشاری هستند برای محاسبه ایجاد کنیم. زبان C++ دارای عملگر غیرباینری cast است که این وظیفه را انجام می دهد. در خط ۸۱ از عملگر cast بصورت static_cast<double>(total) برای ایجاد یک کپی موقت اعشاری از عملوند موجود در درون پرانتزها یعنی total استفاده شده است. به استفاده از یک عملگر cast به این روش، تبدیل صریح می گویند. هنوز مقدار ذخیره شده در total یک عدد صحیح است.
اکنون محاسبه متشکل از یک مقدار اعشاری (نسخه double موقت از total) است که بر یک عدد صحیح در gradeCounter تقسیم می شود. کامپایلر C++ فقط از نحوه ارزیابی عباراتی که در آن نوع دادههای عملوندها یکسان هستند، اطلاع دارد. برای اطمینان از اینکه عملوندها از نوع مشابه هستند، کامپایلر مبادرت به انجام عملی بنام ترفیع که تبدیل ضمنی نیز نامیده می شود بر روی عملوندهای انتخابی می کند. برای مثال، در یک عبارت که حاوی مقادیری از نوع داده int و double است، C++ مبادرت به ترفیع عملوندهای int به مقادیر double می کند. در این مثال با total همانند یک نوع داده double رفتار می کنیم (با استفاده از عملگر cast)، از اینرو کامپایلر مبادرت به ترفیع gradeCounter به double کرده و به محاسبه اجازه انجام می دهد و نتیجه تقسیم اعشاری به average تخصیص می یابد. در فصل ششم، در مورد نوع دادههای بنیادین و نحوه ترفیع آنها توضیح خواهیم داد.
عملگرهای cast برای استفاده در هر نوع داده و همچنین نوعهای کلاس در دسترس هستند. بدنبال عملگر static_cast یک جفت کاراکتر > و < که نوع داده را احاطه کردهاند آورده می شود. عملگر cast یک عملگر غیرباینری است. عملگری که فقط یک عملوند اختیار می کند. در فصل دوم، با عملگرهای محاسباتی باینری آشنا شدهاید. همچنین C++ از نسخههای عملگرهای غیرباینری جمع (+) و منفی (–) پشتیبانی می کند، از اینرو برنامهنویس می تواند عبارتی مثل -۷ یا +۵ بنویسد. عملگر cast از سایر عملگرهای غیرباینری همانند + و – از تقدم بالاتری برخوردار است. این تقدم بالاتر از عملگرهای *، / و % و پایینتر از پرانتز است. در جدول شکل ۲۲-۴ این عملگر را با نماد static_cast<type>() عرضه کردهایم.
قالببندی اعداد اعشاری
قالببندی بکار رفته در برنامه شکل۱۳-۴ را بطور خلاصه در این بخش و بطور دقیقتر در فصل پانزدهم توضیح خواهیم داد. فراخوانی تابع setprecision در خط ۸۶ (با آرگومان ۲) بر این نکته دلالت دارد که متغیر average از نوع double بایستی با دو رقم معنی دار در سمت راست نقطه اعشار چاپ شود (مثلاً ۹۷.۳۷) به اینحالت کنترلکننده جریان پارامتری شده (استریم) می گویند (بدلیل وجود ۲ در درون پرانتز). برنامههایی که از این فراخوانی استفاده می کنند باید حاوی رهنمود دستور دهنده زیر باشند (خط ۱۰)
#include <iomanip>
خط ۱۱ تصریحکننده نام فایل سرآیند <iomanip> است که در این برنامه بکار گرفته خواهد شد. دقت کنید که endl یک کنترلکننده جریان پارامتری نشده است (چرا که پس از آن مقدار یا عبارتی در درون پرانتزها وجود ندارد) و نیازمند فایل سرآیند <iomanip> نیست. اگر دقت تعیین نشود، معمولاً اعداد اعشاری با شش رقم معنی دار چاپ می شوند (دقت پیشفرض در اکثر سیستمهای ۳۲ بیتی). کنترلکننده جریان fixed بر این نکته دلالت دارد که مقادیر اعشاری بایستی با خروجی که فرمت نقطه ثابت نامیده میشوند چاپ شوند، که متضاد نماد علمی می باشد. نماد علمی روشی برای نمایش یک عدد بصورت، عدد اعشاری مابین مقدار۱ الی۱۰ است که در توانی از ۱۰ ضرب می شود. برای مثال، مقدار۳۱۰۰ را می توان در نماد علمی بصورت۳.۱×۱۰۳ به نمایش در آورد. به هنگام نمایش مقادیری که بسیار بزرگ یا بسیار کوچک هستند، نماد علمی می تواند ابزار مناسبی برای اینکار باشد در فصل پانزدهم با قالببندی نماد علمی آشنا خواهید شد. در طرف مقابل، قالببندی نقطه ثابت قرار دارد که یک عدد اعشاری را مجبور می کند تا به تعداد مشخص شده مبادرت به نمایش ارقام کند. همچنین این فرمت نقطه اعشار و دنباله صفرها در چاپ را کنترل می کند، حتی اگر عدد یک عدد صحیح باشد، همانند ۸۸.۰۰، بدون قالببندی نقطه ثابت چنین عددی در C++ بصورت ۸۸ چاپ می شود، بدون دنباله صفرها و نقطه اعشار. زمانیکه از کنترلکنندههای جریان fixed و setprecision در برنامهای استفاده می شود، مقادیر چاپ شده به تعداد نقاط دیسمال که توسط مقدار ارسالی به setprecision مشخص می شود، گرد می شوند (همانند مقدار ۲ در خط ۸۶)، اگرچه مقدار موجود در حافظه بدون تغییر باقی می ماند. برای مثال، مقادیر ۸۷.۹۴۶ و ۶۷.۵۴۳ بصورت ۸۷.۹۵ و ۶۷.۵۴ چاپ می شوند. توجه کنید که می توان نقطه اعشار را با استفاده از کنترلکننده جریان showpoint به نمایش درآورد. اگر showpoint بدون fixed بکار گرفته شود، دنباله صفحهها چاپ نخواهد شد. همانند endl، کنترلکنندههای جریانfixed وshowpoint پارامتری شده نبوده و نیازی به سرآیند فایل <iomanip> ندارند. هر دو آنها را می توان در سرآیند <iostream> پیدا کرد.
خط ۸۶ و ۸۷ از شکل ۱۳-۴ خروجی میانگین کلاس هستند. در این مثال میانگین کلاس گرد شده به نزدیکترین صدم و دقیقاً با دو رقم در سمت راست نقطه اعشار به نمایش درآمدهاند. کنترلکننده جریان پارامتری شده (خط ۸۶) نشان می دهد که مقدار متغیر average بایستی با دقت دو رقم در سمت راست نقطه اعشار به نمایش درآید (setprecision(2)). در اجرای نمونهای برنامه سه نمره وارد برنامه ۱۴-۴ شده که مجموع آنها ۲۵۷ شده است و میانگین حاصل از این رقم عدد ۸۵.۶۶۶۶۶۶ است. کنترلکننده جریان پارامتری شده setprecision سبب می شود تا مقدار به تعداد رقم مشخص گرد شود. در این برنامه، میانگین به ۸۵.۶۷ گرد شده است.
اینا که اصلا لینک دانلود نداره هیچکدومش!!!
راهنمای دانلود !!!!!!!!!!!!!!! مقاله هستش