انجمنصفحه اولجستجوی انجمن

[Mahdi .Tahmouresi]

دوستان سئوال ۴۷ مثل اینکه طلبه زیاد داره جواب صحیح گزینه هیچکدام می باشد و پاسخ صحیح ۱۴۹ هست حالا چرا؟ لطفا مطلب پایین را بخوانید.
تو صورت سئوال گفته هر push و pop رو هر استک ۱ واحد یعنی مجموع این دو عمل ۱ واحد و گفته که بشترین هزینه برای ۱۰۰ عمل که خیلی ساده می توانید حساب کنید، ابتدا ۹۹ عمل push به استک اول حالا عمل آخر از اون ۱۰۰ عمل را انجام می دیم یعنی حذف چون استک دومی خالی مجبوریم ۹۹ pop از استک اول انجام دهیم و سپس ۹۹ Push به استک دوم و در آخر ۱ pop از استک دوم حالا تعداد push و pop ها را جمع می کنیم ۹۹+۹۹+۹۹+۱=۲۹۸ حاصل را بر ۲ تقسیم می کنیم چرا که هر ۲ عمل push و pop یک واحد بود و نتیجه می شود ۱۴۹!!!
توضیح برای آن دساه از دوستان که میگن خیر هر عمل یک واحد خیلی ساده باید بگم به شما که اگر این طور هم فرض کنیم جواب می شود ۲۹۸ حد اکثر هزینه را خواسته
موفق و سربلند باشید

[oli92]

(۲۳ بهمن ۱۳۹۱ ۱۲:۰۷ ب.ظ)arta.66 نوشته شده توسط:  

(23 بهمن ۱۳۹۱ ۰۱:۱۱ ق.ظ)fatima1537 نوشته شده توسط:  تست ۴۹ - ۲ - بخش "الف" که شبیه عملیات روی AVL هست.

سوال ۴۹ الف مطمئنا غلطه!! حالا چرا یه مثال ساده میارم که نقض شه شما یه درخت متوازن با اعداد ۱ تا ۸ بساز!! ۵ میاد توو ریشه ۳و ۷ هم میشن فرزندان چپ و راستش!! وبه همین ترتیب!! حالا سوال من میگم تعداد اعداد ۲ تا ۸ رو واسه من پیدا کن؟؟؟چطوری با لگاریتم میشه؟؟؟ چون اعداد توو ۲تا زیردرختم هستن!! جواب گزینه ۴ هستش جفتش را نمی توان!!

برای بدست آوردن تعداد عناصر بین دو عدد نیاز نیست کل درخت رو پیمایش کنی. اگه برای هر گره تعداد فرزندان چپ و راستش رو نگه داری، بعد از عدد کوچیکه به سمت عدد بزرگه حرکت کنی (حداکثر lgn تا می ری بالا و lgn تا میای پایین) می شه تعدادشون رو بدست آورد.

[mahdiii]

(۲۳ بهمن ۱۳۹۱ ۱۲:۰۷ ب.ظ)arta.66 نوشته شده توسط:  

(23 بهمن ۱۳۹۱ ۰۱:۱۱ ق.ظ)fatima1537 نوشته شده توسط:  تست ۴۹ - ۲ - بخش "الف" که شبیه عملیات روی AVL هست. بخش "ب" غلطه.البته مرتبه ساخت و درج شبیه مین هیپ هست ولی حذف کوچکترین عنصر نیست.به نظر من میشه گزینه۲

سوال ۴۹ الف مطمئنا غلطه!! حالا چرا یه مثال ساده میارم که نقض شه شما یه درخت متوازن با اعداد ۱ تا ۸ بساز!! ۵ میاد توو ریشه ۳و ۷ هم میشن فرزندان چپ و راستش!! وبه همین ترتیب!! حالا سوال من میگم تعداد اعداد ۲ تا ۸ رو واسه من پیدا کن؟؟؟چطوری با لگاریتم میشه؟؟؟ چون اعداد توو ۲تا زیردرختم هستن!! جواب گزینه ۴ هستش جفتش را نمی توان!!

با ساخت درخت AVL با یه تغییراتی فکر کنم بشه. در زمان ساخت برای هر گره تعداد فرزندان چپ و راستش را نگه می داریم. همچنین برای هر گره بازه ای را که اعداد بعدی می توانند بیایند (در زیردرخت چپ و راست آن گره) نگه می داریم. برای ریشه این بازه از منهای بینهایت تا بینهایت است. حال برای پیداکردن تعداد اعداد میان a تا b ابتدا با logn را a می یابیم. همچنین با log b را.
حال برای هر گره a و b تنها کافیست بر روی مسیری پیمایش کنیم تا ما را به جد مشترک آنها برساند. اگر a و b در دو زیردرخت راست و چپ ریشه باشند باید مسیری که ما را به ریشه می رساند که از مرتبه log است را برای دو گره پیمایش کنیم. با داشتن اطلاعات بازه و تعداد فرزندان چپ و راست برای هر گره بدون نیاز به گشتن زیردرختها می توان با مرتبه log تعداد اعداد بین a,b را محاسبه کرد.

[sarous]

(۲۲ بهمن ۱۳۹۱ ۰۷:۵۲ ب.ظ)vahidfrr نوشته شده توسط:  

(22 بهمن ۱۳۹۱ ۰۱:۳۳ ب.ظ)sarous نوشته شده توسط:  دوست عزیز دومی مکس هیپه.
پس هر ۲ رو نمی توان ساخت.

معذرت می خوام منظورم مین هیپ در مین هیپ حذف قطعا logn هست

در مورد مین هیپ,حذف از مرتبه O(logn)هستش نه اوی کوچک.

fatima1537، در تاریخ ۲۳ بهمن ۱۳۹۱ ۱۱:۵۱ ب.ظ برای این مطلب یک پانوشت گذاشته است:

لطفا نقل قول طولانی نکنید.دیدن صفحه رو خسته کننده میکنه.

[MajidManesht2012]

حل سوال ۴۸ ساختمان نرم افزار - گزینه ۱ دفترچه B

DS - 48.pdf
اندازه فایل: ۶۲/۵۱ KB

[mahdiii]

(۲۳ بهمن ۱۳۹۱ ۰۶:۱۱ ب.ظ)sarous نوشته شده توسط:  در مورد مین هیپ,حذف از مرتبه O(logn)هستش نه اوی کوچک.البته بعضی از اساتید بین این دو فرقی قائل نمیشن و بعضی میشن.بستگی به طرح داره که نظرش روی این باشه که یکی هستند یا نه.اگه اینطور باشه جواب صحیحه.

تا اونجایی که من میدونم هیچ کسی این دو تا رو با هم یکی نمیدونه.

[MajidManesht2012]

(۲۲ بهمن ۱۳۹۱ ۱۰:۴۶ ب.ظ)behnam001 نوشته شده توسط:  

(22 بهمن ۱۳۹۱ ۰۹:۱۳ ب.ظ)arta.66 نوشته شده توسط:  

(22 بهمن ۱۳۹۱ ۰۸:۳۹ ب.ظ)mahdiii نوشته شده توسط:  چون اوی کوچک نوشته باید مرتبه الگوریتم کمتر از log باشه که برای مین هیپ نخواهد بود.

دوستان من حل دقیق heapify رو نمیدونم چی میشه ولی اگه از logn+1 هم بشه مرتبه میشه n حالا باقیش با شما
من جفتشم زدم نمی توان ولی الان فکر می کنم الف رو میتوان!!!
ولی تست مرتبسازی قطعا nk میشه شک نکنید روز قبل کنکور اینو خونده بودم
۴۸ ام یا یک میشه یا ۴ ولی من که خدا خدا میکنم یک باشه!!! ولی احتمال ۴ بیشتره مگه بازم معجزه بشه

میشه به من بگی سوال ۴۸ ( با دلیل ) چطوری می شه ۱ یا ۴!!! مطمین ترین راه عدد گذاریه... اگر به ازای n های بزرگ بررسی کنید میشه گزینه ۳ و اگر به ازای k های بزرگ بررسی کنید میشه یه چیزی بین گزینه ۲ یا ۳/// و اگر به ازای nوk برابر بررسی کنید میشه نزدیک گزینه ۳ حالا اگه راه دیگه ای به جز عددگذاری دارید بفرمایید بگید. آخه به ازای nk رشدش خیلی سریعه در صورتی که خاصیت این رابطه این طوری نیست

جواب سوال ۵۰ میشه nlogk - داده سهختار و مبانی الگوریتم ها دکتر قدسی ص ۳۶۷ تمرین ۱/۶ - فقط کافیه تو اون تمرین به جای
logn که داره k بزارین

---

سلام بچه ها
جواب سوال ۵۰ میشه nlogk - داده سختار و مبانی الگوریتم ها دکتر قدسی ص ۳۶۷ تمرین ۱/۶ - فقط کافیه تو اون تمرین به جای
logn که داره k بزارین

---

جواب سوال ۵۰ میشه nlogk - داده سهختار و مبانی الگوریتم ها دکتر قدسی ص ۳۶۷ تمرین ۱/۶ - فقط کافیه تو اون تمرین به جای
logn که داره k بزارین

[azad_ahmadi]

(۲۳ بهمن ۱۳۹۱ ۰۱:۱۱ ق.ظ)fatima1537 نوشته شده توسط:  در مورد تست ۵۰ نظری ندارید ؟

تست ۵۰ هم تکراری بود. دقیقا نمی دونم مال کدوم سال اما منظور از سوال مرتب سازی پایه، Radix sort هست که میشه با تتا n انجام داد.
بر طبق دفترچه B جواب گزینه ۱ میشه. (مشترک رو همین یه دونه اشتباه کردم )

[arta.66]

در مورد سوال ۵۰ اگه nk نشه یعنی من هیچی از این رشته و مجانبها نفهمیدم!! ببین دوستی که میگی میشه nlogk و استناد میکنی به کتاب دکتر قدسی - nlgn با دnlgk یه دنیا فرقشه چون این دوتا کامل از هم مستقلا وقتی صورت سوال میگه اعداد در بازه n^k تا ۰ یعنی اگه حتی k مساوی ۱۰۰۰۰ هم باشه مرتبه میشه خطی میشه!! ولی با تفسیر شما دیگه خطی نیست!!! شک نکنید که جواب nk هستش اگه ۱ درصدم جواب نباشه جواب n میشه نه اونی که شما میگی چون لگاریتم توو این مبحث بی معنیه چون مقایسه ای درکار نیست

[azad_ahmadi]

سوال ۵۰ رو همونطور که گفتم دقیقا و بدون تغییر برای یکی از کنکورهای سالهای قبل داده بودن. که کتاب ساختمان داده پارسه و همچنین پوران تتا n رو انتخاب کرده.

[MajidManesht2012]

(۲۴ بهمن ۱۳۹۱ ۱۲:۰۳ ب.ظ)arta.66 نوشته شده توسط:  در مورد سوال ۵۰ اگه nk نشه یعنی من هیچی از این رشته و مجانبها نفهمیدم!! ببین دوستی که میگی میشه nlogk و استناد میکنی به کتاب دکتر قدسی - nlgn با دnlgk یه دنیا فرقشه چون این دوتا کامل از هم مستقلا وقتی صورت سوال میگه اعداد در بازه n^k تا ۰ یعنی اگه حتی k مساوی ۱۰۰۰۰ هم باشه مرتبه میشه خطی میشه!! ولی با تفسیر شما دیگه خطی نیست!!! شک نکنید که جواب nk هستش اگه ۱ درصدم جواب نباشه جواب n میشه نه اونی که شما میگی چون لگاریتم توو این مبحث بی معنیه چون مقایسه ای درکار نیست

شما معلومه که اصلا" ساختمان داده بلد نیستی، تو کتاب ساختمان دکتر قدسی گفته برای اعداد در بازه ۱ تا [tex]n^{logn}[/tex] میشه با [tex]O(nloglogn)[/tex] مرتب کرد حالا نگاه کن بین ۱ تا [tex]n^{k}[/tex] من حالا به جای logn داخلی تو اون قبلیه K میزارم دقت کن، میشه [tex]nlogK[/tex] ببین عزیزم اینجا دوتا log داریم! گرفتی؟

اون برادر ...ک میگی سوال گفته مرتب سازی پایه کجا نوشته چرا از خودت حرف در میاری، چشاتو خوب باز کن، تازه یه نکته کنکوری بهتون بگم هروقت تو گزینه ها nlogk دیدین همونو بزنین چون این سوالا مال دکتر قدسی کاملا هم مشخصه

[MajidManesht2012]

(۲۴ بهمن ۱۳۹۱ ۱۲:۴۲ ب.ظ)MajidManesht2012 نوشته شده توسط:  

(24 بهمن ۱۳۹۱ ۱۲:۰۳ ب.ظ)arta.66 نوشته شده توسط:  در مورد سوال ۵۰ اگه nk نشه یعنی من هیچی از این رشته و مجانبها نفهمیدم!! ببین دوستی که میگی میشه nlogk و استناد میکنی به کتاب دکتر قدسی - nlgn با دnlgk یه دنیا فرقشه چون این دوتا کامل از هم مستقلا وقتی صورت سوال میگه اعداد در بازه n^k تا ۰ یعنی اگه حتی k مساوی ۱۰۰۰۰ هم باشه مرتبه میشه خطی میشه!! ولی با تفسیر شما دیگه خطی نیست!!! شک نکنید که جواب nk هستش اگه ۱ درصدم جواب نباشه جواب n میشه نه اونی که شما میگی چون لگاریتم توو این مبحث بی معنیه چون مقایسه ای درکار نیست

شما معلومه که اصلا" ساختمان داده بلد نیستی، تو کتاب ساختمان دکتر قدسی گفته برای اعداد در بازه ۱ تا [tex]n^{logn}[/tex] میشه با [tex]O(nloglogn)[/tex] مرتب کرد حالا نگاه کن بین ۱ تا [tex]n^{k}[/tex] من حالا به جای logn داخلی تو اون قبلیه K میزارم دقت کن، میشه [tex]nlogK[/tex] ببین عزیزم اینجا دوتا log داریم! گرفتی؟

اون برادر ...ک میگی سوال گفته مرتب سازی پایه کجا نوشته چرا از خودت حرف در میاری، چشاتو خوب باز کن، تازه یه نکته کنکوری بهتون بگم هروقت تو گزینه ها nlogk دیدین همونو بزنین چون این سوالا مال دکتر قدسی کاملا هم مشخصه

تازه تو سوال هیچ صحبتی از مستقل بودن K نکرده یعنی اگر شما به جای K بیای n بزاری مسلما" اون گزینه ۳ میشه [tex]O(n^{2})[/tex] که بدتر از همه گزینه هاست پس مسلما" nk نمیشه. و همینطور اگر K رو [tex]n^{2}[/tex] بگیری گزینه ۲ رد میشه پس میمونه گزینه ۱ و ۴ که گزینه ۱ نمیشه چون اگر بگیم Radix زده پس مرتبه Radix میدونی که میانگین برای n تا عدد در بازه ۱ تا [tex]n^{k}[/tex] میشه [tex]\Theta (k(n n))=\Theta (2kn)=\Theta (nk)[/tex] پس به هیچ وجه گ ۱ نمیشه حالا تازه فرض کردیم که K مستقل از n باشه یعنی خوشبینانه نگاه کردیم ولی بچه ها یه چیز دیگه هم هست اینه که این سوال اصلا ربطی به Radix نداره چون این سوالا مال فصل مرتب سازی خارجی دکتر قدسی خ تابلو هم هست همون nlogk درسته! یاحق

[azad_ahmadi]

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

[edge]

مطمئن باش nk میشه این روش راه حلش اینه n به توان k رو به صورت یه عدد k رقمی در مبنای n در نظر میگیریم .مثه n2 که میتونیم به صورت یه عدد دورقمی در مبنای n بنویسیم که میشه o(n) این هم میشه nk.

بیشتر اگه میخوای خیالت راحت بشه این لینکو نگاه کن

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

[MajidManesht2012]

(۲۴ بهمن ۱۳۹۱ ۰۱:۴۰ ب.ظ)edge نوشته شده توسط:  مطمئن باش nk میشه این روش راه حلش اینه n به توان k رو به صورت یه عدد k رقمی در مبنای n در نظر میگیریم .مثه n2 که میتونیم به صورت یه عدد دورقمی در مبنای n بنویسیم که میشه o(n) این هم میشه nk.

بیشتر اگه میخوای خیالت راحت بشه این لینکو نگاه کن

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

ممنون از این pdf حالا دیگه کاملا" مطمئن شدم ج همون nlogk