انجمنصفحه اولجستجوی انجمن

[mary87]

سلام
کتاب مقسمی جدول درهم سازی مثال ۷ ص ۴۵۱
جدول 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
که با توجه فقط به جدول دوم حل کرده ایا به نظرتون نباید جدول اول را هم در نظر بگیریم

[momon64amster]

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

[mary87]

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

[sepid]

این لینک رو بخون متوجه میشی
ارسال های ۱۵و ۱۶/

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

[Mansoureh]

(۲۷ آذر ۱۳۸۹ ۰۱:۱۱ ق.ظ)sepid نوشته شده توسط:  این لینک رو بخون متوجه میشی
ارسال های ۱۵و ۱۶/

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

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

[لهمشد]

پاسخ این سوال خیلی راحته ببین:
کلا ما ۱۱ خونه داریم تو حا فظه درست الان در صورت سوال یه جدول داده شده که با این مشخصات

کد:

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

خوب الان ببنید می خواهیم تو حا فظه اینها رو درج کنیم به روش کاوش خطی الان A می‌اید در خانه شماره ۴ حا فظه می نشنید چون جای خالی وجود داره بعد B در خانه ۸ بعد C در خانه ۲ ...... تا نوبت به E می رسد حالا چون A در خانه ۴ بود الان E نمی تونه پس پیمایش خطی میکنه تا اولین خانه پیدا شود که خانه ۵ خالی است و در انجا قرار می گیرد درسته به همین‌تر تیب کل عناصر وارد می شوند حال برای محاسبه U(N) شما باید از ابتدا جدول حافظه از تک تک عناصر از مکان شروع انها تا رسیدن به اولین خانه خالی شمارش کنید مثلا از خانه شماره ۱ که عنصر X قرار دارد تا اولین خانه خالی که شماره ۷ باشد تعداد مقایسه لازم برای خانه ۱ در بدترین حالت محسوب می شود حالا برای خانه دوم از عنصر شماره دوم یعنی C تا اولین خانه خالی که شماره ۷ باشد تعداد مقایسه برای خانه شماره دوم محسوب می شود که ۶ مقایسه است و الی اخر نکته مهم این که برای خانه خالی نیز یک مقایسه نیز لازم است مجموع کل مقایسه‌ها تقسیم بر تعداد خانه بد ترین حالت را می دهد


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

[mary87]

(۲۷ آذر ۱۳۸۹ ۰۳:۵۳ ب.ظ)لهمشد نوشته شده توسط:  پاسخ این سوال خیلی راحته ببین:
کلا ما ۱۱ خونه داریم تو حا فظه درست الان در صورت سوال یه جدول داده شده که با این مشخصات

کد:

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

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

ببخشید سوال من این بود که چرا جواب این نیست
که اول برای A شماره خانه اش ۴ است تا اولین خانه خالی میشه ۴
بعدی B شماره اش ۸ است تا اولین خانه خالی تعداد جستجو میشه ۲
بعدی Cشماره اش ۲است تا اولین خانه خالی تعداد جستجو میشه ۶
بعدی Dشماره اش ۱۱است تا اولین خانه خالی تعداد جستجو میشه ۸
بعدی Eشماره اش ۴است تا اولین خانه خالی تعداد جستجو میشه۴
بعدی Xشماره اش ۱۱است تا اولین خانه خالی تعداد جستجو میشه ۸
بعدی Yشماره اش ۵است تا اولین خانه خالی تعداد جستجو میشه ۳
بعدی Zشماره اش ۱است تا اولین خانه خالی تعداد جستجو میشه ۷
۱۱/(۷+۳+۸+۴+۸+۶+۲+۴)=U

منظورم اینه که جستجو برا مثلا Z از شماره ۱ شروع میشه تا اولین خانه خالی که میشه ۷ یا از خانه شماره ۳ که در ان درج شده تا اولین خانه خالی که میشه ۵

[sepid]

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

[لهمشد]

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

[delta]

یه سوال از این بخش
یک جدول درهم سازی به صورت آدرس دهی باز مدیریت میشودو درهم ساز‌ی به صورت یکنواخت صورت میگیردفرض کنید در حال حاضر ۷۵ درصد جدول پر شده است حداکثر تعداد prob برای جستجوی عنصری که در جدول موجود نیست چند تاست؟
۱) بستگی به الگوریتم prob دارد
۲) بستگی به طول لیست دارد
۳)۲۵ بار
۴) ۴ بار
آیا جواب گزینه ۴ میشه ؟
n/m=3/4
سوال علوم کامپیوتر ۸۹

[sepid]

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

[ف.ش]

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

[sepid]

آفاق جان
فاکتور لود یعنی چند درصد جدول هش داده توش هست.
که همون n/mکه n تعداد داده های داخل جدول و m تعداد خونه های جدوله.
فاکتور لود اینجا ۷۵درصد یا ۴/۳ هست.
باکت بندی شدن هم نمی دونم چیه!

[ف.ش]

آهان.

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