رایانه‌ی باستانی
باستان‌شناسان در زمان حفاری شهر باستانی آتلانتیس به یک رایانه‌ی باستانی برخوردند که در عین سادگی دارای توانایی‌های بسیاری بود. بعد از انجام بررسی‌های اولیه مشخص شد که این رایانه برای انجام محاسبات، اعداد را به صورت نمایش در مبنای ۲ و در رشته‌های به طول ۳۲ از ارقام ۰ و ۱ نگهداری می‌کند. به هر یک از ارقام ۰ و ۱ در نمایش دودویی، یک بیت گفته می‌شود و بیت‌ها را از سمت راست به چپ با اعداد ۰ تا ۳۱ شماره‌گذاری می‌کنیم. به عنوان مثال این رایانه برای ذخیره عدد ۲۷ رشته زیر را نگهداری می‌کند:
0000 0000 0000 0000 0000 0000 0001 1011
برای نگهداری اعداد، این رایانه یک حافظه‌‌ی ۲۶ خانه‌ای دارد که در هر خانه می‌تواند یک عدد ۳۲ بیتی را ذخیره کند. این خانه‌ها با حروف $$a تا $z$ نام‌گذاری می‌شوند.
همچنین مشخص شده‌است این رایانه توانایی انجام عملیات‌های «و بیتی»، «یا بیتی»، «نقیض بیتی»، «شیفت بیتی به سمت راست»، جمع و ضرب را دارد.
برای نمایش راحت‌تر اعداد، هر عدد را به صورت یک عدد ۸ رقمی در مبنای ۱۶ نشان می‌دهیم. به عنوان مثال عدد ۲۷ را به صورت زیر نمایش می‌دهیم: (دقت کنید ارقام ۱۰,۱۱,⋯,۱۵ در مبنای ۱۶ با $A$, $B$ ,… ,$F$ نمایش داده می‌شوند)
0000001B
هر دستور در این رایانه، یکی از عملیات‌های بالا را روی اعداد ثابت یا اعداد درون حافظه‌ها اجرا کرده و نتیجه را در یکی از خانه‌های حافظه ذخیره می‌کند. دستورهای این رایانه به شکل زیر استفاده می‌شوند:
| دستور | عملکرد | توضیح |
| ADD a,b,c | مقدار حافظه a را برابر حاصل جمع b و c قرار می‌دهد | |
| MLT a,b,c | مقدار حافظه a را برابر حاصل ضرب b و c قرار می‌دهد | |
| AND a,b,c | مقدار حافظه a را برابر حاصل «و منطقی» b و c قرار می‌دهد | بیت $i$ام در حافظه a در صورتی برابر ۱ می‌شود که بیت $i$ ام هم در b و هم در c برابر ۱ باشد |
| OR a,b,c | مقدار حافظه a را برابر حاصل «یا منطقی» b و c قرار می‌دهد | |
| SHR a,b,c | b را c واحد به سمت راست شیفت داده و در a ذخیره می کند. | مقدار a را برابر $000...b_{31}b_{30}...b_c$ قرار می دهد(مقدار b تغییر نمی‌کند) |
| NOT a,b | «نقیض منطقی» b را در a ذخیره می کند. | بیت $i$ ام در حافظه a در صورتی برابر ۱ می‌شود که بیت $i$ام درb برابر ۰ باشد |
هر برنامه در این کامپیوتر دنباله‌ای از دستورها است که به ترتیب اجرا می‌شوند. به عنوان مثال فرض کنید دو عدد در حافظه‌های $a$ و $b$ ذخیره شده‌اند. برنامه زیر مشخص می‌کند که حاصل جمع آن‌ها به ۲ بخش‌پذیر است یا نه (اگر بخش‌پذیر باشد عدد ۱ را در حافظه $$z ذخیره می‌کند و در غیر این صورت عدد ۰ را در حافظه $z$ ذخیره می‌کند)
ADD c,a,b
AND d,c,00000001
NOT e,d
AND z,e,00000001
بعد از انجام تحقیقات مرحله دوم مشخص شد که این رایانه دارای یک دستور عجیب نیز هست که تعداد بیت‌های در اندیس‌های زوج یک عدد که دارای مقدار ۱ هستند را در یک خانه حافظه ذخیره می‌کند. برای استفاده از این دستور باید به شکل زیر عمل کرد: CNT a,b بعد از اجرای این دستور، تعداد بیت های ۱ در اندیس‌های زوج عدد در حافظه $b$ (یا عدد ثابت $b$) در خانه‌ی حافظه $$a ذخیره می‌شود. به عنوان مثال بعد از اجرای برنامه زیر، عدد ۲ در متغیر $z$ ذخیره می‌شود، زیرا بیت‌های $a_0$ و a_2$$ دارای مقدار ۱ خواهند بود :
ADD a,00000002,00000005
CNT z,a
توجه: در هر قسمت ابتدا برنامه‌ی خود را نوشته و سپس آن را در چند سطر توضیح دهید.
الف) برنامه‌ای بنویسید که با استفاده از ۴ دستور، تعداد بیت‌های با مقدار ۱ عددی را که در حافظه $$a ذخیره شده است را در حافظه $$z ذخیره کند.
ب) اولین برنامه‌ای که برای این کامپیوتر کشف شد، برنامه‌ای بود که تعداد تکرارهای رشته ۰۱ را در نمایش دودویی عددی که در حافظه a$$ ذخیره شده است، به شرطی که ۰ در یک اندیس فرد و ۱ در یک اندیس زوج آمده باشد را محاسبه و در حافظه z$$ ذخیره می‌کرد. به عنوان مثال اگر عدد درون حافظه $$a برابر DDABCDEF باشد، این مقدار برابر ۳ است.
a = 1101 1101101010111100110111101111
برنامه‌ای با حداکثر ۴ دستور بنویسید تا این کار را انجام دهد. برای برنامه خود شیوه‌ی کارکرد آن را در چند سطر توضیح دهید.
پ) بعد از کشف برنامه‌ی قسمت قبل، محققان برنامه‌ای را پیدا کردند که عملکرد دستور CNT را شبیه‌سازی می‌کرد. اما متاسفانه یک عدد در دستور آخر برنامه قابل خواندن نبود. این برنامه به شکل زیر است:(می‌توانید فرض کنید عدد درون حافظه a$$ برابر ۵۵۵۵۵۵۵۵ نیست)
AND b,a,55555555
SHR c,b,00000002
ADD d,b,c
AND e,d,33333333
MLT f,e,11111111
SHR z,f, (…)
عدد مربوط به مکان خالی را کامل کنید و راه حل خود را توضیح دهید.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
