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

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۷:برنامه نویسی:سوال ۴

سوال ۴

همان‌طورکه می‌دانید یکی از مشکلاتی که در برنامه نویسی وجود دارد، عدم توانایی کامپیوتر در نگه‌داری متغیّرهای یک بیتی است. در این مسئله یک آرایه به نام ‎a‎ با اندازه ‎n8‎ از نوع ‎char‎ به شما داده شده است. می‌توانید فرض کنید که همه‌ی عناصر ‎a‎ در ابتدا صفر هستند. شما بایستی بدون استفاده از هیچ آرایه‌ی اضافی توابع زیر را بنویسید که بتوانند ‎n‎ متغیر ‎1‎ بیتی از ‎0‎ تا ‎n1‎ را ذخیره کنند یا مقدار ذخیره شده را باز گردانند (در ابتدا همه‌ی متغیّرها صفر هستند):

  1. تابع ‎void set(int i‎, ‎bool x)‎ این تابع مقدار متغیّر ‎i‎ام ‎(0i<n)‎ را ‎x‎ قرار می‌دهد. زمان این تابع باید از ‎O(1)‎ باشد.
  2. تابع bool get(int i)‎ این تابع مقدار متغیّر ‎i‎ام را بر می‌گرداند. زمان این تابع باید از ‎O(1)‎ باشد.

ابزار صفحه