توضیحات محصول : کتاب های خلاصه منابع رشته کامپیوتر و نرم افزاربرای آمادگی آزمون دکتری دانشگاه آزاد به همراه مجموعه تست با پاسخنامه تشریحی برای کنکوریها
الگوریتم جست و جوی ترتیبی
می خواهیم ببینیم که آیا کلید x در آرایه [S[1..n با n کلید قرار دارد؟ اگر در آرایه وجود داشت، موقعیت آن (p) را برگردانـد و اگر وجود نداشت، صفر برگرداند.
در این جستجو، عنصر x را با عناصر آرایه از ابتدا به سمت انتها مقایسه می کنـیم. اگـر بـه عنصـر مورد نظر برسیم، از حلقه خارج شده و شماره خانه آرایه که x در آن قرار داشت را بر می گردانیم.
اگر جستجو تا انتهای آرایه انجام شود و x پیدا نشود، در این حالت متغیر حلقه از تعداد عناصر آرایه بیشتر شده است و صفر را بر می گردانیم.
int seqsearch (int n, const keytype S[ ], keytype x){
index p = 1;
while (p <= n="" br="" /> p++;
if (p > n) p=0;
return p;
}
تذکر: نوع داده index برای متغیر صحیحی است که به عنوان اندیس به کار میرود.
تذکر : اگر نخواهیم روالی مقادیر را از طریق آرایه برگرداند، آن آرایه را با واژه const معرفی میکنیم.
الگوریتم جست و جوی دودویی
با فرض این که به دنبال x هستیم، الگوریتم ابتدا، x را با عنصر میانی آرایه مقایسه میکند. اگر مساوی بود، الگوریتم به پایان مـیرسد.
اگر x کوچکتر از عنصر میانی بود، باید در نیمه نخست آرایه باشد (اگر وجود داشته باشد) و الگوریتم جسـت و جـو در نیمـه
نخست آرایه تکرار میگردد (یعنی x با عنصر میانی نیمه اول آرایه مقایسه میشود. اگر مساوی بود، الگوریتم به پایان میرسد و الی
آخر).
اگر x بزرگتر از عنصر میانی آرایه بود، جست و جو در نیمه دوم آرایه تکرار میشد. این رویه چندین بار تکرار میگردد تـا x
پیدا شود یا معلوم گردد که x در آرایه وجود ندارد.
مثال: برای پیدا کردن عدد 9 در آرایه مرتب زیر با روش جستجوی دودویی، به چند مقایسه نیاز است؟
1 2 3 4 5 6 7 8 9
5 9 12 20 35 50 82 88 97
طراحی الگوریتم وطراحی الگوریتم
«11» WWW.SANJESH.IR
حل:
ابتدا عدد 9 با عنصر وسط آرایـه یعنـی 35 مقایسـه مـی شـود و چـون از آن کـوچکتر اسـت مقایسـه بـه طـور بازگشـتی در زیـر
آرایه [x[1..4 انجام می گیرد، یعنی با عنصر وسط این آرایه مقایسه می شود که با آن برابر است. بنابراین با دو مقایسـه بـه نتیجـه
می رسیم.
الگوریتم جستجوی دودویی
در الگوریتم زیر تعیین می مکنی که آیا x در آرایه مرتب n کلیدی [S[1..n وجود دارد یا خیر. اگر وجود داشـت موقعیـت x در S
یعنی p و اگر وجود نداشت صفر را بر می گرداند.
void binsearch (int n ,const keytype S[ ], keytype x, index& p){
index low, high, mid;
low=1; high = n; p = 0;
while (low <= high="" p="=" br="" /> mid = [(low + high)/2];
if (x == S[mid]) p = mid;
else if (x < S[mid]) high = mid–1;
else low = mid+1;
}
}
تذکر: اگر در آخر نوع داده، علامت & قرار دهیم یعنی پارامتر حاوی مقداری اسـت کـه توسـط الگـوریتم بازگردانـده مـیشـود. (از
علامت & برای آرایه استفاده نمی کنیم.)
مقایسه کار انجام شده توسط جست وجوی دودویی و جست وجوی ترتیبی
جست و جوی ترتیبی، n مقایسه انجام میدهد تا تعیین کند آیا x در آرایهای به اندازه n وجود دارد یا خیر.
تعداد مقایسه های انجام شده توسط جست و جوی دودویی در یک آرایه مرتب n عنصری برابر 1nlg+ می باشد.
مثال: در یک آرایه مرتب 32 عنصری ، وقتی x بزرگتر از تمام عناصر موجود در آرایه باشد، الگوریتم جستجوی دودویی 6 مقایسه
انجام میدهد . lg + = )6132) . ترتیب شماره عناصر مقایسه شده عبارتند از: 16 , 24 , 28 , 30 , 31 , 32 .
2 تذکر: در تحلیل الگوریتمها به جای
log از نماد خلاصه lg استفاده می کنیم.
مثال: ههنگامی که آرای حاوی 4 میلیارد عنصر باشد، جست و جوی دودویی تنها بـه 33 مقایسـه و جسـت و جـوی ترتیبـی، چهـار
میلیارد مقایسه نیاز دارد. حتی اگر کامپیوتر قادر به کامل کردن یک بار گذر از حلقه while در عرض یک نانوثانیه باشد، جسـت و
جوی ترتیبی 4 ثانیه زمان میبرد تا عدم وجود x را در آرایه اعلان کند، حال آن که جسـت و جـوی دودویـی تقریبـاً بلافاصـله بـه
نتیجه . میرسد
تذکر: جست و جوی ترتیبی هنوز هم در مقیاسهای زمانی قابل تحمل برای انسان، عمل می کند. حال به یک الگـوریتم نامناسـب
میپردازیم که کار را در زمانی قابل تحمل به انجام نمیرساند. «WWW.SANJESH.IR «12
تست های کارشناسی ارشد
-1 کدام گزینه نادرست است؟ (علوم کامپیوتر - دولتی )83
1) تمام مسائل P به وسیله یک الگوریتم غیر قطعی در زمان چند جمله ای حل می شوند.
2) تمام مسائل NP به وسیله یک الگوریتم غیر قطعی در زمان چند جمله ای حل می شوند.
3) تمام مسائل NP-hard به وسیله یک الگوریتم غیر قطعی در زمان چند جمله ای حل می شوند.
4) تمام مسائل NP-Complete به وسیله یک الگوریتم غیر قطعی در زمان چند جمله ای حل می شوند.
-2 اگر یک مسئله NP-Complete مانند L وجود داشته باشد که L Î P باشد، در آن صورت: (علوم - دولتی )82
¹ NPP (2 = NPP ( 1
Ï - hardNPL (4 Î - hardNPL ( 3
-3 گزینه صحیح را انتخاب کنید. (علوم کامپیوتر - دولتی )82
1) مسائل NP-Complete زیر مجموعه مسائل NP-hard . می باشند
2) مسائل NP-hard زیر مجموعه مسائل NP-Complete . می باشند
3) مسائل NP زیر مجموعه مسائل P . می باشند
P=NP (4
نوع فایل:PDF
سایز:3.64 mb
تعداد صفحه:169