Processing math: 100%

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۵:سوال ۲۹

سوال ۲۹

آرایه‌ی a با n عنصر به صورت صعودی مرتب شده است. می‌خواهیم ببینیم که آیا عنصر x در آرایه‌ي a وجود دارد یا خیر. برای این کار الگوریتم زیر را پیشنهاد می‌کنیم:

  1. i را مساوی ۱ و j را مساوی با n قرار بده.
  2. k را مساوی با [i+j2] قرار بده.
  3. اگر ak<x ، در این صورت i را مساوی با k+1 قرار بده٬ در غیر این صورت j را مساوی با k1 قرار بده.
  4. اگر ak=x ، در این صورت x در آرایه‌ي a وجود دارد؛ به مرحله «۷» برو.
  5. اگر ij ، در این صورت x در آرایه‌ي a وجود ندارد؛ به مرحله «۷» برو.
  6. برو به مرحله‌ي «۲».
  7. پایان.

آیا این الگوریتم برای تمام مقادیر x درست کار می‌کند؟

پاسخ

به عنوان مثال اگر اعداد ما ۴٬۱۰٬۲۰ و ۲ بوده و x=20 باشد به سادگی قابل بررسی است که این ااگوریتم در خروجی خود عدد x=20 را عضوی از آرایه‌ی a معرفی نخواهد کرد.


ابزار صفحه