سه شنبه 30 اردیبهشت 1393
17:57
نظرات()
در این پست پیرامون الگوریتم های داده شده توسط استاد براری بحث می کنم.
1) الگوریتم جایگشت - Permutation - را می توان از راه های گوناگونی بدست آورد؛ هدف این الگوریتم، بدست آوردن تمام حالاتی است که چندین حرف یا عدد می توانند کنار هم بدون تکرار قرار بگیرند. من در اینجا راهی را که با کمک یکی از دوستانم - سپهر محمدی - پیدا کردم، شرح می دهم.
برای ساخت این الگوریتم با راهی که بدست آرودم، باید ابتدا الگوریتمی که در کلاس نیز مطرح شده بود و الگوریتم حبابی - Bubble Algorithm - نام داشت را بنویسیم، سپس عکس الگوریتم حبابی را بدست آوریم.
یعنی ابتدا خود الگوریتم حبابی را می نویسیم که چنین کاری را انجام می دهد:
1) الگوریتم جایگشت - Permutation - را می توان از راه های گوناگونی بدست آورد؛ هدف این الگوریتم، بدست آوردن تمام حالاتی است که چندین حرف یا عدد می توانند کنار هم بدون تکرار قرار بگیرند. من در اینجا راهی را که با کمک یکی از دوستانم - سپهر محمدی - پیدا کردم، شرح می دهم.
برای ساخت این الگوریتم با راهی که بدست آرودم، باید ابتدا الگوریتمی که در کلاس نیز مطرح شده بود و الگوریتم حبابی - Bubble Algorithm - نام داشت را بنویسیم، سپس عکس الگوریتم حبابی را بدست آوریم.
یعنی ابتدا خود الگوریتم حبابی را می نویسیم که چنین کاری را انجام می دهد:
که یعنی اعداد کوچکتر را اول و اعداد بزرگتر را بعد عدد کوچکترش می گذارد.
نکته طلایی: در الگوریتم جایگشت، به جای اعداد باید از شماره آرایه استفاده کرد؛ یعنی به جای
حالا بعد از نوشتن این الگوریتم؛ هر بار که یک جایگشت اتفاق افتاد، باید کل اعضا چاپ شوند، به تصویر زیر نگاه کنید تا متوجه شوید:
اما الگوریتم حبابی همه جایگشت ها را نشان نمی دهد!
پس در ادامه باید عکس الگوریتم حبابی را نوشت؛ اینگونه همه جایگشت های یک دسته از آرایه ها نمایش داده می شوند.
در آخر چیزی شبیه به این خواهیم داشت:
اما این الگوریتمی که نوشته ایم، جایگشت تمام اعضای یک دسته از آرایه ها است، به عبارتی r=n هست که r تعداد اعضای جایگشتی و n تعداد کل اعضا است. مثلا در A={1,2,3,4} n=4 است و اگر بخواهم تعداد جایگشت های دو عضو را نشان دهد، الگوریتم نوشته شده این کار را نمی تواند انجام دهد چون r=2 نیست و همواره در الگوریتم ما r=n است. برای حل این موضوع باید الگوریتم شماره سه که الگوریتم مجموعه هاست را بنویسید و سپس از خروجی آن الگوریتم در ورودی این الگوریتم استفاده نمایید. با این کار r=n میماند اما هربار که از خروجی الگوریتم مجموعه ها استقاده می کند،n بین 1 تا n خواهد بود.
2) الگوریتم گزاره ها؛ این نوع الگوریتم بسیار ساده است. شما باید با مفهوم گزاره ها آشنا باشید، سپس با دانستن اینکه در شرط If در هر زبان برنامه نویسی ای تنها شروط درست اجرا می شوند، ساخت این الگوریتم بسیار آسان می شود. به کد زیر نگاه کنید:
نکته طلایی: در الگوریتم جایگشت، به جای اعداد باید از شماره آرایه استفاده کرد؛ یعنی به جای
1 2 3 4 5 6 7 8 باید نوشت A[1] A[2] A[3] A[4].... pاینگونه می توان جایگشت را انجام داد.
حالا بعد از نوشتن این الگوریتم؛ هر بار که یک جایگشت اتفاق افتاد، باید کل اعضا چاپ شوند، به تصویر زیر نگاه کنید تا متوجه شوید:
پس در ادامه باید عکس الگوریتم حبابی را نوشت؛ اینگونه همه جایگشت های یک دسته از آرایه ها نمایش داده می شوند.
در آخر چیزی شبیه به این خواهیم داشت:
2) الگوریتم گزاره ها؛ این نوع الگوریتم بسیار ساده است. شما باید با مفهوم گزاره ها آشنا باشید، سپس با دانستن اینکه در شرط If در هر زبان برنامه نویسی ای تنها شروط درست اجرا می شوند، ساخت این الگوریتم بسیار آسان می شود. به کد زیر نگاه کنید:
void main()
{
cin>>p>>q;
If ((p==1)&&(q==1))
{
cout<<"1";
}
else cout<<"0";
}
{
cin>>p>>q;
If ((p==1)&&(q==1))
{
cout<<"1";
}
else cout<<"0";
}
این کد بالا؛ دو گزاره p و q را برای شرط p˄q که هردو p=1 و q=1 هستند عدد 1 را چاپ می کند. خب برای اینکه تک تک شروط رو این طور بنویسیم وقتمان گرفته می شود، یک کار دیگر میکنیم.
ابتدا تابعی به نام VA می نویسیم که اعتبار گزاره های ˄ را حساب کند. و یه این تابع مقدار p و q را نسیت می دهیم. یعنی تابعی به شکل زیر می نویسیم:
void VA(int p, int q)
{
If ((p==1)&&(q==1)) // یک یعنی درست و صفر یعنی نادرست
{
cout<<"1";
}
else cout<<"0";
}
ابتدا تابعی به نام VA می نویسیم که اعتبار گزاره های ˄ را حساب کند. و یه این تابع مقدار p و q را نسیت می دهیم. یعنی تابعی به شکل زیر می نویسیم:
void VA(int p, int q)
{
If ((p==1)&&(q==1)) // یک یعنی درست و صفر یعنی نادرست
{
cout<<"1";
}
else cout<<"0";
}
سپس تابعی به نام YA می نویسیم و شروط آن را نیز داخلش پیاده می کنیم:
void YA(int p, int q)
{
If ((p==1)||(q==1)) \\یعنی اگر پی یا کیو درست بود شرط انجام شود
{
cout<<"1";
}
else cout<<"0";
}
{
If ((p==1)||(q==1)) \\یعنی اگر پی یا کیو درست بود شرط انجام شود
{
cout<<"1";
}
else cout<<"0";
}
و نوشتن توابع را برای استلزام و مانع جمع و شرط دو طرقه را ادامه دهید. البته یک کلک هم می توانید بزنید تا نوشتن یک تابع برای شما راحت تر شود؛ آن کلک هم این است که پس از نوشتن تابع مانع جمع که چنین است:
void mYA(int p, int q)
{
If (((p==1)&&(q==0))||(p==0)&&(q==1))) \\برای درستی مانع جمع باید یکی از گزاره ها با گزاره دیگر پاد-ارزش باشد
{ \\یعنی اگر پی درست بود؛ کیو نادرست باشد تا مانع جمعشان درست شود
cout<<"1";
}
else cout<<"0";
}
{
If (((p==1)&&(q==0))||(p==0)&&(q==1))) \\برای درستی مانع جمع باید یکی از گزاره ها با گزاره دیگر پاد-ارزش باشد
{ \\یعنی اگر پی درست بود؛ کیو نادرست باشد تا مانع جمعشان درست شود
cout<<"1";
}
else cout<<"0";
}
تنها جای 0 و 1 را در دستورات if و else جابجا کنید و بدین گونه تابع شرط دو طرفی (اگر و فقط اگر) بدست آید.
حالا این توابع را در تابع main فراخوانی کنید. بهتر است از آرایه استفاده کنید تا بتوان چندین p و q را یکباره ارزش گذاری کرد.
3) الگوریتم مجموعه ها یا PowerSet، نمایش تک تک یک مجموعه هدف این الگوریتم است. الگوریتم های زیادی وجود دارند اما پیچیده هستند، یکی از این الگوریتم ها که درک آن تا حدودی ساده تر از باقی هم نوعانش هست؛ الگوریتم زیر است که البته کامل نیست:
این هم از راهنمایی من برای نوشتن الگوریتم ها، من اجازه پاسخ صریح الگوریتم ها را نداشتم و به همین راهنمایی برای شما، بسنده نموده ام.
امیدوارم که هر "دانشجو" ای موفق باشد.
حالا این توابع را در تابع main فراخوانی کنید. بهتر است از آرایه استفاده کنید تا بتوان چندین p و q را یکباره ارزش گذاری کرد.
3) الگوریتم مجموعه ها یا PowerSet، نمایش تک تک یک مجموعه هدف این الگوریتم است. الگوریتم های زیادی وجود دارند اما پیچیده هستند، یکی از این الگوریتم ها که درک آن تا حدودی ساده تر از باقی هم نوعانش هست؛ الگوریتم زیر است که البته کامل نیست:
void printPowerSet(char *set, int set_size){ /*اندزه سایز الگوریتم set_size n is (2**n -1)*/ pow_set_size = pow(2, set_size); counter, j=0; /*Run from counter 000..0 to 111..1*/ for(counter = 0; counter < pow_set_size; counter++) { for(j = 0; j < set_size; j++) { /* چک کنه که آرایه جـِی ام در شمارنده است
اگر هست؛ چاپ کند */ if(counter & (1<<j)) printf("%c", set[j]); } printf("\n"); \\چاپ یک خط جدید جهت منظم سازی
}}/*تابع مین برای اجرا این الگوریتم*/int main(){ char set[] = {'a','b','c'}; printPowerSet(set, 3); getchar(); return 0;}این هم از راهنمایی من برای نوشتن الگوریتم ها، من اجازه پاسخ صریح الگوریتم ها را نداشتم و به همین راهنمایی برای شما، بسنده نموده ام.
امیدوارم که هر "دانشجو" ای موفق باشد.