المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۰:سوال ۱۱

سوال ۱۱

یک ماشین محاسبه‌گر یک حافظه‌ی داخلی به نام ‎$M$‎ دارد. این ماشین می‌تواند با انجام دستورهای زیر یک عبارت را محاسبه کند:

  • $X$ $Add$‎: مقدار ‎$X$‎ را با مقدار ‎$M$‎ جمع و حاصل را در ‎$M$‎ ذخیره می‌کند.
  • $X$ $Mul$: مقدار ‎$X$‎ را در مقدار ‎$M$‎ ضرب و حاصل را در ‎$M$‎ ذخیره می‌کند.

در دستورهای فوق ‎$X$‎ می‌تواند یک عدد صحیح یا یک متغیر باشد. فرض کنید مقدار ‎$M$‎ در ابتدا صفر است. برای مثال، دستورهای زیر، از راست به چپ، عبارت ‎$ax+5$‎ را محاسبه می‌کند: $a$‎ ،$‎Add$ ‎$x$ $Mul$ و ۵‎ $‎Add$.

کدام یک از عبارت‌های زیر با این ماشین قابل محاسبه نیست؟

  1. ‎$ax^2+bx+c$
  2. $(a+b)xy+ya$
  3. $(ax+by)(a+b)$
  4. $3x^5+1$
  5. همه‌ی این عبارت‌ها را می‌توان محاسبه کرد‎.‎

پاسخ

گزینه (۳) درست است.

برنامه‌ی گزینه‌ی ۱ از چپ به راست:

$$ax^2+bx+c=(a\times x +b) \\ Add \quad a,Mul \quad x,Add \quad b,Mul\quad x,Add \quad b$$

برنامه‌ی گزینه‌ی ۲ از چپ به راست:

$$(a+b)xy+ya=[(a+b)\times x+a]\times y \\ Add \quad a,Add \quad b,Mul\quad x,Add \quad a,Mul\quad y$$

برنامه‌ی گزینه‌ی ۴ از چپ به راست:

$$3x^5+1=(((((3\times x)\times x)\times x)\times x)\times x)+1 \\ Add \quad x, Mul\quad 3,Mul\quad x,Mul\quad x,Mul\quad x,Mul\quad x,Add \quad 1$$

گزینه ۳ را به صورت‌های اشاره شده نمی‌توان پرانتزگذاری کرد.


ابزار صفحه