دنباله‌ی اعداد فیبوناچی

[برو به فهرست نوشته‌ها]
        بررسی الگوریتم‌های محاسبه‌ی دنباله‌ی اعداد فیبوناچی و کارایی آنها

بسیاری از فرآیندهای طبیعی از جمله ترکیب ساختار بدن موجودات زنده نظم مشخصی دارند و از دنباله‌ی اعدادی تبعیت می‌کنند که امروزه با نام دنباله‌ی اعداد فیبوناچی (فیبوناتچی - Fibonacci) شناخته می‌شود. مشهورترین خاصیت این اعداد نسبت دو جمله‌ی متوالی آنها به ازای جملات بزرگ دنباله است که به عدد طلایی مشهور است.

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

    تعریف: دنباله‌ی اعداد فیبوناچی روی اعداد حسابی به صورت زیر تعریف می‌شود:

\[ F_n= \left \{\begin{matrix} F_{n-1} + F_{n-2} & & & \; n > 1\\ 1 & & & \; n = 1 \\ 0 & & & n = 0 \end{matrix}\right. \]

ادامه ...

مرتب‌سازی ادغامی

[برو به فهرست نوشته‌ها]
        آشنایی با روش مرتب‌سازی ادغامی با قطعه کدهایی به زبان برنامه‌نویسی ++C

روش مرتب‌سازی ادغامی (Merge Sort) یک روش مرتب‌سازی مبتنی بر مقایسه‌ی عناصر با استفاده از روش تقسیم و غلبه است. این روش از مراحل بازگشتی زیر تشکیل یافته است:

    1- آرایه را به دو زیرآرایه با اندازه‌ی تقریبا یکسان تقسیم کن.

    2- دو زیرآرایه را به روش مرتب‌سازی ادغامی مرتب کن.

    3- دو زیرآرایه‌ی مرتب‌شده را ادغام کن.

      

مرتب‌سازی ادغامی

ادامه ...

مرتب‌سازی سریع

[برو به فهرست نوشته‌ها]
        آشنایی با روش مرتب‌سازی سریع، همراه با قطعه کدهای نمونه به زبان برنامه‌نویسی ++C

روش مرتب‌سازی سریع (Quick Sort) یکی از الگوریتم‌های مشهور مرتب‌سازی داده‌ها است. این الگوریتم طی مراحل بازگشتی زیر یک روش تقسیم و غلبه برای مرتب کردن داده‌ها ارائه می‌نماید:

    1- انتخاب عنصر محوری: یکی از عناصر آرایه به عنوان عنصر محوری (pivot) - به عنوان مثال عنصر اول - انتخاب می‌شود.

    2- تقسیم آرایه: چینش عناصر آرایه به قسمی تغییر داده می‌شود که تمامی عناصر کوچکتر یا مساوی محور در سمت چپ آن و تمامی عناصر بزرگتر در سمت راست آن قرار بگیرند. این دو قسمت زیر آرایه‌های چپ و راست نامیده می‌شوند.

    3- مرتب‌سازی بازگشتی: زیرآرایه‌های چپ و راست به روش مرتب‌سازی سریع مرتب می‌شوند.

ادامه ...

دنباله‌ی اعداد کاتالان و محاسبه‌ی آن

[برو به فهرست نوشته‌ها]
        آشنایی با دنباله‌ی عددی کاتالان، کاربردها و روش پیاده‌سازی آن به زبان برنامه‌نویسی ++C

دنباله‌ی اعداد کاتالان (Catalan Numbers) یکی از دنباله‌های عددی مشهور ریاضیات است که برای عدد نامنفی n به صورت $C_n$ نمایش داده می‌شود.

  

$C_n:\qquad 1,\;1,\;2,\;5,\;14,\;42,\;132,\;429,\;1430,\;4862,\;16796,\;\cdots$

  

    این دنباله کاربردهای بسیاری در مسائل شمارشی دارد. از جمله:

    1- تعداد درخت‌های دودویی با n رأس داخلی برابر $C_n$ است:

      

اعداد کاتالان و درخت دودویی

ادامه ...

محاسبه‌ی ضرایب دوجمله‌ای

[برو به فهرست نوشته‌ها]
        بررسی روش‌های مختلف محاسبه‌ی ضرایب دوجمله‌ای نیوتن یا ترکیب دو عدد با قطعه کد به زبان برنامه‌نویسی ++C

تعریف ترکیب (Combination)

    تعداد حالت‌های انتخاب r (عدد صحیح و نامنفی) شیء از n (عدد صحیح و بزرگتر یا مساوی r) شیء را که ترتیب انتخاب اهمیت نداشته باشد، انتخاب r از n یا ترکیب r روی n گویند و به یکی از صورت‌های زیر نمایش می‌دهند:

      

\[C(n,r) = C_r^n= \begin{pmatrix} n \\ r \end{pmatrix} \]

    این عدد به ضریب دوجمله‌ای نیز مشهور است که یکی از محل‌های استفاده‌ی آن است.

    بر اساس اصل ضرب از اصول شمارش، ترکیب دو عدد از رابطه‌ی زیر قابل محاسبه است:

      

\[\begin{pmatrix} n \\ r \end{pmatrix} = \frac{n!}{(n-r)!\cdot r!} \]

ادامه ...

محاسبه‌ی دترمینان ماتریس

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

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

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

ادامه ...

برج هانوی

[برو به فهرست نوشته‌ها]
        بررسی مسئله‌ی برج هانوی و روش‌های حل بازگشتی و غیربازگشتی آن به همراه کد به زبان ++C

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

    مسئله‌ی برج هانوی (Tower of Hanoi) یکی از مسائل تاریخی مشهور است که در مباحث طراحی الگوریتم نیز به آن پرداخته می‌شود.

    به شکل زیر توجه کنید:

      

برج هانوی

      

ادامه ...

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

[برو به فهرست نوشته‌ها]
        بحث در مورد مسئله‌ی کاشیکاری یا فرش کردن زمین با موزاییک به روش تقسیم و حل

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

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

      

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

      

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

      

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

ادامه ...

درخت جستجوی دودویی

[برو به فهرست نوشته‌ها]
        آشنایی با درخت جستجوی دودویی (Binary Search Tree) و عملیات جستجو و درج و حذف گره

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

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

      

    

درخت دودویی

      

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

ادامه ...

ضرب استراسن

[برو به فهرست نوشته‌ها]
        آشنایی با الگوریتم استراسن برای محاسبه‌‌ی حاصلضرب ماتریس‌ها

همه‌ی ما با تعریف ضرب ماتریس‌های مربعی آشنایی داریم. حاصلضرب ماتریس‌های مربعی A و B به صورت زیر تعریف می‌شود:

      

\[ A=(a_{ij})_{n \times n} = \qquad , \qquad B=(b_{ij})_{n \times n} \] \[ C = A \times B = (c_{ij})_{n \times n} \qquad ; \qquad c_{ij}= \sum_{k=1}^{n} a_{ik} \; b{kj} \]

      

    به عنوان مثال در حالت $n = 2$ داریم:

      

\[ \begin{pmatrix} a_{11} & a_{12}\\ a_{21} & a_{22} \end{pmatrix} \times \begin{pmatrix} b_{11} & b_{12}\\ b_{21} & b_{22} \end{pmatrix} = \begin{pmatrix} a_{11}b_{11}+a_{12}b_{21} & a_{11}b_{12}+a_{12}b_{22}\\ a_{21}b_{11}+a_{22}b_{21} & a_{21}b_{12}+a_{22}b_{22} \end{pmatrix} \]

ادامه ...