بستن پنجره
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
بستن پنجره
حمایت از وب‌گاه:
برای حمایت از وب‌گاه در گوگل روی 1+ کلیک کنید.
19211.00 4.38 5.00
وبگاه آموزشی برنامه‌نویسی، طراحی الگوریتم و آمادگی مسابقات برنامه‌نویسی الگوریتمستان الگوریتمستان الگوریتمستان FB Twitter Google
»  مسأله‌ی انتخابات
بررسی مسأله‌ی انتخابات، از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2016 سایت تهران

مسأله

    جناب خان که با کسب و کار لبوی خود میلیاردر شده است، می‌خواهد رئیس جمهور شود! در کشور او که از چندین ایالت تشکیل شده است، از روشی با عنوان هیئت انتخاب (یا هیئت الکترال) برای انتخاب رئیس جمهور استفاده می‌شود. در چنین ساختاری شمارش رأی در هر ایالت به صورت مستقل انجام می‌شود و هر ایالت متناسب با جمعیت خود تعدادی نماینده در هیئت انتخاب کنندگان رئیس جمهور دارد. تمام نمایندگان یک ایالت در نهایت به نامزدی رأی می‌دهند که در آن ایالت اکثریت آرا را کسب کرده باشد. اگر نامزدها رأی برابر داشته باشند، هر ایالت قوانین خاص خود برای انتخاب نهایی را دارد. در نهایت رئیس جمهور کسی است که بیش از نصف مجموع رأی‌های هیئت انتخاب را از آن خود کند.

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

ادامه ...
»  مسأله‌ی اعداد اردوش
بررسی مسأله‌ی اعداد اردوش (Erdos Numbers) یا فاصله‌ی همکاری اردوش از سوالات آمادگی مسابقات برنامه‌نویسی

مسأله

    پل اردوش (اردیش - Paul Erdős) ریاضیدان مشهور و برجسته‌ی قرن بیستم است که تا پایان عمر خود تلاش گسترده‌ای برای انتشار مقالات علمی داشت و همکاری با وی در انتشار مقاله یک افتخار بزرگ برای هر ریاضیدان محسوب می‌گردد.

    با توجه به آنکه همکاری با ایشان برای هر کس ممکن نبود، تلاش می‌کردند با نفراتی در انتشار مقاله‌ی علمی همکاری کنند که با این دانشمند بزرگ مقاله داشتند. این رویکرد باعث پدید آمدن عدد اردوش (Erdős number) یا فاصله‌ی همکاری اردوش شد؛ یعنی برای نویسندگانی که به صورت مستقیم با ایشان همکاری داشتند عدد 1 و برای کسانی که با این نفرات مقاله داشتند عدد 2 نسبت داده شد و ارتباطات دورتر نیز به همین ترتیب با اعداد طبیعی بعدی مشخص شدند.

ادامه ...
»  ظرف‌ها در ++C
معرفی انواع ظرف‌ها (نگهدارنده‌ها - containers) در زبان برنامه‌نویسی ++C

منظور از ظرف یا نگهدارنده (Container) ساختمان داده‌ای‌ست که دسته‌ای از اطلاعات را در خود نگه می‌دارد. آنچه که این ساختمان‌ها را از هم متمایز می‌کند، نوع تخصیص حافظه، نوع دسترسی و کارایی درج و حذف عنصر در آنها است که به برخی از آنها کاربری‌های ویژه می‌دهد.

    در ادامه با انواع این نوع ساختمان داده‌ها در زبان برنامه‌نویسی ++C نسخه‌ی C++11 آشنا می‌شویم. با توجه به گسترده بودن این بحث، جزئیات بیشتر هر کلاس را در «پیوندها برای مطالعه‌ی بیشتر» بخوانید.

    توجه: تمامی کلاس‌های بحث شده در کتابخانه‌ی قالب استاندارد (STL) تعریف شده و در فضای نام std قرار دارند.

  

ادامه ...
»  مسأله‌ی کاشیکاری
        بحث در مورد مسأله‌ی کاشیکاری یا فرش کردن زمین با موزاییک به روش تقسیم و حل

یکی از مسائل جالب طراحی الگوریتم مسأله‌ی کاشیکاری یا فرش کردن زمین با موزاییک‌ است.

    فرض کنید قطعه زمین مربعی شکل با ابعادی از توان عدد دو داریم. مثلا با ابعاد 16 متر:

      

مسأله‌ی کاشیکاری

      

    هدف فرش کردن این قطعه زمین با استفاده از موزاییک‌هایی با شکل‌های زیر است:

      

مسأله‌ی کاشیکاری

ادامه ...
»  الگوریتم جستجوی اول سطح (BFS)
        معرفی الگوریتم جستجوی اول سطح (BFS) برای پیمایش گراف و کاربردهای آن به همراه قطعه کد به زبان برنامه‌نویسی ++C

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

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

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

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

    3- گره‌های مجاور گره جاری که پردازش نشده و در صف پردازش نیز قرار ندارند به این صف اضافه کن.

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

ادامه ...
»  الگوریتم دایکسترا
        آشنایی با الگوریتم دایکسترا برای یافتن کوتاهترین مسیر تک‌مبدأ در گراف وزن‌دار بدون یال منفی با قطعه کد به زبان ++C

الگوریتم دایکسترا (دیکسترا، دایجسترا - Dijkstra) یک راهکار حریصانه برای یافتن کوتاهترین مسیر از مقصد ثابت (تک منبع) به سایر گره‌های گراف وزن‌دار است. این گراف می‌تواند معرف مسیرهای یک شهر و تقاطع‌های آن باشد که انبار شرکت در یک گره آن قرار داشته و هدف یافتن کوتاهترین مسیر به هر محل دیگر از این انبار است. طبیعتا این الگوریتم در یافتن کوتاهترین مسیر بین دو گره مشخص نیز کاربرد دارد. تنها شرط لازم برای استفاده از این الگوریتم نامنفی بودن وزن یال‌های گراف است.

    الگوریتم دایکسترا به صورت حریصانه عمل کرده و در تکرارهای متوالی طول کوتاهترین مسیر از مبدأ به یکی از گره‌های گراف را به دست می‌آورد. در این الگوریتم از سه مجموعه استفاده می‌شود:

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

دترمینان ماتریس مربعی - که به صورت $ \vert A \vert $ یا $ det( A ) $ نمایش داده می‌شود - یکی از مفاهیم مشهور جبر خطی است که کاربردهای بسیاری در علوم مختلف دارد. امکان محاسبه‌ی سریع دترمینان یک ماتریس با ابعاد بزرگ بحث مهمی است که در ادامه سه روش محاسباتی رایج و پیچیده‌گی زمانی آنها مرور خواهند شد.

    طبق تعریف دترمینان اگر اندازه‌ی ابعاد ماتریس مربعی یک باشد ($n = 1$)، دترمینان همان مقدار تک‌عضو آن است. یعنی:

      

\[ det( \begin{bmatrix} a \end{bmatrix} ) = \vert \begin{bmatrix} a \end{bmatrix} \vert = a \]

      

    اما اگر مرتبه‌ی ماتریس بزرگتر از یک باشد ($n > 1$) دترمینان را به یکی از روش‌های زیر می‌توان محاسبه کرد.

ادامه ...