سلام جدول درهم سازی ساده ساختمان داده هستش با این فرضیات
index: یک اندیس از آرایه است
key: کلیدی است که قرار است وارد آرایه شود
array_length: طول آرایه است
شما باید یه ارایه ای بسازید که ابتدا کلید هارو سرجای خودش قرار بدین دوم اگر کلید ها سرجای خودش نبودن یه خونه دیگ براشون پیدا کنید.سیاست ها و الگوریتم های متفاوتی برای وقتی که کلید سرجای خودش قرار نمیگیره وجود داره توی سوال اول به سیاست وارسی خطی linear probing اشاره کرده.که توضیح میدم
توی سوال اول سطر اول سوال همون کلید ها هستن
توی سطر دوم شماره اندیس مربوط به هر کلید.که اگر اندیس های یکسان نداشته باشیم هر عنصر سر جای خودش قرار میگیره.
منظور از این دوسطر چیه؟یعنی کلید Aتو خونه ۳ قرار بگیره کلید B توی خونه ۵ قرار بگیره کلید C توی خونه ۳ قرار بگیره و به همین ترتیب ...
صورت سوال گفته با هر ترتیب دلخواه یعنی ممکنه اول G رو بخوای بذاری بعد D رو بذاری و ...
توی این سوال شما باید تک تک گزینه هارو تست کنید ، من پیشنهاد میکنم توی اینجور سوالا که همه گزینه ها باید تست بشن اول گزینه ۱ بعد گزینه ۴ بعد گزینه ۲ بعد گزینه ۳ رو تست کن.
اینطوری وقتی جواب گزینه ۴ باشه مجبور نیستی هرچهار تا گزینه رو چک کنی.
فک کنم شما دقیقا مفهموم هش رو در کنار وارسی خطی با هم نگرفتید.
فرض کنید ابتدا بخوایم A رو وارد هش کنیم ، A اندیس ۳ داره و توی خونه ۳ قرار میگیره(نکته اول :توی هش وقتی ارایه اولیه خالی باشه اولین عنصر حتما سرجای خودش قرار میگیره )
حالا قصد داریم کلید C رو وارد کنیم C اندیس ۳ رو داره به خونه ۳ مراجعه میشه پرهستش به ترتیب روی آرایه جلو میریم تا اولین خونه خالی بعدی رو بهش بدیم (سیاست وارسی خطی)
حالا قصد داریم B رو وارد کنیم B به خونه ۵ مراجعه میکنه ، چون اندیس صورت سوالش ۵ فرض شده.خونه ۵ خالیه سرجاش قرار میگیره
حالا قراره D وارد بشه اندیس ۴ رو داره طبق وارسی خطی اخرین خونه ی ارایه بهش میرسه
عنصر بعدی E با اندیس ۵ وارد میشه که جاش قبلا گرفته شده تا اخر ارایه میره جایی رو پیدا نمیکنه ، میاد از اول ارایه شروع میکنه خونه اول خالیه پس جاش پیدا شد
عنصر بعدی F با اندیس ۶ وارد میشه که جاش قبلا گرفته شده تا اخر ارایه میره جایی رو پیدا نمیکنه ، میاد از اول ارایه شروع میکنه و بالاخره یه خونه خالی پیدا میکنه
حالا قصد داریم کلید G رو وارد کنیم.G اندیس ۳ رو داره به خونه ۳ مراجعه میشه چون که پرهستش اولین خونه خالی بعد از ۳ رو بهش میدیم که میشه اندیس ۲ یعنی تا اخر رفت و پیدا نکرد دوباره اومد از اول شروع کرد تا یه جایی رو پیدا کرد
این مراحل ساخت گزینه ۱ بود.

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

---

(۱۵ دى ۱۳۹۲ ۱۲:۴۴ ق.ظ)soheila2012 نوشته شده توسط:  یعنی خیلی از اعداد جای خودشون نیستن.تا چند تا کلید مناسب خودشون داشته باشن درست میشه؟

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

سوال ۳۷:
حروف رو به ترتیبی که نوشتم از چپ به راست وارد کنید:
گزینه۱-
ACBDEFG
گزینه۲-
???G
گزینه۳-
ACEGBDF
گزینه۴-
ADEFCGB
فقط گزینه ۲ هست که اول G وارد میشه ولی هرکدوم از حروف دیگه رو که بخوایم به عنوان حرف دوم وارد کنیم باید در خونه خودش قرار بگیره که قرار نگرفته.
(چون گفته با هر ترتیب دلخواه) مثلا E یا D یا... به عنوان حرف دوم که وارد میشود...

--------------------------------------------
سوال ۳۸:


-------------------------------------------
هر قسمتی که متوجه نشدید، لطفا بگید تا توضیح بدم...

ببخشید من کلا با این مبحث مشکل دارم!
اصلا چطوری این ترتیب ایجاد میشه؟
مرسی

(۱۴ دى ۱۳۹۲ ۱۰:۲۷ ب.ظ)soheila2012 نوشته شده توسط:  ببخشید من کلا با این مبحث مشکل دارم!
اصلا چطوری این ترتیب ایجاد میشه؟
مرسی

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

من تو شکلی که دوباره کشیدم، آدرس طبیعی و واقعی کلیدها رو مشخص کردم.
گزینه۱:
A و B تو خونه خودشونن. حالا بقیه کلیدها رو اگه تونستی با یک ترتیبی وارد کنی که چیدمان گزینه ۱ درست بشه، معلوم میشه که
گزینه ۱ درسته!! چی گفتم؟! خودمم نفهمیدم!!
ازنقطه A شروع کن به ترتیب برو به سمت چپ
ACBDEFG
اگر وارد کنی میبینی که چیدمان گزینه ۱ صحیحه.
گزینه ۳ و ۴ هم همینطور.

ولی گزینه ۲: G تو خونه خودش قرار گرفته. اگر فرض کنیم اول G وارد شده کلیدهای بعدیشو به هر ترتیبی که دوست داری وارد کن، میبینی که غلطه
مثلا
اگر بعد از G، کلید F رو وارد کنی باید بره تو خونه ۶ اما در خونه ۴ قرار گرفته
اگر بعد از G، کلید D رو وارد کنی باید بره تو خونه ۴ اما در خونه ۵ قرار گرفته
اگر بعد از G، کلید A رو وارد کنی باید بره تو خونه ۴ اما در خونه ۶ قرار گرفته
اگر بعد از G، کلید C رو وارد کنی باید بره تو خونه ۴ اما در خونه ۰ قرار گرفته
اگر بعد از G، کلید E رو وارد کنی باید بره تو خونه ۵ اما در خونه ۱ قرار گرفته
اگر بعد از G، کلید B رو وارد کنی باید بره تو خونه ۵ اما در خونه ۲ قرار گرفته
پس بعد از G هر کلیدی که وارد کنی اشتباه قرار گرفته که این یعنی گزینه ۲ غلطه.

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

شکل:

چقد با حوصله جواب دادین؟!
مرسی
بازم متوجه نشدم
ببینید این ترتیب رو متوجه نمیشم!!! گفتین گزینه ی ۱ الان اگه c بخوایم وارد کنیم باید توی خونه ی ۳ باشه که نیست و اولین جای خالی میشه ۴ و بقیه...خب برای گزینه ی ۲ هم همینطوره! یعنی خیلی از اعداد جای خودشون نیستن.تا چند تا کلید مناسب خودشون داشته باشن درست میشه؟
ببخشیدا آخه تا حالا این مبحث رو جای درس ندادن برای همین دارم خودم میخونم یکم سخت شد.

(۱۵ دى ۱۳۹۲ ۱۲:۴۴ ق.ظ)soheila2012 نوشته شده توسط:  چقد با حوصله جواب دادین؟!
مرسی
بازم متوجه نشدم
ببینید این ترتیب رو متوجه نمیشم!!! گفتین گزینه ی ۱ الان اگه c بخوایم وارد کنیم باید توی خونه ی ۳ باشه که نیست و اولین جای خالی میشه ۴ و بقیه...خب برای گزینه ی ۲ هم همینطوره! یعنی خیلی از اعداد جای خودشون نیستن.تا چند تا کلید مناسب خودشون داشته باشن درست میشه؟
ببخشیدا آخه تا حالا این مبحث رو جای درس ندادن برای همین دارم خودم میخونم یکم سخت شد.

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

الان برای گزینه ی ۱ اگه این ترتیب رو بدیم که مشکلی پیش نمیاد؟ ADBFECG

---

پس یعنی حداقل یک خونه پیدا کنیم که کلیدش جای خودش باشه؟

(۱۵ دى ۱۳۹۲ ۰۱:۰۰ ق.ظ)soheila2012 نوشته شده توسط:  الان برای گزینه ی ۱ اگه این ترتیب رو بدیم که مشکلی پیش نمیاد؟ ADBFECG

چراا
ببین با این ترتیبی ک شما دادی اگه وارد کنیم
A-->3
D-->4
B-->5
F-->6
E-->0
C-->1
G-->2

---

(۱۵ دى ۱۳۹۲ ۰۱:۰۰ ق.ظ)soheila2012 نوشته شده توسط:  الان برای گزینه ی ۱ اگه این ترتیب رو بدیم که مشکلی پیش نمیاد؟ ADBFECG

---

پس یعنی حداقل یک خونه پیدا کنیم که کلیدش جای خودش باشه؟

منظور منو اشتباه متوجه شدید.
من نگفتم ترتیبی پیدا کنیم که یک خونه جای خودش باشه.
گفتم یک ترتیبی پیدا کنیم که اگه با اون ترتیب کلید ها رو وارد کردیم طوری در جدول قرار بگیرن که گزینه ۱ قرار گرفته.

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

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



یعنی باید خودمون چند تا حدس بزنیم و بعد چک کنیم تعداد برخورد چن تاست؟

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



یعنی باید خودمون چند تا حدس بزنیم و بعد چک کنیم تعداد برخورد چن تاست؟

ببین عددات اصلا خونده نمیشه.
بنویسشون لطفا
من با این عددا حل کردم
۶-۱۴-۹-۳۶-۲۳
گزینه۱ و ۳: ۲ برخورد
گزینه ۲ و ۴: ۱ برخورد!

من الان دارم از روی همین شکل میبینم و مینویسم!!!
۶,۱۲,۹,۲۶,۲۳

(۲۰ دى ۱۳۹۲ ۰۳:۱۳ ب.ظ)soheila2012 نوشته شده توسط:  من الان دارم از روی همین شکل میبینم و مینویسم!!!
۶,۱۲,۹,۲۶,۲۳

یعنی میخوای بگی من چشمام ضعیف شده؟؟
عمرااااااااا
خوب با این عددایی که شما میگی گزینه ۱ بیشترین برخورد رو داره
۶mod5=1
۱۲mod5=2
۹mod5=4
۲۶mod5=1
۲۳mod5=3
خوب حالا یه جدول داریم با ۵ خونه. از چپ به راست عددها رو وارد میکنیم.
۶ رو میذاریم تو خونه ۱
۱۲ رو میذاریم تو خونه ۲
۹ رو میذاریم تو خونه ۴
۲۶ رو میخوایم بذاریم تو خونه ۱ اما خونه۱ پره پس یک برخورد، یک خونه به سمت راست حرکت میکنیم که ۲۶ رو بذاریم تو خونه ۲ اما خونه ۲ هم پر شده قبلا، دومین برخورد، باز یک خونه به سمت راست میریم خونه ۳ خالیه پس میذاریمش تو خونه ۳/
۲۳ رو میخوایم بذاریم تو خونه ۳ اما پره چون قبلا ۲۶ رو اینجا گذاشتیم، سومین برخورد، یک خونه به سمت راست میریم اما ۴ هم پره چون قبلا ۹ رو تو خونه ۴ گذاشتیم پس چهارمین برخورد. باز یک خونه به سمت راست میریم، ۵ خالیه پس ۲۳ رو میذاریم تو خونه ۵/
کلا ۴ برخورد.
بقیه گزینه ها هم همینطوری حساب میشن. اما برخورداشون کمتر از ۴ هست.
جوابشو داری؟؟ کدوم گزینه رو جواب اعلام کرده؟؟

نه بابا جسارت نکردم من خودم عینکی ام!!
جواب همون گزینه ی که شما بدست اوردین یعنی گزینه ی ۱
مرسی
عالی بود توضیحتون.
تونستم همه رو بدست بیارم.خیلی ممنون
فقط برای تکمیل خواستم بدونم این کلید ها با چه منطقی وارد جدول میشن؟من که به ترتیب از اول تا انتهای جدول رفتم،از کم به زیاد، برای سه تا درست شد ولی به گزینه ی آخر که رسیدم دیگه نشد.
بازم ممنون خیلی کیف کردم!

سوال ۴۴ کنکور IT 89

چرا گزینه ی ۴؟
با استدلالی که واسه خودم انجام داده بودم جور در نمیاد!!!

اینم جوابش از راهیان ارشد

(۲۲ دى ۱۳۹۲ ۱۱:۴۶ ب.ظ)soheila2012 نوشته شده توسط:  سوال ۴۴ کنکور IT 89

چرا گزینه ی ۴؟
با استدلالی که واسه خودم انجام داده بودم جور در نمیاد!!!

اینم جوابش از راهیان ارشد

جواب این سوال کلا اشتباهه ۱۱ که خونه ۰ قرار گرفته

---

(۲۳ دى ۱۳۹۲ ۱۲:۱۷ ق.ظ)soheila2012 نوشته شده توسط:  مرسی که جواب دادین اونم خیلی سریع.
۱۱ که خونه ی صفر گذاشته...
تو سوال اول دو تا ۶ و ۷ جای خودشون هستن میخوایی ۱۰ رو بزاریم که کلیدش ۰ هست و خالی ولی گذاشتیم ۳ که اشتباه ست!!
بد تحلیل کردم؟

به نظرم تو این سوال فقط گزینه ۳ درسته بقیه شون اشتباهه
یعنی ترتیب ۳ میتونه درست باشه بقیه نمیشه کاملا هم واضحه

اینجا وارسی خطی داریم
گزینه ۴
اول ۱۱ میاد میره توی خونه ۱
بعد۱۰ میاد میره تو خونه ۰
بعدش ۶ میاد باید بره تو خونه ۱ ولی ۱۱ اونجاس میره خونه بعدی، پره؟ نه پس اونجا میشینه
بعدش ۱۵ میاد میره تو خونه ۰، پره؟ بله برو بعدی پره؟ بله برو بعدی (۲) پره بله برو بعدی (۳) خالی هست پس باید ۱۵ اونجا باشه.

مرسی که جواب دادین اونم خیلی سریع.
۱۱ که خونه ی صفر گذاشته...
تو سوال اول دو تا ۶ و ۷ جای خودشون هستن میخوایی ۱۰ رو بزاریم که کلیدش ۰ هست و خالی ولی گذاشتیم ۳ که اشتباه ست!!
بد تحلیل کردم؟