تالار گفتمان مانشت

سلام

جواب گزینه 2 هست.

هر کسی میتونه برام توضیح بده دو تا گزینه رو متوجه بشم.

ممنونم.


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

اول گ 1 که می تواند عناصر به ترتیب گفته شده به دلیل جستجوی خطی ای در جدول درج شوند را بررسی می کنیم. در این گزینه موقعیت اندیس هر عنصر صورت زیر است
6-5-4-3-2-1-0
e-f-g-a-c-b-d
و بر طبق تابع hash اندیس خروجی هر عنصر به صورت زیر است
4-5-3-3-3-6-5
e-f-g-a-c-b-d
همان طور که می بینید a,b در همان اندیس های خروجی تابع hash درج شده اند. پس می توان این ترتیب درج را در نظر گرفت
جدول خالی است و عدد a در خانه با اندیس 3 درج می شود.
عدد b در خانه با اندیس 5 درج می شود.
عدد c می خواهد درج شود خروجی تابع 3 است ولی این خانه پر است پس در در خانه با اندیس 4درج می شود.
عدد d می خواهد درج شود خروجی تابع 4 است ولی این خانه پر است پس در در خانه با اندیس 6درج می شود.
عدد e می خواهد درج شود خروجی تابع 5است ولی این خانه پر است پس در در خانه با اندیس 0درج می شود.
عدد f می خواهد درج شود خروجی تابع 6است ولی این خانه پر است پس در در خانه با اندیس 1درج می شود.
عدد g می خواهد درج شود خروجی تابع 3است ولی این خانه پر است پس در در خانه با اندیس 2درج می شود.
پس اول عناصری را که در اندیس های خروجی تابع درج شده اند را پیدا می کنیم و از روی انها سعی می کنیم ترتیبی برای درج صجیج تمام عناصر پیدا کنیم.

و حالا بررسی می کنیم که چرا گ 2 غلط هست
در این گزینه موقعیت اندیس هر عنصر صورت زیر است
6-5-4-3-2-1-0
c-e-b-g-f-d-a
و بر طبق تابع hash اندیس خروجی هر عنصر به صورت زیر است
3-4-6-3-5-5-3
c-e-b-g-f-d-a
فقط g در همان اندیس خروجی تابع hash درج شده. خوب پس اولین عنصری که در جدول خالی درج شده g می باشد. حالا بررسی می کنیم کدام عنصر می تواند دومین عنصر درجی باشد
c نمی تواند دومین عنصر باشد چون اگر این طور بود در خانه با اندیس 4 درج می شد
e نمی تواند دومین عنصر باشد چون اگر این طور بود در خانه با اندیس 5 درج می شد
b نمی تواند دومین عنصر باشد چون اگر این طور بود در خانه با اندیس 5 درج می شد
f نمی تواند دومین عنصر باشد چون اگر این طور بود در خانه با اندیس 6 درج می شد
dنمی تواند دومین عنصر باشد چون اگر این طور بود در خانه با اندیس 4 درج می شد
a نمی تواند دومین عنصر باشد چون اگر این طور بود در خانه با اندیس 4 درج می شد
پس هیچ عنصر کاندیدی برای دومین درج وجود ندارد پس این گ غلط است.

تابع خروجیhash بگید چطور برای هر ترتیب بدست اوردید ؟ من بدست اوردنش مشکل دارم مثل شما نمیارم.

بعد از اینکه فهمیدیم کدوم عنصر سرجای خودش قرار گفته شروع به بررسی کردن ادامه عناصر میکنیم مثلا در همین گزینه 2 فقط gسرجای خودش گرفته بود و اندیس g هم 3 هست بقیه عناصرو چرا از g به بعد بررسی نکردید؟ و شما ترتیب درج عناصر طبق تابع خروجیhash انجام میدید که ببینید واقعا در سرجای خودشون قرار گرفتن یا نه؟

نمیدونم چرا خوب متوجه نمیشم....

---

ببینید منظور سوال اینه که بعد از اینکه فهمیدیم کدوم عنصر سرجای خودش قرار گرفته اگه بقیه عناصر هم درست قرار گرفتن جواب درست ولی چون گزینه 2 بعد از اینکه فهمیدیم g سرجای خودش قرار گرفته بقیه عناصر هیچ کدوم درست سرجای خودشون نیستن پس این گزینه غلط میشه ....آخه اون طوری که شما توضیح دادید خیلی جواب طولانی شده و اصلا مگه نیازی به تابع خروجی داریم خوب ل از روی جدول هم میشه اندیس و جایگاه عناصرو فهمیدید من دنبال راه آسون میگردم برای جواب....

من در حد توان و دانسته هام همین قدر بلد بودم دوستان اگر راه حل کوتاهتر و سریعتر می دانند ارائه بدهند.

از شما ممنونم به خاطر وقتی گذاشتید و به این سوال پاسخ دادید

یک دنیا ممنونم.

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

اول سلام

من اگه بخوام این سوال را حل کنم اینجوری برا خودم تحلیل میکنم
گزینه اول
اولین کلیدی که طبق جدول سر جاش قرار گرفته در نظر میگیرم، در گزینه اول طبق جدول فقط کلید A سر جاش قرار داره (باید توی خونه ۳ باشه که هست اما کلید های قبلی نیست) از این کلید شروع میکنم
A درست درج شده، کلید C را باید درخونه ۳ درج کنیم که چون پر بوده توی خونه چهارم درج شده، کلید B باید توی خونه ۵ درج بشه که اونم درست درج شده،کلید D باید توی خونه ۴ درج بشه که چون پر شده میره خونه ۶، سپس کلید E که اینم باید توی خونه ۵ باشه که چون ۵ پر هست و ۶ هم پر هست میره تو خونه ۱، F ,G هم به همین ترتیب...
می بینم گزینه یک درسته
اگه گزینه سوم و چهارم را هم به این شکل انجام بدی درست میشه

اما گزینه دوم
G در مکان درست درج شده، از این کلید شروع میکنم، G توی خونه ۳ درج میشه، سپس F باید درج بشه که طبق صورت سوال میره توی خونه ۶ درج میشه اما اینجا توی این گزینه، توی خونه ۴ درج شده (اولین غلط) و اینکه وقتی D باید درج بشه باید توی خونه ۴ درج بشه که اونم توی خونه ۶ درج شده


من اینجوری بلد بودم توضیح بدم
شرمنده اگه نامفهومه

منم تقریبا همین تحلیلو برای خودم میکردم گفتم شاید غلط باشه

ممنونم از شما که سوالات منو از زیر چندین روز خاک بیرون آوردید و جواب دادید بسیار ثواب کردید

ممنونم از شما به خاطر وقتی که گذاشتید و همین طور کوتاه پاسخ دادن که من خیلی راه حل کوتارو دوست دارم.

موفق باشید

منم بالاخره با کلی کلنجار متوجه شدم.
تحلیل من : زمانی که کلید پیدا شد از اولین کلید بعد آن ، مقدارش را از جدول میبینم اگر جای خالی داشت ولی کلید در جای خود قرار نگرفته یعنی ترتیب نادرست!