زمان کنونی: ۰۵ تیر ۱۳۹۸, ۰۴:۲۲ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

جدول درهم سازی(دولتی ۸۲)

ارسال:
  

tarane1992 پرسیده:

جدول درهم سازی(دولتی ۸۲)

سلام

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

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

ممنونم.Shy


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

۲
ارسال:
  

rad.bahar پاسخ داده:

RE: جدول درهم سازی(دولتی ۸۲)

اول گ ۱ که می تواند عناصر به ترتیب گفته شده به دلیل جستجوی خطی ای در جدول درج شوند را بررسی می کنیم. در این گزینه موقعیت اندیس هر عنصر صورت زیر است
۶-۵-۴-۳-۲-۱-۰
e-f-g-a-c-b-d
و بر طبق تابع hash اندیس خروجی هر عنصر به صورت زیر است
۴-۵-۳-۳-۳-۶-۵
e-f-g-a-c-b-d
همان طور که می بینید a,b در همان اندیس های خروجی تابع hash درج شده اند. پس می توان این ترتیب درج را در نظر گرفت
جدول خالی است و عدد a در خانه با اندیس ۳ درج می شود.
عدد b در خانه با اندیس ۵ درج می شود.
عدد c می خواهد درج شود خروجی تابع ۳ است ولی این خانه پر است پس در در خانه با اندیس ۴درج می شود.
عدد d می خواهد درج شود خروجی تابع ۴ است ولی این خانه پر است پس در در خانه با اندیس ۶درج می شود.
عدد e می خواهد درج شود خروجی تابع ۵است ولی این خانه پر است پس در در خانه با اندیس ۰درج می شود.
عدد f می خواهد درج شود خروجی تابع ۶است ولی این خانه پر است پس در در خانه با اندیس ۱درج می شود.
عدد g می خواهد درج شود خروجی تابع ۳است ولی این خانه پر است پس در در خانه با اندیس ۲درج می شود.
پس اول عناصری را که در اندیس های خروجی تابع درج شده اند را پیدا می کنیم و از روی انها سعی می کنیم ترتیبی برای درج صجیج تمام عناصر پیدا کنیم.

و حالا بررسی می کنیم که چرا گ ۲ غلط هست
در این گزینه موقعیت اندیس هر عنصر صورت زیر است
۶-۵-۴-۳-۲-۱-۰
c-e-b-g-f-d-a
و بر طبق تابع hash اندیس خروجی هر عنصر به صورت زیر است
۳-۴-۶-۳-۵-۵-۳
c-e-b-g-f-d-a
فقط g در همان اندیس خروجی تابع hash درج شده. خوب پس اولین عنصری که در جدول خالی درج شده g می باشد. حالا بررسی می کنیم کدام عنصر می تواند دومین عنصر درجی باشد
c نمی تواند دومین عنصر باشد چون اگر این طور بود در خانه با اندیس ۴ درج می شد
e نمی تواند دومین عنصر باشد چون اگر این طور بود در خانه با اندیس ۵ درج می شد
b نمی تواند دومین عنصر باشد چون اگر این طور بود در خانه با اندیس ۵ درج می شد
f نمی تواند دومین عنصر باشد چون اگر این طور بود در خانه با اندیس ۶ درج می شد
dنمی تواند دومین عنصر باشد چون اگر این طور بود در خانه با اندیس ۴ درج می شد
a نمی تواند دومین عنصر باشد چون اگر این طور بود در خانه با اندیس ۴ درج می شد
پس هیچ عنصر کاندیدی برای دومین درج وجود ندارد پس این گ غلط است.
مشاهده‌ی وب‌سایت کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

tarane1992 پاسخ داده:

RE: جدول درهم سازی(دولتی ۸۲)

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

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

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

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

۰
ارسال:
  

rad.bahar پاسخ داده:

RE: جدول درهم سازی(دولتی ۸۲)

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

۰
ارسال:
  

tarane1992 پاسخ داده:

RE: جدول درهم سازی(دولتی ۸۲)

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

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

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

۰
ارسال:
  

۲۰۱۳محمد پاسخ داده:

RE: جدول درهم سازی(دولتی ۸۲)

اول سلام

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

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


من اینجوری بلد بودم توضیح بدم
شرمنده اگه نامفهومه
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

tarane1992 پاسخ داده:

RE: جدول درهم سازی(دولتی ۸۲)

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

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

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

موفق باشید
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

soheila2012 پاسخ داده:

RE: جدول درهم سازی(دولتی ۸۲)

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  سوال ۵۱ ساختمان داده ۹۲ مهندسی - جداول درهم سازی Morris ۴ ۱,۶۵۹ ۱۶ بهمن ۱۳۹۲ ۰۲:۲۲ ب.ظ
آخرین ارسال: mahsalove
  علوم کامپیوتر ۸۸ - مرتب سازی unicornux ۴ ۱,۲۹۳ ۰۸ بهمن ۱۳۹۲ ۰۲:۰۴ ق.ظ
آخرین ارسال: hoomanab
  درخت جستجوی دودویی(دولتی ۷۹) tarane1992 ۲ ۸۲۳ ۱۷ دى ۱۳۹۲ ۱۰:۰۹ ب.ظ
آخرین ارسال: tarane1992
  زمان اجرای الگوریتم مرتب سازی (آی تی ۹۲) tarane1992 ۴ ۱,۴۶۱ ۰۱ دى ۱۳۹۲ ۰۲:۱۵ ب.ظ
آخرین ارسال: tarane1992
  حل سوال ۵۰ کنکور ۹۲ (مهندسی)- مرتبه مرتب سازی یک بازه عددی SnowBlind ۴ ۱,۹۰۶ ۲۸ آذر ۱۳۹۲ ۰۵:۳۲ ق.ظ
آخرین ارسال: izadan11
  بیشترین تعداد تعویض در الگوریتم مرتب سازی(کامپیوتر ۸۴) tarane1992 ۲ ۱,۰۰۳ ۲۶ آذر ۱۳۹۲ ۰۸:۲۵ ب.ظ
آخرین ارسال: tarane1992
  عمق پشته بازگشتی در الگوریتم مرتب سازی سریع(کامپیوتر آزاد ۸۶) tarane1992 ۱ ۱,۰۵۱ ۲۱ آذر ۱۳۹۲ ۰۱:۱۱ ق.ظ
آخرین ارسال: Morris
  هزینه مرتب سازی ادغامی(کامپیوتر ۸۹) tarane1992 ۴ ۱,۱۹۵ ۲۱ آذر ۱۳۹۲ ۱۲:۴۰ ق.ظ
آخرین ارسال: rad.bahar
  ترتیب درج عناصر در جدول درهم ساز(آی تی ۸۹) tarane1992 ۲ ۹۴۹ ۱۸ آذر ۱۳۹۲ ۱۱:۵۵ ق.ظ
آخرین ارسال: tarane1992
  IT دولتی ۸۴ RadMan ۱ ۷۹۵ ۲۲ آبان ۱۳۹۲ ۰۲:۱۴ ق.ظ
آخرین ارسال: rad.bahar

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close