المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۸:تئوری نهایی دوم:سوال ۳

سوالو چطوری حل می‌کنی؟

دنباله‌ای از اعداد طبیعی داریم. هر مرحله دو عدد ابتدای دنباله را در نظر می‌گیریم و عدد کوچک‌تر را با یک جمع کرده وبه انتهای دنباله می‌فرستیم. اگر هم دو عدد برابر بودند،‌ یکی را به دلخواه به عنوان عدد کوچک‌تر می‌گیریم و کار را انجام می‌دهیم.

  1. ثابت کنید پس از متناهی گام، بالأخره تمام اعداد برابر می‌شوند.
  2. فرض کنید از ورودی $n$ (تعداد اعداد دنباله) و سپس خود اعداد دنباله به شما داده شود. الگوریتمی از $O(n)$ ارائه دهید که تعداد مراحل تا رسیدن به وضعیت قسمت آ (برابر شدن تمام اعداد) را پیدا کند.

ابزار صفحه