فهرست مندرجات
زبان چرخشی
در این سوال با یک زبان برنامه نویسی جدید سر و کار دارید. ابتدا توضیحات زیر را در مورد بخش های مختلف زبان بخوانید:
حافظه و اشاره گر
این زبان تنها از سه خانه ی حافظه با شماره های ۱ تا ۳ استفاده می کند که دور یک دایره قرار گرفته اند و هر کدام می توانند یک عدد صحیح را ذخیره کنند. به این خانه ها متغیر نیز می گوییم. یک اشاره گر هم وجود دارد که در هر لحظه به یکی از این سه متغیر اشاره می کند و در هنگام شروع برنامه روی متغیر شماره ۱ است. به متغیری که اشاره گر به آن اشاره می کند، متغیر درگیر می گوییم. برنامه دارای تعدادی دستور است که پس از اجرای هر یک، اشاره گر یک واحد در جهت ساعت گرد حرکت می کند تا به متغیر بعدی اشاره کند.
زیربرنامه ها
هر برنامه در این زبان از تعدادی زیربرنامه تشکیل می شود. فرض کنید زیربرنامه های یک برنامه به ترتیب $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
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
