تبلیغات
گروه مهندسی IT نئوهوش - راهنمای حل الگوریتم های جایگشت، گزاره و مجموعه ها.
برای مشاهده هر پست، روی آن کلیک کنید تا محتوای آن پست به نمایش درآید

راهنمای حل الگوریتم های جایگشت، گزاره و مجموعه ها.

نویسنده: دانوش
سه شنبه 30 اردیبهشت 1393 ساعت 17:57 مشاهده مطلب نظرات
در این پست پیرامون الگوریتم های داده شده توسط استاد براری بحث می کنم.

1) الگوریتم جایگشت - Permutation - را می توان از راه های گوناگونی بدست آورد؛ هدف این الگوریتم، بدست آوردن تمام حالاتی است که چندین حرف یا عدد می توانند کنار هم بدون تکرار قرار بگیرند. من در اینجا راهی را که با کمک یکی از دوستانم - سپهر محمدی - پیدا کردم، شرح می دهم.

برای ساخت این الگوریتم با راهی که بدست آرودم، باید ابتدا الگوریتمی که در کلاس نیز مطرح شده بود و الگوریتم حبابی - Bubble Algorithm - نام داشت را بنویسیم، سپس عکس الگوریتم حبابی را بدست آوریم.
یعنی ابتدا خود الگوریتم حبابی را می نویسیم که چنین کاری را انجام می دهد:

که یعنی اعداد کوچکتر را اول و اعداد بزرگتر را بعد عدد کوچکترش می گذارد.
نکته طلایی: در الگوریتم جایگشت،  به جای اعداد باید از شماره آرایه استفاده کرد؛ یعنی به جای

  1 2 3 4 5 6 7 8 باید نوشت A[1] A[2] A[3] A[4]....  pاینگونه می توان جایگشت را انجام داد.

حالا بعد از نوشتن این الگوریتم؛ هر بار که یک جایگشت اتفاق افتاد، باید کل اعضا چاپ شوند، به تصویر زیر نگاه کنید تا متوجه شوید:

اما الگوریتم حبابی همه جایگشت ها را نشان نمی دهد!
پس در ادامه باید عکس الگوریتم حبابی را نوشت؛ اینگونه همه جایگشت های یک دسته از آرایه ها نمایش داده می شوند.
در آخر چیزی شبیه به این خواهیم داشت:
اما این الگوریتمی که نوشته ایم، جایگشت تمام اعضای یک دسته از آرایه ها است، به عبارتی r=n هست که r تعداد اعضای جایگشتی و n تعداد کل اعضا است. مثلا در A={1,2,3,4} n=4 است و اگر بخواهم تعداد جایگشت های دو عضو را نشان دهد، الگوریتم نوشته شده این کار را نمی تواند انجام دهد چون r=2 نیست و همواره در الگوریتم ما r=n است. برای حل این موضوع باید الگوریتم شماره سه که الگوریتم مجموعه هاست را بنویسید و سپس از خروجی آن الگوریتم در ورودی این الگوریتم استفاده نمایید. با این کار r=n میماند اما هربار که از خروجی الگوریتم مجموعه ها استقاده می کند،n بین 1 تا n خواهد بود.


2) الگوریتم گزاره ها؛ این نوع الگوریتم بسیار ساده است. شما باید با مفهوم گزاره ها آشنا باشید، سپس با دانستن اینکه در شرط If در هر زبان برنامه نویسی ای تنها شروط درست اجرا می شوند، ساخت این الگوریتم بسیار آسان می شود. به کد زیر نگاه کنید:

void main()
{
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";
}
سپس تابعی به نام YA می نویسیم و شروط آن را نیز داخلش پیاده می کنیم:
void YA(int p, int q)
{
 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";
}
تنها جای 0 و 1 را در دستورات if و else جابجا کنید و بدین گونه تابع شرط دو طرفی (اگر و فقط اگر)  بدست آید.

حالا این توابع را در تابع 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;
}

این هم از راهنمایی من برای نوشتن الگوریتم ها، من اجازه پاسخ صریح الگوریتم ها را نداشتم و به همین راهنمایی برای شما، بسنده نموده ام.
امیدوارم که هر "دانشجو" ای موفق باشد.

آرشیو

برچسب ها

گروه مهندسی IT نئوهوش

بلاگ ویژه مهندسی آی تی و کامپیوتر

صفحه نخست

مدیر سایت

دانوش

نوشته های مدیر

آرشیو مطالب

لیست کامل مطالب سایت

آرشیو

با ما در تماس باشید

NeoHoosh.official@gmail.com

تماس با ما

کلیه حقوق این سایت محفوظ است.

طراح قالب: ـنقاشـ ، ویرایش: دانوش پیچگاه

درآمد بیت کوین از روش آگهی Earn free bitcoin - دریافت رایگان بیت کوین

آمار سایت

  • بازدید کل:
  • بازدید امروز:
  • بازدید دیروز:
  • بازدید ماه قبل:
  • بازدید این ماه:
  • آخرین بازدید:
  • بروزرسانی:
  • تعداد مطالب:
  • نویسندگان:

سایر امکانات

  • نظرسنجی

    برای شرکت در نظرسنجی سایت اینجا را کلیک کنید

    image
    شما چه فردی هستید؟







درود!
این جا مکانی است ویژه برای دانشجویان مهندسی کامپیوتر / آی تی و نرم افزار و صد البته افرادی که جویندگان دانش و تکنولوژی هستند.
آقایان دانوش ،یاشار و آمالی دارندگان این بلاگ بودند و هم اکنون تنها آقای دانوش مدیریت این وبلاگ را بر عهده دارد، با توجه به زمان بندی ها هم اکنون در این سایت فعالیت پویا ای نداریم.

موضوعات

نویسندگان

آخرین عناوین

با ما در ارتباط باشید و ما را از نظرات ارزشمند خود مطلع کنید

  • مدیر سایت: دانوش
  • NeoHoosh.official@gmail.com
  • http://danoush.mihanblog.com
  • شعار سایت: بلاگ ویژه مهندسی آی تی و کامپیوتر
  • فرم تماس با ما