دوستان من این سوال رو دارم اما از جواب خودم زیاد مطمئن نیستم، امکانش هست لطف کنید و توضیح بدین این سوال رو؟
آرایه مرتب [A[1…۶۳ حاوی ۶۳ عنصر را در نظر بگیرید که در مکان i این آرایه عدد ۴*i+1 ذخیره شده است. اگر
الگوریتم جستجوی دودویی را روی این آرایه اعمال کنیم، میانگین تعداد مقایسهها برای جستجوی موفق را بدست
آورید.
سلام .
بهترین راه برای حل این سوال استفاده از روش درخت دودویی است .
روش کار : به تعداد اعداد داخل آرایه شروع کن یه درخت دودویی بکش یعنی اینجا که ۶۳ عدد داریم یه درخت دودویی پر با ۶ سطح میشه . حالا تعداد گره های هر سطح رو ضربدر شماره سطح کن در نهایت تقسیم به تعداد اعداد تا میانگین جستجوی موفق به دست بیاد.
[tex](1*1) (2*2) (4*3) (8*4) (16*5) (32*6)=\frac{401}{63}= 6.36[/tex]
برای جستجوهای ناموفق نیز داریم :
مجموع جستجوهای موفق = مجموع جستجوهای ناموفق - n
مجموع جستجوهای ناموفق = ۴۶۴
میانگین جستجوهای ناموفق = [tex]\frac{464}{64}= 7.25[/tex]
سلام: میشه بگید چرا در مخرج فرمول بدست آوردن میانگین تعداد مقایسه ها در جستجوی ناموفق به جای n(تعداد عناصر آرایه) قرار میدهیم: n+1
(۰۳ اسفند ۱۳۹۲ ۰۲:۱۷ ب.ظ)bahman2000 نوشته شده توسط:(02 اسفند ۱۳۹۲ ۰۷:۰۶ ب.ظ)bahman2000 نوشته شده توسط:(30 بهمن ۱۳۹۲ ۰۴:۲۴ ب.ظ)bahman2000 نوشته شده توسط: سلام: میشه بگید چرا در مخرج فرمول بدست آوردن میانگین تعداد مقایسه ها در جستجوی ناموفق به جای n(تعداد عناصر آرایه) قرار میدهیم: n+1کسی نیست یه توضیح مختصری ارائه بده!!!
در سطح آخر ،۶۴ گره هست که به عنوان نود های جستجوی ناموفق در نظر گرفته میشه و تعداد مقایسه ها رو از پدر به ارث می برند.