سوال ۴

یک ماشین‌حساب در اختیار داریم که دارای ۴ حافظه است که با شماره‌های ۱ تا ۴ مشخص می‌شوند. هر یک از این حافظه‌ها می‌تواند یک عدد صحیح مثبت را در خود نگهداری کند (محدودیتی در مقدار این عدد وجود ندارد). این ماشین‌حساب می‌تواند یک برنامه را اجرا کند. هر برنامه شامل تعدادی دستور است که به ترتیب مشخصی قرار گرفته‌اند. این ماشین‌حساب تنها سه نوع دستور را قبول می‌کند. این سه نوع دستور عبارت‌اند از:

• $n$ I ($n$ یک عدد صحیح بین ۱ تا ۴ است.): این دستور به مقدار حافظه‌ی شماره‌ی$ n$ یکی اضافه می‌کند. پس از اجرای این دستور، ماشین‌حساب دستور بعدی را اجرا می‌کند.

• $n$ D ($n$ یک عدد صحیح بین ۱ تا ۴ است.): اگر مقدار حافظه‌ی شماره‌ی $n$ مساوی صفر باشد، این دستور هیچ کاری انجام نمی‌دهد و پس از آن دستور بعدی اجرا می‌شود. ولی اگر مقدار حافظه‌ی شماره‌ی $n$ مثبت باشد، این دستور یکی از مقدار حافظه‌ی شماره $n$ کم می‌کند و سپس از دستور بعدی صرف‌نظر کرده و دستور بعدازآن را اجرا می‌کند.

• $d$ T ($d$ یک عدد صحیح مثبت یا منفی است.): این دستور به تنهایی کاری انجام نمی‌دهد ولی مقدار $d$ مشخص می‌کند که چه دستوری پس از این دستور اجرا شود. اگر $d$ یک عدد منفی باشد، دستوری که ∣$d$∣ تا قبل از این دستور قرار گرفته است پس از این دستور اجرا می‌شود. به همین صورت اگر $d$ یک عدد مثبت باشد، دستوری که $d$ تا بعد از این دستور قرار گرفته است پس از این دستور اجرا می‌شود.

اجرای یک برنامه از دستور اول آن شروع می‌شود و با توجه به شرایط فوق تا وقتی‌ که دستوری که باید اجرا شود وجود داشته باشد، ادامه می‌یابد. برای مثال این برنامه را در نظر بگیرید:

D 2

T 2

T -2

D 1

T 3

I 2

T -3

این برنامه ابتدا حافظه‌ی شماره‌ی ۲ را پاک می‌کند و سپس مقدار حافظه‌ی شماره‌ی ۱ را در حافظه‌ی شماره‌ی ۲ ذخیره می‌کند و مقدار حافظه‌ی شماره‌ی ۱ را مساوی با صفر می‌کند. اجرای برنامه پس از اجرای دستور T 3 تمام می‌شود؛ چون دستوری که باید اجرا شود وجود ندارد.

۱) برنامه زیر را در نظر بگیرید:

D 1

T 6

D 1

T 3

I 2

T -5

I 3

D 2

T 5

I 1

D 2

T -11

T -3

اگر مقدار حافظه‌ی شماره‌ی ۱ برابر با ۱۳۷۴ و مقدار بقیه‌ی حافظه‌ها برابر با صفر باشد، پس از اجرای این برنامه این مقادیر به چه صورت خواهند بود؟

۲) فرض کنید$ a_n$ تعداد اعدادی باشد که از ارقام ۱ و ۲ تشکیل شده‌اند و مجموع ارقام آن‌ها برابر با$ n$ است. برنامه‌ای برای این ماشین‌حساب بنویسید که مقدار$ a_n$ را محاسبه کند. مقدار$ n$ قبل از اجرای برنامه در حافظه‌ی شماره ۱ قرار داده می‌شود و مقدار بقیه‌ی حافظه‌ها در ابتدا برابر صفر است. در انتهای اجرای برنامه مقدار$ a_n$ باید در حافظه‌ی شماره‌ی ۱ ذخیره شده باشد. تعداد دستورهای برنامه‌ی شما نباید از ۳۰ بیشتر باشد.

۳) فرض کنید$ b_n$ تعداد اعدادی باشد که از ارقام ۱ و ۲ و ۳ تشکیل شده‌اند و مجموع ارقام آن‌ها برابر با$ n$ است و همچنین ارقام یکان و دهگان آن‌ها هر دو همزمان یک نیستند. (برای مثال $b_4= 5$است چون تنها عددهای ۳۱ و ۲۲ و ۱۲۱ و ۱۱۲ و ۱۳ وجود دارند که دارای این شرایط هستند.) برنامه‌ای برای این ماشین‌حساب بنویسید که مقدار$ b_n$ را محاسبه کند. مقدار$ n$ قبل از اجرای برنامه در حافظه‌ی شماره‌ی ۱ قرار داده می‌شود و مقدار بقیه‌ی حافظه‌ها در ابتدا برابر با صفر است. در انتهای اجرای برنامه مقدار$ b_n$ باید در حافظه‌ی شماره‌ی ۱ ذخیره شده باشد.

توجه کنید که در قسمت‌های ۲ و ۳ باید در مورد ایده‌ی برنامه‌ای که می‌نویسید توضیح دهید.

• سوال بعد
• سوال قبل