صفحه‌ها: ۱ ۲
با n گره چند درخت با ارتفاع n-1 می توان رسم کرد ؟
جواب: دو به توان n-1
با n گره چند درخت با ارتفاع n-3 می توان رسم کرد ؟
برای درخت با ارتفاع n-1 چون که این ارتفاع درخت رو مجبور می کرد که در هر سطح فقط یک عنصر داشته باشه میتونیم با اصل ضرب تعداد کل این درخت‌ها رو به دست بیاریم ولی اینجا چون که با این ارتفاع نمیتونیم مشخصا بگیم که در هر سطح چند عنصر باشه فک نکنم فرمولی داشته باشه.
شایدم با یک راه دیگه بشه بدست آورد
فکر کنم برای ارتفاع n-1 ریشه در ارتفاع ۱قرار میگیره و بقیه گره هاکه n-1 تاهست میتونن تو زیردرخت چپ قراربگیرن یا راست پس هرکدام دوحالت دارن.پس میشه دو ب توانn_1.دومی هم یه کم فکر میخاد.شمااگه جوابوداری بزار ببینیم میتونیم بهش برسیم یانه.
اگر سوال تستی هست گزینه‌ها رو بگید.در غیر اینصورت بدست آوردن فرمول کار ساده ای نیست.بهر حال اولین چیزی که به ذهنم میرسه اینه:
توی حالتی که می خواهیم ارتفاعمون n-1 بشه یک گره توی ریشه(سطح صفر) قرار میگره و n-1 گره دیگه هر کدوم به ترتیب توی سطحهای ۱ تا n-1 باید قرار بگیرند و تمام گره‌ها به غیر از آخری که برگ هست تک فرزندی میشند که هر کدوم دو حالت دارند(فرزند چپ یا راست والد باشند)
حالا اگر تا اینجارو فهمیدید سوال دومتون رو میشه اینطوری تفسیر کرد:
ما نیاز به ارتفاع دقیقا n-3 داریم.پس بیشترین فاصله برگمون از ریشه باید n-3 بشه.یعنی یک زیر درخت با ارتفاع n-3 داریم.پس باید n-3 گره توی عمق قرار بگیرند تا ارتفاعمون n-3 بشه.این n-3 گره هم می تونند فرزند چپ باشند هم فرزند راست.پس تا اینجا ۲ بتوان n-3 تا حالت داشتیم.ریشه هم هم که گذاشتیمش سر جاش و از n تا گره دو تا گره‌ی دیگه مونده که باید یه جایی بزاریمشون.حالا کجا می تونیم بزاریمشون؟ توی اتصالات خالی(به غیر از اتصالات خالی اخرین سطح چونکه اگر گره را اونجا بزاریم ارتفاع درخت از اونی که می خواهیم زیادتر میشه) که میشه تعداد کل اتصالات(۲(n-3)) منهای اتصالات پر(n-3).که میشه:n-3.
ولی اگر من این گره در سطح یکی مونده به اخر بزارم گره‌ی اخر را هم می تونم فرزند اون قرار بدم(سطح آخر) و بازم ارتفاع میریزه بهم! پس یکبار در نظر میگیریم که توی سطح اخر گره را نمی گذاریم و یکبار یک گره را در سطح اخر میگذاریم.
اگر در سطح اخر گره را نگذاریم گره اولو توی n-4 حالت می تونیم بزاریم و گره‌ی بعدیش رو توی n-3 تا(چراکه گره اولو که میزاریم درسته که یک اتصال کم میشه ولی دو تا اتصال به عنوان فرزند چپ و راست اون گره ایجاد میشه و در کل مکانهامون یکی زیاد میشه!)
اگر گره اولو در سطح اخر بگذاریم گره بعدی می تواند در n-4 حالت قرار بگیرد.(در این حالت چون گره اول توی سطح اخر هست نمی تونه فرزند داشته باشه مگرنه ارتفاع درخت بهم می خوره)
پس با این حساب باید جواب یه چیزی توی مایه های (!) دو بتوان n-3 ضربدر( (n-4)(n-3)+(n-4) )بشود ولی نمیشه! چونکه توی اون دو بتوان n-3 حالت خیلی از حالتها با حالت هایی که توی قسمت دو گره بدست اوردیم تکراری در میاد و بعضی حالات دوبار شمرده میشوند! حالا باید حالات تکراری رو بشماریم.اگر کسی تا این قسمتو خونده عجب حوصله ای داشته!!!
بگذریم در نهایت یک تقسیم بر دو میکنیم(!) و جواب نهایی میشه:دو بتوان n-4 ضربدر (n-4)(n-2)
مثلا با ۵ گره میشه ۶ تا درخت با ارتفاع ۲ رسم کرد.(ارتفاع رو از صفر باید بگیرید)
حسابی دری بری گفتم نه؟!!
احیانا منظورتون درخت دودویی نیست؟
در مورد خود درخت هم باید اطلاعاتی بدین
فک کنم n هم باید از ۳ بزرگتر باشه
(۳۰ آذر ۱۳۸۹ ۰۸:۲۷ ق.ظ)afagh1389 نوشته شده توسط: احیانا منظورتون درخت دودویی نیست؟
با توجه به جواب سوال اولشون باید درخت دودویی باشه.
(۳۰ آذر ۱۳۸۹ ۰۹:۰۰ ق.ظ)samanium نوشته شده توسط: در مورد خود درخت هم باید اطلاعاتی بدین
فک کنم n هم باید از ۳ بزرگتر باشه
ارتفاع رو باید از صفر بگیرید چونکه جواب اول را هم بر این اساس دادند.پس n باید بزرگتر مساوی ۵ باشه.
به نظر اساتید این راه که دیشب توی حالت خواب و بیدار(!) نوشتم درسته؟!
خوب وقتی میگه به ارتفاع n-1 یعنی درخت اریب حالا وقتی بخوایم از ارتفاعش کم کنیم باید ۲ تا از گره های آخر رو برداریم و بعد n-3 تا گره پدر رو انتخاب کنیم و اون گره‌ها رو جای فرزندشون قرار بدیم چون درخت ما اربیه جای یک فرزند رو بیشتر نداره (فرزند قبلی سر جای خودش هست) پس میشه تعداد حالات ساخت درخت قبلی ضربدر انتخاب ۲ از n-3
حالات اضافه کردن گره‌ها میشه n-3*n-4/2 جواب آخر از نظر من میشه دو به توان n-2 ضرب در n-3*n-4
آقا حامد نمیدونم جواب شما هم همین بود یا نه؟!
فقط شما گفتین حالات تکراری پیش میاد اما پیش نمیاد چون فرق داره که نود رو بگذاریم سمت چپ یا راست.
به خاطر همین وقتی درخت اریب به راسته میگذاریم سمت چپ و وقتی اریب به چپه میگذاریم سمت راست { یعنی دستمون بسته است} پس حالت تکراری ایجاد نمیشه.
واژه اریب واژه مناسبی برای این حالت نیست توی اریب ما یا اریب چپ داریم یا اریب راست.ولی توی این مساله لازم نیست همه فرزند چپ باشند یا همه فرزند راست.مهم اینه که والد‌ها تک فرزندی هستند.
چرا دو به توان n-2 ؟ باید دو به توان n-3 باشه.درسته؟
مثلا با ۵ گره می خواهیم درختهایی با ارتفاع ۲ رسم کنیم.۳ تا گره برای ارتفاع دو نیاز داریم که بصورت عمقی قرار بگیرند و ارتفاعشون ۲ بشه.مثلا مثل شکل زیر:
[attachment=201]
اگر حساب کنید میبینید که توی ۴ حالت می تونند با ارتفاع ۲ قرار بگیرند.(هر دو چپ-هر دو راست-اولی چپ دومی راست-اولی راست دومی چپ) که با فرمول دو به توان n-3 جور در میاد.
حالا روی همون شکل توضیح میدم.دو تا گره‌ی دیگه هم باید قرار بدیم تا تعداد گره هامون بشه ۵ و ارتفاعمون هم نباید عوض بشه.شما میگید دو تا جا(فرزند راست A و فرزند راست B) داریم و حالاتمون می شه ترکیب ۲ از ۲(n-3) ولی اینجا نباید از ترکیب استفاده کنید.اگر من گره‌ی اولو فرزند راست A قرار بدم گره‌ی دوم می تونه فرزند چپ یا راست گره اول باشه.که این حالت رو شما در نظر نمی گیرید.مطابق شکل زیر:
[attachment=202]
در مورد تکراری ها:من نگفتم توی اون دو به توان n-3 تا تکراری داریم.گفتم ترکیب حالات قبلی با حالات اضافه کردن دو گره حالات تکراری ایجاد میکنه.برگردیم به شکل بالا.توی این حالت من یک اریب چپ در نظر گرفته بودم و دو تا گره(D,E) رو فرزند راست انتخاب کرده بودم.اگر من اریب راست میگرفتم و دو تا گره را فرزند چپ می گرفتم بازم همون شکل بالا ایجاد میشد.
در کل فرمولی که من گفتم برای ۵ تا گره میگه ۶ تا درخت با ارتفاع ۲ وجود دارد که اگر شکل بکشید دقیقا بدین گونه میباشد.۶ درخت مطابق شکل‌ها‌ی زیر:
![[تصویر: i573499_01.jpg]](http://0o2.815.82.img98.com/out.php/i573499_01.jpg)
![[تصویر: i573500_02.jpg]](http://0o2.815.82.img98.com/out.php/i573500_02.jpg)
![[تصویر: i573501_03.jpg]](http://0o2.815.82.img98.com/out.php/i573501_03.jpg)
![[تصویر: i573502_04.jpg]](http://0o2.815.82.img98.com/out.php/i573502_04.jpg)
![[تصویر: i573503_05.jpg]](http://0o2.815.82.img98.com/out.php/i573503_05.jpg)
![[تصویر: i573504_06.jpg]](http://0o2.815.82.img98.com/out.php/i573504_06.jpg)
(۳۰ آذر ۱۳۸۹ ۰۱:۳۳ ب.ظ)حامد نوشته شده توسط: در مورد تکراری ها:من نگفتم توی اون دو به توان n-3 تا تکراری داریم.گفتم ترکیب حالات قبلی با حالات اضافه کردن دو گره حالات تکراری ایجاد میکنه.برگردیم به شکل بالا.توی این حالت من یک اریب چپ در نظر گرفته بودم و دو تا گره(D,E) رو فرزند راست انتخاب کرده بودم.اگر من اریب راست میگرفتم و دو تا گره را فرزند چپ می گرفتم بازم همون شکل بالا ایجاد میشد.نه همون شکل بالا ایجاد نمیشه چون اینجا D,E سمت راست درخت هستند و اگر اریب راست میگرفتید سمت چپ قرار میگرفتند.
ما وقتی n تا گره داریم خود چیدن اینها توی این ۶ مدل درخت کلی حالت داره چون فرق داره که مثلا A ریشه باشه یا A برگ باشه.
(۳۰ آذر ۱۳۸۹ ۰۲:۰۷ ب.ظ)afagh1389 نوشته شده توسط:(30 آذر ۱۳۸۹ ۰۱:۳۳ ب.ظ)حامد نوشته شده توسط: در مورد تکراری ها:من نگفتم توی اون دو به توان n-3 تا تکراری داریم.گفتم ترکیب حالات قبلی با حالات اضافه کردن دو گره حالات تکراری ایجاد میکنه.برگردیم به شکل بالا.توی این حالت من یک اریب چپ در نظر گرفته بودم و دو تا گره(D,E) رو فرزند راست انتخاب کرده بودم.اگر من اریب راست میگرفتم و دو تا گره را فرزند چپ می گرفتم بازم همون شکل بالا ایجاد میشد.نه همون شکل بالا ایجاد نمیشه چون اینجا D,E سمت راست درخت هستند و اگر اریب راست میگرفتید سمت چپ قرار میگرفتند.
ما وقتی n تا گره داریم خود چیدن اینها توی این ۶ مدل درخت کلی حالت داره چون فرق داره که مثلا A ریشه باشه یا A برگ باشه.
گره‌ها لیبل ندارند!و اصلا A,B,.. وجود نداره.من نام گذاری کردم که راحت‌تر توضیح بدم.
اگر قرار بود لیبل داشته باشند سوال اول هم جوابش نباید دو بتوان n-1 میشد.چونکه مثلا با دو برگ باید دو تا درخت میداشتیم ولی اگر لیبل بزاریم براشون می تونیم ۴ تا درخت داشته باشیم.
همیشه Key را برای جستجوی دودویی در نظر میگیرند و در درخت محدودیتی رو Key قرار نداره و در نظرش نمی گیرند.
با این حال اگر هم لیبل می دادیم فرقش یه !N بود.,ولی صورت مساله همچین چیزی رو ذکر نکرده و واضحه که نمی خواد.
ممنون متوجه شدم.
حالا آخر جواب چی میشه؟؟
(۳۰ آذر ۱۳۸۹ ۰۲:۲۸ ب.ظ)afagh1389 نوشته شده توسط: ممنون متوجه شدم.به نظر خودم راهم یه جاییش اشتباه داره! یه خورده بی منطق اون قسمت اخر بخاطر تعداد حالات تکراری تقسیم بر دو کردم و شاید برای اعداد بزرگتر جواب غلط بده.
حالا آخر جواب چی میشه؟؟
بهر حال کسی همچین سوال هایی رو حل نمی کنه.توی ۴ تا گزینه ۵ میزاریم و می بینیم کدوم ۶ میشه.
آره نمیدونم چرا توی مانشت بچه‌ها تستها رو بدون گزینه و جواب میگذارن؟ شاید میخوان مارو تست کنن!
با سلام خدمت شما دوستان.
در جوابا بود که حالات تکراری ایجاد نمیشه در صورتی که ایجاد میشه.
با n گره چند درخت با ارتفاع n-1 می توان رسم کرد ؟
جواب: دو به توان n-1
با n گره چند درخت با ارتفاع n-2 می توان رسم کرد ؟
جواب
(دو به توانn-2 )* (n-2)) منهای ۲ به توان n-3با n گره چند درخت با ارتفاع n-3 می توان رسم کرد ؟
راستی منظور درخت دودویی بوده حالا جواب چیه؟
راستی آقا حامد از کجا میدونی که حالات تکراری بیشتری در گره های بیشتر ایجاد نمیشه؟