قضیه مستر و برخی از توابع بازگشتی که باید با استفاده از درخت حل شوند.

#طراحی_الگوریتم

📣👨‍💻 @AlgorithmDesign_DataStructuer

برنامه‌نویسی پویا چه ویژگی‌های شاخصی دارد؟


یک مسئله باید دارای دو مشخصه کلیدی باشد تا بتوان برنامه‌نویسی پویا را برای آن استفاده کرد. اول آن‌که زیرساختار بهینه و دوم زیرمسئله‌های هم‌پوشان داشته باشد. به حل یک مسئله با ترکیب جواب‌های بهینه زیرمسئله‌های ناهم‌پوشان، «تقسیم و حل» گفته‌ می‌شود. به همین علت است که مرتب‌سازی ادغامی و سریع به عنوان مسائل برنامه‌نویسی پویا شناخته‌نمی‌شوند. نکته مهمی که در ارتباط با برنامه‌نویسی پویا وجود دارد، اصل بهینگی است. اگر بنا باشد پرانتزبندی کل عبارت بهینه شود، پرانتزبندی زیرمسئله‌ها هم باید بهینه باشند. یعنی بهینه بودن مسئله، بهینه بودن زیرمسئله‌ها را ایجاب می‌کند. پس می‌توان از روش برنامه‌نویسی پویا استفاده کرد. حل بهینه، سومین مرحله از بسط یک الگوریتم برنامه‌نویسی پویا برای مسائل بهینه‌سازی است. مراحل بسط چنین الگوریتمی به سه بخش تقسیم می‌شوند. اول ارائه یک ویژگی بازگشتی که حل بهینه نمونه‌ای از مسئله را به دست می‌دهد، دوم محاسبه مقدار حل بهینه به شیوه جزء به کل و سوم بنا کردن یک حل نمونه به شیوه جزء به کل.

تمام مسائل بهینه‌سازی را نمی‌توان با برنامه‌نویسی پویا حل کرد چرا که باید اصل بهینگی در مسئله صدق کند. اصل بهینگی در یک مسئله صدق می‌کند اگر یک حل بهینه برای نمونه ای از مسئله، همواره حاوی حل بهینه برای همه زیر نمونه‌ها باشد.


📣👨‍💻 @AlgorithmDesign_DataStructuer

یکی از کاربردهای پشته در کامپیوتر عبارت های حسابی می باشد که در زیر میتونیم با نمادگذاری infix و postfix آشنا شویم.


نماد گذاری infix (میانوندی):
عبارات Infix توسط انسان قابل خواندن و حل هستند. ما به راحتی می‌توانیم ترتیب عملگرها را تشخیص دهیم و همچنین می‌توانیم از پرانتز برای حل آن قسمت ابتدا در حین حل عبارات ریاضی استفاده کنیم. کامپیوتر نمی تواند عملگرها و پرانتزها را به راحتی متمایز کند، به همین دلیل تبدیل postfix مورد نیاز است.

برای تبدیل عبارت infix به عبارت postfix، از ساختار داده پشته استفاده می کنیم. با اسکن عبارت infix از چپ به راست، زمانی که هر عملوندی را دریافت می کنیم، به سادگی آنها را به فرم پسوند اضافه می کنیم و برای عملگر و پرانتز، آنها را با حفظ اولویت آنها در پشته اضافه می کنیم.

infix:A*B(C+D)
posfix:AB*CD+

📣👨‍💻 @AlgorithmDesign_DataStructuer

آرایه:
در واقعا ما آرایه ها را بای ذخیر سازی دیتا استفاده میکنیم که به بعدی های مختلفی میتوانیم ان را تقسیم کنیم که برای ذخیره کردن دیتا هم باید از حلقه استفاده کنیم تا بتوانیم به اندیس های آرایه دسترسی داشته باشیم و میتونیم دیتا ها رو در آن ها ذخیر کنیم و از آن ها استفاده کنیم. آرایه از سطر(افقی) و ستون(عمودی)تشکیل می شود.

📣👨‍💻 @AlgorithmDesign_DataStructuer

محاسبه الگوریتم بازگشتی محاسبه ترکیب mاز n:

📣👨‍💻 @AlgorithmDesign_DataStructuer

اگر n=10 حاصل الگوریتم بازگشتی چه مقداری را برمیگرداند؟

پاسخ تشریحی

جزوه بسیار خوب در مورد صف همراه با کد به زبان سی پلاس پلاس

📣👨‍💻 @AlgorithmDesign_DataStructuer

یکی از روش های نمایش گراف ماتریس مجاورت می باشد.

📣👨‍💻 @AlgorithmDesign_DataStructuer

انواع متغییر هایی که در زبان برنامه نویسی استفاده میشه شامل سایز و بازه ایی هستند که ما باید در برنامه ها به آن ها توجه کنیم که از چه نوع متغیری استفاده کنیم که هزینه کمتری داشته باشد(حافظه کمتر).

📣👨‍💻 @AlgorithmDesign_DataStructuer

هرم-بیشترین(max-heap):
یک درخت باینری کامل است که در آن مقدار هر گره داخلی بزرگتر یا مساوی با مقادیر فرزندان آن گره است. نگاشت عناصر یک پشته در یک آرایه بی اهمیت است: اگر یک گره با اندیس k ذخیره شود، فرزند سمت چپ آن در شاخص 2k + 1 و فرزند سمت راست آن در شاخص 2k + 2 ذخیره می شود.

📣👨‍💻 @AlgorithmDesign_DataStructuer

چند تعریف و نکته در مورد گراف

در یک گراف , یک مجوعه از راس ها و یک مجوعه از یال ها داریم که میتوان گفت هر یال 2 راس را به هم متصل می کند.
گراف ساده:
گراف بدون جهت می باشد.
کوتاه ترین مسیر بین دو راس:
این به این معنی می باشد که مجوعه وزن های مورد استفاده بایستی به حداقل مسیر برسانیم.
گراف وزن دار:
هر یال داری وزنی می باشد.
گراف جهت دار:
هر یال علاوه بر وزن جهت نیز دارد که این به معنی می باشد که مشخص می کند که از چه راسی به چه راسی میتوان حرکت کرد.
توجه:
به این نکته دقت کنید که گراف یک درخت نمی باشد زیرا در آن دور(حلقه) وجود ندارد ولی اگر دقت کرده باشید در گراف ها نیز دور وجود دارید.

📣👨‍💻 @AlgorithmDesign_DataStructuer

سورس کد مرتب کردن اعداد با استفاده از پشته

📣👨‍💻 @AlgorithmDesign_DataStructuer