طراحی الگوریتم و طراحی الگوریتم 2

 طراحی الگوریتم و  طراحی الگوریتم 2

توضیحات محصول : کتاب های خلاصه منابع  رشته کامپیوتر و نرم افزاربرای آمادگی آزمون دکتری دانشگاه آزاد به همراه مجموعه تست با پاسخنامه تشریحی برای کنکوریها

الگوریتم جست و جوي ترتیبی 
می خواهیم ببینیم که آیا کلید x در آرایه [S[1..n با n کلید قرار دارد؟ اگر در آرایه وجود داشت، موقعیت آن (p) را برگردانـد و اگر وجود نداشت، صفر برگرداند.

در این جستجو، عنصر x را با عناصر آرایه از ابتدا به سمت انتها مقایسه می کنـیم. اگـر بـه عنصـر مورد نظر برسیم، از حلقه خارج شده و شماره خانه آرایه که x در آن قرار داشت را بر می گردانیم.

اگر جستجو تا انتهاي آرایه انجام شود و x پیدا نشود، در این حالت متغیر حلقه از تعداد عناصر آرایه بیشتر شده است و صفر را بر می گردانیم. 
int seqsearch (int n, const keytype S[ ], keytype x){ 
 index p = 1; 
 while (p  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  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