درس أول محاضرة خوارزميات عملي

[Golden man]

أول محاضرة خوارزميات عملي



لقياس جودة الخوارزمية ندرس تأثير حجم المعطيات على زمن تنفيذ الخوارزمية و يتم ذلك بأخذ لقطة للزمن قبل البدء بتنفيذ الجزء الذي نريد معرفة جودته و لقطة أخرى للزمن في نهاية الخوارزمية , ثم نطرح الزمنين و يكون الناتج هو زمن تنفيذ هذه الخوارزمية .


لمعرفة الزمن الذي مضى على تشغيل الحاسب نستخدم تابعGetTickCount() من مكتبة windows.h يرد الزمن المنقضي على تشغيل الحاسب بالميلي ثانية.


مثال لتجربة التابع:



#include<iostream.h>
#include<windows.h>
void main()
{
int StartTime = GetTickCount();
for(int i=0; i<100000000; i++);\\الجزء الذي نريد معرفة زمن تنفيذه
int EndTime = GetTickCount();
int ProgramTime = EndTime - StartTime;
cout<<"The Program take "<<ProgramTime<<" seconds";
}


حيث أن الجزء الفعال في المثال السابق هو الحلقة التي تدور مئة مليون مرة و قد استخدمت هذا الرقم لكي يتحسس التابع الزمن المنقضي على تنفيذ هذه الحلقة لأنه برقم أقل ينتج فرق زمن صفر أي ينفذ البرنامج بأقل من ميلي ثانية.



و قد كانت الخوارزمية التي درسنا جودتها في أول محاضرة هي خوارزمية الفرز الفقاعي لمصفوفة من الأعداد الصحيحة .



كتابة البرنامج:

سوف نقوم بتقسم البرنامج إلى عدة كتل برمجية (توابع) لتسهل معرفة زمن تنفيذ أي جزء:



عناصر البرنامج : 1 – مصفوفة من الأعداد الصحيحة 2 – حجم المصفوفة (ثابت)


1 – التابع الأول يقوم بملأ مصفوفة بقيم عشوائية .
2 – تابع لطباعة المصفوفة عند الحاجة.

3 – تابع لتنفيذ خوارزمية الفرز الفقاعي على المصفوفة السابقة.

4 – تابع الـ main الذي سوف نستدعي التوابع السابقة خلاله.

أولا : تعريف عناصر البرنامج :



const int ARRDIM = 10000;
int InitArr[ARRDIM];


حيث أن ARRDIM هو ثابت يمثل حجم المصفوفة و هذا الثابت سوف نستخدمه في جميع أجزاء البرنامج و يفيدنا عندما نحتاج إلى تغيير حجم المصفوفة حيث يكفي تغيير قيمته لتغيير جميع الأطوال التي تدل على المصفوفة في البرنامج.

المصفوفة InitArr[ARRDIM]; هي المصفوفة التي سنتعامل معها في البرنامج و يكون عدد عناصرها هو ARRDIM.


ثانيا: التوابع التي نحتاجها:

1 – تابع ملأ المصفوفة :



void FillArr()
{
for(int i=0; i<ARRDIM; i++)
InitArr[i] = rand()%10;
}


حيث يقوم هذا التابع بملأ المصفوفة بقيم عشوائية .

و لكن يوجد مشكلة أن الأرقام العشوائيةالمولدة من التابع rand() تتكرر نفسها دائما و لكن بما أنه لكل مشكلة حل فهذه هي الطريقة :

نضيف السطر التالي قبل استخدام التابع لربط العشوائية بالزمن .



srand(GetTickCount());


فيصبح التابع كما يلي :



void FillArr()
{
srand(GetTickCount());
for(int i=0; i<ARRDIM; i++)
InitArr[i] = rand()%10;
}



2 – تابع طباعة المصفوفة:



void PrintArr()
{
for(int i=0; i<ARRDIM; i++)
cout<<InitArr[i]<<' ';
cout<<endl;
}


3 – تابع الفرز الفقاعي لمصفوفة من الأعداد الصحيحة:



void BubleSort()
{
for(int i=0; i<ARRDIM-1 ; i++)
for(int j=i+1; j<ARRDIM; j++)
if(InitArr[i] > InitArr[j])
{
int tmp = InitArr[i];
InitArr[i] = InitArr[j];
InitArr[j] = tmp;
}
}


4 – تابع الـ main() :



int main()
{
FillArr();
// PrintArr();

int FTime = GetTickCount();

BubleSort();

int STime = GetTickCount();
int Time = STime - FTime;
cout<<Time<<endl;

// PrintArr();

return 0;
}


يصبح البرنامج كاملا كما يلي:




#include <iostream.h>
#include <windows.h>
const int ARRDIM = 10000;
int InitArr[ARRDIM];

void FillArr()
{
srand(GetTickCount());
for(int i=0; i<ARRDIM; i++)
InitArr[i] = rand()%10;

}

void PrintArr()
{
for(int i=0; i<ARRDIM; i++)
cout<<InitArr[i]<<' ';
cout<<endl;
}

void BubleSort()
{
for(int i=0; i<ARRDIM-1 ; i++)
for(int j=i+1; j<ARRDIM; j++)
if(InitArr[i] > InitArr[j])
{
int tmp = InitArr[i];
InitArr[i] = InitArr[j];
InitArr[j] = tmp;
}
}

int main()
{
FillArr();
// PrintArr();

int FTime = GetTickCount();

BubleSort();

int STime = GetTickCount();
int Time = STime - FTime;
cout<<Time<<endl;

// PrintArr();

return 0;
}


بقي الآن حل الوظيفة التي طلبها الأستاذ و هي رسم المخطط البياني لتأثير حجم المصفوفة على زمن التنفيذ و يتم ذلك برسم المنحني البياني لذلك حيث يمثل محور السينات حجم المصفوفة و محور العينات الزمن المستغرق لفرز المصفوفة و يجب أن تكون القيمة البدائية لحجم المصفوفة 10000 لأنه عند هذه القيمة يبدأ ظهور زمن فعلي في التنفيذ و قبله يفرز بأقل من ميلي ثانية.



سوف أترك الوظيفة لكم فكل شخص يجب أن يحلها على ورقة منفصلة و بطريقته الخاصة فأرجو منكم محاولة حلها بشكل جدي و عند وجود أي سؤال لن نبخل بالإجابة بإذن الله عند معرفة الجواب....



نهاية أتمنى أن لا تكون المشاركات شكر و إنما أرجو أن تكون إما إضافة على الموضوع أو سؤال .



و شكرا على حسن إصغائكم..

[allmaida]

شكرا كتير اخ golden man انا سنة اولى وفهمت كل يللي انت قلتو

فشكرا كتير على مجهودك بس في الشغلة تبع تغير القيمة العشوائية

srand(GetTickCount());

ما فهمت شو بساوي فيا ريت تقلي ولك جزيل الشكر

يمكن تكون شغلة مناخدها بعدين بس يا ريت اذا معك وقت تشرحلي ياها

[Golden man]

صديقي إليك ما هو موجود في مكتبة الـ MSDN عن التابع srand :
The srand function sets the starting point for generating a series of pseudorandom integers. To reinitialize the generator, use 1 as the seed argument. Any other value for seed sets the generator to a random starting point. rand retrieves the pseudorandom numbers that are generated. Calling rand before any call to srand generates the same sequence as calling srand with seed passed as 1.

و المغزى من هذا الكلام هو أن التابع srand يؤثر على نقطة البداية التي سيبدأ منها التابع rand و بما أننا ربطنا نقطة البداية بالزمن فهذا يؤدي إلى توليد نقاط بداية عشوائية (أي عشوائية لتوليد العشوائية) مما يؤدي المطلوب.

باختصار : التابعين rand و srand متكاملين لتأدية العمل في توليد أرقام عشوائية لا تكرر نفسها في كل مرة.

[صعب المنال]

مرحبــــــــــــــــــا
الصراحة اول مرا ببداية هذا الفصل بسمع بتابع اسمو srand وذلك بمقابلة المشروع يلي طرحو او طرح اسمو قدامي الاستاذ مسعود ردا على سؤال ما
المهم ..حاولت الاستفسار عنو فاجابني احدهم :
انو
(rand)*(any type of num)

ما يغنيك عنه هوا :
srand

فهل اجابة من اجابني صحيحة يا صديقي..

[يونس]

انت واحد رهيب