وبلاگ رسمی مهدی غلامی میاندهی

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

سوال : اگn ورودی از یک stack داشته باشیم تعداد حالات خروجی مجاز با چه فرمولی محاسبه میشود؟
سلام ...ممنون میشم اگه جوابو زود واسم ایمیل کنید

پاسخ : اگر منظور شما این است که یک Stack با N ورودی متمایز باشد و بخواهیم تعداد ترتیب‌های خروجی مجاز را حساب کنیم، پاسخ با اعداد کاتالان (Catalan) داده می‌شود :

یا به شکل دیگر :

◄مثال : اگر ۳ ورودی داشته باشیم:

پس برای ورودی :

3 2 1

۵ خروجی مجاز داریم :

1 2 3

1 3 2

2 1 3

2 3 1

3 2 1

ولی مثلاً :

3 1 2

با یک Stack قابل تولید نیست.

بنابراین اگر سؤال شما دقیقاً درباره‌ی تعداد جایگشت‌های قابل تولید توسط یک Stack باشد، فرمول اصلی همان عدد کاتالان است :

حالا برسیم به قسمت برنامه نویسی، اگر n ورودی متمایز وارد یک Stack شوند و فقط عملیات‌های استاندارد push و pop داشته باشیم، تعداد ترتیب‌های خروجی مجاز برابر با عدد کاتالان است :

#include
using namespace std;

long long catalan(int n)
{
long long result = 1;

for (int i = 0; i < n; i++)
{
result = result * (2 * n - i) / (i + 1);
}

return result / (n + 1);
}

int main()
{
int n;
cout << "\nInsert Number: ";
cin >> n;

cout << "Number of valid Outputs: "<< catalan(n) << endl;

cout < system("pause");
return 0;
}

مثلاً :

Input: 5

Output: 42

چون :

اگر فقط کد خیلی ساده برای محاسبه می‌خواهید، از کد زیر استفاده کنید :

#include
using namespace std;

int main() {

int n;
cin >> n;
long long c = 1;
for (int i = 0; i < n; i++)
c = c * (2 * n - i) / (i + 1);
cout << c / (n + 1);

cout < system("pause");
return 0;

}

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