سلام
لطفا این سوال رو حل میکنید
سلام!!!راستش این سوال حذف شده علتش هم ابهام در صورت سوال بوده
فک کنم به دلیلی که الان میگم این سوال از طرف دکتر قدسی ابهام دار تلقی شده.
ابهام سوال:
اگه همه حالت های درخت های جست و جوی دودویی با اختلاف عمق ۱ برای برگاش رو بخوایم مد نظر بگیریم این سوال فک کنم پاسخش تو گزینه ها نیست ولی طراح سوال تو گزینه ها حرکت جالبی انجام داده و تو همه گزینه ها جایگشت ۵ عنصر از یه تعداد حالت رو حساب کرده!!!این حالت وقتی توی شرایطی پیش میاد که توی هر سطح ماکزیمم نود رو داشته باشیم.یا همون درخت متوازن باشه حالا با هم انجام میدیم ببینید(احتمالا به خاطر همین سوال حذف شده!!جواب داره ولی مبهمه صورت سوال چون درخت موربم جز حالات مورد نظر ما هستش)
قبلش چند تا تعریفم مرور میکنیم:
ببینید گفته درخت دودویی جست و جو یعنی مقدار هر گره از فرزند سمت چپش بیشتره و از فرزند سمت راستش کمتره!!
خب نکته ای که تو صورت سوال گفته اینه که اختلاف عمق برگ ها باید حداکثر یک باشه یعنی یا هم سطح باشن یا یه واحد اختلاف داشته باشند
عمق رو هم فاصله گره تا ریشه در نظر میگیریم !خب حالا این حالتی که گفته ما رو یاد چه نوع درختی میندازه؟؟گفته شده اختلاف عمق برگ حداکثر ۱
خب ما هم همین کارو میکنیم ببینیم چی میشه
سطح اول ریشه
سطح دوم، ۲ تا نود
سطح سوم، ۴ تا نود
سطح چهارم ،۸ تا نود
سطح پنجم ،۱۶ تا نود
خب دیگه نمیتونیم سطح بعدی رو کامل نود بذاریم چون تا اینجا ۳۱ تا نود مصرف کردیم و فقط ۵ تا مونده.خب الان دقت کنید ما توی سطح پنجم ۱۶ تا نود قرار دادیم پس الان ۳۲ تا حالت برای قرار دادن این ۵ تا گره داریم درسته؟؟؟و ترتیب قرار گرفتن این ۵ تا نود هم مهمه چون برامون مهمه
چه نودی چپ باشه یا چه نودی راست باشه(باید شرایط درخت جست و جوی دودویی رو حفظ کنه)پس میشه ترتیب [tex]\binom{32}{5}[/tex]
دقت کنید که اون ۳۱ تا نود که گذاشتیم نمیتونن با هم جا به جا شن چون BST رو به هم میزنن پس فقط یه حالت میتونن داشته باشن
چقد راحت بود
دستتون درد نکنه
(۱۶ دى ۱۳۹۳ ۰۹:۳۹ ب.ظ)miladcr7 نوشته شده توسط: سلام!!!راستش این سوال حذف شده علتش هم ابهام در صورت سوال بوده
فک کنم به دلیلی که الان میگم این سوال از طرف دکتر قدسی ابهام دار تلقی شده.
ابهام سوال
۱- گفته درخت دودوی جستجو یا همون BST ولی منظوره سوال درخت دودویی بوده و راه حلی هم که شما رفتی واسه درخت دودویی بود نه BST به همون دلیلی که ره های میانی ممکنه ترتیب BST رو به هم بریزه گره های پایانی هم ممکنه بهم بریزه و نمیتونی هر ۳۲ مکان سطح آخرو بگیره.
۲-این که اختلاف برگ ها حداکثر یک باشه مفهوم پر بودن درخت تا عمق یکی مونده به آخر رو نمیده برای اینکه مطمئن شی میتونی درخت اریب چپ یا راست را در نظر بیگیری که هر دو میتونن درخت دودویی جستجو هم باشن
پس گزینه ای که سنجش داده یعنی همون جوابی که شما دادین با دو فرض درسته یکی اینکه درخت دودویی باشه (نه درخت دودویی جستجو)
دوم اینکه درخت تا عمق یکی مونده به آخر پر باشه ( نمیدونم اسم خاص داره یه نه)
یا میشد گفت درخت دودویی محض باشه و اختلاف گره های برگ حداکثر یک باشه. ( فک کنم با این شرایط هم درست باشه مطمئن نیستم بقیه در این مورد نظر بدن بهتره)
ولی با همون شرایطی که سوال گفته این سوال امروز روزگار منو سیاه کرد و همه کتابا هم به همین جواب غلط بسنده کردن الا نصیر اونم بدون هیچ توضیحی یه جوابی داده که آخرش معلوم نیس چیو میخواد ثابت کنه!