اگه دوست عزیزمون مسعود جان سطح سوال رو مناسب بدونند انتقالش بدن به مباجث داغ وگرنه که همینجا روش بحث میکنیم.
![[تصویر: 59298_1_1379097001.jpg]](https://img.manesht.ir/59298_1_1379097001.jpg)
دوستان نظرات و روشتون رو نیز بگین تا روش بحث بشه.
(۲۸ آذر ۱۳۹۰ ۰۱:۲۶ ق.ظ)mamat نوشته شده توسط: اگه دوست عزیزمون مسعود جان سطح سوال رو مناسب بدونند انتقالش بدن به مباجث داغ وگرنه که همینجا روش بحث میکنیم.
دوستان نظرات و روشتون رو نیز بگین تا روش بحث بشه.
![[تصویر: 59339_1_1379096941.jpg]](https://img.manesht.ir/59339_1_1379096941.jpg)
سطح سوال خوبه اما چون دیگه اینجا گزاشتین همین جا بررسیش میکنیم (اگه خواستین منتقلش کنید ):
اول مینیمم رو بزار توی ریشه ---> فقط ۱ حالت میتونه رخ بده
بعدش بیا از ۶ گره باقیمانده( بجز ریشه )۳ تاش رو بزار در زیر درخت راست و ۳ تاش هم زیر درخت چپ( چون هیپ یه درخت کامله )برای گزاشتن این ۳ گره دلخواه از بین ۶ مقدار باید ۳ را از ۶ انتخاب کنی( انتخاب ۳ از ۶ )بعد اینو در ۲ ضربش کن چون ۲ تا زیر هیپ که والدشون همون ریشه است داریم( زیر هیپ راست و چپ )
حاصل بالا رو در ۲ ضرب کن چون زیر هیپ راست و چپ هر کدوم می تونه ۲ حالت باشه( یعنی با ۳ عنصر فقط ۲ هیپ مختلف می تونیم داشته باشه چون مینیمم رو میزاریم تو ریشه و با ۲ عنصر دیگه میتونیم به دلخواه یکی رو سمت راست و دیگری رو سمت چپ بزاریم )
جواب گزینه ۲ است.
[tex]2*\begin{pmatrix} 6\\ 3 \end{pmatrix} * 2 = 80 [/tex]
با تشکر از شما
مشخصاً این روند برای MaxHeap هم تفاوتی نخواهد داشت؛ درسته؟
با تشکر از مسعود جواب کاملا درست هست.
یعنی فرمول خاصی برای ساخت درختان متنوع heap با عناصر یا کلیدهای ۱ تا n وجود نداره بجز یافتن جایگشتها.
(۲۸ آذر ۱۳۹۰ ۰۲:۰۸ ب.ظ)mam نوشته شده توسط: مشخصاً این روند برای MaxHeap هم تفاوتی نخواهد داشت؛ درسته؟
بله تفاوتی نخواهد داشت.
اما یکم سوال رو پیچیده‌تر بکنیم فرض کنیم برای عناصر ۱ تا ۹ بخواهیم یک max-heap یا min-heap بسازیم (یعنی دیگه درخت پر نیست و فقط شرط کامل بودن رو داره). چند درخت متفاوت میتوان ساخت؟ البته با جوابی که بالا گفته شده یافتنش کار مشکلی نیست.
دوستان مشارکت کنید. اصلا نگران غلط بودن جوابتون نباشید.
اینجا هدف اینه که دور هم یه چیزایی یاد بگیریم.
نقل قول: اما یکم سوال رو پیچیده‌تر بکنیم فرض کنیم برای عناصر ۱ تا ۹ بخواهیم یک max-heap یا min-heap بسازیم (یعنی دیگه درخت پر نیست و فقط شرط کامل بودن رو داره). چند درخت متفاوت میتوان ساخت؟ البته با جوابی که بالا گفته شده یافتنش کار مشکلی نیست.من فکر می کنم جوابش اینطوری میشه:
دوستان مشارکت کنید. اصلا نگران غلط بودن جوابتون نباشید.
اینجا هدف اینه که دور هم یه چیزایی یاد بگیریم.
اول اینکه چون درخت هیپ کامله پس با ۹ گره ما ۵ گره در زیر درخت چپ داریم و ۳ گره در زیر درخت راست(تا شرط کامل بودن رعایت بشه)
برای min-heap اوا کمترین رو میذاریم ریشه و حالت های زیر درخت چپ و راست برای ۸ گره باقی مانده:[tex]\binom{8}{5}[/tex]
در زیر درخت چپ باز کمترین تو ریشه و ۴ تا گره باقی میمونه که ۳ تاش زیر دخت چپ و یکی سمت راست:[tex]\binom{4}{3}[/tex]
باز در ۳ گره باقی مانده کمترین در ریشه قرار میگیرد و دو گره باقی مانده هر کدام میتواند درهر طرف از گره ریشه قرار بگیرد پس ۲ حالت برای آن‌ها وجود دارد
در مورد زیر درخت سمت راست گره ریشه(ریشه اصلی درخت) هم کمترین در ریشه قرار میگیرد و دو گره باقی مانده هر کدام میتواند درهر طرف از گره ریشه قرار بگیرد پس ۲ حالت برای آن‌ها وجود دارد
و در کل: [tex]\binom{8}{5}*\binom{4}{3}*2*2[/tex]
امیدوارم جوابم درست باشه
جوابتون در رابطه با یافتن جایگشتها برای هر زیر درخت درسته. اما آخر سر یه اشتباه جزئی فکر کنم کردین اونم در محاسبه جواب کل.
(۲۸ آذر ۱۳۹۰ ۰۳:۳۱ ب.ظ)homa نوشته شده توسط: و در کل: [tex]\binom{8}{3}*\binom{8}{5}*\binom{4}{3}*\binom{4}{1}*2*2[/tex]
ببینین میتونین ایرادو پیدا کنین.
خوب جواب خودم رو بگم اگر مشکلی هم داشت لطفا بگین.
این درخت با شرایط جدید که در پست ۴ این تاپیک شرایطش رو گفتم یک درخته کامل میشه با ۳ گره در زیر درخت ریشه سمت راست و ۵ گره در زیر درخت ریشه سمت چپ.
اول از همه ک.چکترین عنصر که تکلیفش معلومه و در ریشه قرار میگیره و حالتی نداره
الف) بررسی حالات زیر درخت ریشه سمت راست که از ۸ کلید باقی مانده میتوان [tex]\binom{8}{3}[/tex] حالت کلید انتخاب کرد حالا این ۳ کلید انتخاب شده هم به دو حالت میتونه در ۳ گره موجود در سمت راست ریشه جایگشت بشه. در نتیجه [tex]\binom{8}{3}*2[/tex]
ب) بررسی حالات سمت چپ ریشه که تعداد حالات کلید های متفاوتی که میشه بهش داد [tex]\binom{8}{5}[/tex] است و حالا حالات مختلف سمت چپ ریشه که خودش یک درخته با ۳ گره در سمت چپش و ۱ گره در سمت راستش:
ب-۱) تو این درخت جدید باز از اون ۵ تا انتخابی که تو مرحله قبل داشتیم باز کوچکترینش به عنوان ریشه قرار خواهد گرفت و حالت خاصی نخواهد داشت.
ب-۲) در زیر درخت سمت راستش که ۱ گره داره از ۴ کلید باقس مانده میتوان [tex]\binom{4}{1}[/tex] حالت انتخاب کرد و چون فقط یک گره هست پس حالت دیگه ای برای چینش نداره.
ب-۳) در زیر درخت سمت چپش باز ۳ گره موجود است که حالات انتخاب کلید برای این زیر درخت [tex]\binom{4}{3}[/tex] است و چون میشه به دوحالت مختلف کلیدها رو جایگشت داد پس میشه [tex]\binom{4}{3}*2[/tex]
خوب حالا جواب نهایی [tex]\left [ \binom{8}{3}*2 \right ] \left [ \binom{8}{5}*\left( \binom{4}{3}*2 \binom{4}{1} \right )\right ][/tex]
البته میخواستم با شکل توضیح بدم که یکم وقت ندارم دوستان ببخشن.
حالا باز اگه مشکلی چه در راه حل بنده یا اینکه قابل فهم نبودنش هست بگین
نمیدونم من دارم اشتباه میکنم یا شما !
اینجا یه سوال برای من پیش اومده!
تا قسمت الف توضیحاتتونو هیچ مشکلی ندارم دقیقا از بین ۸ کلید باقیمونده باید ۳تا انتخاب بشه و از بین این سه تا یکی از همه کوچیکتره که کنار گذاشته میشه و بین دو کلید باقیمونده دوباره ۲حالت وجود داره اما تو قسمت ب توضیحات بنظرم یه مشکلی هست
وقتی تو قسمت الف از بین ۸ تا کلید ۳ تا انتخاب شد دیگه نباید این ۳تا کلید در انتخابهای بعدی شرکت داده بشن چون انتخابهامون به این شکلی که شما گفتید انتخاب با جایگذاری محسوب درحالیکی ما نمیتونیم از کلیدها بطور تکراری در چند مکان استفاده کنیم من فکر میکنم برای انتخاب کلیدهای سمت چپ باید از بین ۵ کلید ۴ کلید انتخاب کنیم که برابر ۵ میشه یعنی میتونیم اصلا دیگه انتخابی انجام ندیم، درواقع وقتی در قسمت الف از بین ۸ کلید ۳تا انتخاب کردیم هرچی کلید باقی میمونه مربوط به سمت چپه که از ۵ تا دوباره یکیش از همه کوچکتره و ما باید از بین ۴ کلید یکی رو برای سمت راست و ۳تا رو برای سمت چپ انتخاب کنیم!
همینطور برای قسمت ب-۳، وقتی از بین ۴ کلید یکی رو برای سمت راست انتخاب کردیم حالا فقط ۳تا کلید داریم که یکی از اونها از همه کوچیکتره پس فقط میمونه ۲ کلید که باید جایگشتشونو حساب کنیم!
یکم سوال اماریه تا ساختمانی
ایرادتون اینکه قسمت الف رو درست متوجه نشدین.
ما اول برای هر زیر درخت داریم حالات مختلف تخصیص کلید رو محاسبه میکنیم. بعد از تخصیص جایگشتها رو محاسبه میکنیم.
اول در هر سطح تعداد کلید باقی مونده رو باید حالات مختلف تخصیصشون رو به زیر درختها در نظر گرفت.
دیگه نمیشه برای زیر درخت چپ در قسمت (ب) گفت که دیگه برات ۵ کلید باقی موند سهم تو از زندگی همین بوده
.امیدوارم بتونم منظورمو برسونم.
شما باید اول فکرتون لینطوری باشه که از ۸ کلید باقی مونده در سطح ۱ زیر درخت راست چند حالت انتخاب داره و زیر درخت سمت چپ چند حالت انتخاب داره.
نه اینکه ۳ تا رو دادیم به سمت راستی حالا موند ۵ تا همون ۵ تا سهم سمت چپی هست.
ما میگیم مثلا چه اعدادی میتونن در زیر درخت سمت چپ و رایت قرار بگیرند.
شما از همون اول جایگشتی فکر میکنین در حالی که اول حالات انتخاب هست.
امیدوارم خوب تونسته باشم برسونم منظورمو.
ببینید اگر سوال اولی که گذاشتید رو هم بخوایم به همین روشی که شما گفتید حل بکنیم باید یک بار از ۶ تا یه ۳تا انتخاب بکنیم برای سمت راست و دوباره یه ۳ تا از ۶ تا انتخاب بکنیم برای سمت چپ که اینطوری عدد بدست اومده خیلی بیشتر از ۸۰ میشه
درواقع داریم از ۶ تا یه ۳تا انتخاب میکنیم برای یک سمت و ۳تای باقیمونده هم برای سمت دیگه در نظر میگیریم
بالاخره هرکی از زندگی یه سهمی داره
(۲۸ آذر ۱۳۹۰ ۰۳:۳۱ ب.ظ)homa نوشته شده توسط:نقل قول: اما یکم سوال رو پیچیده‌تر بکنیم فرض کنیم برای عناصر ۱ تا ۹ بخواهیم یک max-heap یا min-heap بسازیم (یعنی دیگه درخت پر نیست و فقط شرط کامل بودن رو داره). چند درخت متفاوت میتوان ساخت؟ البته با جوابی که بالا گفته شده یافتنش کار مشکلی نیست.من فکر می کنم جوابش اینطوری میشه:
دوستان مشارکت کنید. اصلا نگران غلط بودن جوابتون نباشید.
اینجا هدف اینه که دور هم یه چیزایی یاد بگیریم.
اول اینکه چون درخت هیپ کامله پس با ۹ گره ما ۵ گره در زیر درخت چپ داریم و ۳ گره در زیر درخت راست(تا شرط کامل بودن رعایت بشه)
برای min-heap اوا کمترین رو میذاریم ریشه و حالت های زیر درخت چپ و راست برای ۸ گره باقی مانده:[tex]\binom{8}{5}[/tex]
در زیر درخت چپ باز کمترین تو ریشه و ۴ تا گره باقی میمونه که ۳ تاش زیر دخت چپ و یکی سمت راست:[tex]\binom{4}{3}[/tex]
باز در ۳ گره باقی مانده کمترین در ریشه قرار میگیرد و دو گره باقی مانده هر کدام میتواند درهر طرف از گره ریشه قرار بگیرد پس ۲ حالت برای آن‌ها وجود دارد
در مورد زیر درخت سمت راست گره ریشه(ریشه اصلی درخت) هم کمترین در ریشه قرار میگیرد و دو گره باقی مانده هر کدام میتواند درهر طرف از گره ریشه قرار بگیرد پس ۲ حالت برای آن‌ها وجود دارد
و در کل: [tex]\binom{8}{5}*\binom{4}{3}*2*2[/tex]
امیدوارم جوابم درست باشه
من هم مثل هما حل کردم و کاملا با جواب هما جان موافقم
بله به نظر من هم جواب ایشون بعد از تصحیح که تو پست شماره ۵ این تاپیک موجوده صحیح هست.
البته من هم این جواب رو بار اول حل سوال بدست آوردم اما به نظرم غلط رسید.
ولی یکی از دوستان هم با اشاره به اینکه تو کتاب پوران پژوهش هم سوالی شبیه به این با تعداد کلید ۸ تا حل شده با اینکه راه حل آن هم قابل فهم نیست اما همان جواب که راه حل ذکر شده بدست می دهد را بدست می آورد.
پس راه حل بنده که در پست ۷ و نقل قولی که از پست خانم homa در پست ۶ آورده شده غلط می باشد.
در ضمن خانم narges_r هم اشاره صحیح کردن به جواب.
اگر با جواب بنده گمراه شدید معذرت میخوام. اما من فکر نمیکردم جواب به این سادگی بدست بیاید و برای همین مسدله را برای خودم پیچیده میکردم.
تاپیک خم بسته شد چون جواب صحیح در پست ۵ موجود است
.موفق باشید