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

المپدیا

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

ابزار کاربر

ابزار سایت


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

بامزه

حمید می‌خواهد یک دستگاه بامزه طراحی کند. هر دستگاه بامزه این خصوصیات را دارد:

عدد 0e1 روی آن نوشته شده زیر آن عدد N نوشته شده یک دریچه ورودی دارد که از آن دریچه اعداد ۱ یا ۱- به دستگاه داده می‌شود. یک دکمه دارد که هر وقت آن دکمه را فشار بدهیم، مجموع N عدد آخری که به دستگاه داده شده است را با تقریب e نمایش می دهد. یعنی در صورتی که مجموع N عدد آخر، k‌ باشد عددی که دستگاه اعلام می‌کند بین (یا برابر) k(1+e) و k (1e) می‌باشد.

حمید می‌خواهد یک e پیدا کند به صورتی که برای تمام N ها بتواند دستگاهی با این اعداد بسازد. ثابت کنید هر دستگاه با اعداد e و N، حداقل Ω(N) لازم دارد.

پاسخ

اگر دو ورودی به دستگاه بدهیم که جواب یکی ۱ و دیگری ۱- باشد، باید حالت حافظه‌ی دستگاه بعد از خواندن دو ورودی متفاوت باشد. (چرا؟) یک دنباله‌ی n تایی از ۱ و ۱- را خوب می‌نامیم اگر جمع عدد 2i ام و 2i1 ام آن ۰ شود. حال دستگاه باید برای هر دو عدد خوب حالت حافظه‌ی متفاوت داشته باشد.

در غیر این صورت فرض کنید دو عدد خوب A و B باشند که حالت حافظه‌ پس از خواندن آن‌ها یکسان است. آن‌قدر به دستگاه ۰ می‌دهیم که تا جایی که مثلا جواب A، ۱ شود و جواب B، ۱-. در این دو حالت، دستگاه حافظه‌ی یکسانی دارد که تناقض است. پس 2n2 ورودی داریم که حالت حافظه به ازای آن‌ها متفاوت است. پس دستگاه حداقل n2 بیت حافظه نیاز دارد.


ابزار صفحه