۰
subtitle
ارسال: #۱
سوال دولتی سال ۷۷
با سلام:
ارایه مرتب A داده شده است. تابع زیر برای جستجوی دودویی در A( از اندیس L تا R )برای پیدا کردن x نوشته شده است .
کدامیک از گزینه های زیر در مورد الگوریتم فوق برای جستجوی دودویی در
غلط می باشد .
۱-اگر x در ارایه باشد . همواره با حداکثر( O(lgn پیدا می شود .
۲-اگر x در ارایه نباشد و پاسخ false وبا حداکثر O(lgn) مقایسه بدست می‌اید .
۳- در جستجوی نا موفق برای دو مقدار متفاوت x که در ارایه موجود است. همواره تعداد مقایسه‌ها برابر است .
۴-حداکثر تعداد مقایسه‌ها (چه موفق چه نا موفق )همواره از O(n) کمتر است .
جواب این سوال گزینه ۳ میشه ولی من نمیدونم چرا ؟؟ اصلا منظور از تعداد مقایسه در حالت ناموفق یعنی چه ؟؟
ارایه مرتب A داده شده است. تابع زیر برای جستجوی دودویی در A( از اندیس L تا R )برای پیدا کردن x نوشته شده است .
کد:
function search (x:real;L,R:integer):boolean;
var M:integer;
begin
M:=(L+r)div 2;
if (x=a[M])then return (true);
if (x<a[M] and (M>L)) then return (search (n,L,m-1));
if (x>a[M] and (m<R)) then return (search (n,M+1,r));
return (False)
end;کد:
a[1..n]۱-اگر x در ارایه باشد . همواره با حداکثر( O(lgn پیدا می شود .
۲-اگر x در ارایه نباشد و پاسخ false وبا حداکثر O(lgn) مقایسه بدست می‌اید .
۳- در جستجوی نا موفق برای دو مقدار متفاوت x که در ارایه موجود است. همواره تعداد مقایسه‌ها برابر است .
۴-حداکثر تعداد مقایسه‌ها (چه موفق چه نا موفق )همواره از O(n) کمتر است .
جواب این سوال گزینه ۳ میشه ولی من نمیدونم چرا ؟؟ اصلا منظور از تعداد مقایسه در حالت ناموفق یعنی چه ؟؟
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close