سه دستورالعمل
یک کامپیوتر دارای حافظه‌ای است که می‌تواند یک لیست از عددها (که هر کدام از آن‌ها ۰، ۱ یا ۲ هستند) را نگه‌داری کند. محدودیتی در طول لیستی که در حافظه‌ی این کامپیوتر نگه‌داری می‌شود وجود ندارد. این کامپیوتر می‌تواند یک برنامه را اجرا کند. هر برنامه شمال تعدادی دستور است که به ترتیب مشخصی قرار گرفته‌اند. این کامپیوتر تنها سه نوع دستورالعمل را قبول می‌کند که عبارت‌اند از:
- $E\quad x$($x$ یکی از عددهای ۰، ۱ یا ۲ است.): این دستور، عدد $x$ را به انتهای (سمت راست) لیست عددها اضافه می‌کند و پس از آن دستور بعدی را انجام می‌دهد.
- $D$: عددی که در ابتدای (سمت چپ) لیست عددها قرار دارد را از لیست برمی‌دارد. اگر این عدد ۰ بود، دستور بعدی را اجرا می‌کند؛ اگر ۱ بود، یک دستور را جا می‌اندازد و دستور بعد از آن را اجرا می‌کند؛ و اگر ۲ بود، دو دستور را جا می‌اندازد و دستور بعدی را اجرا می‌کند.
- $J\quad d$ ($d$ یک عدد صحیح مثبت یا منفی است.): اگر $d$ مثبت بود، دستوری که $d$ تا بعد از دستور فعلی است و اگر $d$ منفی بود، دستوری که $d$ تا قبل از دستور فعلی است را اجرا می‌کند.
اجرای برنامه با اجرای دستورالعمل اول آن شروع می‌شود و مطابق با قوانین فوق ادمه می‌یابد. اگر در یک مرحله، دستورالعملی که قرار است اجرا شود، وجود نداشت (برای مثال به یک دستور $J$ به یک دستور که در برنامه وجود ندارد پرش کردیم)، اجرای برنامه متوقف می‌شود. همچنین اگر لیست عددهای خالی بود و به دستورالعمل $D$ برخوردیم، برنامه متوقف می‌شود.
برای مثال برنامه‌ی زیر را در نظر بگیرید. (شماره‌های نوشته شده در سمت چپ دستورات، نشان‌دهنده‌ی ترتیب اجرای آن‌هاست.) در صورتی که پیش از اجرای این برنامه لیست عددها $1,1$ باشد، با اجرای این برنامه به ترتیب دستورات شماره‌ی ۱، ۳، ۵، ۶، ۳ و ۴ اجرا می‌شوند و پس از آن، برنامه متوقف می‌شود. پس از متوقف شدن برنامه، لیست عددها خالی خواهد بود.
$1.D \\ 2.E\quad 1 \\ 3.D \\ 4.J\quad 4 \\ 5.E\quad 0 \\ 6.J\quad -3$
الف) برنامه‌ی زیر را در نظر بگیرید:
$1.E \quad 2 \\ 2.D \\ 3.J \quad 3\\ 4.J\quad 4 \\ 5.J\quad 10 \\ 6.E \quad 1 \\ 7. J\quad -5 \\ 8.E \quad 0 \\ 9.J\quad -7$
در صورتی که قبل از اجرای برنامه، لیست عددها ۰، ۱، ۰، ۰، ۱ باشد، پس از اجرای برنامه این لیست به چه شکلی در خواهد آمد؟ توضیح دهید.
ب) برنامه‌ی زیر را در نظر بگیرید:
$1.E\quad 2 \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad 10.E\quad 0 \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad 19.J \quad-15 \\ 2.E\quad 2 \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad 11.J\quad-8 \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad 20.J\quad-15 \\ 3.D \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad 12.E\quad 2 \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad 21.J\quad 10 \\ 4.J\quad 5 \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad 13.E\quad 1 \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad 22.E\quad 0 \\ 5.J \quad 1 \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad 14.D \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad 23.J\quad -9 \\ 6.E\quad 2 \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad 15.J\quad 7 \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad 24.E\quad 1 \\ 7.E\quad 0 \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad 16.J\quad 8 \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad 25.J\quad -11 \\ 8.J\quad 6 \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad 17.E\quad 2 \\ 9.D \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad 18.D$
در صورتی که قبل از اجرای این برنامه، لیست عددها از ۱۳۷۶ تا عدد صفر تشکیل شده باشد، پس از اجرای این برنامه این لیست به چه شکلی در خواهد آمد؟ توضیح دهید.
ج) فرض کنید که یک لیست که یک لیست از عددهای ۰ و ۱ در حافظه‌ی این کامپیوتر قرار دارد. (توجه کنید که لیست، شامل عدد ۲ نیست.) برنامه‌ای برای این کامپیوتر بنویسید که پس از اجرای آن، این لیست برعکس شود. در مورد برنامه‌ای که می‌نویسید توضیح دهید.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
