تالار گفتمان مانشت

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

به نظر من گزینه 1 صحیح است
منظور از دنباله های مجاز هم حالتهایی است که میتوان k عدد رو داخل پشته کرد و از آن خارج کرد.
مثلا برای AB
دو حالت AB و BA وجود دارد که اولی با وارد کردن A به پشته و خارج کردن A از پشته و سپس وارد کردن B به پشته و خارج کردن B از پشته
حالت بعدی وارد کردن A به پشته سپس وارد کردن B به پشته و سپس خارج کردن B و A بدست می آید.

(18 مهر 1390 05:02 ب.ظ)mamat نوشته شده توسط: [ -> ]به نظر من گزینه ۱ صحیح است
منظور از دنباله های مجاز هم حالتهایی است که میتوان k عدد رو داخل پشته کرد و از آن خارج کرد.
مثلا برای AB
دو حالت AB و BA وجود دارد که اولی با وارد کردن A به پشته و خارج کردن A از پشته و سپس وارد کردن B به پشته و خارج کردن B از پشته
حالت بعدی وارد کردن A به پشته سپس وارد کردن B به پشته و سپس خارج کردن B و A بدست می آید.

ممنون از پاسختون ...
اما یه سوال ... آیا حتما باید کلیه‌ی ورودی‌ها رو از پشته خارج کنیم که بگیم دنباله داریم ؟
مثلا اگه سه ورودی a-b-c رو داشته باشیم و فقط 2 تا از اونها رو از پشته خارج کنیم( مثلا b & c )آیا نمیشه به این گفت دنباله ؟

ممنون میشم دوستان دیگه هم نظراتشون رو بیان کنن

مرسی

جواب سوال‌، عدد کاتالان هستش .

که در نتیجه گزینه 1 صحیحه.

همچنین می تونید با مقدار دادن هم به جواب برسید.

---

منظور از تعداد دنباله خروجی یعنی تعداد کل ترتیب های خروجی که می تونیم در پایان (وقتی همه مقادیر از پشته خارج شدند) از مقادیرمان با استفاده از پشته داشته باشیم.
مثلا برای سه مقدار A و B و C جمعا پنج دنباله خروجی مجاز داریم.
یک دنباله رو من می سازم:
push A
Push B
Pop B
Pop A
Push C
Pop C
پس ترتیب دنباله خروجی (Pop ها) در این مثال ما شد‌: BAC

چهار دنباله دیگر هم بصورت زیر هستند:
ABC
CBA
BCA
ACB

(18 مهر 1390 05:38 ب.ظ)PaNriis نوشته شده توسط: [ -> ]آیا حتما باید کلیه‌ی ورودی‌ها رو از پشته خارج کنیم که بگیم دنباله داریم ؟

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