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

[Farid_Feyzi]

در مورد سوال ۴۸ با چند مثال میشه همه گزینه ها بجز گزینه ۳ رو رد کرد.

[SoheilGh]

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

توضیحاتی راجع به سوال ۴۷ ساختمان و الگوریتم آی تی

با توجه به توضیحاتی که دکتر قدسی دادن قضیه به این صورته

۱-اگه عنصری فراوانیش بیشتر از ۲/۵ باشه حتما تو عمق ۱ قرار میگیره و طول کدش یک نویسه ای خواهد بود.

۲- اگه فراوانی همه عناصر کمتر از ۱/۳ باشه هیچ عنصری تو عمق یک قرار نمیگیره و عنصری با طول کد یک نویسه ای نخواهیم داشت.

پس قسمت اول درست و قسمت دوم نادرست خواهد بود که گزینه ۲ جواب صحیحه.

رشته ای به طول ۱۰۰

۴۱ کاراکتر A
۴۱ کاراکتر B
۱۸ کاراکتر C


A و B فراوانیشون هر دو از ۲/۵ بیشتره ولی یکیشون ۱ بیت میشه یکی دیگه ۲ بیت!

[beniamin]

۳۷- ۴ همون درخت هیپه پس کل این اعمال در logn انجام میگیره
۳۸- ۱ فقط گزینه آخر درسته
۳۹- نزدم
۲-۴۰
۳-۴۱
۴-۴۲ اولی رو ابتدا توسط الگوریتم کامین کوچکترین عنصر با مرتبه n کامین عنصر رو پیدا میکنیم و پارتیشن میکنیم حال kعنصر ابتدای آرایه را با quick sort با مرتبه klogk مرتب میکنیم پس در کل میشود n+klogk و این kعنصر مرتب شده ابتدای آرایه همان عناصر i1 تا ik هستند. برای بخش دوم هم با همین الگوریتم ابتدا با مرتبه n میانه را یافته پارتیشن میکنیم و حال نیمه اول آرایه را با مرتبه nlogn مرتب میکنیم در این بخش مرتب شده عناصر خواسته شده را مبتوان با مرتبه ۱ بدست آورد پس در کل میشود n+nlogn که آن هم از مرتبه nlogn است.
۱-۴۳ bfs گرهها را گسترش میدهد و به اولین گره خاکستری که برخورد کند دور را تشخیس داده حال اگر تعداد فردی گره دیده باشد دور زوج را تشخیص داده .
۲-۴۷ من با مثال اثباتش کردم
۴۸- بین ۱و۳ شک داشتم فک کنم ۱ رو زدم

[Farid_Feyzi]

سهیل جان حق با شماس، درواقع بهتره بگیم حداقل یکی در عمق ۱ قرار میگیره و یه نویسه با طول کد یک حتما خواهیم داشت.[ارسال مربوطه اصلاح شد]

---

درمورد سوال ۳۷ مشخصا این درخت هیپ نیس بلکه درخت تصمیمه. چرا که همه عناصر تو برگ ها قرار گرفتن و درخت تورنومنت هم میگن بهش. مسئله ای که اینجا وجود داره بحث جستجوی عنصر دلخواهه که زمان n میبره و گرنه همه اعمال تو logn قابل انجامن. حتی واسه حذف هم من یه روش مشابه حذف از هیپ پیدا کردم که لگاریتمیه. اگه زمان جستجو رو درنظر بگیریم فقط درج قابل انجامه واگه درنظر نگیریم هرسه.

[saho]

(۲۷ بهمن ۱۳۹۱ ۱۰:۵۱ ق.ظ)farid_express نوشته شده توسط:  سهیل جان حق با شماس، درواقع بهتره بگیم حداقل یکی در عمق ۱ قرار میگیره و یه نویسه با طول کد یک حتما خواهیم داشت.[ارسال مربوطه اصلاح شد]

---

درمورد سوال ۳۷ مشخصا این درخت هیپ نیس بلکه درخت تصمیمه. چرا که همه عناصر تو برگ ها قرار گرفتن و درخت تورنومنت هم میگن بهش. مسئله ای که اینجا وجود داره بحث جستجوی عنصر دلخواهه که زمان n میبره و گرنه همه اعمال تو logn قابل انجامن. حتی واسه حذف هم من یه روش مشابه حذف از هیپ پیدا کردم که لگاریتمیه. اگه زمان جستجو رو درنظر بگیریم فقط درج قابل انجامه واگه درنظر نگیریم هرسه.

اخرشم نفهمیدم سوال ۴۷ کدوم گزینه میشه؟

[saho]

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

نقل قول: اخرشم نفهمیدم سوال ۴۷ کدوم گزینه میشه؟

چرا خوب؟! هر دو نادرست هستن پس گزینه یک صحیحه.

دومی مگه درست نیست؟؟؟
من خودم ۲زدم اما فکر کنم ۴ میشه

[Farid_Feyzi]

نقل قول: دومی مگه درست نیست؟؟؟
من خودم ۲زدم اما فکر کنم ۴ میشه

معذرت میخوام من دقت نکردم! قسمت دوم درسته و گزینه ۴ صحیحه.

[variant20002000]

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

اینو تو اینترنت دیدم گفتم بزارم واستون.

n تا گوی باردار داریم که بار آن‌ها را نمی‌دانیم. در هر مرحله می‌توانیم دو گوی را به هم نزدیک کنیم و تشخیص دهیم که آیا بار آن‌ها یکسان می‌باشد یا نه.
اگر n فرد باشد و زوجیت تعداد بارهای منفی را بدانیم، n-1 بار مقایسه‌ی گلوله‌ها برای تشخیص بار گوی‌ها لازم و کافی است

منم سر جلسه کنکور همین استلال رو کردم
کاش تو المپیاد شرکت می کردم

[hadilg]

جواب n-1 با این استدلال
گوی اولو بر می داربم و با تک تک گوی ها مقایسه می کنیم . در هر مفایسه اگر گوی از گوی اول دور شد هم نام هستند پس گوی را یک طرف ارایه کنار می گذآریم و اگر چسبید گوی را به طرف مخالف ارایه انتقال می دهیم پس از n-1مقایسه گوی های مثبت یک طرف و گوی های منفی یک طرف هستند
گوی هایی که زوج هستند بار منفی و گوی های فرد مثبت

البته گوی اخر هم به انتهتی یک گروه اضآفه می کنیم

پس با n-1 مقایسه و دانست زوج و یا فرد بود مسءﻻه حل شد