Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

جست‌و‌جوی عدد در جدول

یک جدول n×n، شامل اعداد طبیعی و یک ماشین مقایسه‌گر در اختیار داریم. می‌دانیم در این جدول، اعداد در هر سطر و در هر ستون به صورت اکیدا صعودی مرتب شده‌اند. می‌خواهیم عدد k را در جدول جست‌وجو کنیم. برای این کار در هر مرحله، می‌توانیم یک کارت شامل دو عدد i و j به ماشین بدهیم و ماشین با گرفتن این کارت به ما پاسخ می‌دهد که عددی که در خانه‌ی سطر i و ستون j قرار دارد، بزرگ‌تر، کوچک‌تر، یا مساوی k است. روشی ارائه دهید که با حداکثر 2n1 کارت ورودی مشخص کند که k در این جدول وجود دارد یا نه؛ و در صورت وجود k، جای آن را در جدول مشخص کند.

روش خود را با پاسخ به سوالات زیر بیان کنید و درستی آن را ثابت کنید:

  • با چه کارتی شروع می‌کنید؟
  • بعد از دادن هر کارت و با توجه به جوابی که ماشین می‌دهد، چه کارتی را به ماشین می‌دهید؟

ابزار صفحه