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

سلام
کتاب مقسمی جدول درهم سازی مثال 7 ص 451
جدول T، 11 خانه T[1] ‌، T[2]‌، .. ‌، T[11] دارد فایل F نیز 8 رکورد با ادرس های درهم سازی زیر تشکیل یافته است مطلوب است میانگین تعداد جستجو های ناموفق در استفاده از روش جستجوی خطی
Z Y X E D C B A رکوردها
1 5 11 4 11 2 8 4 H(K)
حل کتاب
11 10 9 8 7 6 5 4 3 2 1 ادرس
D B Y E A Z C X داده ها
U=(7+6+5+4+3+2+1+2+1+1+8)/11
که با توجه فقط به جدول دوم حل کرده ایا به نظرتون نباید جدول اول را هم در نظر بگیریم

بهتر نیست از صورت سوال یه عکس بگیری بزاری تو پست؟با گوشیت؟

لطفا یکی جواب چطوریی تعداد جستجوی ناموفق را پیدا می کنیم

این لینک رو بخون متوجه میشی
ارسال های 15و 16.

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

(27 آذر 1389 01:11 ق.ظ)sepid نوشته شده توسط: [ -> ]این لینک رو بخون متوجه میشی
ارسال های 15و 16.

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

سلام...
واقعاً برای من هم سئوال شده! این لینکی که دادید عکس هاش نمیاد! برای همین نمیدونم سئوال چیه که جوابش اونه!!!

پاسخ این سوال خیلی راحته ببین:
کلا ما 11 خونه داریم تو حا فظه درست الان در صورت سوال یه جدول داده شده که با این مشخصات
خوب الان ببنید می خواهیم تو حا فظه اینها رو درج کنیم به روش کاوش خطی الان A می‌اید در خانه شماره 4 حا فظه می نشنید چون جای خالی وجود داره بعد B در خانه 8 بعد C در خانه 2 ...... تا نوبت به E می رسد حالا چون A در خانه 4 بود الان E نمی تونه پس پیمایش خطی میکنه تا اولین خانه پیدا شود که خانه 5 خالی است و در انجا قرار می گیرد درسته به همین‌تر تیب کل عناصر وارد می شوند حال برای محاسبه U(N) شما باید از ابتدا جدول حافظه از تک تک عناصر از مکان شروع انها تا رسیدن به اولین خانه خالی شمارش کنید مثلا از خانه شماره 1 که عنصر X قرار دارد تا اولین خانه خالی که شماره 7 باشد تعداد مقایسه لازم برای خانه 1 در بدترین حالت محسوب می شود حالا برای خانه دوم از عنصر شماره دوم یعنی C تا اولین خانه خالی که شماره 7 باشد تعداد مقایسه برای خانه شماره دوم محسوب می شود که 6 مقایسه است و الی اخر نکته مهم این که برای خانه خالی نیز یک مقایسه نیز لازم است مجموع کل مقایسه‌ها تقسیم بر تعداد خانه بد ترین حالت را می دهد


-------------------------------------------------------------------------------
و من یتوکل علی الله فهو حسبه

(27 آذر 1389 03:53 ب.ظ)لهمشد نوشته شده توسط: [ -> ]پاسخ این سوال خیلی راحته ببین:
کلا ما 11 خونه داریم تو حا فظه درست الان در صورت سوال یه جدول داده شده که با این مشخصات

کد:

A=4
B=8
C=2
D=11
E=4
X=11
Y=5
Z=1

U(N) شما باید از ابتدا جدول حافظه از تک تک عناصر از مکان شروع انها تا رسیدن به اولین خانه خالی شمارش کنید مثلا از خانه شماره 1 که عنصر X قرار دارد تا اولین خانه خالی که شماره 7 باشد تعداد مقایسه لازم برای خانه 1 در بدترین حالت محسوب می شود حالا برای خانه دوم از عنصر شماره دوم یعنی C تا اولین خانه خالی که شماره 7 باشد تعداد مقایسه برای خانه شماره دوم محسوب می شود که 6 مقایسه است و الی اخر نکته مهم این که برای خانه خالی نیز یک مقایسه نیز لازم است مجموع کل مقایسه‌ها تقسیم بر تعداد خانه بد ترین حالت را می د

ببخشید سوال من این بود که چرا جواب این نیست
که اول برای A شماره خانه اش 4 است تا اولین خانه خالی میشه 4
بعدی B شماره اش 8 است تا اولین خانه خالی تعداد جستجو میشه 2
بعدی Cشماره اش 2است تا اولین خانه خالی تعداد جستجو میشه 6
بعدی Dشماره اش 11است تا اولین خانه خالی تعداد جستجو میشه 8
بعدی Eشماره اش 4است تا اولین خانه خالی تعداد جستجو میشه4
بعدی Xشماره اش 11است تا اولین خانه خالی تعداد جستجو میشه 8
بعدی Yشماره اش 5است تا اولین خانه خالی تعداد جستجو میشه 3
بعدی Zشماره اش 1است تا اولین خانه خالی تعداد جستجو میشه 7
11/(7+3+8+4+8+6+2+4)=U

منظورم اینه که جستجو برا مثلا Z از شماره 1 شروع میشه تا اولین خانه خالی که میشه 7 یا از خانه شماره 3 که در ان درج شده تا اولین خانه خالی که میشه 5

ببینید ما داریم عنصری را جستجو می کنیم که در لیست نیست مثلا N
حال تابع هش ممکنه هر یک از اعداد 1 تا 11 رو برای h(N)تولید کنه.
اگر حاصل 1 بشه میبینه خونه 1 پره و چون روش خطی است اونقدر جلو میره تا به اولین خونه خالی برسه و مطمین بشه که عنصر در لیست نیست.
اگر 2بشه باز همینطور
تا الی آخر .
برای 11 تا خروجی این تعداد جستجوها رو بشمر .
در نهایت جمع همه تقسیم بر 11.
ببین جمله هات هم غلطه چون جستجوی برای zو عناصری که در لیست هستن یک جستجوی موفقه در حالی ما به دنبال جستجوهای ناموفقیم نه عناصری که در لیست هستن.

دقیقا همین چیزی که speid گفتند درسته

یه سوال از این بخش
یک جدول درهم سازی به صورت آدرس دهی باز مدیریت میشودو درهم ساز‌ی به صورت یکنواخت صورت میگیردفرض کنید در حال حاضر 75 درصد جدول پر شده است حداکثر تعداد prob برای جستجوی عنصری که در جدول موجود نیست چند تاست؟
1) بستگی به الگوریتم prob دارد
2) بستگی به طول لیست دارد
3)25 بار
4) 4 بار
آیا جواب گزینه 4 میشه ؟
n/m=3/4
سوال علوم کامپیوتر 89

جواب گزینه 4 میشه.
فرمولش اینطوریه:
اگر m فاکتور لود در یک جدول هش با آدرسدهی باز باشه زمان جستجوی ناموفق برابر
1 تقسیم بر 1منهای m.
منبع: پاور پوینت clrs که تو بسته مانشت هست .
اثباتش رو نوشته.

اینجا که حرفی از فاکتور لود یا مثلا باکت بندی شدن نزده! از کجا بفهمیم منظورش چی بوده!

آفاق جان
فاکتور لود یعنی چند درصد جدول هش داده توش هست.
که همون n/mکه n تعداد داده های داخل جدول و m تعداد خونه های جدوله.
فاکتور لود اینجا 75درصد یا 4/3 هست.
باکت بندی شدن هم نمی دونم چیه!

آهان.

باکت بندی یعنی توی هر خونه چند رکورد بشه جا داد(مثل بلوک بندی توی معماری) اونوقت به طور متوسط توی هر خونه n/m جا میگیره.