(۰۱ آذر ۱۳۹۳ ۱۰:۵۰ ق.ظ)Aurora نوشته شده توسط:  تعداد درخت های دودویی رو خواسته یا جستجوی دودویی؟




اگر جستجوی دودویی باشه و مورب چب باشه، میشه فقط یک درخت.
۵
۴
۳
۲
۱

(۲۹ آبان ۱۳۹۳ ۰۲:۰۲ ب.ظ)ana9940 نوشته شده توسط:  در کتاب الگوریتم دکتر قدسی، سوال ۹ بخش ۴ اینطور اومده:
چه تعداد درخت دودویی جستجو متفاوت با n گره و برچسب های ۱ تا n دارای ترتیب ها یکسانی در هر دو روش پس ترتیب و میان ترتیب هستند؟
۰
۱
n!
عدد nام کاتالان

در جواب گزینه چهارم گفته شده ولی به نظر من یا غلطه یا سوال رو متوجه نمیشم.
پیمایش پس ترتیب و میان ترتیب در درخت دودویی زمانی برابر است که درخت مورب چپ باشه، میخواهیم LDR و LRD یکسان شوند که باید گره ها فرزند راست نداشته باشند)
با این فرض و به دلیل اینکه N گره داریم ، تعداد این درخت ها برابر با تعداد جایگشت برچسب ها میباشد که میشه در گره ها اونا رو جابجا کرد، یعنی n! ولی جواب عدد کاتالان رو گفته که میشه تمام حالات ایجاد یک د.د.ج با n گره!

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

(۰۲ آذر ۱۳۹۳ ۰۵:۱۵ ب.ظ)Aurora نوشته شده توسط:  میشه بیشتر توضیح بدید؟
چطور میگید هم باید میانوندی و هم پسوندی یکی باشه ولی لزومی نداره!

(۰۲ آذر ۱۳۹۳ ۰۵:۵۸ ب.ظ)Aurora نوشته شده توسط:  خوب
چطوری میشه برای هر جایگشت هم میاوندی و هم پسوندیش یکی باشه؟ فقط در حالت مورب چپ امکان پذیره. حالتش دیگه اش چیه؟ میشه مثال بزنید؟

نقل قول: بنظرم‏ ‏
جواب‏ ‏دکتر‏ ‏درسته‏ ‏منظور‏ ‏چیز‏ ‏دیگه‏ ‏ایه.‏ ‏گفته‏ ‏چندتا‏ ‏ددج‏ ‏وجود‏ ‏داره‏ ‏که‏ ‏‏جایگشتهایی‏ ‏از‏ ‏اعداد‏ ‏۱‏ ‏تا‏ ‏إن‏ ‏رو‏ ‏به‏ ‏ترتیبی‏ ‏به‏ ‏شما‏ ‏میده‏ ‏که‏ ‏میان‏ ‏ترتیب‏ی‏با‏ ‏پس‏ ‏ترتیب‏ ‏مساوی‏ ‏داشته‏ ‏باشه‏ ‏لزومی‏ ‏نداره‏ ‏ددج‏ ‏ای‏ ‏برای‏ ‏پیمایش‏ ‏میان‏ ‏ترتیب‏ ‏استفاده‏ ‏میشه‏ ‏مساوی‏ ‏پیمایش‏ ‏پس‏ ‏ترتیب‏ ‏باشه.‏ ‏‏ ‏‏ ‏

(۰۲ آذر ۱۳۹۳ ۰۶:۱۵ ب.ظ)Ava.arshad94 نوشته شده توسط:  

نقل قول: بنظرم‏ ‏
جواب‏ ‏دکتر‏ ‏درسته‏ ‏منظور‏ ‏چیز‏ ‏دیگه‏ ‏ایه.‏ ‏گفته‏ ‏چندتا‏ ‏ددج‏ ‏وجود‏ ‏داره‏ ‏که‏ ‏‏جایگشتهایی‏ ‏از‏ ‏اعداد‏ ‏۱‏ ‏تا‏ ‏إن‏ ‏رو‏ ‏به‏ ‏ترتیبی‏ ‏به‏ ‏شما‏ ‏میده‏ ‏که‏ ‏میان‏ ‏ترتیب‏ی‏با‏ ‏پس‏ ‏ترتیب‏ ‏مساوی‏ ‏داشته‏ ‏باشه‏ ‏لزومی‏ ‏نداره‏ ‏ددج‏ ‏ای‏ ‏برای‏ ‏پیمایش‏ ‏میان‏ ‏ترتیب‏ ‏استفاده‏ ‏میشه‏ ‏مساوی‏ ‏پیمایش‏ ‏پس‏ ‏ترتیب‏ ‏باشه.‏ ‏‏ ‏‏ ‏

حرف ایشون کاملا درسته
سوال میخواد تمام میان ترتیب ها باهم برابر و تمام پس ترتیب ها باهم برابر باشه، نه اینکه توو هر درخت میان ترتیبش با پس ترتیبش برابر باشه
حرف حساب اصلی هم همینه که توو ددج همیشه میان ترتیب داره صعودی میچینه که قضیه حلله، برای پس ترتیب هم که میایم وقتی درختو ساختیم گره ها رو جوری میچینیم که توو همه درخت ها پس ترتیبا یکی بشن

(۰۲ آذر ۱۳۹۳ ۰۷:۰۷ ب.ظ)Ava.arshad94 نوشته شده توسط:  نشد
اومدم مثال بزنم گیر کردم
همون ١ باید باشه و برداشت aurora ، هرجور به سوال نگاه کنیم فقط اون حالت درسته، تو پاسخ هم تا وسطش درختو جستجو گرفته، در ادامه ش نگرفته
خیلی دلم میخواد اینجور سوالای ٦٠٠ رو جمع کنیم به استاد قدسی ایمیل کنیم

نقل قول: !!!
اگر‏ ‏اعداد‏ ‏۱‏ ‏تا‏ ‏إن‏ ‏باشند‏ ‏که‏ ‏إن‏ ‏فاکتوریل‏ ‏جایگشت‏ ‏داشته‏ ‏باشند‏ ‏از‏ ‏این‏ ‏إن‏ ‏فاکتوریل‏ ‏کاتالانتاشون‏ ‏میان‏ ‏ترتیب‏ ‏دارند‏ ‏و‏ ‏برای‏ ‏اون‏ ‏کاتالانتاییی‏ ‏که‏ ‏میان‏ ‏ترتیب‏ ‏دارن‏ ‏حتما‏ ‏به‏ ‏ازای‏ ‏هر‏ ‏کدومشون‏ ‏پس‏ ‏ترتیبی‏ ‏وجود‏ ‏داره.‏ ‏

(۰۲ آذر ۱۳۹۳ ۰۷:۲۵ ب.ظ)Ava.arshad94 نوشته شده توسط:  

نقل قول: !!!
اگر‏ ‏اعداد‏ ‏۱‏ ‏تا‏ ‏إن‏ ‏باشند‏ ‏که‏ ‏إن‏ ‏فاکتوریل‏ ‏جایگشت‏ ‏داشته‏ ‏باشند‏ ‏از‏ ‏این‏ ‏إن‏ ‏فاکتوریل‏ ‏کاتالانتاشون‏ ‏میان‏ ‏ترتیب‏ ‏دارند‏ ‏و‏ ‏برای‏ ‏اون‏ ‏کاتالانتاییی‏ ‏که‏ ‏میان‏ ‏ترتیب‏ ‏دارن‏ ‏حتما‏ ‏به‏ ‏ازای‏ ‏هر‏ ‏کدومشون‏ ‏پس‏ ‏ترتیبی‏ ‏وجود‏ ‏داره.‏ ‏

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


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

(۰۲ آذر ۱۳۹۳ ۰۸:۰۹ ب.ظ)ahp89 نوشته شده توسط:  

(02 آذر ۱۳۹۳ ۰۷:۲۵ ب.ظ)Ava.arshad94 نوشته شده توسط:  

نقل قول: !!!
اگر‏ ‏اعداد‏ ‏۱‏ ‏تا‏ ‏إن‏ ‏باشند‏ ‏که‏ ‏إن‏ ‏فاکتوریل‏ ‏جایگشت‏ ‏داشته‏ ‏باشند‏ ‏از‏ ‏این‏ ‏إن‏ ‏فاکتوریل‏ ‏کاتالانتاشون‏ ‏میان‏ ‏ترتیب‏ ‏دارند‏ ‏و‏ ‏برای‏ ‏اون‏ ‏کاتالانتاییی‏ ‏که‏ ‏میان‏ ‏ترتیب‏ ‏دارن‏ ‏حتما‏ ‏به‏ ‏ازای‏ ‏هر‏ ‏کدومشون‏ ‏پس‏ ‏ترتیبی‏ ‏وجود‏ ‏داره.‏ ‏

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


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

بنظرم
کلمه‏ ‏یکسان‏ ‏برای‏ ‏شکل‏ ‏ددج‏ ‏نیست‏ ‏برای‏ ‏نتیجه‏ ‏ای‏ ‏هستش‏ ‏که‏ ‏از‏ ‏میانترتیب‏ ‏و‏ ‏پس‏ ‏‏ترتیب‏ ‏یک‏ ‏ددج‏ ‏میشه‏ ‏بدست‏ ‏آورد.ما‏ ‏قراره‏ ‏که‏ ‏انواع‏ ‏ترتیب‏ ‏های‏ ‏(‏جایگشت‏ ‏های‏)‏‏یکسان‏ ‏یک‏ ‏تا‏ ‏إن‏ ‏رو‏ ‏که‏ ‏با‏ ‏ددج‏ ‏میشه‏ ‏بدست‏ ‏آورد‏ ‏که‏ ‏پس‏ ‏ترتیب‏ ‏و‏ ‏میانترتیب‏ ‏دارند‏ ‏بدست‏ ‏آوریم.سوالی‏ ‏که‏ ‏به‏ ‏جواب‏ ‏شما‏ ‏ختم‏ ‏میشود‏ ‏این‏ ‏است‏ ‏که:چه‏ ‏تعداد‏ ‏ددج‏ ‏متفاوت‏ ‏با‏ ‏إن‏ ‏گره‏ ‏و‏ ‏برچسب‏ ‏های‏ ‏یک‏ ‏تا‏ ‏إن‏ ‏که‏ ‏میانترتیب‏ ‏و‏ ‏پس‏ ‏ترتیب‏ ‏آنها‏ ‏یکسان‏ ‏است‏ ‏وجود‏ ‏دارند؟این‏ ‏سوال‏ ‏روی‏ ‏شکل‏ ‏تاکید‏ ‏داره‏ ‏‏ولی‏ ‏سوال‏ ‏دکتر‏ ‏روی‏ ‏نتیجه‏ ‏بدست‏ ‏آمده‏ ‏از‏ ‏خروجی‏ ‏ددج‏ ‏ها.موفق‏ ‏باشید.

(۰۲ آذر ۱۳۹۳ ۰۸:۲۷ ب.ظ)Ava.arshad94 نوشته شده توسط:  

(02 آذر ۱۳۹۳ ۰۸:۰۹ ب.ظ)ahp89 نوشته شده توسط:  

(02 آذر ۱۳۹۳ ۰۷:۲۵ ب.ظ)Ava.arshad94 نوشته شده توسط:  

نقل قول: !!!
اگر‏ ‏اعداد‏ ‏۱‏ ‏تا‏ ‏إن‏ ‏باشند‏ ‏که‏ ‏إن‏ ‏فاکتوریل‏ ‏جایگشت‏ ‏داشته‏ ‏باشند‏ ‏از‏ ‏این‏ ‏إن‏ ‏فاکتوریل‏ ‏کاتالانتاشون‏ ‏میان‏ ‏ترتیب‏ ‏دارند‏ ‏و‏ ‏برای‏ ‏اون‏ ‏کاتالانتاییی‏ ‏که‏ ‏میان‏ ‏ترتیب‏ ‏دارن‏ ‏حتما‏ ‏به‏ ‏ازای‏ ‏هر‏ ‏کدومشون‏ ‏پس‏ ‏ترتیبی‏ ‏وجود‏ ‏داره.‏ ‏

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


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

بنظرم
کلمه‏ ‏یکسان‏ ‏برای‏ ‏شکل‏ ‏ددج‏ ‏نیست‏ ‏برای‏ ‏نتیجه‏ ‏ای‏ ‏هستش‏ ‏که‏ ‏از‏ ‏میانترتیب‏ ‏و‏ ‏پس‏ ‏‏ترتیب‏ ‏یک‏ ‏ددج‏ ‏میشه‏ ‏بدست‏ ‏آورد.ما‏ ‏قراره‏ ‏که‏ ‏انواع‏ ‏ترتیب‏ ‏های‏ ‏(‏جایگشت‏ ‏های‏)‏‏یکسان‏ ‏یک‏ ‏تا‏ ‏إن‏ ‏رو‏ ‏که‏ ‏با‏ ‏ددج‏ ‏میشه‏ ‏بدست‏ ‏آورد‏ ‏که‏ ‏پس‏ ‏ترتیب‏ ‏و‏ ‏میانترتیب‏ ‏دارند‏ ‏بدست‏ ‏آوریم.سوالی‏ ‏که‏ ‏به‏ ‏جواب‏ ‏شما‏ ‏ختم‏ ‏میشود‏ ‏این‏ ‏است‏ ‏که:چه‏ ‏تعداد‏ ‏ددج‏ ‏متفاوت‏ ‏با‏ ‏إن‏ ‏گره‏ ‏و‏ ‏برچسب‏ ‏های‏ ‏یک‏ ‏تا‏ ‏إن‏ ‏که‏ ‏میانترتیب‏ ‏و‏ ‏پس‏ ‏ترتیب‏ ‏آنها‏ ‏یکسان‏ ‏است‏ ‏وجود‏ ‏دارند؟این‏ ‏سوال‏ ‏روی‏ ‏شکل‏ ‏تاکید‏ ‏داره‏ ‏‏ولی‏ ‏سوال‏ ‏دکتر‏ ‏روی‏ ‏نتیجه‏ ‏بدست‏ ‏آمده‏ ‏از‏ ‏خروجی‏ ‏ددج‏ ‏ها.موفق‏ ‏باشید.

مسلما مشخصه که یکسان برای شکل ددج نیس
من از شما یه چیزی میخوام تا ابهام بر طرف شه، با n=3 شکلش رو بکشید، ٥ حالت بیشتر نمیشه طبق جوابی که گفته کاتالان تا، حالا اون ٥ تارو برامون بکشین طوری که میانترتیب و پس ترتیب ها یکسان بشن، موضوع سر میانترتیب حلله چون صعودیه، پس ترتیب های یکسان رو روی این ٥ ددج نشون بدید

(۰۲ آذر ۱۳۹۳ ۰۸:۳۸ ب.ظ)ahp89 نوشته شده توسط:  جواب‏ ‏دکتر
دنباله‏ ‏میان‏ ‏ترتیب‏ ‏هر‏ ‏ددج‏ ‏با‏ ‏برچسب‏ ‏های‏ ‏از‏ ‏۱‏ ‏تا‏ ‏إن‏ ‏دنباله‏ ‏ی‏ ‏مرتب‏ ‏صعودی‏ ‏۱‏ ‏تا‏ ‏إن‏ ‏است.از‏ ‏سوی‏ ‏دیگر‏ ‏هر‏ ‏درخت‏ ‏دودوییی‏ ‏با‏ ‏إن‏ ‏گره‏ ‏را‏ ‏میتوان‏ ‏به‏ ‏روش‏ ‏پس‏ ‏ترتیب‏ ‏پیمایش‏ ‏کرد‏ ‏و‏ ‏ب‏ه‏ ‏همان‏ ‏ترتیب‏ ‏برچسب‏ ‏های‏ ‏۱تا‏ ‏إن‏ ‏را‏ ‏به‏ ‏گرههای‏ ‏آن‏ ‏داد.پس‏ ‏جواب‏ ‏تعداد‏ ‏درخت‏ ‏های‏ ‏دودویی‏ ‏با‏ ‏إن‏ ‏گره‏ ‏است‏ ‏که‏ ‏برابر‏ ‏با‏ ‏عدد‏ ‏.إن‏ ‏کاتالان‏ ‏است.

‏طبق‏ ‏متن‏ ‏بالا‏ ‏میانترتبا‏ ‏رو‏ ‏بصورت‏ ‏پس‏ ‏ترتیب‏ ‏پیمایش‏ ‏کن‏ ‏و‏ ‏به‏ ‏درخت‏ ‏جدید‏ ‏همزمان‏ ‏اضافه‏ ‏کن.‏!‏