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

[saho]

(۲۱ بهمن ۱۳۹۱ ۰۳:۰۱ ق.ظ)MR_KH نوشته شده توسط:  تحلیل من در مورد سوال ۳۷ اینه که اولا هیپ نیست و هرچند متوازنه ولی BST نیست که اعمال logn باشه ولی شبیه درخت مسابقات حذفی بین n شرکت کننده هست.
چون اعداد در برگها هستند برای حذف یک عدد باید از مکان n/2 (اگر ذخیره سازی آرایه ای باشد) جستجو کنیم پس تا اینجا (o(n تازه بعد باید بعد حذف ساختار درخت رو درست کنیم چون ممکنه این عدد درسطرهای بالاتر تکرار شده باشد و هم شکل درخت دوباره کامل شود، اگه ازساختار گره پیوندی هم استفاده بشه از logn بیشتر میشه.
برای درج چون باید عدد باید به عنوان یک برگ درج بشه بهترین حالت اینه که آخرین گره غیر برگ فرزند راست نداشته باشه و به جای فرزند راست آخرین گره غیر برگ درج خواهد شد و بعد هم باید با برادرش مقایسه شود تا در صورت کوچکتر بودن در والد تکرار شود تا ریشه ، پس logn ولی این بهترین حالت بود در حالتی که همه ی گره های داخلی دو فرزندی باشد باید ۲ گره به درخت اضافه بشه پس یا باید برگها رو یه واحد شیفت بدیم یا از اول درخت رو بسازیم که در هر صورت و با هر شیوه ذخیره سازی (o(n میشه.
برای کاهش یک عدد با فرض اینکه مکان مشخص باشد در بدترین حالت اگر عدد مینیموم باشد تا ریشه تکرار شده و باید اصلاح شود پس logn
امیدوارم این یکی گزینه ۲ باشه!

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

[mahdiii]

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

(21 بهمن ۱۳۹۱ ۰۳:۰۱ ق.ظ)MR_KH نوشته شده توسط:  تحلیل من در مورد سوال ۳۷ اینه که اولا هیپ نیست و هرچند متوازنه ولی BST نیست که اعمال logn باشه ولی شبیه درخت مسابقات حذفی بین n شرکت کننده هست.
چون اعداد در برگها هستند برای حذف یک عدد باید از مکان n/2 (اگر ذخیره سازی آرایه ای باشد) جستجو کنیم پس تا اینجا (o(n تازه بعد باید بعد حذف ساختار درخت رو درست کنیم چون ممکنه این عدد درسطرهای بالاتر تکرار شده باشد و هم شکل درخت دوباره کامل شود، اگه ازساختار گره پیوندی هم استفاده بشه از logn بیشتر میشه.
برای درج چون باید عدد باید به عنوان یک برگ درج بشه بهترین حالت اینه که آخرین گره غیر برگ فرزند راست نداشته باشه و به جای فرزند راست آخرین گره غیر برگ درج خواهد شد و بعد هم باید با برادرش مقایسه شود تا در صورت کوچکتر بودن در والد تکرار شود تا ریشه ، پس logn ولی این بهترین حالت بود در حالتی که همه ی گره های داخلی دو فرزندی باشد باید ۲ گره به درخت اضافه بشه پس یا باید برگها رو یه واحد شیفت بدیم یا از اول درخت رو بسازیم که در هر صورت و با هر شیوه ذخیره سازی (o(n میشه.
برای کاهش یک عدد با فرض اینکه مکان مشخص باشد در بدترین حالت اگر عدد مینیموم باشد تا ریشه تکرار شده و باید اصلاح شود پس logn
امیدوارم این یکی گزینه ۲ باشه!

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

لازم نیست برای درج در این مکان دو گره اضافه بشه؟!!!!!!!!!
همون گره رو اضافه می کنیم و چون یدونست(تعداد فرزندان ) (بنا به صورت سوال که گفته کمترین مقدار از فرزندان به پدر تعلق می گیره)مقدار اون به پدرش میرسه و این کار تا بالا ادامه پیدا می کنه.
در مورد تغییر هم خوبه خودتون گفتید اگه فرض کنیم جاشو بدونیم. ما چطور می تونیم این فرضو از خودمون کنیم در صورتی که سوال هیچی نگفته؟!!!

[csharpisatechnology]

دوستان عزیز ننویسید ۱و۲و۳و۴و۵
--
هر سوالی رو که دارید پاسخ می دید شماره ی دقیق سوال رو بنویسید تا ما گیج نشیم. با تشکر.

---

من ۳۷ رو زدم ۴ نمیدونم درسته یا نه

---

۳۸ رو زدم ۱ فکر کنم

---

۳۹ چی میشد؟

---

۴۲و۴۴و۴۵ رو کی بلده؟

[MR_KH]

(۲۱ بهمن ۱۳۹۱ ۰۳:۳۲ ق.ظ)mahdiii نوشته شده توسط:  لازم نیست برای درج در این مکان دو گره اضافه بشه؟!!!!!!!!!
همون گره رو اضافه می کنیم و چون یدونست(تعداد فرزندان ) (بنا به صورت سوال که گفته کمترین مقدار از فرزندان به پدر تعلق می گیره)مقدار اون به پدرش میرسه و این کار تا بالا ادامه پیدا می کنه.
در مورد تغییر هم خوبه خودتون گفتید اگه فرض کنیم جاشو بدونیم. ما چطور می تونیم این فرضو از خودمون کنیم در صورتی که سوال هیچی نگفته؟!!!

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

[mahdiii]

(۲۱ بهمن ۱۳۹۱ ۰۳:۵۲ ق.ظ)MR_KH نوشته شده توسط:  برای درج یه عدد جدید نمیشه عدد رو فرزند یک برگ قرار داد چون دیگه اون وقت اون گره دیگه برگ نیست ولی صورت سوال گفته عددها در برگها هستند در ثانی چون گره درج شده برادر نداره مقدارش به والدش منتقل میشه و اونوقت داده ی والد رو از دست میدین پس باید تعداد برگها یک واحد افزایش پیدا کنه پس تعداد گره های داخلی هم باید یکی زیاد بشه (این برای حالتی بود که آخرین گره غیربرگ دو فرزند دارد)

مساله رو خیلی پیچیده می کنین. خوب برادر نداشته باشه. اون موقع که مقایسه بین دو برادر انجام میشد مگه چی میشد؟ اون یکی که کوچکتر بود میومد جای پدر. خوب داده پدر از دست میره مشکل چیه؟ حالا هم جایگزین میشه و داده پدر از دست میره. اگه می خواین از دست نره اونو تو گره ی بعدی بگذارین. خیلی راحت می تونید اونو(مقدار پدر رو بگذارید تو گره آخر)

---

(۲۱ بهمن ۱۳۹۱ ۰۳:۴۱ ق.ظ)csharpisatechnology نوشته شده توسط:  دوستان عزیز ننویسید ۱و۲و۳و۴و۵
--
هر سوالی رو که دارید پاسخ می دید شماره ی دقیق سوال رو بنویسید تا ما گیج نشیم. با تشکر.

---

من ۳۷ رو زدم ۴ نمیدونم درسته یا نه

---

۳۸ رو زدم ۱ فکر کنم

---

۳۹ چی میشد؟

---

۴۲و۴۴و۴۵ رو کی بلده؟

من که جواب داده بودم
۴۲-۲ الگوریتمشو می دونم
۴۴-۳ با نظر بچه ها

[MR_KH]

(۲۱ بهمن ۱۳۹۱ ۰۴:۰۶ ق.ظ)mahdiii نوشته شده توسط:  مساله رو خیلی پیچیده می کنین. خوب برادر نداشته باشه. اون موقع که مقایسه بین دو برادر انجام میشد مگه چی میشد؟ اون یکی که کوچکتر بود میومد جای پدر. خوب داده پدر از دست میره مشکل چیه؟ حالا هم جایگزین میشه و داده پدر از دست میره. اگه می خواین از دست نره اونو تو گره ی بعدی بگذارین. خیلی راحت می تونید اونو(مقدار پدر رو بگذارید تو گره آخر)

دوست عزیز من میگم تویه n تا نود برگ نمیشه n+1 عدد قرار داد شما ساختار. رو درست متوجه نمیشین
برای درج میشه یه بهینه سازی انجام داد. درحالتی که آخرین گره غیر برگ یک فرزند داشته باشه که به راحتی درج میشه ودر logn ساختار تصحیح میشه ولی در حلتی که دو فرزند داشته باشه به سراغ اولین برگ میریم و دو فرزندش رو رسم میکنیم تو یکی مقدار خودش و دیگری رو عدد جدید رو میزاریم و تصحیح می کنیم و در کل هم میشه logn . پس دو گره یه درخت اضافه شد

[mohammadjavadkho]

(۲۱ بهمن ۱۳۹۱ ۰۳:۰۱ ق.ظ)MR_KH نوشته شده توسط:  تحلیل من در مورد سوال ۳۷ اینه که اولا هیپ نیست و هرچند متوازنه ولی BST نیست که اعمال logn باشه ولی شبیه درخت مسابقات حذفی بین n شرکت کننده هست.
چون اعداد در برگها هستند برای حذف یک عدد باید از مکان n/2 (اگر ذخیره سازی آرایه ای باشد) جستجو کنیم پس تا اینجا (o(n تازه بعد باید بعد حذف ساختار درخت رو درست کنیم چون ممکنه این عدد درسطرهای بالاتر تکرار شده باشد و هم شکل درخت دوباره کامل شود، اگه ازساختار گره پیوندی هم استفاده بشه از logn بیشتر میشه.
برای درج چون باید عدد باید به عنوان یک برگ درج بشه بهترین حالت اینه که آخرین گره غیر برگ فرزند راست نداشته باشه و به جای فرزند راست آخرین گره غیر برگ درج خواهد شد و بعد هم باید با برادرش مقایسه شود تا در صورت کوچکتر بودن در والد تکرار شود تا ریشه ، پس logn ولی این بهترین حالت بود در حالتی که همه ی گره های داخلی دو فرزندی باشد باید ۲ گره به درخت اضافه بشه پس یا باید برگها رو یه واحد شیفت بدیم یا از اول درخت رو بسازیم که در هر صورت و با هر شیوه ذخیره سازی (o(n میشه.
برای کاهش یک عدد با فرض اینکه مکان مشخص باشد در بدترین حالت اگر عدد مینیموم باشد تا ریشه تکرار شده و باید اصلاح شود پس logn
امیدوارم این یکی گزینه ۲ باشه!

ببین دوست عزیز حتی اگر درخت پر هم باشه میشه با log n درج کرد.ما میایم اولین برگ رو حذف میکنیم یعنی برای اولین برگ از سمت چپ دو تا فرزند در نظر میگیریم .مقدار این فرزند ها هم یکیش میشه مقدار همین برگ و یکی هم میشه مقدار گره ی جدیدی که میخواییم اضافه کنیم.بعدش مینیمم این دو تا رو میزاریم جای اون گره برگی که براش دو تا فرزند گذاشتیم.بعدش با log n تا ریشه رو چک میکنیم که درست باشه.پس میشه با log n درج رو هم انجام داد.

[MR_KH]

(۲۱ بهمن ۱۳۹۱ ۱۱:۵۹ ق.ظ)mohammadjavadkho نوشته شده توسط:  ببین دوست عزیز حتی اگر درخت پر هم باشه میشه با log n درج کرد.ما میایم اولین برگ رو حذف میکنیم یعنی برای اولین برگ از سمت چپ دو تا فرزند در نظر میگیریم .مقدار این فرزند ها هم یکیش میشه مقدار همین برگ و یکی هم میشه مقدار گره ی جدیدی که میخواییم اضافه کنیم.بعدش مینیمم این دو تا رو میزاریم جای اون گره برگی که براش دو تا فرزند گذاشتیم.بعدش با log n تا ریشه رو چک میکنیم که درست باشه.پس میشه با log n درج رو هم انجام داد.

منم که درج رو تصحیح کردم همینو بالا گفتم

[osho]

سوال ۴۵ طراحی الگوریتم زیر دنباله مشترک از مرتبه n^2 و از روش برنامه ریزی پویا است کسی نظری نداره این سوال مستقیما تو کتاب طراحی هادی یوسفی است.

---

سوال ۴۳ طراحی الگوریتم
باید n بار dfs بزنی که مرتبه آن از فلوید که n^ 3 کمتر است.
سوال ۴۲ n+klogk و قسمت دوم n میشه
سوال ۳۹ تو کتاب جدید قدسی است که میشه n\2,m\2 +log(m)+1 میشه.

[xani]

(۲۱ بهمن ۱۳۹۱ ۰۲:۲۲ ب.ظ)osho نوشته شده توسط:  سوال ۴۵ طراحی الگوریتم زیر دنباله مشترک از مرتبه n^2 و از روش برنامه ریزی پویا است کسی نظری نداره این سوال مستقیما تو کتاب طراحی هادی یوسفی است.

منم ۴۵ همین گزینه رو زدم

---

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

(20 بهمن ۱۳۹۱ ۰۴:۳۶ ب.ظ)IT86 نوشته شده توسط:  دوستان اگر avl هم درنظربگیریم حذف و درج و جستجو میشه log n
برای کاهش فک کنم بشه بازم log n آخه گفته شده کوچکترین فرزند در ریشه هستش ااگرکاهش بدیم یک مقداررو ممکنه اون مقدارازریشه کمترشه و باید جابه جابشه
ازطرفیم ممکنه باز پدراون ریشه هم بزرگترباشه و بازهم جابه جامیشه
بازم میشه log n
پس هرشه بازم میشه اگرهیپ درنظرنگیریم
هیپ درنظربگیریمم میشه هرسه
مگر اینکه درخت انتخابی بگیریم ک بستگی داره به تعداد آرایه ها که باتوجه به سوال ک ذکرنکرده از ارایه پس انتخابی نمیشه

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

---

(۲۰ بهمن ۱۳۹۱ ۰۶:۰۶ ب.ظ)IT86 نوشته شده توسط:  بله دوست عزیز گفته شده اگرسطح آخر رو بردارین میشه درخت دودویی متوازن
درثانی کی حرف از جستجو زد؟
خود سوال گفته شده درخت دودویی کامل هستش اگر سطح آخر رو برداری میشه متوازن
این تعریف واضحه
دوست عزیز شما بیشتر گویا پافشاری میکنی و صورت سوالو متوجه نشدی!

شما خودت گفتی AVLهست.
الآن داری میگی کی گفته درخت جستجوی دودویی(BST)؟!!!
من تعریف AVL رو گفتم. گویا شما تعریف درستی از AVL ندارید.

درخت AVL
درختی است که از نظر ارتفاع زیر درخت‌هایش متوازن است‌

تعریف
یک درخت تهی متوازن است‌
اگر T یک درخت دودویی ناتهی باشد که دو زیر درخت TL و TR دارد، آنگاه T درختی با ارتفاع متوازن است، اگر و تنها اگر:
TL و TR هر دو متوازن باشند
اختلاف ارتفاع آنها کوچک‌تر یا برابر با ۱ باشد

شما میگی avl نیست باشه نیست (به نظر من که هست)

[saho]

سوال ۳۷ که ظاهرا ختم بخیرشد.
درمورد سوال گوی های مثبت منفی نظرتون چیه؟
من هرطور حساب میکنم n-1نمیشه
یه مثال ساده داشتن ۳ گوی که مسلما دوتاش مثبته وبهترین حالتشه اینکه اول همین دوتا را نزدیک هم کنیم .
پس بایک بار امتحان که به n/2نزدیکتره.(سوال گفته دست کم)

[mahdiii]

(۲۱ بهمن ۱۳۹۱ ۰۵:۳۲ ب.ظ)xani نوشته شده توسط:  درخت AVL
درختی است که از نظر ارتفاع زیر درخت‌هایش متوازن است‌

گفتم نمی دونید AVL چیه؟ تعریف شما اشتباهه. من دیگه حوصلم سر رفت. زیاد الکی بحث کردم. تو تمام کتابها مثل قدسی، مقسمی و پوران و پارسه و ... این طوری تعریف کردند. من دقیقا جمله ای که تو یکی از این کتابها "مقسمی"هستو براتون میارم.
صفحه ۲۸۶ چاپ ششم درس و کنور ساختمان داده مقسمی
"درخت AVL درخت دودویی جستجویی است که ارتفاع آن متوازن باشد."
درخت دودویی جستجو هم اگه تعریفشو نمی دونید بگم.
درخت دودویی جستجو با درخت دودویی کاملا متفاوته
دیگه نمی دونم چه جوری باید بگم.

[saho]

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

(21 بهمن ۱۳۹۱ ۰۵:۳۲ ب.ظ)xani نوشته شده توسط:  درخت AVL
درختی است که از نظر ارتفاع زیر درخت‌هایش متوازن است‌

گفتم نمی دونید AVL چیه؟ تعریف شما اشتباهه. من دیگه حوصلم سر رفت. زیاد الکی بحث کردم. تو تمام کتابها مثل قدسی، مقسمی و پوران و پارسه و ... این طوری تعریف کردند. من دقیقا جمله ای که تو یکی از این کتابها "مقسمی"هستو براتون میارم.
صفحه ۲۸۶ چاپ ششم درس و کنور ساختمان داده مقسمی
"درخت AVL درخت دودویی جستجویی است که ارتفاع آن متوازن باشد."
درخت دودویی جستجو هم اگه تعریفشو نمی دونید بگم.
درخت دودویی جستجو با درخت دودویی کاملا متفاوته
دیگه نمی دونم چه جوری باید بگم.

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

[mahdiii]

(۲۱ بهمن ۱۳۹۱ ۰۷:۱۰ ب.ظ)saho نوشته شده توسط:  سوال ۳۷ که ظاهرا ختم بخیرشد.
درمورد سوال گوی های مثبت منفی نظرتون چیه؟
من هرطور حساب میکنم n-1نمیشه
یه مثال ساده داشتن ۳ گوی که مسلما دوتاش مثبته وبهترین حالتشه اینکه اول همین دوتا را نزدیک هم کنیم .
پس بایک بار امتحان که به n/2نزدیکتره.(سوال گفته دست کم)

آره برای این مثال (۳ گوی) با یه مقایسه میشه. کلا سوالا غیر استاندارده. باید می گفت تعداد گویها ۳=<
شما برای ۵ و بعد از اون دیگه نمی تونید با n/2 به نتیجه برسید.
به عنوان مثال برای ۵ (شما نمی دونید که ۴ و ۱ هست یا ۳ و ۲) بنابراین باید همون n-1 مقایسه رو انجام بدید حداقل که زمانی هست که گویهای با بار موافق با هم مقایسه می شوند.

[saho]

---

[/quote]آره برای این مثال (۳ گوی) با یه مقایسه میشه. کلا سوالا غیر استاندارده. باید می گفت تعداد گویها ۳=<
شما برای ۵ و بعد از اون دیگه نمی تونید با n/2 به نتیجه برسید.
به عنوان مثال برای ۵ (شما نمی دونید که ۴ و ۱ هست یا ۳ و ۲) بنابراین باید همون n-1 مقایسه رو انجام بدید حداقل که زمانی هست که گویهای با بار موافق با هم مقایسه می شوند.
[/quote]
نه واسه ۵ هم میشه ۳تا در حالت حداقل که بازم n-1 نمیشه وبه ۲/۵ نزدیکتره

---

ا به ۳ گروه تقسیم میکنیم.
۲جفت بارشون همنامه.یک منفی هم تنها(بازم میگم گفته دست کم پس بهترینوباید بگیریم)
حالا با دوبار امتحان میفهمیم که ۲گروه انتخاب شده یاهردومثبتن یا هم یک گروه منفی ویک گروه مثبت.مطمئنا اون تکیه منفیه.
حالا از هرگروه یک گوی برداشته وبهم نزدیک میکنیم اگه جذب کردن که میشه ۲تا مثبت و ۳تا منفی واگر دفع یعنی ۴ تا مثبت و یکی منفی
(بازم میگم گفته دست کم منم بهترین حالتوگرفتم)
این تحلیل من بود که اصلا n-1 نشد.وبهn/2نزدیکتره