الگوریتمستان

برنامه‌نویسی، طراحی الگوریتم و حل مسئله‌های الگوریتمی

 
در صورت ناخوانا بودن نوشته‌ها، از مرورگر دیگری استفاده کنید.
نوشته‌ها با برچسب درخت‌ها نوشته‌ها با برچسب درخت‌ها - الگوریتمستان الگوریتمستان الگوریتمستان
نوشته‌ها با برچسب «

درخت‌ها

»

الگوریتم پیمایش اول سطح یا جستجوی اول سطح (Breadth First Search - BFS) از جمله الگوریتم‌های مشهور پیمایش و جستجوی گراف است که در حل مسائل الگوریتمی و هوش مصنوعی کاربرد دارد. این الگوریتم برای پیمایش و جستجوی گراف از یک صف برای نگهداری ترتیب جستجو استفاده می‌کند.

الگوریتم BFS با وارد کردن گره مبدأ به صف پردازش شروع شده و تا خالی نشدن این صف مراحل زیر را تکرار می‌شود:

1- عنصر جلوی صف را به عنوان گره جاری انتخاب و از صف حذف کن.

2- گره جاری را پردازش کن.

ادامه ...

مرتب‌سازی هرمی (Heap Sort) یکی از روش‌های مشهور مرتب‌سازی داده‌ها است که بر اساس خصوصیات درخت heap (هیپ، هرم یا کپه)  و عملکرد آن پیاده‌سازی شده است.

بر اساس تعریف درخت heap، در یک max-heap (یا min-heap) بزرگترین (یا کوچکترین) مقدار بین داده‌ها همواره در ریشه‌ی درخت قرار دارد. یافتن بزرگترین (یا کوچکترین) عنصر بین عناصر، هزینه‌ی ثابت ( Ө( 1 دارد. با حذف این عنصر از درخت، بزرگترین (یا کوچکترین) عنصر بعدی مجددا در ریشه قرار می‌گیرد. به این ترتیب با حذف متوالی عناصر درخت heap و درج آنها در محل جدید، یک آرایه‌ی مرتب‌شده‌ی نزولی (یا صعودی) به دست خواهد آمد.

ادامه ...

درخت دودویی (Binary Tree)

درختی است که هر گره آن دارای حداکثر دو گره فرزند است که به آنها فرزند راست و چپ گره گفته می‌شود. به همین ترتیب زیردرختی که فرزند راست در رأس آن قرار دارد زیردرخت راست و زیردرختی که فرزند چپ در رأس آن قرار دارد زیردرخت چپ گره نامیده می‌شوند.

  

درخت دودویی

  

درخت جستجوی دودویی (Binary Search Tree - BST)

درختی دودویی است که برای هر گره آن شروط زیر برقرار هستند:

ادامه ...

صف اولویت‌دار (یا صف اولویتی - Priority Queue) از جمله ساختمان داده‌های بسیار پرکاربرد است. در صف عادی از تکنیک FIFO - مخفف First In First Out - استفاده می‌شود. در این تکنیک، مثل یک صف نانوایی، داده‌ها به ترتیب ورود پشت سر هم در صف قرار می‌گیرند. بنابراین اولین داده‌ی ورودی، اولین داده‌ی خروجی نیز خواهد بود. اما در صف اولویت‌دار برای هر داده، اولویتی - نه لزوما منحصربفرد - مشخص می‌شود. صف اولویت را می‌توان به اورژانس یک بیمارستان تشبیه کرد که هر بیمار با شدت بیماری بیشتر اولویت بیشتری برای رسیدگی دارد. سیستم عامل کامپیوتر هم برای مدیریت پردازش‌ها از صف‌های اولویت‌دار استفاده می‌کند.

ادامه ...

درخت دودویی کامل

یک درخت دودویی کامل است، هرگاه تمامی سطوح درخت به غیر از احتمالا آخرین سطح پر بوده و برگ‌های سطح آخر از سمت چپ قرار گرفته باشند.

  

به یک مثال دقت کنید:

  

درخت هیپ یا هرم یا کپه

  

همانطور که مشاهده می‌کنید، تمامی سطوح درخت به غیر از آخرین سطح به طور کامل پر و همه‌ی برگ‌های سطح آخر نیز در سمت چپ درخت هستند. در واقع تمامی برگ‌های درخت دودویی کامل در دو سطح آخر آن قرار دارند.

ادامه ...

الگوریتمستان در تلگرام

   

 

پیوند کوتاه:
برچسب‌ها
#دانلود کتاب #مسابقات برنامه‌نویسی ACM #مسابقه برنامه نویسی #مسئله‌ی کوله‌پشتی #جستجوی اول سطح #الگوریتم‌های برنامه‌نویسی پویا #آموزش برنامه‌نویسی ++C #مسأله‌های برنامه‌نویسی #نمونه سوال مسابقه ACM #مسابقه برنامه‌نویسی #پیمایش گراف #آموزش طراحی الگوریتم #تمرین مسابقه برنامه‌نویسی #کتاب مسابقات برنامه‌نویسی #برنامه‌نویسی #نمونه سوال فارسی مسابقات برنامه‌نویسی #الگوریتم‌های تقسیم و غلبه #آمادگی مسابقه ACM #تمرین المپیاد کامپیوتر #ترجمه‌ی فارسی سوالات ACM #برنامه‌نویسی ++C #درخت پوشا #تمرین طراحی الگوریتم #کتابخانه قالب استاندارد ++C #سوالات مسابقات برنامه‌نویسی بیان #ترجمه‌ی فارسی سوالات برنامه‌نویسی #ماتریس #ساختمان داده #درخت‌ها #گراف #نمونه سوال فارسی مسابقه‌ی ACM #الگوریتم‌های مسیریابی #مسئله‌های الگوریتمی #ویدئوی آموزشی #حل سوالات ACM-ICPC #نمونه سوال فارسی مسابقات ACM #الگوریتم‌های بازگشتی #مسابقات برنامه‌نویسی #الگوریتم‌های حریصانه #کتاب الکترونیکی #الگوریتم‌های کوتاهترین مسیر #الگوریتم‌های گراف #حل سوالات Timus Online Judge #منبع آموزشی #معرفی وب‌سایت #کتاب الگوریتم #الگوریتم‌های مرتب‌سازی #سوالات مسابقات ACM-ICPC #آمادگی مسابقه برنامه‌نویسی #سوالات UVa Online Judge #جستجوی اول عمق #آمادگی المپیاد کامپیوتر #الگوریتم #صف #الگوریتم فلوید-وارشال #آموزش ساختمان داده‌ها #نمونه سوالات مسابقه برنامه‌نویسی #Python #ترجمه‌ی فارسی سوالات UVa Online Judge #سوالات برنامه‌نویسی #وبلاگ #حل سوالات UVa Online Judge #تمرین مسابقه‌ی برنامه‌نویسی ای‌سی‌ام #حل سوالات مسابقات برنامه‌نویسی #تکنیک‌های طراحی الگوریتم #ترجمه فارسی سوالات کتاب Programming Challenges #الگوریتم‌های عقبگرد #آموزش الگوریتم #حل مسئله‌‌ی الگوریتمی #سوالات چالشی برنامه‌نویسی #محاسبات ریاضی #نکات برنامه‌نویسی #مسأله‌های الگوریتمی #الگوریتم دایکسترا #مسئله‌های برنامه‌نویسی