تالار گفتمان مانشت

سلام
دوستان سوال ۵۲ کامپیوتر ۸۶ رو چطور باید حل کرد؟
مرسی

سلام
این الگوریتم درخت را به صورت درجا به max-heap تبدیل می کنه که عملیات max-heapify درون حلقه repeat انجام می شود.اگر بخواهیم به طور فلسفی نگاه کنیم که یخورده سخت میشه ولی با توجه به اینکه این سوال تعداد دفعات اجرای حلقه repeat را خواسته یه کار خیلی خیلی ساده انجام بدید به دست می یاد:
خود سوال گفته k=log n خوب شما بیایید برای n پایه مثلا 2 این کارو انجام بدید و حلقه repeato ببینید چند بار تکرار می شه
!که اگه توجه کنید حداکثر 2 بار اجرا می شه!
خوب حالا بیایید به جای k ها در جوابها همون چیزی که خود سوال داده بگذارید که log n و اینجا هم n=2 و تعداد تکرار هم 2 شده!
و اگر چک کنید فقط جواب 4 که برابر 4 می شود درست است و از تعداد تکرار ما که 2 , (t)است بیشتر است.

t<=2*2^log2-1+log2+1=2+1+1=4
ولی اگه برای بقیه بخواهیم حساب کنیم تعداد تکرار می شه منفی که تعداد تکرار هم نمی تونه منفی باشه!و برای همینم ج4 رو تا همینجا به دست میاریم!و اگر برای پایه ج بده برای بقیشم ج می ده!

موفق باشید.....

(14 بهمن 1392 12:33 ب.ظ)mahsalove نوشته شده توسط: [ -> ]سلام
این الگوریتم درخت را به صورت درجا به max-heap تبدیل می کنه که عملیات max-heapify درون حلقه repeat انجام می شود.اگر بخواهیم به طور فلسفی نگاه کنیم که یخورده سخت میشه ولی با توجه به اینکه این سوال تعداد دفعات اجرای حلقه repeat را خواسته یه کار خیلی خیلی ساده انجام بدید به دست می یاد:
خود سوال گفته k=log n خوب شما بیایید برای n پایه مثلا ۲ این کارو انجام بدید و حلقه repeato ببینید چند بار تکرار می شه
!که اگه توجه کنید حداکثر ۲ بار اجرا می شه!
خوب حالا بیایید به جای k ها در جوابها همون چیزی که خود سوال داده بگذارید که log n و اینجا هم n=2 و تعداد تکرار هم ۲ شده!
و اگر چک کنید فقط جواب ۴ که برابر ۴ می شود درست است و از تعداد تکرار ما که ۲ , (t)است بیشتر است.

t<=2*2^log2-1+log2+1=2+1+1=4
ولی اگه برای بقیه بخواهیم حساب کنیم تعداد تکرار می شه منفی که تعداد تکرار هم نمی تونه منفی باشه!و برای همینم ج۴ رو تا همینجا به دست میاریم!و اگر برای پایه ج بده برای بقیشم ج می ده!

موفق باشید.....

ممنون از توضیحاتتون فقط من نفهمیدم چطور بقیه جوابها منفی میشه چون اصلا علامت منفی نداریم؟؟؟ ( البته ریاضیات من یه خورده ... )

شما لطف کنید جایگزین کنید!:/بعد می فهمید چرا؟!:/
log 2=1
حالا گفته k-2 پس می شه log n که همون k با شه -2
یعنی
1-2=-1

دیگه آنقدر آدم ریاضیشم ضعیف باشه واسه امتحان ارشد خوب نیس!

الان من اینطوری حل می کنم و منفی در نمیاد ، کجاش دارم اشتباه می کنم؟

n=2
k=log n =1
2 <= 2*2^(1-2)+3*2^(1-3)+1
2 <= 2*2^(-1)+3*2^(-2)+1
2<= 2*(1/2)+3(1/4)+1

درسته به صورت کلی جواب تعداد تکرار برای همشون منفی نمی شه ولی منظورم از منفی شدن منفی شدن تعداد گره در هر سطح که ضربدر 2 شده و توانش میشه منفی و غلط جواب به دست میاد!
من یه جور دیگه این سوالو توضیح می دم اگر متوجه نشدید یا کتاب پارسه رو بخوانید یا دوستان دیگه کمک کنند!
من تحلیل دیگم اینجوریه که تعداد تکرار repeat برای یک درخت بر حسب ارتفاعش زمانی Max می شه که درخت پر باشه و حداکثر تعداد گره رو در هر سطح داشته باشه!k رو وقتی log n داده یه جورایی با توجه به اندیس هایی که داده شده در داخل حلقه repeat بایستی متوجه بشید که داره به یه درخت اشاره می کنه و اون درخت با ارتفاع log n درخت پر است!
در واقع در سطح آخر آن حداکثر 2^k نود وجود دارد و همگی برگ هستند و حلقه repeat برای آْنها اجرا نمی شود.در سطح ما قبل آخر حداکثر 2^k-1 نود وجود دارد که همگی لزوما داخلی نیستند و برای نودهای داخلی در این سطح حلقه repeat حداکثر 2 بار اجرا می شود.در سطح 2 ما قبل آخر 2^k-2 بار اجرا می شود که برای هر یک حداکثر 3 بار repeat اجرا می شودو به همین ترتیب.
در واقع تعداد تکرار حلقه repeat برای هر گره داخلی i در سطح r ام برابر با ارتفاع زیر درخت مشتق شده از آن است.

توضیح حلقه repeat:
برای گره ما قبل آخر 2 بار یکی فرزند بزرگتر پیدا شود و دوم اندیس j و k که تغییر کرده اند یا ثابت مانده اند.اگر ثابت شود که repeat تمام و اگر j نسبت به k تغییر کرده باشد دوباره حلقه تکرار پس برای ریشه k+1 یعنی به ارتفاع این عمل تکرار مشود.پس برای درخت پر برابر است با
k=log n +1

پس اگه ما برای 2 گره حساب کنیم می بینیم که تعداد حداکثر تکرار حلقه repeat عدد 2 است که باید ضربدر تعداد گره در سطح خودش یعنی 1 شود(یعنی 2 بار اجرا شدن بستگی به تعداد گره در این سطح دارد.)حالا اگر توجه کنید فقط گزینه 4 ج درست است!و در نهایت هم باید با تعداد تکرار حلقه repeat در سطح اول ریشه جمع شود که برای ریشه اگه توجه کنید نسبت به همون 2 گره ,2 بار این عملیات انجام می شود.(در واقع چون 2 گره در نظر گرفتیم گره ریشه با همان گره که تعداد تکرارشو در اول حساب کردیم با هم برابر می شوند.)

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

موفق باشید.....

الان متوجه شدم داستان چیه ، مرسی