زبان چرخشی
در این سوال با یک زبان برنامه نویسی جدید سر و کار دارید. ابتدا توضیحات زیر را در مورد بخشهای مختلف زبان بخوانید:
حافظه و اشاره گر
این زبان تنها از سه خانهی حافظه با شمارههای ۱ تا ۳ استفاده میکند که دور یک دایره قرار گرفته اند و هر کدام میتوانند یک عدد صحیح را ذخیره کنند. به این خانه ها متغیر نیز میگوییم. یک اشاره گر هم وجود دارد که در هر لحظه بهیکی از این سه متغیر اشاره میکند و در هنگام شروع برنامه روی متغیر شماره ۱ است. به متغیری که اشاره گر به آن اشاره میکند، متغیر درگیر میگوییم. برنامه دارای تعدادی دستور است که پس از اجرای هر یک، اشاره گر یک واحد در جهت ساعت گرد حرکت میکند تا به متغیر بعدی اشاره کند.
زیربرنامه ها
هر برنامه در این زبان از تعدادی زیربرنامه تشکیل میشود. فرض کنید زیربرنامههای یک برنامه به ترتیب $C_1$ تا $C_k$ باشد. زیربرنامه بعدی $C_i$ به ازای هر $1\le i \le k-1$ برابر $C_{i+1}$ است. زیربرنامه بعدی $C_k$ نیز $C_1$ است. زیربرنامه قبلی زیربرنامه بعدی هر زیربرنامه، خود آن است.
هر برنامه تعدادی دستور دارد که زیر هم نوشته شده است. دستور بعدی هر دستور، دستور زیر آن است و دستور بعدی دستور آخر، دستور اول زیربرنامه است.
دستور ها
در این قسمت دستورهای مجاز آمده است. در صورتی که دستور خط بعدی برای اجرا را مشخص نکند به دستور بعدی میرویم.
- افزایش (INC): متغیر درگیر را یک واحد زیاد میکند.
- کاهش (DEC): متغیر درگیر را یک واحد زیاد میکند.
- پرش (JMP): کار خاصی انجام نمی دهد.
- خروج (EXT): اگر متغیر درگیر ۰ باشد به برنامه خاتمه میدهد
- حرکت به جلو (NXT): اگر متغیر درگیر ۰ باشد به دستور اول زیربرنامه بعدی میرویم.
- حرکت به عقب (PRV): اگر متغیر درگیر ۰ باشد به دستور قبلی میرویم.
مثال
مساله
شما باید برای هر یک از قسمتهای زیر، با زبان گفته شدهیک برنامه متشکل از تعدادی زیر برنامه بنویسید. برای درستی برنامه خود اثباتی مختصر نیز بنویسید. تنها کسانی نمره کامل میگیرند که هر دوی برنامه و اثبات را به درستی نوشته باشند.
در زیر A و B اعدادی طبیعی هستند. مقدار متغیرهای ۱ و ۲ در انتها اهمیتی ندارد.
آ) برنامه ای بنویسید که اگر مقدار متغیرهای ۱ و ۲ و ۳ در ابتدا به ترتیب A و B و ۰ باشد، پس از اجرای برنامه مقدار متغیر ۳ برابر A+B شود.
پاسخ
برنامه زیر دو زیر برنامه دارد. در زیربرنامه اول تا زمانی که مقدار متغیر ۱ برابر ۰ نیست، یک واحد از آن کم شده و به متغیر ۳ اضافه میشود. سپس به زیربرنامه دوم رفته و همین کار با متغیر ۲ انجام میشود. به این ترتیب مقدار $A+B$ در متغیر ۳ ریخته خواهد شد.
- C1:NXT,JMP,JMP,DEC,JMP,INC
- C2:JMP,EXT,JMP,JMP,DEC,INC
ب) برنامه ای بنویسید که اگر مقدار متغیرهای ۱ و ۲ و ۳ در ابتدا به ترتیب A و B و ۰ باشد، پس از اجرای برنامه مقدار متغیر ۳ برابر max(A,B) شود.
پاسخ
برنامه زیر سه زیربرنامه دارد. در زیربرنامه اول تا زمانی که مقدار هیچ کدام از دو متغیر ۱ و ۲ برابر صفر نیست، یک واحد از هر کدام کم شده و به متغیر ۳ اضافه میشود. با این کار min(A,B) در متغیر ۳ ریخته شده و یکی از متغیرهای ۱ و ۲ برابر ۰ و دیگری برابر $|A-B|$ است.کافی است در زیربرنامههای دوم و سوم مقادیر باقی ماندهی متغیرهای ۱ و ۲ را در متغیر ۳ بریزیم ( مانند قسمت آ ):
- C1:NXT,NXT,JMP,DEC,DEC,INC
- C2:NXT,JMP,JMP,DEC,JMP,INC
- C3:JMP,EXT,JMP,JMP,DEC,INC
پ) برنامه ای بنویسید که اگر مقدار متغیرهای ۱ و ۲ و ۳ در ابتدا به ترتیب A و B و ۰ باشد، پس از اجرای برنامه مقدار متغیر ۳ برابر ب.م.م A و B شود.
پاسخ
ایده کلی استفاده از الگوریتم نردبانی و استفاده از این ویژگی است که: $(p,q)=(p-q,q)$
در زیربرنامه اول مقدار متغیر ۲ در متغیر ۳ ریخته میشود. اگر مقدار متغیر ۱ برابر ۰ باشد کار تمام است. زیر برنامه دو این موضوع را بررسی میکند. زیربرنامه سوم مانند زیربرنامه اول قسمت ب، min(a,b) را در متغیر ۲ میریزد و یکی از متغیرهای ۱ و ۳ برابر ۰ و دیگری برابر $|A-B|$ میشود. در زیربرنامه چهارم مقدار متغیر ۳ را به ۱ اضافه کرده و کار را از ابتدا با اعداد $|A-B|$ و $min(a,b)$ ادامه میدهیم.
- C1:JMP,NXT,JMP,JMP,DEC,INC
- C2:EXT,NXT
- C3:NXT,JMP,NXT,DEC,INC,DEC
- C4:JMP,JMP,NXT,INC,JMP,DEC
ت) برنامه ای بنویسید که اگر مقدار متغیرهای ۱ و ۲ و ۳ در ابتدا به ترتیب A و ۰ و ۰ باشد، پس از اجرای برنامه مقدار متغیر ۳ برابر A*A شود.
پاسخ
ایده کلی، استفاده از عبارت زیر است: $1+3+5+…+(2n-1) = n^2$
هر مرحله اگر مقدار متغیر ۱ برابر k باشد، 2k-1 را به متغیر ۳ اضافه میکنیم و سپس یک واحد از متغیر ۱ کم میکنیم تا زمانی که ۰ شود.
- C1:EXT,NXT
- C2:NXT,JMP,JMP,DEC,INC,JMP
- C3:JMP,NXT,JMP,INC,DEC,INC,JMP,JMP,INC
- C4:DEC,JMP,DEC,JMP,NXT