الگوریتم و برنامه محاسبه بزرگترین مقسوم علیه مشترک

سلام

یکی از پرکاربردترین مفاهیم ریاضی، که در بسیاری از برنامه های کامپیوتری هم مورد استفاده دارد، "بزرگ‌ترین مقسوم‌علیه مشترک" هست که با نام اختصاری "ب.م.م" نیز شناخته شده است. به احتمال زیاد در منابع خارجی با عبارت Greatest Common Divisor یا GCD مواجه شده باشید. البته الگوریتم‌های زیادی (با پیچیدگی های مختلف) برای محاسبه ب.م.م ارائه شده است؛ اما یکی از راه هایی که بسیاری از ما در دوران مدرسه از آن استفاده کرده ایم، روش تقسیم متوالی، یا روش نردبانی هست.

امروز با الگوریتم محاسبه بزرگترین مقسوم علیه مشترک دو عدد و همچنین برنامه آن در زبان برنامه نویسی #C در خدمت شما هستم.

به تصویر زیر دقت کنید:

در این شکل روش محاسبه ب.م.م دو عدد 12 و 20، نشان داده شده است. 

مقایسه تصویری انواع الگوریتم های مرتب‌سازی

مقدمه

به نظرم اولین و مهمترین چیزی که باید بفهمیم اینه که اصلا الگوریتم های مرتب سازی چه هستند. بر اساس ویکی‌پدیا، الگوریتم مرتب سازی، الگوریتمی است که عناصر یک لیست را به ترتیب خاصی در می‌آورد. کاربردی‌ترین ترتیب ها، ترتیب‌های عددی و ترتیب‌های وابسه به حروف هستند. بعضی از الگوریتم‌ها (از جمله الگوریتم‌های جستجو و ادغام) برای اینکه بدرستی کار کنند، نیازمند لیست‌های مرتب شده می باشند؛ مرتب‌سازی مؤثر و کارآمد، برای بهینه سازی کارائی چنین الگوریتم‌هایی، مهم هستند. این اگوریتم‌ها، اغلب اوقات، برای به نظم در آوردن داده‌ها و تولید خروجی قابل خواندن برای انسان، مفید هستند.

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

الگوریتم‌هایی که در این مقاله با آنها آشنا خواهید شد:

• مرتب سازی حبابی دوطرفه (Bidirectional Bubble Sort)
• مرتب سازی حبابی (Bubble Sort)
• مرتب سازی سطلی (Bucket Sort)
• مرتب سازی شانه ای (Comb Sort)
• مرتب سازی چرخه‌ای (Cycle Sort)
• مرتب سازی گورزاد (Gnome Sort)
• مرتب سازی هرمی (Heap Sort)
• مرتب سازی درجی (Insertion Sort)
• مرتب سازی ادغامی (Merge Sort)
• مرتب سازی زوج-فرد (Odd-Even Sort)
• مرتب سازی لانه کبوتری (Pigeonhole Sort)
• مرتب سازی سریع (Quick Sort)
• مرتب سازی سریع با استفاده از مرتب سازی حبابی (Quick Sort with Bubble Sort)
• مرتب سازی انتخابی (Selection Sort)
• مرتب سازی شل یا پوسته ای (Shell Sort)

قصد دارم طرز کار این الگوریتم ها رو بصورت دیداری به شما نشان بدهم. کاربر می تواند، خروجی این پروژه را بصورت تصاویر متحرک GIF، با سرعت دلخواه، ذخیره کند.

چطور: پیاده سازی رویدادهای رابط

رابط (interface) می تواند یک رویداد را اعلان کند. مثال زیر چگونگی پیاده سازی رویدادهای رابطی را در یک کلاس نشان می دهد. بطور مقدماتی قواعد و قوانین کار مانند پیاده سازی متد ها یا پراپرتی های رابطی می باشد.
برای پیاده سازی رویدادهای رابطی در یک کلاس

• رویداد را در کلاستان اعلان کرده، سپس آنرا در مکان دلخواه فراخوانی کنید.
  

  namespace ImplementInterfaceEvents
  {
      public interface IDrawingObject
      {
          event EventHandler ShapeChanged;
      }
      public class MyEventArgs : EventArgs 
      {
          // class members
      }
      public class Shape : IDrawingObject
      {
          public event EventHandler ShapeChanged;
          void ChangeShape()
          {
              // Do something here before the event…
  
              OnShapeChanged(new MyEventArgs(/*arguments*/));
  
              // or do something here after the event. 
          }
          protected virtual void OnShapeChanged(MyEventArgs e)
          {
              if(ShapeChanged != null)
              {
                 ShapeChanged(this, e);
              }
          }
      }
  
  }

مثال
مثال زیر نشان می دهد که چگونه موقعیتی تقریبا" غیر عادی را که در آن کلاس شما از دو رابط یا بیشتر ارث بری می کند و درعین حال هر رابط دارای یک رویداد با نام مشابه است را مدیریت کنید. در این موقعیت، شما باید حداقل برای یکی از رویدادها، بصورت صریح پیاده سازی رابط را فراهم کنید. وقتی شما برای یک رویداد، پیاده سازی صریح رابط می نویسید، همچنین باید دستیابی کننده های رویداد add و remove را بنویسید. در حالت عادی اینها توسط کامپایلر فراهم می شوند، اما در این مورد کامپایلر نمی تواند آنها را فراهم کند.