سلام
کتاب مقسمی جدول درهم سازی مثال ۷ ص ۴۵۱
جدول T، ۱۱ خانه T[1] ، T[2]، .. ، T[11] دارد فایل F نیز ۸ رکورد با ادرس های درهم سازی زیر تشکیل یافته است مطلوب است میانگین تعداد جستجو های ناموفق در استفاده از روش جستجوی خطی
Z Y X E D C B A رکوردها
۱ ۵ ۱۱ ۴ ۱۱ ۲ ۸ ۴ H(K)
حل کتاب
۱۱ ۱۰ ۹ ۸ ۷ ۶ ۵ ۴ ۳ ۲ ۱ ادرس
D B Y E A Z C X داده ها
U=(7+6+5+4+3+2+1+2+1+1+8)/11
که با توجه فقط به جدول دوم حل کرده ایا به نظرتون نباید جدول اول را هم در نظر بگیریم
بهتر نیست از صورت سوال یه عکس بگیری بزاری تو پست؟با گوشیت؟
لطفا یکی جواب چطوریی تعداد جستجوی ناموفق را پیدا می کنیم
این لینک رو بخون متوجه میشی
ارسال های ۱۵و ۱۶/
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
(۲۷ آذر ۱۳۸۹ ۰۱:۱۱ ق.ظ)sepid نوشته شده توسط: این لینک رو بخون متوجه میشی
ارسال های ۱۵و ۱۶/
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
سلام...
واقعاً برای من هم سئوال شده! این لینکی که دادید عکس هاش نمیاد! برای همین نمیدونم سئوال چیه که جوابش اونه!!!
پاسخ این سوال خیلی راحته ببین:
کلا ما ۱۱ خونه داریم تو حا فظه درست الان در صورت سوال یه جدول داده شده که با این مشخصات
کد:
A=4
B=8
C=2
D=11
E=4
X=11
Y=5
Z=1-------------------------------------------------------------------------------
و من یتوکل علی الله فهو حسبه
(۲۷ آذر ۱۳۸۹ ۰۳:۵۳ ب.ظ)لهمشد نوشته شده توسط: پاسخ این سوال خیلی راحته ببین:ببخشید سوال من این بود که چرا جواب این نیست
کلا ما ۱۱ خونه داریم تو حا فظه درست الان در صورت سوال یه جدول داده شده که با این مشخصات
U(N) شما باید از ابتدا جدول حافظه از تک تک عناصر از مکان شروع انها تا رسیدن به اولین خانه خالی شمارش کنید مثلا از خانه شماره ۱ که عنصر X قرار دارد تا اولین خانه خالی که شماره ۷ باشد تعداد مقایسه لازم برای خانه ۱ در بدترین حالت محسوب می شود حالا برای خانه دوم از عنصر شماره دوم یعنی C تا اولین خانه خالی که شماره ۷ باشد تعداد مقایسه برای خانه شماره دوم محسوب می شود که ۶ مقایسه است و الی اخر نکته مهم این که برای خانه خالی نیز یک مقایسه نیز لازم است مجموع کل مقایسه‌ها تقسیم بر تعداد خانه بد ترین حالت را می دکد:
A=4
B=8
C=2
D=11
E=4
X=11
Y=5
Z=1
که اول برای A شماره خانه اش ۴ است تا اولین خانه خالی میشه ۴
بعدی B شماره اش ۸ است تا اولین خانه خالی تعداد جستجو میشه ۲
بعدی Cشماره اش ۲است تا اولین خانه خالی تعداد جستجو میشه ۶
بعدی Dشماره اش ۱۱است تا اولین خانه خالی تعداد جستجو میشه ۸
بعدی Eشماره اش ۴است تا اولین خانه خالی تعداد جستجو میشه۴
بعدی Xشماره اش ۱۱است تا اولین خانه خالی تعداد جستجو میشه ۸
بعدی Yشماره اش ۵است تا اولین خانه خالی تعداد جستجو میشه ۳
بعدی Zشماره اش ۱است تا اولین خانه خالی تعداد جستجو میشه ۷
۱۱/(۷+۳+۸+۴+۸+۶+۲+۴)=U
منظورم اینه که جستجو برا مثلا Z از شماره ۱ شروع میشه تا اولین خانه خالی که میشه ۷ یا از خانه شماره ۳ که در ان درج شده تا اولین خانه خالی که میشه ۵
ببینید ما داریم عنصری را جستجو می کنیم که در لیست نیست مثلا N
حال تابع هش ممکنه هر یک از اعداد ۱ تا ۱۱ رو برای h(N)تولید کنه.
اگر حاصل ۱ بشه میبینه خونه ۱ پره و چون روش خطی است اونقدر جلو میره تا به اولین خونه خالی برسه و مطمین بشه که عنصر در لیست نیست.
اگر ۲بشه باز همینطور
تا الی آخر .
برای ۱۱ تا خروجی این تعداد جستجوها رو بشمر .
در نهایت جمع همه تقسیم بر ۱۱/
ببین جمله هات هم غلطه چون جستجوی برای zو عناصری که در لیست هستن یک جستجوی موفقه در حالی ما به دنبال جستجوهای ناموفقیم نه عناصری که در لیست هستن.
دقیقا همین چیزی که speid گفتند درسته
یه سوال از این بخش
یک جدول درهم سازی به صورت آدرس دهی باز مدیریت میشودو درهم سازی به صورت یکنواخت صورت میگیردفرض کنید در حال حاضر ۷۵ درصد جدول پر شده است حداکثر تعداد prob برای جستجوی عنصری که در جدول موجود نیست چند تاست؟
۱) بستگی به الگوریتم prob دارد
۲) بستگی به طول لیست دارد
۳)۲۵ بار
۴) ۴ بار
آیا جواب گزینه ۴ میشه ؟
n/m=3/4
سوال علوم کامپیوتر ۸۹
جواب گزینه ۴ میشه.
فرمولش اینطوریه:
اگر m فاکتور لود در یک جدول هش با آدرسدهی باز باشه زمان جستجوی ناموفق برابر
۱ تقسیم بر ۱منهای m.
منبع: پاور پوینت clrs که تو بسته مانشت هست .
اثباتش رو نوشته.
اینجا که حرفی از فاکتور لود یا مثلا باکت بندی شدن نزده! از کجا بفهمیم منظورش چی بوده!
آفاق جان
فاکتور لود یعنی چند درصد جدول هش داده توش هست.
که همون n/mکه n تعداد داده های داخل جدول و m تعداد خونه های جدوله.
فاکتور لود اینجا ۷۵درصد یا ۴/۳ هست.
باکت بندی شدن هم نمی دونم چیه!
آهان.
باکت بندی یعنی توی هر خونه چند رکورد بشه جا داد(مثل بلوک بندی توی معماری) اونوقت به طور متوسط توی هر خونه n/m جا میگیره.