سوال ۵۱ -گزینه ۲
۵۵- گزینه ۳ ؟لطفا جواب بدید

نظرتون چیه
۵۲-۴ سوال ساده ای هست نمیدونم که چرا بچه‌ها نزدن
۵۳-۲ با مثال حل کردم

ما طبق دفترچه a که از همین مانشت دانلود کردیم داریم میگیم شما بگید چی زدید دلایلش بعد

من ۵۱ رو ۴ زدم چون عناصر مرتب نیستند و حالت میانگین و بدترین حالت هم یکیه چون معمولاً با یه تابع تصادفی بدترین حالت هیچ وقت رخ نمیده( احتمالش خیلی کمه)
۵۵ رو هم ۳ زدم که تشریح عمل یک AVL هست که فقط نیاز داره عناصر غیر تکراری رو ذخیره کنه. در غیر اینصورت چطوری میشه جستجو در زمان خطی انجام داد( فقط با آرایه مرتب یا جداول د رهم سازی )خوب چطوری حالا در زمان خطی درج کنیم که جستجو هم خطی باشه و هم میزان حافظه رادیکالی باشه (تناقض )و ...

سلام
سوال ۵۳-۳ مثال درختی بکش به n,k هر عددی بدی گزینه ۳ میاد مثلا ۱۶ و۴ بده میبینی.
۵۴-۲ اینم با مثال عددی حل میشد.
۵۵-۳ ساختمان داده avl جواب میشد در ضمن بچه‌ها هش نمیشه میدونین چرا چون در هش ممکن تصادم داشته باشیم و همه اعمال‌ها در o(n) بشه.
بقیه شم نزدم
اما سوال ۵۲-من حساب کردم ۲۰۴۷ شد چون فقط توان های دو را با هم جمع میزنه از دو به توان یک تا دو به توان ۱۰ اما شک کردم نزدم.

(۳۰ بهمن ۱۳۸۹ ۰۷:۴۱ ب.ظ)www نوشته شده توسط:  سلام
سوال ۵۳-۳ مثال درختی بکش به n,k هر عددی بدی گزینه ۳ میاد مثلا ۱۶ و۴ بده میبینی.
۵۴-۲ اینم با مثال عددی حل میشد.
۵۵-۳ ساختمان داده avl جواب میشد در ضمن بچه‌ها هش نمیشه میدونین چرا چون در هش ممکن تصادم داشته باشیم و همه اعمال‌ها در o(n) بشه.
بقیه شم نزدم
اما سوال ۵۲-من حساب کردم ۲۰۴۷ شد چون فقط توان های دو را با هم جمع میزنه از دو به توان یک تا دو به توان ۱۰ اما شک کردم نزدم.

اما سوال از دو به توان یک تا دو به توان ۱۰ رو باهم جمع میزنه اما دقت نکردی بازم ما نمیتونیم توی یه بافر ۱۰۲۴ تایی همه رو جا بدیم پس در نهایت کل قبلی‌ها با همه اونایی که مونده وارد بافر جدید میشه که ۱۳۸۹ با عددی که تو بدست آوردی جمع میشه گزینه چهار میشه جواب

آقا کسی میدونه سوال ۵۴ یعنی چی؟
من که هنوزم نفهمیدم این سوال دقیق چی میخواد؟

خوب منم اونو نزدم واسه همین

---

در مورد سوال ۵۴ هم بگم یه درخت به ارتفاع سه بکش گره‌ها رو جمع بزن میشه گزینه دو دقیق. سه تا از ساختمان که من زدم اینا بودن.
در مورد سوال ۵۲ بگم فکر کنم جواب ۲۰۴۸ هست برا یقین تو فصل ۱۴ یا ۱۷ کورمن نوشته اونجا بخون جداول پویا را بخون میبینی. در ضمن من نزدم. در مورد دروس دیگه هم بگم سیستم عامل سخت بود بقیه متوسط بود نظریه اش شبیه جزوه گام اخر پارسه بود.

۵۲ منم ۴ زدم.

در مورد سوال ۵۵ هم که یکی از دوستان گفتند که counting الگوریتمه نه ساختار داده بگم که منم نگفتم ساختار داده است ساختار داده ما آرایه است که با counting مرتب میکنیم اعداد رو و در O(1 هم جستجو،درج و حذف میکنیم.

(۳۰ بهمن ۱۳۸۹ ۰۸:۴۷ ب.ظ)afagh1389 نوشته شده توسط:  52 منم ۴ زدم.

در مورد سوال ۵۵ هم که یکی از دوستان گفتند که counting الگوریتمه نه ساختار داده بگم که منم نگفتم ساختار داده است ساختار داده ما آرایه است که با counting مرتب میکنیم اعداد رو و در O(1 هم جستجو،درج و حذف میکنیم.

مرتب سازی شمارشی فقط برا حالاتی هست که بازه مشخص باشه و نه یه مقدار مثل n که به بینهایت میل میکنه. پس این تحلیل غلطه.

در مورد سوال ۵۳ به نظر من گزینه ۴ درسته بستگی داره که k , n چند در نظر گرفته بشه ماکزیمم این‌ها فکر کنم جواب درست تری بدهد.

(۳۰ بهمن ۱۳۸۹ ۰۸:۵۰ ب.ظ)hatami84 نوشته شده توسط:  در مورد سوال ۵۳ به نظر من گزینه ۴ درسته بستگی داره که k , n چند در نظر گرفته بشه ماکزیمم این‌ها فکر کنم جواب درست تری بدهد.

دقیقا" درست میگین، حداکثر ارتفاع درخ را در سوال داده که چون k,n را نمی دونیم باید max بگیریم

---

(۳۰ بهمن ۱۳۸۹ ۰۹:۰۱ ب.ظ)Masoud05 نوشته شده توسط:  

(30 بهمن ۱۳۸۹ ۰۸:۴۷ ب.ظ)afagh1389 نوشته شده توسط:  52 منم ۴ زدم.

در مورد سوال ۵۵ هم که یکی از دوستان گفتند که counting الگوریتمه نه ساختار داده بگم که منم نگفتم ساختار داده است ساختار داده ما آرایه است که با counting مرتب میکنیم اعداد رو و در O(1 هم جستجو،درج و حذف میکنیم.

مرتب سازی شمارشی فقط برا حالاتی هست که بازه مشخص باشه و نه یه مقدار مثل n که به بینهایت میل میکنه. پس این تحلیل غلطه.

کاملا" موافقم، فقط یک آرایه میخواهیم به اندازه رادیکال n که مقدار هر درایه، تعداد عناصر تکرار شده آن اندیس(که همان مقدار آن درایه است-counting sort) در آن ذخیره می شود
پس همه عملیت در O(1)

۵۲ روش حلش اینه تا ۱۰۲۵ متوسط هزینه هر دستور ۳ هست که میشه ۳۰۷۵ از ۱۰۲۶ تا ۱۳۸۹ هم هزینه ۳۶۴ است ۳۰۷۵+۳۶۴=۳۴۳۹

---

چون گفته ارتفاع درخت ۱۰۰% میشه ماکزیمم اگه گفته مدت زمان اجرا اونوقت جمع میکردیم.

سوال ۵۳: گزینه ۳، اگر منظور سوال از ارتفاع، طولانی ترین مسیر از ریشه تا برگ باشه، این جوری میشه: توی از ریشه به سمت پایین سعی کنید فقط n رو به دو تقسیم کنید. وقتی که به k و ۱ رسیدیم تا این جا log2 n رو داریم. حالا از این جا به پایین k رو تقسیم کنید تا به ۱ و ۱ برسید. تا این جا هم log4 k اومدیم پایین و در مجموع log2 n + log4 k

سوال ۵۵: گزینه ۱، در سوال هیچ اشاره ای به اعداد خارج بازه sqrt n و ۱ نشده. اگر اعداد آینده رو هم در همین بازه در نظر بگیریم، می تونیم یک آرایه به اندازه sqrt n در نظر گرفته و برای درج و حذف و جستجو اعداد داخل آرایه رو زیاد و کم کنیم.

سوال ۵۶: گزینه ۲، به توان دو می رسونیم و داریم:

$T^2(n) = \frac{1}{2} \left [ T^2(n-1) T^2(n-2) \right ] n\Rightarrow S(n) = \frac{1}{2} \left [ S(n-1) S(n-2) \right ] n\Rightarrow \left\{\begin{matrix} S(n)\leq \frac{1}{2} \left [ S(n-1) S(n-1) \right ] n=S(n-1) n \in \theta(n^2)\\ S(n)\geq \frac{1}{2} \left [ S(n-2) S(n-2) \right ] n=S(n-2) n \in \theta(n^2) \end{matrix}\right.\Rightarrow S(n) \in \theta(n^2)\Rightarrow T^2(n) \in \theta(n^2)$

(۳۰ بهمن ۱۳۸۹ ۱۰:۴۴ ب.ظ)psps1368 نوشته شده توسط:  سوال ۵۳: گزینه ۳، اگر منظور سوال از ارتفاع، طولانی ترین مسیر از ریشه تا برگ باشه، این جوری میشه: توی از ریشه به سمت پایین سعی کنید فقط n رو به دو تقسیم کنید. وقتی که به k و ۱ رسیدیم تا این جا log2 n رو داریم. حالا از این جا به پایین k رو تقسیم کنید تا به ۱ و ۱ برسید. تا این جا هم log4 k اومدیم پایین و در مجموع log2 n + log4 k

سلام
مگه اینکه نوشته $T(1,*)=T(*,1)=a$
منظورش این نیست که هرکدوم ۱ شد جواب بر میگرده؟ حتما باید به ۱و۱ برسیم؟

(۰۱ اسفند ۱۳۸۹ ۰۱:۰۷ ق.ظ)Masoud05 نوشته شده توسط:  اینایی که میگید درست‌، اما من قصد دارم عدد تغریباً وسط آرایه رو حذف کنم‌، خوب چطوری بفهمم که کجا هست که در زمان خطی پیداش کنم و بعدش هم حذفش کنم .
در ضمن شما برای مرتب سازی شمارشی نیاز به n حافظه دارید چراکه باید خانه های خالی رو هم داشته باشید پس این روش از نظر حافظه بهینه نیست هر چند که جستجو در آن لگاریتمی هست و طبق راهکار شما باید هر جا داده داریم توی آرایه دیگه که تعداد هست ۱ واحد اضافه کنیم که اینم وابسته به جستجو هست و میشه لگاریتمی.

تو سوال نوشته فرقی بین آنها نیست. پس وسط و اول و آخر نداریم
همون آرایه که داره تعداد رو نشون میده شامل خود داده بطور ضمنی هستش
نباید که حتما خود عدد ذخیره بشه
برای درج a
$array[a] ;$
و برای حذف a
$array[a]--;$

واسه ۵۱ کافیه تو اینترنت سرچ کنید.
گزینه ۳ درسته.

در مورد سوال ۵۳ من فکر کنم چون یکی مربوط به شاخه راست درخته و یکی چپ ماکزیممشون میشه.

psps1368 چرا دارید دو شاخه چپ و راست را به صورت مجزا در نظر میگیرید ؟ مگه این دو شاخه با هم به پایین نمی‌آیند ؟

یه مدل الگوریتم شمارشی بر مبنای فراوانی نسبی است یعنی مثلا اگه شما ۵ تا یک دارید خونه با اندیس یک آرایه ۵ است پس وقتی میخواهید یک رو حذف کنید فقط کافیه محتوای آرایه رو یک واحد کاهش بدین برای جستجو هم کافیه چک کنید محتوا صفر نباشه.

الگوریتم counting به این خاطر کاربرد نداره که فضای حافظه زیادی اشغال میکنه ولی بقیه گزینه‌ها فضای حافظه n است پس اینجا counting که رادیکال n است خیلی بهتره مخصوصا که بازه اعداد مشخصه!

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

الگوریتم counting به این خاطر کاربرد نداره که فضای حافظه زیادی اشغال میکنه ولی بقیه گزینه‌ها فضای حافظه n است پس اینجا counting که رادیکال n است خیلی بهتره مخصوصا که بازه اعداد مشخصه!

اینایی که میگید درست‌، اما من قصد دارم عدد تغریباً وسط آرایه رو حذف کنم‌، خوب چطوری بفهمم که کجا هست که در زمان خطی پیداش کنم و بعدش هم حذفش کنم .
در ضمن شما برای مرتب سازی شمارشی نیاز به n حافظه دارید چراکه باید خانه های خالی رو هم داشته باشید پس این روش از نظر حافظه بهینه نیست هر چند که جستجو در آن لگاریتمی هست و طبق راهکار شما باید هر جا داده داریم توی آرایه دیگه که تعداد هست ۱ واحد اضافه کنیم که اینم وابسته به جستجو هست و میشه لگاریتمی.

خوب حالا اگه برمبنای فراوانی مطلق هم باشه فرقی نداره بازم درج و حذف با یه تفریق حل میشه عدد وسط آرایه هم مشخصه.

(۰۱ اسفند ۱۳۸۹ ۱۰:۳۴ ق.ظ)afagh1389 نوشته شده توسط:  خوب حالا اگه برمبنای فراوانی مطلق هم باشه فرقی نداره بازم درج و حذف با یه تفریق حل میشه عدد وسط آرایه هم مشخصه.

من گفتم تغریباً وسط آرایه‌، علتش هم اینه که میخواستم ذهنتون روی جستجوی دودویی نره که با ۱ عمل جستجو وسط رو پیدا میکنه .

امکان نداره سوال ۵۵ ۱ بشه چون اگه خودتون میگید لیستتون آرایه ای هست پس چجوری جستجوش توی o(1) میشه من هنوزم با ۳ موافقم با هیپ به ۳ میرسیم از bst هم نمیتونیم استفاده کنیم چون لیست عنصر تکراری داره ...

من که توضیح دادم چرا نمیخونید!!!
من گفتم تو شمارشی اگه بخواهیم ببینیم ۱ توی آرایه هست یا نه کافیه ببینیم خونه ۱ آرایه صفر نباشه.

اگر بر مبنای فراوانی مطلق هم باشه کافیه مثلا اگه میخواهیم ببینیم ۳۰ توی آرایه هست یا نه [A[31 -A[30 میکنیم اگر ۰ شد یعنی ۳۰ نداریم یعنی تعداد ۳۰‌ها رو به ما میده حتی جای ۳۰ هم مشخصه از روی A[30

قرار دادن این شروط در صورتی که با هیپ به گزینه ۳ میرسم به نظرتون عادلانه است بگذریم آفاق جون درمورد سوال ۵۱ نظری ندارید به نظرتون این سوالات برای سخت افزار چه طور بود منصفانه بود ؟ ساختمان رو عرض میکنم ///

اینها شرط نیست الگوریتمه به هر حال این سوال کاملا به نظر طراح بستگی داره.
۵۱ رو من ۴ زدم اما میگن ۳ میشه یعنی اشتباه زدم

چرا بر چه اساسی اشتراک ۲ تا لیست n نمشه در حالت میانگین من ۲ زدم ؟

منم نگفتم وسط میگم هر خونه ای با جمع و تفریق بدست میاد.

شما بگو عنصر ۱۰۰۰! خوب راحت پیدا میشه اگر بازه اعداد رو نداشتیم خوب نمیشد ولی حالا که داریم.

بازم میگم نظر من اصلا مهم نیست باید ببینیم نظر طراح چی بوده!

در مورد سوال ۵۳ بگم که به ازای همه حالت های n,k جواب ۳ میاید.
۵۵- couning sort برای این مسیله درست جواب نمیدهد.

شما واسه ۵۳ درخت کشیدین دیگه؟!

بله من درخت کشیدم

(۰۱ اسفند ۱۳۸۹ ۰۳:۳۲ ب.ظ)www نوشته شده توسط:  بله من درخت کشیدم

در کجایی درخت مثل ارتفاع را تا log k میرید بعد ادامه همان شاخه را با log n میرید به صورت سوال دقت کنید گفته اگه یکی از K یا N مساوی با ۱ بشه دیگه اون شاخه را ادامه نمیدیم .
پس اگه یکی از اینها یک بشه دیگه اون شاخه را نمیتونیم پیش برویم و باید یک شاخه دیگه را در صورت وجود انتخاب بکنیم . پس با این اوصاف بازم به نظر من همون ماکزیمم درسته . و یکجورایی به احتمال خیلی زیاد نمیتونیم جمع را به عنوان گزینه درست انتخاب بکنیم .در صورتی در صورت سوال مثلاً گفته بود T(1,1 )اونوقت حرف شما درست بود ولی حالا که میگه اگه یکی ۱ شد دیگه رشد شاخه را ادامه نمیدیم پس ماکزیمم شاخه را باید در نظر بگیریم

من یادم نیست موقع کنکور چه تحلیلی کردم ولی نمیدونم ۳ زدم یا ۴!
امیدوارم همونی که درسته زده باشم‌: دی

خوبه سوال یه جور سخت نشون میداد اما اسون حل میشد. در ضمن افاق سوال ۵۵ رو تو چی زدی؟

---

کلیدا دو هفته بعد از کنکور اگه اقایون بتونن میزارن.

۵۵ رو ۱ زدم!

واسه سوال ۵۸ من حوصله نکردم اگه نه همون سرجلسه میشد با یه مثال مطمئن شد!

چرا یک زدی ۳ که از همشون بهتر بود.

باشه.
راستی اون سوالایی که دو گزینشون یکی بود چی میشن؟

نمیدونم لابد
اگه هر دو درسته خوب هر دو رو درست میگیرن .اگر نه هم همون گزینه درست رو.

نه اینطوری نیست با عدد حل کن دیگه ارتفاع به دست امده را تو گزینه‌ها امتحان کن ببین کدومش میشه بازم میگم به ازای هر مقداری ازn,k گزینه ۳ میشه در ضمن بله t(1,1) میدونم نیست یه بار به ازایn=16,k,k=4 امتحان کن.

خودتون این مثال را امتحان کردید ؟ من امتحان کردم ارتفاع ۴ شد در صورتی که با گزینه ای که شما میگید باید ۵ بشه
T(1 , * )را به عنوان برگ آخر کار در نظر گرفته‌اید ؟

---

آره فکر کنم ۳ درست باشه من با k=16 و n=16 امتحان کردم ارتفاع ۵ میشه

ساختمان داده رو من منفی زدم!
۵۳ رو که اشتباه کردم و ۴ رو زدم در حالی که واضحه ۳ میشه.
۵۶ رو هم ۳ زدم و فکر می کردم ۱ ریشه مرتبه دوم هست.حالا که حساب کردم دیدم ریشه مرتبه ۳ هست و جواب از مرتبه n میشه و گزینه ۲ درسته.
۵۵ هم که قبلا غلط زده بودم.
۵۲ هم چونکه جوابم بین دو گزینه ۳ و ۴ در میومد گزینه‌ی ۳ رو زدم که بچه‌ها میگند به گزینه‌ی ۴ رسیدند.
در صورتی که ۵۴ را درست زده باشم(گزینه ۲) باز هم نمره منفی میخورم.
الان من باید ناراحت باشم؟!

۵۲ من هر چی حساب میکنم میشه ۳۴۳۵ فکر کنم ۳۴۴۵ اشتباه تایپی باشه ها!!

---

۵۵ هم که هنوز توش شک هست.

سوال ۵۴ رو چه طوری به ۲ رسیدید؟
دوستانی که کلید A داشتند یادشون هست که گزینه ۲ همین گزینه بود یا نه؟

در مورد سوال ۵۴ بازم مثله ۵۳ یه درخت بکش به گزینه دو میرسی فکر کنم این سوال فرق میکرد من دفترچم c بود گزینه یک میشد.
ئر مورد سوال ۵۵ هم بگم تو کتاب کورمن فصل ۱۴ درحت اماره پویا جواب این سوال میشه که مطمینا گزینه ۳ جوابه البته اگه ملاک کورمن باشه که هست.

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

اون درختی که شما می گی دیگه فضای اضافی نمی خاد.

منظورتو متوجه نشدم

سلام
من این چند روزه خیلی سرم شلوغ بوده. خوب گویا امسال پیش‍‏‏بینی من مبنی بر متفاوت بودن درست از آب در اومده.

سوال ۵۵ به نظر من گزینه ۱ کاملاً درسته. این داده‍‏‏ساختار رو می‍‏‏شه به راحتی به روش hash و با شماردن تعداد تکرارها به وجود آورد. توی متن سوال اشاره کرده که عناصر تکرار فرقی با هم ندارند، بنابراین تنها کافیه که تعداد تکرارها رو توی خانه مربوطه قرار بدیم.
الگوریتم اضافه عدد n برابر است با اضافه کردن مقدار خانه n‌ام آرایه
الگوریتم حذف عدد n برابر است با کاهش مقدار خانه n ام، در صورتی که خانه n صفر نباشد( یعنی عنصر وجود داشته باشد)
الگوریتم یافتن عدد n برابر است با مقدار خانه n (که نشان دهنده تعداد موجود از n است) اگر این خانه صفر باشد یعنی عنصر وجود ندارد.

پیچیدگی ساختار بالا از لحاظ الگوریتمی برابر O1 و از لحاظ حافظه برابر طول آرایه یعنی رادیکال n است.

بله منم گفتم ۵۵-۱ میشه فقط با hash یا counting ????

در مورد سوال ۵۱ ساختمان داده: گزینه ۴
با پیچیدگی nlogn می‌‍‏‏توان لیست A و با همین پیچیدگی لیست B را مرتب‌‍‏‏سازی کرد.
برای گرفتن اشتراک دو لیست A و B هر کدام از اعضای A را به صورت باینری در لیست B جستجو می‌‍‏‏نماییم. در حالت متوسط و بدترین حالت تعداد هر جستجو برابر با logn خواهد بود و در نتیجه پیچیدگی جستجو برابر با nlogn در هر دو حالت متوسط و بدترین است.
بنابراین پیچیدگی الگوریتم طراحی شده برابر با ۳nlogn خواهد بود (در حالت متوسط و بدترین) و گزینه ۴ بهترین پاسخ به این سوال.

نکته: می‌‍‏‏توان در زمان ۲n هم الگوریتم جستجو و یافتن اشتراک دو لیست مرتب را طراحی کرد. طراحی این الگوریتم به عنوان تمرین به شما واگذار می‌‍‏‏شود!!

(۰۳ اسفند ۱۳۸۹ ۰۹:۵۱ ق.ظ)admin نوشته شده توسط:  در مورد سوال ۵۱ ساختمان داده: گزینه ۴
با پیچیدگی nlogn می‌‍‏‏توان لیست A و با همین پیچیدگی لیست B را مرتب‌‍‏‏سازی کرد.
برای گرفتن اشتراک دو لیست A و B هر کدام از اعضای A را به صورت باینری در لیست B جستجو می‌‍‏‏نماییم. در حالت متوسط و بدترین حالت تعداد هر جستجو برابر با logn خواهد بود و در نتیجه پیچیدگی جستجو برابر با nlogn در هر دو حالت متوسط و بدترین است.
بنابراین پیچیدگی الگوریتم طراحی شده برابر با ۳nlogn خواهد بود (در حالت متوسط و بدترین) و گزینه ۴ بهترین پاسخ به این سوال.

نکته: می‌‍‏‏توان در زمان ۲n هم الگوریتم جستجو و یافتن اشتراک دو لیست مرتب را طراحی کرد. طراحی این الگوریتم به عنوان تمرین به شما واگذار می‌‍‏‏شود!!

دکتر نظرتون در مورد این الگوریتم چیه:
در سوال نگفته از چه نظر بهینه باشه.پس ما تنها از لحاظ سرعت اجرا(که در اکثر موارد همینه)،الگوریتم خواسته شده رو در نظر می گیریم.
حالتی رو در نظر بگیرید که بشه با استفاده از درج عناصر در hashی متعادل(به روش مستقیم فرضا،البته گفته میشه که در صورت استفاده از حداکثر چند بار rehashing با توابع بررسی شده،میتونیم همواره جدول hash متعادلی داشته باشیم که از صحت اون من بی اطلاعم) عناصر آرایه اول رو به ساختمان اضافه کرد.در ادامه آرایه دوم رو را در hash قبلی درج می کنیم و در صورت بروز برخورد و تساوی مقادیر اونا رو چاپ می کنیم.
مرتبه الگوریتم فوق در صورت استفاده از hashی متعادل در حالت میانگین و بدترین حالت از مرتبه n هستش.
پس گزینه مناسب،از نظر من گزینه ۱ه.نظر دیگران هم قابل احترامه و ممکنه بنده اشتباه کنم.

---

(۰۲ اسفند ۱۳۸۹ ۰۷:۳۴ ب.ظ)admin نوشته شده توسط:  سلام
من این چند روزه خیلی سرم شلوغ بوده. خوب گویا امسال پیش‍‏‏بینی من مبنی بر متفاوت بودن درست از آب در اومده.

سوال ۵۵ به نظر من گزینه ۱ کاملاً درسته. این داده‍‏‏ساختار رو می‍‏‏شه به راحتی به روش hash و با شماردن تعداد تکرارها به وجود آورد. توی متن سوال اشاره کرده که عناصر تکرار فرقی با هم ندارند، بنابراین تنها کافیه که تعداد تکرارها رو توی خانه مربوطه قرار بدیم.
الگوریتم اضافه عدد n برابر است با اضافه کردن مقدار خانه n‌ام آرایه
الگوریتم حذف عدد n برابر است با کاهش مقدار خانه n ام، در صورتی که خانه n صفر نباشد( یعنی عنصر وجود داشته باشد)
الگوریتم یافتن عدد n برابر است با مقدار خانه n (که نشان دهنده تعداد موجود از n است) اگر این خانه صفر باشد یعنی عنصر وجود ندارد.

پیچیدگی ساختار بالا از لحاظ الگوریتمی برابر O1 و از لحاظ حافظه برابر طول آرایه یعنی رادیکال n است.

دقیقا،کاملا با نظرتون موافقم.
احساس می کنم طراح اکثر سوالات را بر مبنای hash طرح کرده باشند.

در مورد سوال ۵۳ با گزینه ۴ موافقم.

(۰۳ اسفند ۱۳۸۹ ۰۹:۵۱ ق.ظ)admin نوشته شده توسط:  در مورد سوال ۵۱ ساختمان داده: گزینه ۴
با پیچیدگی nlogn می‌‍‏‏توان لیست A و با همین پیچیدگی لیست B را مرتب‌‍‏‏سازی کرد.
برای گرفتن اشتراک دو لیست A و B هر کدام از اعضای A را به صورت باینری در لیست B جستجو می‌‍‏‏نماییم. در حالت متوسط و بدترین حالت تعداد هر جستجو برابر با logn خواهد بود و در نتیجه پیچیدگی جستجو برابر با nlogn در هر دو حالت متوسط و بدترین است.
بنابراین پیچیدگی الگوریتم طراحی شده برابر با ۳nlogn خواهد بود (در حالت متوسط و بدترین) و گزینه ۴ بهترین پاسخ به این سوال.

نکته: می‌‍‏‏توان در زمان ۲n هم الگوریتم جستجو و یافتن اشتراک دو لیست مرتب را طراحی کرد. طراحی این الگوریتم به عنوان تمرین به شما واگذار می‌‍‏‏شود!!

من این سوال رو گزینه ۱ زدم (میانگین و بدترین $O(n)$
آخه گفتم هر سری کوچکترین عنصر از هر آرایه با استفاده از "درخت تورنمنت " میکشیم بیرون و با هم مقایسه میکنیم و به همین ترتیب پیش میریم
و تو کتاب مقسمی خونده بودم یک قضیه رو که Kامین عنصر از یک آرایه رو میشه با $O(n)$ بدست آورد.
؟!

من فکر میکنم سوال ۵۵-۳ میشه بابا هشم در نظر بگیری خودش گفته میشه عناصری تکراری داشت پس میشه ۳ دیگه.

در مورد hash که دوستمون مطرح کردند درباره سوال ۵۱ به هیچ وجه امکان چنین کاری وجود نداره. از لحاظ تئوری باید بدترین حالت رو در نظر بگیریم و بدترین حالت hash هر چند که متعادل هم باشه اینه که همه مقادیر به یک خانه map شوند و در این حالت الگوریتم مطرح شده شما از مرتبه n به توان ۲ خواهد بود. الگوریتم hash رو در مورد سوال ۵۵ می‌‍‏‏شد به کار برد اما توی این سوال نه.

(۰۳ اسفند ۱۳۸۹ ۱۱:۳۴ ب.ظ)admin نوشته شده توسط:  در مورد hash که دوستمون مطرح کردند درباره سوال ۵۱ به هیچ وجه امکان چنین کاری وجود نداره. از لحاظ تئوری باید بدترین حالت رو در نظر بگیریم و بدترین حالت hash هر چند که متعادل هم باشه اینه که همه مقادیر به یک خانه map شوند و در این حالت الگوریتم مطرح شده شما از مرتبه n به توان ۲ خواهد بود. الگوریتم hash رو در مورد سوال ۵۵ می‌‍‏‏شد به کار برد اما توی این سوال نه.

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

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

از لحاظ تئوری بدترین حالت hash برای insert و find از O( n )l هست اما به طور میانگین برای hash این دو عملیات O(1)l زمان میبره و من فکر میکنم نظر طراح هم گزینه ۲ بوده.( خودم ۴ زدم )

hashMap رو نمی‌‍‏‏شه توی این موقعیت و برای این سوال به کار برد. شما تابع hash رو چه طور می‌‍‏‏خوای معرفی کنی که دو عضو غیر همتا هیچ برخوردی با هم نداشته باشند؟ دقت کنید که ما هیچ اطلاعی از نوع داده‌‍‏‏های دو لیست نداریم. اگر به فرض مثال می‌‍‏‏دونستیم که همه داده‌‍‏‏ها عدد صحیح هستند و ... می‌‍‏‏شد با برخی کارها الگوریتم از مرتبه n ارایه داد اما الان چنین فرضی رو نمی‌‍‏‏شه کرد. فرض کنید که اعداد داخل آرایه از نوع اعشاری با تعداد بی نهایت اعشار باشند. شما چه hashMap ای رو می‌‍‏‏تونی طراحی کنی که بتونه این مسئله رو حل کنه؟ اصلاً این خودش یه مسئله NP هست که بشه یه ترتیب dictionary برای این اعداد پیدا کرد. چرا که بین هر دو عدد می‌‍‏‏تونه یه عدد دیگه قرار بگیره. در مورد مصاحبه شرکت‌‍‏‏ها و غیره:
متد ۱ اش: که پیچیدگی مرتب‌‍‏‏سازی رو غلط نوشته! nlogn هست نه logn.
متد ۲ اش: با فرض مقدار صحیح بودن از hashMap استفاده کرده که کاری بس آسان و شدنی است. اما با فرض‌‍‏‏های دیگه محال و غیر ممکن است.

(۰۴ اسفند ۱۳۸۹ ۰۱:۴۳ ق.ظ)admin نوشته شده توسط:  hashMap رو نمی‌‍‏‏شه توی این موقعیت و برای این سوال به کار برد. شما تابع hash رو چه طور می‌‍‏‏خوای معرفی کنی که دو عضو غیر همتا هیچ برخوردی با هم نداشته باشند؟ دقت کنید که ما هیچ اطلاعی از نوع داده‌‍‏‏های دو لیست نداریم. اگر به فرض مثال می‌‍‏‏دونستیم که همه داده‌‍‏‏ها عدد صحیح هستند و ... می‌‍‏‏شد با برخی کارها الگوریتم از مرتبه n ارایه داد اما الان چنین فرضی رو نمی‌‍‏‏شه کرد. فرض کنید که اعداد داخل آرایه از نوع اعشاری با تعداد بی نهایت اعشار باشند. شما چه hashMap ای رو می‌‍‏‏تونی طراحی کنی که بتونه این مسئله رو حل کنه؟ اصلاً این خودش یه مسئله NP هست که بشه یه ترتیب dictionary برای این اعداد پیدا کرد. چرا که بین هر دو عدد می‌‍‏‏تونه یه عدد دیگه قرار بگیره.

سلام

کلا وقتی صحبت از کامپیوتر هست، همیشه محدودیتی هم وجود داره. این مورد رو در نظر بگیرید که اگر اعداد اعشاری با بینهایت رقم اعشار داشیم حتی نمی شد این اعداد رو با nlogn مرتب کرد. (با روش های مبتی بر مقایسه) چون زمان مقایسه هم دو عنصر را دیگه نمی شد ثابت در نظر گرفت. طراح حتما در ذهن خودش فرض ثابت بودن زمان مقایسه عناصر رو داشته چون در غیر این صورت تست کلا غلط خواهد بود. در رابطه با روش hash کردن داده های مختلف، می شه هر عنصر با هر نوع داده ای رو به صورت دنباله ای از ۰ و ۱ در نظر گرفت و اون وقت دیگه hash کردن کاره دشواری نیست. (همون چیزی که خودتون هم اشاره کردید) بنابراین اگر در حالت میانگین بخواهیم بررسی کنیم، می شه پراکندگی عناصر در خانه های جدول hash را برابر فرض کرد. بنابراین من هم فکر می کنم که گزینه ۲ صحیح باشه. من خودم گزینه ۱ رو زدم اما با توجه به این که ما هیچ شناختی از ماهیت داده‌ها نداریم قاعدتا نمی شه تابع بهینه hash رو در تحلیل مد نظر قرار داد.

سوال ۵۵ ساختمان داده:
فرض میکنیم n=16 پس ما چهار تا عنصر داریم فرض کنیم هر چهر عنصر ما عدد ۲ باشد.
اگر از روش هش استفاده کنیم(با توجه به فصل ۱۱ کتاب کورمن میدانیم ۳ روش هش با ادرس دهی باز عبارتند از ۱-خطی ۲- مجذوری ۳- مضاعف) اگر از روش زنجیر استفاده کنیم چون گفته عناصر تکراری هیچ فرقی باهم ندارند برای درج ما چهار بار باید در خانه ۲ درج کنیم یعنی اگر تمام عناصر تکراری باشد بهn به توان یک دوم برای درج نیاز خواهیم داشت. پس روش هش جواب نمیدهد. در ضمن اگر از هر کدام از ۳ روش استفاده کنیم باز همون زمان بالا برقرار خواهد بود.
با توجه به فصل ۱۴ کتاب کورمن و با استفاده از درخت آماره پویا هر سه عمل جواب lgn میباشد.
با این اوصاف گزینه ۳ درست است.

(۰۴ اسفند ۱۳۸۹ ۰۱:۳۶ ب.ظ)www نوشته شده توسط:  سوال ۵۵ ساختمان داده:
فرض میکنیم n=16 پس ما چهار تا عنصر داریم فرض کنیم هر چهر عنصر ما عدد ۲ باشد.
اگر از روش هش استفاده کنیم(با توجه به فصل ۱۱ کتاب کورمن میدانیم ۳ روش هش با ادرس دهی باز عبارتند از ۱-خطی ۲- مجذوری ۳- مضاعف) اگر از روش زنجیر استفاده کنیم چون گفته عناصر تکراری هیچ فرقی باهم ندارند برای درج ما چهار بار باید در خانه ۲ درج کنیم یعنی اگر تمام عناصر تکراری باشد بهn به توان یک دوم برای درج نیاز خواهیم داشت. پس روش هش جواب نمیدهد. در ضمن اگر از هر کدام از ۳ روش استفاده کنیم باز همون زمان بالا برقرار خواهد بود.
با توجه به فصل ۱۴ کتاب کورمن و با استفاده از درخت آماره پویا هر سه عمل جواب lgn میباشد.
با این اوصاف گزینه ۳ درست است.

موقعی که الگوریتم بهتری داریمO(1) گزینه ۳ که قابل قبول نیست!

نقل قول: سوال ۵۵ ساختمان داده:
فرض میکنیم n=16 پس ما چهار تا عنصر داریم فرض کنیم هر چهر عنصر ما عدد ۲ باشد.
اگر از روش هش استفاده کنیم(با توجه به فصل ۱۱ کتاب کورمن میدانیم ۳ روش هش با ادرس دهی باز عبارتند از ۱-خطی ۲- مجذوری ۳- مضاعف) اگر از روش زنجیر استفاده کنیم چون گفته عناصر تکراری هیچ فرقی باهم ندارند برای درج ما چهار بار باید در خانه ۲ درج کنیم یعنی اگر تمام عناصر تکراری باشد بهn به توان یک دوم برای درج نیاز خواهیم داشت. پس روش هش جواب نمیدهد. در ضمن اگر از هر کدام از ۳ روش استفاده کنیم باز همون زمان بالا برقرار خواهد بود.
با توجه به فصل ۱۴ کتاب کورمن و با استفاده از درخت آماره پویا هر سه عمل جواب lgn میباشد.
با این اوصاف گزینه ۳ درست است.

موقعی که الگوریتم بهتری داریمO(1) گزینه ۳ که قابل قبول نیست!
الگوریتم بهتر را میشه توضیح بدهید؟

(۰۴ اسفند ۱۳۸۹ ۰۲:۲۵ ب.ظ)www نوشته شده توسط:  

نقل قول: سوال ۵۵ ساختمان داده:
فرض میکنیم n=16 پس ما چهار تا عنصر داریم فرض کنیم هر چهر عنصر ما عدد ۲ باشد.
اگر از روش هش استفاده کنیم(با توجه به فصل ۱۱ کتاب کورمن میدانیم ۳ روش هش با ادرس دهی باز عبارتند از ۱-خطی ۲- مجذوری ۳- مضاعف) اگر از روش زنجیر استفاده کنیم چون گفته عناصر تکراری هیچ فرقی باهم ندارند برای درج ما چهار بار باید در خانه ۲ درج کنیم یعنی اگر تمام عناصر تکراری باشد بهn به توان یک دوم برای درج نیاز خواهیم داشت. پس روش هش جواب نمیدهد. در ضمن اگر از هر کدام از ۳ روش استفاده کنیم باز همون زمان بالا برقرار خواهد بود.
با توجه به فصل ۱۴ کتاب کورمن و با استفاده از درخت آماره پویا هر سه عمل جواب lgn میباشد.
با این اوصاف گزینه ۳ درست است.

موقعی که الگوریتم بهتری داریمO(1) گزینه ۳ که قابل قبول نیست!
الگوریتم بهتر را میشه توضیح بدهید؟

دکتر تنهایی که گفتن.

اون روش به نظر من نمیشه کتاب مرجع کتاب کورمن هستش تو اونم اینو نوشته نظرات شخصی جواب نمیده.
لااقل بجای اینکه از گفتن این حرفا یه سر میرفتین کورمنو میخوندین.
امیدوارم که موفق باشید.

(۰۴ اسفند ۱۳۸۹ ۰۱:۴۳ ق.ظ)admin نوشته شده توسط:  hashMap رو نمی‌‍‏‏شه توی این موقعیت و برای این سوال به کار برد. شما تابع hash رو چه طور می‌‍‏‏خوای معرفی کنی که دو عضو غیر همتا هیچ برخوردی با هم نداشته باشند؟ دقت کنید که ما هیچ اطلاعی از نوع داده‌‍‏‏های دو لیست نداریم. اگر به فرض مثال می‌‍‏‏دونستیم که همه داده‌‍‏‏ها عدد صحیح هستند و ... می‌‍‏‏شد با برخی کارها الگوریتم از مرتبه n ارایه داد اما الان چنین فرضی رو نمی‌‍‏‏شه کرد. فرض کنید که اعداد داخل آرایه از نوع اعشاری با تعداد بی نهایت اعشار باشند. شما چه hashMap ای رو می‌‍‏‏تونی طراحی کنی که بتونه این مسئله رو حل کنه؟ اصلاً این خودش یه مسئله NP هست که بشه یه ترتیب dictionary برای این اعداد پیدا کرد. چرا که بین هر دو عدد می‌‍‏‏تونه یه عدد دیگه قرار بگیره. در مورد مصاحبه شرکت‌‍‏‏ها و غیره:
متد ۱ اش: که پیچیدگی مرتب‌‍‏‏سازی رو غلط نوشته! nlogn هست نه logn.
متد ۲ اش: با فرض مقدار صحیح بودن از hashMap استفاده کرده که کاری بس آسان و شدنی است. اما با فرض‌‍‏‏های دیگه محال و غیر ممکن است.

البته اگر اعداد double هم باشند فکر میکنم مشکلی برای hash کردنشون وجود نداره. چون میتونیم این اعداد double رو به صورت یک عدد مثلا ۶۴ بیتی درنظر بگیریم و بعد عملیات hash رو روی داده‌ها انجام بدیم!

در مورد سوال ۵۵ من این نظرم مینویسمو بس اگراز روش هش با الگوریتم گفته شده استفاده کنیم برای پیاده سازی این کد باید یه حلقه از ۱ تا رادیکال ان بنویسی و در درون حلقه شرط برابری مقدار را با یکی از خانه‌ها را انجام دهی که اگر با هر خونه ای برابر شد یک واحد در درج به ان اضافه یا در حذف کم کنی و در جستجو هم بگردی با این اوصاف جواب این حلقه میشه رادیکال ان. این تفسیر من از الگوریتم شماست. اگه اشتبا میکنمشماتوضیح دهید.[/php]

گویا شما hash رو درست متوجه نشدین! من شیوه دسترسی بر اساس o1 رو توضیح دادم. خیلی واضح و مشخصه این سوال و جای هیچ شک و شبهه‌‍‏‏ای نداره.
در مورد کتاب کورمن: دوستان به جای ارجاع کردن وقت و بی وقت به این کتاب به شرایط مسایل دقت کنند. کتاب کورمن هم می‌‍‏‏تونه اشکال داشته باشه. ما اینجا دلایل عقلی می‌‍‏‏آوریم و دوستان جواب‌‍‏‏های نقلی!
کی گفته تنها تابع hash رو به سه روش می‌‍‏‏شه ساخت؟ به هر روشی می‌‍‏‏شه این تابع رو ساخت و اصلاً این ساختن این توابع برای خودش صنعتی مهم به حساب میاد! اگه به همین سادگی و سر راستی بود که بسیاری از شرکت‌‍‏‏ها واسه به دست آوردن اعداد اول بزرگ پول‌‍‏‏های هنگفت هزینه نمی‌‍‏‏کردن. من یه تابع hash خیلی ساده( به قول شما خطی) پیشنهاد دادم و شما اصرار بر غلط بودن دارید.

در نظر داشته باشید که من کنکوری نیستم و ذی‌‍‏‏نفع جواب‌‍‏‏ها هم نیستم. تنها به اصرار دوستان توی این مباحث شرکت کردم

من خودم این سوال اجتماع رو اشتباه زدم چون به مرتب بودن دو لیست دقت نکردم ولی قبلا یه سوال دیده بودم مشابه این سوال که میخواست میانه رو پیدا کنه و logn میشد(البته در پایه ۴/۳)