گام دهم در برنامه نویسی ++C
اهداف کلی:
آشنایی با الگوریتم های مرتب سازی و جستجو و تمرین و استفاده کاربردی از آرایه ها
اهداف رفتاری و عمکردی:
انتظار می‌رود پس از پایان این جلسه بتوانید: «جستجوی خطی» و «جستجوی دودویی» را به اختصار شرح دهید و الگوریتم های مرتب سازی را فرابگیرید و الگوریتم برنامه هایی را که نوشتیم را به صورت ساختاری به خاطر بسپارید.
سرفصل های تئوری:
- توضیح درمورد مرتب سازی ها
- الگوریتم ـ مرتب‌سازی Insertion (درجی)
- الگوریتم ـ مرتب‌سازی حبابی (bubble sort)
- الگوریتم ـ مرتب‌سازی max-min
- توضیح درمورد جستو جودودویی وتفاوت های آن
سرفصل های عملی:
- حل مثال الگوریتم ـ مرتب‌سازی max-min
- حل مثال مرتب‌سازی Insertion (درجی)
- حل مثال مرتب‌سازی max-min
- حل مثال جستو جودودویی
مواد و تجهیزات لازم برای گام:
مواد و تجهیزات لازم برای گام:
فواید مرتب‌سازی:
امكان جستجوی سریع تر میان اقلام زیاد
اطلاعات آماری معمولاً به‌صورت مرتب شده قابل استفاده‌تر هستند
ابتدا لازم می بینیم که دو الگوریتم ساده - را قبل از توضیح الگوریتم مرتب سا زی توضیح دهیم بنابراین به برنامه های نوشته شده زیر دقت کنید.
الگوریتم ـ شمارش (counter)
برنامه‌ای بنویسید كه تعداد مقسوم‌علیه‌های یك عدد را محاسبه و آنها را بر روی صفحه چاپ كند:
توضیح: مجموعه‌ی همه‌ی اعدادی كه از عددی كوچك تر هستند و آن عدد، بر آنها قابل تقسیم است، مقسوم‌علیه‌های آن عدد گویند.
int counter(int num)
{
int count=0;
for (int i=1; i<=num/2; ++i)
if (num%i == 0)
{
printf(“%d\t”, i);
count++;
}
return count;
}
الگوریتم ـ flag (پرچم)
توضیح الگوریتم پرچم را در غالب مثال زیرتوضیح داده شود.
مثال الگورتم پرچم:
برنامه‌ای بنویسید كه ورودی كاربر را بصورت كاراكتر دریافت كند. این كار را ادامه دهد تا وقتی كاربر حروف OK را تایپ كند. لازم نیست ورودی كار بر جایی ذخیره شود. سایر دنباله‌ها نظیر ko، kao یا oak قابل قبول نیستند.
هدف: یادگیری استفاده از متغیرهای بولی
{
bool chO=false;
bool stop=flase;
do {
switch ( getch() ) {
case ‘o’:
case ‘O’: ch0=true;
break;
case ‘k’:
case ‘K’: if (chO)
stop=true;
break;
default:
chO=false;
// break;
}
} while (!stop);
}
- الگوریتم ـ مرتب‌سازی max-min
توضیح :
در این روش، با هر بار پویش آرایه، بزرگ ترین عنصر یافته شده با عنصر ابتدایی آرایه (بازه) جابه‌جا (swap) می‌شود و عنصر ابتدایی، از دامنه‌ی پویش حذف می‌شود.
توجه: در اینكه پیشنهادات دانش‌آموزان در زمینه بهبود روش‌های مرتب‌سازی باید مورد توجه قرار گیرد و در مورد صحت آنها توضیح داده شود، به این موضوع اشاره شود كه تغییرات جزیی، هر چند در حالات ساده ممكن است تأثیر در سرعت اجرای برنامه داشته باشد ولی در حجم زیاد اطلاعات، چندان تأثیری ندارد
پیاده‌سازی:
void sortMaxMin(int array[], int n)
{
int i ,j
int max; // index of max element
int swapTemp;
for (i=0; i
max=i ; // the first element is selected temporarily
for (j=i+1 ; j
max = j;
// swap max and i (first element)
swapTemp=array[max];
array[max]=array[i];
array[i]=swapTemp;
}
}
تمرین: برنامه‌ای بنویسید كه با استفاده از maxmin یك آرایه از نمرات دانش‌آموزان را مرتب كند.
- الگوریتم ـ مرتب‌سازی حبابی (bubble sort)
نکته 1: مرتب‌سازی حبابی با نحوه‌ی مرتب‌سازی دانش‌آموزان در یك صفر (مقایسه‌ی دوبه‌دوی دانش‌آموزان) توضیح داده شود.
نکته2: به این محدودیت اشاره شود كه كامپیوتر نمی‌توان در آن واحد تمام عناصر آرایه را ببیند و آنها را مرتب كند. بلكه تنها در هر بار مقایسه، دو عنصر قابل مقایسه هستند. به علاوه نمی‌تواند مثل آدم‌ها، در بین عناصر برای یك عنصر جدید جا باز كند.
توضیح:
از ابتدای آرایه شروع می‌كنیم. در صورتی كه عنصراولی از دومی بزرگ تر بود، جای آنها را عوض می‌كنیم. حالاعنصر دومی را با سومی و همین طور تا به پایان آرایه بریم. در این حالت، بزرگ ترین عنصر در انتهای آرایه قرار گرفته است. حالا همین كار را برای عناصر باقی‌مانده انجام می‌دهیم. در مرحله‌ای كه هیچ دو عنصری جابه‌جا نشوند یا اینكه لیست عناصر بزرگ تر به ابتدای آرایه برسد، آرایه مرتب شده است.
تمرین: برنامه‌ای بنویسید كه معدل 30 دانش‌آموز (اعداد اعشاری) را از كاربر بگیرد و نمرات مرتب شده، هم چنین میانه (عنصری كه نیمی از اقلام از آن بزرگ تر و نیمی كوچك ترند) را چاپ كند.
پباده سازی:
void print(float[],int);
void sort(float[],int);
int main()
{
float a[]={55.5,22.2,99.9,66.6,44.4,88.8,33.3, 77.7};
print(a,8);
sort(a,8);
print(a,8);
}
void sort(float a[], int n)
{ // bubble sort:
for (int i=1; i
for (int j=0; j
//INVARIANT: a[n-1-i..n-1] is sorted
}
الگوریتم ـ مرتب‌سازی Insertion (درجی)
نکته: اگر داده‌ها به صورت تصادفی وارد شده باشند، مرتب‌سازی درجی تقریباً دو برابر سریع تر از مرتب‌سازی حبابی عمل می‌كند.
توجه: پس از توضیح الگوریتم مقایسه آن دو انجام شود.
توضیح:
برای تفهیم نحوه‌ی كاركرد الگوریتم می‌توان صفی از دانش‌آموزان را در نظر گرفت كه با یك پرچم به دو قسمت تقسیم شده‌اند، كسانی كه در سمت راست پرچم هستند، نامرتب ایستاده‌اند و در سمت چپ پرچم به ترتیب قد ایستاده‌اند. در هر مرحله پرچم یك نفر به سمت راست می‌رود و فرد جدید در سمت چپ صف در جای مناسب خود می‌ایستد وقتی پرچم به انتهای سمت راست صف برسد، تمام دانش‌آموزان مرتب شده‌اند.
پیاده سازی الگوریتم:
مرتب سازی از كوچك به بزرگ
{ int i, j;
int temp;
for (i=1; i
temp=array [i];
for (j=i ; j>0 && array[j-1]>temp; --j)
array[j]=array[j-1]; // shift left
array[j]=temp; // insert new element in its pos
}
}
تمرین: در صورتی كه هر یك از عناصر یك آرایه كه ممكن است تكراری هم باشند، یك علامت همیشه مشخصه منحصر بفرد به همراه داشته باشند، در كدام یك از روش‌های مرتب‌سازی ذكر شده، ترتیب ظهور عناصر تكراری با توجه به علامت مشخصه منحصر بفردشان حفظ می‌شود؟
جواب: در هر سه مورد این روش‌ها، ترتیب حفظ می‌شود. به این خاصیت پایداری الگوریتم مرتب‌سازی گفته می‌شود. بعضی روش‌های مرتب‌سازی پیشرفته‌تر هستند كه این خاصیت را ندارند.
تمرین: برنامه‌ای بنویسید كه نمرات دانش‌آموزان یك كلاس را دریافت كند و آنها را با مرتب‌سازی درجی، مرتب كند. پس از آن، برنامه را بصورتی تغییر دهید كه عمل مرتب‌سازی را حین دریافت اطلاعات از كاربر انجام دهد (عمل درج در یك آرایه‌ی مرتب)
تابع sort() از دو حلقۀ تودرتو استفاده می‌كند.
1- حلقه for داخلی زوج‌های همسایه را با هم مقایسه می‌كند و اگر آنها خارج از ترتیب باشند، جای آن دو را با هم عوض می‌کند.
وقتی for داخلی به پایان رسید، بزرگ‌ترین عنصر موجود در محدودۀ فعلی به انتهای آن هدایت شده است.
2-سپس حلقۀ for بیرونی محدودۀ جستجو را یکی کم می‌کند و دوباره for داخلی را راه می‌اندازد تا بزرگ‌ترین عنصر بعدی به سمت بالای آرایه هدایت می شود.
- الگوریتم جستجوی دودویی
در روش جستجوی دودویی به یک آرایه ی مرتب نیاز است.
هنگام جستجو آرایه از وسط به دو بخش بالایی و پایینی تقسیم می‌شود. مقدار مورد جستجو با آخرین عنصر بخش پایینی مقایسه می‌شود. اگر این عنصر کوچک‌تر از مقدار جستجو بود، مورد جستجو در بخش پایینی وجود ندارد و باید در بخش بالایی به دنبال آن گشت. دوباره بخش بالایی به دو بخش تقسیم می‌گردد و گام‌های بالا تکرار می‌شود.
سرانجام محدوده ی جستجو به یک عنصر محدود می‌شود که یا آن عنصر با مورد جستجو برابر است و عنصر مذکور یافت شده و یا این که آن عنصر با مورد جستجو برابر نیست و لذا مورد جستجو در آرایه وجود ندارد. این روش پیچیده‌تر از روش جستجوی خطی است اما در عوض بسیار سریع‌تر به جواب می‌رسیم.
مثال :تابعی که در زیر آمده از روش جستجوی دودویی برای یافتن مقدار درون آرایه استفاده می‌کند:
#include
using namespace std;
int index(int, int[],int);
int main()
{ int a[] = { 22, 33, 44, 55, 66, 77, 88};
cout << "index(44,a,7) = " << index(44,a,7) << endl;
cout << "index(60,a,7) = " << index(60,a,7) << endl;
}
int index(int x, int a[], int n)
{ // PRECONDITION: a[0] <= a[1] <= ... <= a[n-1];
// binary search:
int lo=0, hi=n-1, i;
while (lo <= hi)
{ i = (lo + hi)/2; // the average of lo and hi
if (a[i] == x) return i;
if (a[i] < x) lo = i+1; // continue search in a[i+1..hi]
else hi = i-1; // continue search in a[0..i-1]
}
return n; // x was not found in a[0..n-1]
}
برای این که بفهمیم تابع چطور کار می‌کند، فراخوانی index(44,a,7) را دنبال می‌کنیم.
وقتی حلقه شروع می‌شود، x=44 و n=7 و lo=0 و hi=6 است.
ابتدا i مقدار(0+6)/2 = 3 را می‌گیرد.پس عنصرa[i] عنصر وسط آرایه یa[0..6] است. مقدار a[3] برابر با 55 است که از مقدار x بزرگ‌تر است. پس x در نیمه ی بالایی نیست و جستجو در نیمه ی پایینی ادامه می‌یابد. لذا hi با i-1 یعنی 2 مقداردهی می‌شود و حلقه تکرار می‌گردد.
حالا hi=2 و lo=0 است و دوباره عنصر وسط آرایه ی a[0..2] یعنی a[1] با x مقایسه می‌شود. a[1] برابر با 33 است که کوچک‌تر از x می‌باشد. پس این دفعه lo برابر با i+1 یعنی 2 می‌شود.
در سومین دور حلقه، hi=2 و lo=2 است. پس عنصر وسط آرایه ی a[0..2] که همان a[2] است با x مقایسه می‌شود. a[2] برابر با 44 است که با x برابر است. پس مقدار 2 بازگشت داده می‌شود؛ یعنی x مورد نظر درa[2] وجود دارد.
در تابع فوق هر بار که حلقه تکرار می‌شود، محدوده ی جستجو 50% کوچک‌تر می‌شود. در آرایه ی n عنصری، روش جستجوی دودویی حداکثر به مقایسه نیاز دارد تا به پاسخ برسد.
حال آن که در روش جستجوی خطی به n مقایسه نیاز است.
تفاوت های جستجوی دودویی و خطی
دومین تفاوت در این است که اگر چند عنصر دارای مقادیر یکسانی باشند، آنگاه جستجوی خطی همیشه کوچک‌ترین ایندکس را برمی‌گرداند ولی در مورد جستجوی دودویی نمی‌توان گفت که کدام ایندکس بازگردانده می‌شود.
گام به گام با برنامه نویسی به زبانC++
بخش پژوهش های دانش آموزی سایت تبیان
منبع:
