با تشکر از شما

مشخصاً این روند برای MaxHeap هم تفاوتی نخواهد داشت؛ درسته؟

با تشکر از مسعود جواب کاملا درست هست.

یعنی فرمول خاصی برای ساخت درختان متنوع heap با عناصر یا کلیدهای ۱ تا n وجود نداره بجز یافتن جایگشتها.

(۲۸ آذر ۱۳۹۰ ۰۲:۰۸ ب.ظ)mam نوشته شده توسط:  مشخصاً این روند برای MaxHeap هم تفاوتی نخواهد داشت؛ درسته؟

بله تفاوتی نخواهد داشت.

اما یکم سوال رو پیچیده‌تر بکنیم فرض کنیم برای عناصر ۱ تا ۹ بخواهیم یک max-heap یا min-heap بسازیم (یعنی دیگه درخت پر نیست و فقط شرط کامل بودن رو داره). چند درخت متفاوت میتوان ساخت؟ البته با جوابی که بالا گفته شده یافتنش کار مشکلی نیست.

دوستان مشارکت کنید. اصلا نگران غلط بودن جوابتون نباشید.

اینجا هدف اینه که دور هم یه چیزایی یاد بگیریم.

جوابتون در رابطه با یافتن جایگشتها برای هر زیر درخت درسته. اما آخر سر یه اشتباه جزئی فکر کنم کردین اونم در محاسبه جواب کل.

(۲۸ آذر ۱۳۹۰ ۰۳:۳۱ ب.ظ)homa نوشته شده توسط:  و در کل: $\binom{8}{3}*\binom{8}{5}*\binom{4}{3}*\binom{4}{1}*2*2$

ببینین میتونین ایرادو پیدا کنین.

خوب جواب خودم رو بگم اگر مشکلی هم داشت لطفا بگین.

این درخت با شرایط جدید که در پست ۴ این تاپیک شرایطش رو گفتم یک درخته کامل میشه با ۳ گره در زیر درخت ریشه سمت راست و ۵ گره در زیر درخت ریشه سمت چپ.


اول از همه ک.چکترین عنصر که تکلیفش معلومه و در ریشه قرار میگیره و حالتی نداره
الف) بررسی حالات زیر درخت ریشه سمت راست که از ۸ کلید باقی مانده میتوان $\binom{8}{3}$ حالت کلید انتخاب کرد حالا این ۳ کلید انتخاب شده هم به دو حالت میتونه در ۳ گره موجود در سمت راست ریشه جایگشت بشه. در نتیجه $\binom{8}{3}*2$

ب) بررسی حالات سمت چپ ریشه که تعداد حالات کلید های متفاوتی که میشه بهش داد $\binom{8}{5}$ است و حالا حالات مختلف سمت چپ ریشه که خودش یک درخته با ۳ گره در سمت چپش و ۱ گره در سمت راستش:
ب-۱) تو این درخت جدید باز از اون ۵ تا انتخابی که تو مرحله قبل داشتیم باز کوچکترینش به عنوان ریشه قرار خواهد گرفت و حالت خاصی نخواهد داشت.
ب-۲) در زیر درخت سمت راستش که ۱ گره داره از ۴ کلید باقس مانده میتوان $\binom{4}{1}$ حالت انتخاب کرد و چون فقط یک گره هست پس حالت دیگه ای برای چینش نداره.
ب-۳) در زیر درخت سمت چپش باز ۳ گره موجود است که حالات انتخاب کلید برای این زیر درخت $\binom{4}{3}$ است و چون میشه به دوحالت مختلف کلیدها رو جایگشت داد پس میشه $\binom{4}{3}*2$

خوب حالا جواب نهایی $\left [ \binom{8}{3}*2 \right ] \left [ \binom{8}{5}*\left( \binom{4}{3}*2 \binom{4}{1} \right )\right ]$

البته میخواستم با شکل توضیح بدم که یکم وقت ندارم دوستان ببخشن.

حالا باز اگه مشکلی چه در راه حل بنده یا اینکه قابل فهم نبودنش هست بگین

نمیدونم من دارم اشتباه میکنم یا شما !
اینجا یه سوال برای من پیش اومده!
تا قسمت الف توضیحاتتونو هیچ مشکلی ندارم دقیقا از بین ۸ کلید باقیمونده باید ۳تا انتخاب بشه و از بین این سه تا یکی از همه کوچیکتره که کنار گذاشته میشه و بین دو کلید باقیمونده دوباره ۲حالت وجود داره اما تو قسمت ب توضیحات بنظرم یه مشکلی هست
وقتی تو قسمت الف از بین ۸ تا کلید ۳ تا انتخاب شد دیگه نباید این ۳تا کلید در انتخابهای بعدی شرکت داده بشن چون انتخابهامون به این شکلی که شما گفتید انتخاب با جایگذاری محسوب درحالیکی ما نمیتونیم از کلیدها بطور تکراری در چند مکان استفاده کنیم من فکر میکنم برای انتخاب کلیدهای سمت چپ باید از بین ۵ کلید ۴ کلید انتخاب کنیم که برابر ۵ میشه یعنی میتونیم اصلا دیگه انتخابی انجام ندیم، درواقع وقتی در قسمت الف از بین ۸ کلید ۳تا انتخاب کردیم هرچی کلید باقی میمونه مربوط به سمت چپه که از ۵ تا دوباره یکیش از همه کوچکتره و ما باید از بین ۴ کلید یکی رو برای سمت راست و ۳تا رو برای سمت چپ انتخاب کنیم!
همینطور برای قسمت ب-۳‌، وقتی از بین ۴ کلید یکی رو برای سمت راست انتخاب کردیم حالا فقط ۳تا کلید داریم که یکی از اونها از همه کوچیکتره پس فقط میمونه ۲ کلید که باید جایگشتشونو حساب کنیم!
یکم سوال اماریه تا ساختمانی

ایرادتون اینکه قسمت الف رو درست متوجه نشدین.
ما اول برای هر زیر درخت داریم حالات مختلف تخصیص کلید رو محاسبه میکنیم. بعد از تخصیص جایگشت‌ها رو محاسبه میکنیم.
اول در هر سطح تعداد کلید باقی مونده رو باید حالات مختلف تخصیصشون رو به زیر درختها در نظر گرفت.
دیگه نمیشه برای زیر درخت چپ در قسمت (ب) گفت که دیگه برات ۵ کلید باقی موند سهم تو از زندگی همین بوده.
امیدوارم بتونم منظورمو برسونم.
شما باید اول فکرتون لینطوری باشه که از ۸ کلید باقی مونده در سطح ۱ زیر درخت راست چند حالت انتخاب داره و زیر درخت سمت چپ چند حالت انتخاب داره.
نه اینکه ۳ تا رو دادیم به سمت راستی حالا موند ۵ تا همون ۵ تا سهم سمت چپی هست.
ما میگیم مثلا چه اعدادی میتونن در زیر درخت سمت چپ و رایت قرار بگیرند.

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

امیدوارم خوب تونسته باشم برسونم منظورمو.

ببینید اگر سوال اولی که گذاشتید رو هم بخوایم به همین روشی که شما گفتید حل بکنیم باید یک بار از ۶ تا یه ۳تا انتخاب بکنیم برای سمت راست و دوباره یه ۳ تا از ۶ تا انتخاب بکنیم برای سمت چپ که اینطوری عدد بدست اومده خیلی بیشتر از ۸۰ میشه
درواقع داریم از ۶ تا یه ۳تا انتخاب میکنیم برای یک سمت و ۳تای باقیمونده هم برای سمت دیگه در نظر میگیریم

بالاخره هرکی از زندگی یه سهمی داره