(۲۲ بهمن ۱۳۹۱ ۰۲:۴۰ ب.ظ)mfXpert نوشته شده توسط:(22 بهمن ۱۳۹۱ ۰۲:۳۷ ب.ظ)ADELZX نوشته شده توسط: خب چطور شما میفرمایید که میشه گره ریشه رو در کمتر از logn حذفش کرد ؟شما می‌تونید به من بگید تفاوت اصلی اوی کوچیک و بزرگ در چی هستش؟
واسه جواب این تست همون تفاوت کوچیکتر و کوچیکتر مساوی رو هم در نظر بگیریم کامل جواب شما رد میشه.
(۲۲ بهمن ۱۳۹۱ ۱۱:۵۸ ق.ظ)sasanbabai نوشته شده توسط: من در مورد سوال ۱۰۰ موافق نیستم. رابطه بازگشتیش میشه
T(N) = 2T(N/2) + 1
خوب جوابشم میشه تتای N که نزدیکترین گزینه همان اوی بزرگ N میشه. رابطه بازگشتی به این خاطر این میشه که اگر در ریشه باشیم کافیه که طول وزن دار زیر درخت چپ و زیر درخت راست رو بدست بیاریم بعد با یک مقایسه بزرگترین رو انتخاب کنیم وسچس با وزن ریشه جمع کنیم. مقایسه و جمع تتای ۱ هستن و چون درخت متوازن هست پس رابطه بازگشتی همونیه که نوشتم.
درسته ولی یه نکته ای رو دقت نکردین، تا اونجایی که گفتین زیر درخت چپ و زیر درخت راست رو به دست میاریم بعد با یک مقایسه بزرگترین رو انتخاب می کنیم درسته ولی بعد شما اونو با ریشه جمع می کنین که این درست نیست چون ممکنه مسیر بزرگتر از ریشه عبور نکنه پس باید با تمام گره ها جمع بشه و بعد بزرگترین انتخاب بشه یعنی n مقایسه نه یکی پس رابطه بازگشتی می شه
T(N) = 2T(N/2) + n
که اینم از درجه nlogn
(۲۲ بهمن ۱۳۹۱ ۰۳:۲۵ ب.ظ)freidoony نوشته شده توسط:من اینو از طریق عدد گذاری تو یه درخت متوازن حساب کردم فکر کنم میشه O(n)(22 بهمن ۱۳۹۱ ۱۱:۵۸ ق.ظ)sasanbabai نوشته شده توسط: من در مورد سوال ۱۰۰ موافق نیستم. رابطه بازگشتیش میشه
T(N) = 2T(N/2) + 1
خوب جوابشم میشه تتای N که نزدیکترین گزینه همان اوی بزرگ N میشه. رابطه بازگشتی به این خاطر این میشه که اگر در ریشه باشیم کافیه که طول وزن دار زیر درخت چپ و زیر درخت راست رو بدست بیاریم بعد با یک مقایسه بزرگترین رو انتخاب کنیم وسچس با وزن ریشه جمع کنیم. مقایسه و جمع تتای ۱ هستن و چون درخت متوازن هست پس رابطه بازگشتی همونیه که نوشتم.
درسته ولی یه نکته ای رو دقت نکردین، تا اونجایی که گفتین زیر درخت چپ و زیر درخت راست رو به دست میاریم بعد با یک مقایسه بزرگترین رو انتخاب می کنیم درسته ولی بعد شما اونو با ریشه جمع می کنین که این درست نیست چون ممکنه مسیر بزرگتر از ریشه عبور نکنه پس باید با تمام گره ها جمع بشه و بعد بزرگترین انتخاب بشه یعنی n مقایسه نه یکی پس رابطه بازگشتی می شه
T(N) = 2T(N/2) + n
که اینم از درجه nlogn
این مسئله رو میشه با مقایسه خونه های آرایه متناظر با این درخت هم حل کرد فکرکنم که مرتبش میشه n البته این نظر منه دوستای دیگم نظر بدن ببینیم چی میشه
سوال ۱۰۰ که واضحه n میشه - من بدجوری داغونم کل زمانم رفت واسه مشترک نه زبان زدم نه ریاضی از طرفی چون اونارو تایم نشد سر تخصصی ام انقدر عصبی بودم که گند زدم اینطورم که معلومه مشترکام به زور به ۵۰ درصد برسه تخصص ام ۲۵ درصد!! به نظرتون امیدی هست؟؟؟؟ کلیدا کی میاد بچه ها؟؟
(۲۲ بهمن ۱۳۹۱ ۰۴:۳۸ ب.ظ)arta.66 نوشته شده توسط: سوال ۱۰۰ که واضحه n میشه - من بدجوری داغونم کل زمانم رفت واسه مشترک نه زبان زدم نه ریاضی از طرفی چون اونارو تایم نشد سر تخصصی ام انقدر عصبی بودم که گند زدم اینطورم که معلومه مشترکام به زور به ۵۰ درصد برسه تخصص ام ۲۵ درصد!! به نظرتون امیدی هست؟؟؟؟ کلیدا کی میاد بچه ها؟؟
درصدات که عالیه.اگه واقعا اینجوری باشهمعدلتون هم خوب باشه رتبتون خیلی خوب میاد.
منم نرسیدم ریاضی و زبان بزنم لحظه ی آخر فکر کنم ۲ دقیقه مونده بود دفترچه رو بگیرن تونستم ۱ تست ریاضی و یه تست زبان بزنم.
درسدام فکر کنم اینجوری بشه:
زبان ۳/۳۳(۳ و ۳۳)
ریاضی ۵/۱۲(۵ و ۱۲)
مشترک ۳۱
تخصصی ۴۳
فکر کنم رتبم زیر ۵۰۰ بشه با احتساب معدلم!!!
(۲۲ بهمن ۱۳۹۱ ۰۱:۳۳ ب.ظ)sarous نوشته شده توسط: دوست عزیز دومی مکس هیپه.در مکس هیپ کوچکترین عنصر در یکی از برگهاس و معلوم نیست کدوم برگ که بخوای با زمان logn پیداش کنی.باید n/2 عناصر که برگ هستند مورد جستجو قرار بگیره و از مرتبه n هستش که قطعا این رو نمی توان ساخت.
اولیش هم که avl فرض میکنیم به ازای هر a و b دلخواه گفته در مرتبه logn هست.a رو ریشه avl فرض میکنیم و b رو فرزند چپ a,حالا باید چند تا از نودها بررسی بشه؟n-1 که از مرتبه n هست.
پس هر ۲ رو نمی توان ساخت.
معذرت می خوام منظورم مین هیپ در مین هیپ حذف قطعا logn هست چون درخت کامل است و حذف ریشه میکنیم و سپس از برگ ها به سمت ریشه مین هیپ را دوباره میسازیم و کوچترین همیشه در ریشه هست
در مورد Avl با طرز فکر شما شک کردم و شما درست می فرمایید به کلمه تعداد دقت نکرده بودم
طبق دفترچه B
۴۷ - ۴
۴۸ - ۴
۴۹ - ?
۵۰ - ۱
۵۱ - ۱
۵۲ - ?
۴۹-۵۲ رو یادم نیست چی زدم !
(۲۲ بهمن ۱۳۹۱ ۰۲:۴۰ ب.ظ)mfXpert نوشته شده توسط:(22 بهمن ۱۳۹۱ ۰۲:۳۷ ب.ظ)ADELZX نوشته شده توسط: خب چطور شما میفرمایید که میشه گره ریشه رو در کمتر از logn حذفش کرد ؟شما می‌تونید به من بگید تفاوت اصلی اوی کوچیک و بزرگ در چی هستش؟
چون اوی کوچک نوشته باید مرتبه الگوریتم کمتر از log باشه که برای مین هیپ نخواهد بود.
این جور سوالا منظورم سوالای ساخت یک ساختمان داده سخته و خیلی جواب دادن بهش ریسکیه.
(۲۲ بهمن ۱۳۹۱ ۰۲:۴۲ ب.ظ)ADELZX نوشته شده توسط: واسه جواب این تست همون تفاوت کوچیکتر و کوچیکتر مساوی رو هم در نظر بگیریم کامل جواب شما رد میشه.برای تعریف اوی کوچیک صرفا به حافظه خودم اعتماد کردم اما وقتی تعریف رو توی کتاب دیدم به اشتباه خودم پی بردم. حرف شما کاملا درسته و مین هیپ نخواهد بود.
(۲۲ بهمن ۱۳۹۱ ۰۸:۳۹ ب.ظ)mahdiii نوشته شده توسط: چون اوی کوچک نوشته باید مرتبه الگوریتم کمتر از log باشه که برای مین هیپ نخواهد بود.دوستان من حل دقیق heapify رو نمیدونم چی میشه ولی اگه از logn+1 هم بشه مرتبه میشه n حالا باقیش با شما
من جفتشم زدم نمی توان ولی الان فکر می کنم الف رو میتوان!!!
ولی تست مرتبسازی قطعا nk میشه شک نکنید روز قبل کنکور اینو خونده بودم
۴۸ ام یا یک میشه یا ۴ ولی من که خدا خدا میکنم یک باشه!!! ولی احتمال ۴ بیشتره مگه بازم معجزه بشه
(۲۲ بهمن ۱۳۹۱ ۰۹:۱۳ ب.ظ)arta.66 نوشته شده توسط:(22 بهمن ۱۳۹۱ ۰۸:۳۹ ب.ظ)mahdiii نوشته شده توسط: چون اوی کوچک نوشته باید مرتبه الگوریتم کمتر از log باشه که برای مین هیپ نخواهد بود.دوستان من حل دقیق heapify رو نمیدونم چی میشه ولی اگه از logn+1 هم بشه مرتبه میشه n حالا باقیش با شما
من جفتشم زدم نمی توان ولی الان فکر می کنم الف رو میتوان!!!
ولی تست مرتبسازی قطعا nk میشه شک نکنید روز قبل کنکور اینو خونده بودم
۴۸ ام یا یک میشه یا ۴ ولی من که خدا خدا میکنم یک باشه!!! ولی احتمال ۴ بیشتره مگه بازم معجزه بشه
میشه به من بگی سوال ۴۸ ( با دلیل ) چطوری می شه ۱ یا ۴!!! مطمین ترین راه عدد گذاریه... اگر به ازای n های بزرگ بررسی کنید میشه گزینه ۳ و اگر به ازای k های بزرگ بررسی کنید میشه یه چیزی بین گزینه ۲ یا ۳/// و اگر به ازای nوk برابر بررسی کنید میشه نزدیک گزینه ۳ حالا اگه راه دیگه ای به جز عددگذاری دارید بفرمایید بگید. آخه به ازای nk رشدش خیلی سریعه در صورتی که خاصیت این رابطه این طوری نیست
(۲۲ بهمن ۱۳۹۱ ۱۰:۴۶ ب.ظ)behnam001 نوشته شده توسط: میشه به من بگی سوال ۴۸ ( با دلیل ) چطوری می شه ۱ یا ۴!!! مطمین ترین راه عدد گذاریه... اگر به ازای n های بزرگ بررسی کنید میشه گزینه ۳ و اگر به ازای k های بزرگ بررسی کنید میشه یه چیزی بین گزینه ۲ یا ۳/// و اگر به ازای nوk برابر بررسی کنید میشه نزدیک گزینه ۳ حالا اگه راه دیگه ای به جز عددگذاری دارید بفرمایید بگید. آخه به ازای nk رشدش خیلی سریعه در صورتی که خاصیت این رابطه این طوری نیستدوست من این تست تکراریه با یه تفاوت که سال ۹۰ عمق درخت بازگشت رو خواسته بود که میشد جمع ۲تا لگاریتم که در واقع میشد log4+log2 یعنی عمق میشد هر کدوم که دیرتر به برگ می رسید!! البته میدونم واضح نگفتم ولی راحش همون درخت هست تفاوت سوال امسال این بود که مرتیه رو خواسته بود که میشه عمق درخت ضرب در بخش ناهمگن که همون nk هست و با این اوصاف جواب به گزینه ۴ خیلی نزدیک میشه ولی نمیدونم چرا یه حسی سر جلسه بهم گفت یه کرمی توو این سوال هست و من nk رو زدم ولی الان نظرم عوض شده!!! میگم ۴ میشه ولی بازم یه مشکلی توو ۴ هست و اونم فاکتورگیری که کرده هست و همین این احتمال رو بهم میده که جواب همون nk باشه!!!
تست ۴۸ شبیه کنکور سال ۹۰ هست.یک درخت رو میبایست بسط میدادیم و عمقش رو حساب میکردیم.اینجا هم مسئله فرقی نکرده.گزینه ۴ مثل جواب همون تست هست.
تست ۴۹ - ۲ - بخش "الف" که شبیه عملیات روی AVL هست. بخش "ب" غلطه.البته مرتبه ساخت و درج شبیه مین هیپ هست ولی حذف کوچکترین عنصر نیست.به نظر من میشه گزینه۲
در مورد تست ۵۰ نظری ندارید ؟
۵۲ هم من با کلی ترس و لرز زدم.دیدم دیگه زیادی آسونه.ولی آخرش زدم۲/یعنی همون مرتبه n
(۲۳ بهمن ۱۳۹۱ ۰۱:۱۱ ق.ظ)fatima1537 نوشته شده توسط: تست ۴۹ - ۲ - بخش "الف" که شبیه عملیات روی AVL هست. بخش "ب" غلطه.البته مرتبه ساخت و درج شبیه مین هیپ هست ولی حذف کوچکترین عنصر نیست.به نظر من میشه گزینه۲سوال ۴۹ الف مطمئنا غلطه!! حالا چرا یه مثال ساده میارم که نقض شه شما یه درخت متوازن با اعداد ۱ تا ۸ بساز!! ۵ میاد توو ریشه ۳و ۷ هم میشن فرزندان چپ و راستش!! وبه همین ترتیب!! حالا سوال من میگم تعداد اعداد ۲ تا ۸ رو واسه من پیدا کن؟؟؟چطوری با لگاریتم میشه؟؟؟ چون اعداد توو ۲تا زیردرختم هستن!! جواب گزینه ۴ هستش جفتش را نمی توان!!
سوال ۴۷ به نظرم گزینه درست نداره. این حالت رو در نظر بگیرید. ۹۹ تا push بعد یه pop. خب برای pop مجبوریم ۹۹ تا از استک اول pop کنیم و ۹۹ تا تو استک دوم push کنیم و در نهایت یه pop انجام بدیم که میشه ۹۹+۹۹+۹۹+۱=۳۹۸/
سوال ۵۱ هم اگه هزینه هر عمل رو ۲ در نظر بگیریم و هر دفعه یکی رو مصرف کنیم و یکی رو ذخیره وقتی که می خوایم جدول رو بزرگ یا کوچیک کنیم از دخایرمون استفاده میشه و هزینه ی اضافی نداره. بنابراین از تتای ۱ هستش.