زبان اعصاب
فرهاد هم‌واره دوست داشت که توابع را به صورت ساده بیان کند. به همین دلیل، امروز به این نتیجه رسید که اکثر توابع را می‌توان با تعدادی تابع اولیه و عمل‌گر ساده پیاده‌سازی کرد. از شما می‌خواهیم که به فرهاد در پیاده‌سازی برخی از این توابع کمک کنید. هم‌چنین فرهاد تنها به توابعی علاقه دارد که ورودی و خروجی آن‌ها، اعدادی صحیح و نامنفی هستند. علی‌رضا به فرهاد، توابع ساده‌ی اولیه‌ی زیر را پیشنهاد داده است:
- تابع پوچ:این تابع تنها یک ورودی می‌گیرد و در خروجی، عدد ۰ را تحویل می‌دهد. این تابع را با $z$ نشان می‌دهیم. برای مثال $z(10)=0$.
- تابع افزون‌گر:این تابع تنها یک ورودی می‌گیرد و اگر عدد $n$ در ورودی به آن داده شود، عدد $n+1$ را به عنوان خروجی تحویل می‌دهد. این تابع را با $inc$ نشان می‌دهیم. برای مثال $inc(5)=6$. فرهاد برای سادگی نمادی نیز تعریف کرده است. او به جای $x+1$ یا همان $inc(x)$ از نماد $x'$ استفاده می‌کند.
- توابع بازتاب:این توابع به صورت $P_i^n(a_1, a_2, \ldots, a_n)$ هستند که $n$ عدد از ورودی می‌گیرند و $i$-امین عدد را تحویل می‌دهند. برای مثال تابع $P_3^{10}$، تابعی است که با گرفتن ۱۰ ورودی، هم‌واره سومین ورودی را برمی‌گرداند. به عنوان مثالی دیگر$P_2^3(0, 10, 8) = 10$ است.
با توابع بالا به تنهایی کار خاصی نمی‌توان کرد. به همین دلیل علی‌رضا عمل‌گرهای زیر را نیز به فرهاد پیشنهاد داده است. فایده‌ی این عمل‌گرها این است که با گرفتن چند تابع می‌توان توابع جدید ساخت.
۱. عمل‌گر ترکیب: این عمل‌گر یک تابع اصلی $f$ می‌گیرد. فرض کنید $f$، $m$ ورودی بگیرد. سپس این عمل‌گر توابع $g_1, g_2, \ldots, g_m$ را نیز از ورودی تحویل می‌گیرد که $g_i$-ها ورودی‌های یک‌سانی می‌گیرند (مثلن $x_1, x_2, \ldots, x_n$). به این ترتیب تابع جدید $h$ ساخته می‌شود که $h(x_1, x_2, \ldots, x_n)$،
$$f\Big(g_1(x_1, x_2, \ldots, x_n), g_2(x_1, x_2, \ldots, x_n), \ldots, g_m(x_1, x_2, \ldots, x_n)\Big)$$
را برمی‌گرداند. این عمل‌گر را با
$$CN\big[f, g_1, g_2, \ldots, g_m\big]$$
نشان می‌دهیم.
۲. عمل‌گر بازگشت: این عمل‌گر، دو تابع $f, g$ را می‌گیرد که $f$ تابعی با یک ورودی و $g$ تابعی با سه ورودی است. سپس این عمل‌گر، تابع بازگشتی $h$ (با دو ورودی) را به صورت زیر می‌سازد:
$$\left\{ \begin{array}{ll} h(x, 0) = f(x)\\ h(x, y') = g\big(x, y, h(x, y)\big)\\ \end{array} \right.$$
یادآوری می‌کنیم منظور از $y'$، همان $y+1$ یا $inc(y)$ است. در واقع این عمل‌گر، برای محاسبه‌ی $h(x, y')$، مقدار $h(x, y)$ را به صورت بازگشتی محاسبه می‌کند و سپس حاصل $g\big(x, y, h(x, y)\big)$ را برمی‌گرداند. این عمل‌گر را با$PR\big[f, g\big]$ نشان می‌دهیم.
فرهاد که حسابی گیج شده بود، از علی‌رضا خواست تا چند مثال برای او بزند. علی‌رضا دو مثال زیر را برای بهتر فهمیدن فرهاد، ارائه کرد:
۱. فرض کنید می‌خواهیم تابع $const_1$ را بسازیم. این تابع باید به ازای هر ورودی $x$، هم‌واره عدد ۱ را به عنوان خروجی، تحویل دهد. قبل از پیاده‌سازی این تابع، به هدف پیاده‌سازی این تابع توجه کنید. توابع و عمل‌گرهای تعریف شده، بسیار ساده و مقدماتی هستند و شما حتی دسترسی مستقیم به یک عدد صحیح ندارید و حتی نمی‌توانید مستقیمن یک عدد صحیح به عنوان ورودی یک تابع بدهید؛ به همین دلیل برای ساختن عدد ۱، این تابع را می‌سازیم. پس از پیاده‌سازی این تابع، دسترسی به عدد ۱ خواهیم داشت. علی‌رضا روش زیر را برای پیاده‌سازی این تابع، پیشنهاد کرد:
$$const_1(x) = CN\big[inc, z\big]$$
این تابع، در واقع با گرفتن عدد $x$، ابتدا آن را به تابع $z$ می‌دهد و حاصل یا همان صفر را به تابع $inc$ می‌دهد و در انتها خروجی ۱ برگردانده می‌شود.
فرض کنید $const_i$ تابعی باشد که با گرفتن هر عدد $x$، عدد ثابت $i$ را برگرداند. علی‌رضا به این نکته توجه کرد که به ازای هر $c$ ثابت، با داشتن تابع $const_{c-1}$، تابع $const_c$ را می‌توان به صورت زیر، پیاده‌سازی کرد:
$$const_c(x)=Cn\big[inc, const_{c-1} \big]$$
سپس فرهاد به روش استقرایی نتیجه گرفت، به ازای هر $c$ ثابت، تابع $const_c$ را می‌توان پیاده‌سازی کرد.
۲. فرض کنید می‌خواهیم تابع جمع ($sum$) را بسازیم. این تابع باید با گرفتن دو ورودی $x, y$، جمع آن‌ها ($x+y$) را تحویل دهد. علی‌رضا برای پیاده‌سازی این تابع به صورت زیر استدلال کرد:
«در صورتی که $y=0$ باشد، آن‌گاه حاصل $x+y$ برابر $x$ می‌شود. در غیر این صورت، حاصل $x+y$ برابر $\big(x+(y-1)\big)+1$ می‌شود. پس می‌توان به صورت بازگشتی، این تابع را پیاده‌سازی کرد و کافی است دو تابع $f, g$ را برای عمل‌گر بازگشت، تعریف کنیم:
- از آن‌جایی که $sum(x, 0)=x$، پس باید تابع $f$ را طوری تعریف کنیم که $f(x)=x$ شود. تابع بازتاب $P_1^1$، با گرفتن یک ورودی، همان را برمی‌گرداند؛ پس اگر قرار دهیم $f(x) = P_1^1(x)$ تابع مطلوب $f$ را ساخته‌ایم. پس
$$f = P_1^1$$
- داریم $sum(x, y') = sum(x,y)+1$. از طرفی قرار است تابع $g$ را طوری تعریف کنیم که $sum(x, y')=g\big(x, y, sum(x, y)\big)$ شود. با استفاده از تابع بازتاب $P_3^3$ روی ورودی‌های تابع $g$، می‌توانیم ورودی سوم آن یا همان $sum(x, y)$ را به دست آوریم. سپس اگر حاصل را به تابع $inc$ بدهیم، مقدار مورد نظر یا همان $sum(x, y')$ ساخته می‌شود. پس اگر قرار دهیم
$$g\big(x, y, sum(x, y)\big) = inc\Big(P_3^3\big(x, y, sum(x, y)\big)\Big)$$
تابع مطلوب $g$ را ساخته‌ایم. پس $g = CN\big[inc, P_3^3 \big]$
پس توابع $f, g$ را برای پیاده‌سازی توسط عمل‌گر بازگشت، ساختیم.»
علی‌رضا پس از استدلال بالا، پیاده‌سازی زیر را ارائه داد:
$$sum(x, y) = PR\Big[P_1^1, CN\big[inc, P_3^3 \big] \Big]$$
حال برای پیاده‌سازی توابع زیر، به فرهاد کمک کنید. توجه کنید فقط باید از توابع و عمل‌گرهای گفته شده، استفاده کنید. برای ساده نوشتن، می‌توانید چند تابع کمکی تعریف کرده و پیاده‌سازی کنید و در پیاده‌سازی تابع خواسته شده، از آن‌ها استفاده کنید. در هر قسمت توضیحی کوتاه (در حد چند جمله) نیز برای پیاده‌سازی خود بدهید.
الف) تابع ضرب ($mul$) را پیاده‌سازی کنید. این تابع باید دو عدد $x, y$ به عنوان ورودی بگیرد و $x \times y$ را به عنوان خروجی تحویل دهد. در واقع باید $mul(x,y) = x \times y$ شود.
ب) تابع $poly$ را پیاده‌سازی کنید. این تابع باید یک عدد $x$ به عنوان ورودی بگیرد و $x^2+x+2$ را به عنوان خروجی تحویل دهد. در واقع باید $poly(x) = x^2+x+2$ شود.
پ) تابع فاکتوریل ($fact$) را پیاده‌سازی کنید. این تابع باید عدد $n$ را به عنوان ورودی بگیرد و $n!$ را به عنوان خروجی تحویل دهد. در واقع باید $fact(n) = n!$ شود.
ت) تابع مینیمم ($min$) را پیاده‌سازی کنید. این تابع باید عدد $x, y$ را به عنوان ورودی بگیرد و عدد کوچک‌تر را از میان دو عدد $x, y$ تحویل دهد. برای مثال اگر $3,4$ به عنوان ورودی به این تابع داده شوند، باید عدد ۳ و اگر $7,7$ داده شوند، باید عدد ۷ به عنوان خروجی داده شود.
پاسخ
الف) کاملا مانند مثال جمع در متن سوال عمل می‌کنیم. اگر $y=0$ باشد، $x \times y = 0$ و در غیر این صورت $x \times y = x \times (y-1) + x$ است. پس اگر در عمل‌گر بازگشت، تابع $f$ را برابر تابع $z$ و تابع $g$ را برابر $sum\big(x, mul(x, y-1)\big)$ قرار دهیم، پیاده‌سازی انجام می‌شود. به دست آوردن $x, mul(x, y-1)$ جهت دادن ورودی به تابع $sum$ به راحتی توسط تابع $P$ انجام می‌شود؛ زیرا هر دو مورد در ورودی‌های تابع $g$ موجود هستند. پس داریم:
$$mul(x, y) = PR\big[z, CN[sum, P_1^3, P_3^3] \big]$$
ب) داریم $x^2+x+2 = x(x+1) + 2$. ابتدا $x \times (x+1)$ را محاسبه می‌کنیم. برای ساختن $x+1$ باید از تابع $inc$ و برای ساختن $x(x+1)$ باید از تابع $mul$ نوشته شده در قسمت قبل استفاده کنیم و آن‌ها را ترکیب کنیم. پس برای ساختن $x(x+1)$ کافی است تابع
$$tri(x) = CN\big[mul, P_1^1, inc\big]$$
را در نظر بگیریم. حال باید حاصل را با دو جمع کنیم. پس پاسخ برابر
$$f(x) = CN\Big[sum, tri, const_2\Big]$$
ج) ابتدا تابعی مانند $sudoFact(x, y)$ می‌نویسیم که $sudoFact(x, y) = y!$ شود. از عمل‌گر بازگشت استفاده می‌کنیم. اگر $y=0$ باشد، باید ۱ برگردانده شود؛ پس کافی است در عمل‌گر بازگشت، $f$ را برابر $const_1$ قرار دهیم که در متن سوال پیاده‌سازی شده است. اگر $y=0$ نباشد، $sudoFact(x, y') = y' \times sudoFact(x, y)$ است. پس تابع $g$ باید $y'$ را در $sudoFact(x, y)$ ضرب کند. پیاده‌سازی زیر برای $g$ این کار را انجام می‌دهد:
$$g\big(x, y, sudoFact(x, y)\big) = CN\Big[mul, P_3^3, CN[inc, P_2^3] \Big]$$
پس تابع $sudoFact$ را می‌توان به شکل زیر، پیاده‌سازی کرد:
$$sudoFact(x, y) = PR\Big[const_1, CN\big[mul, P_3^3, CN[inc, P_2^3] \big] \Big]$$
اکنون فقط کافی است تابع $sudoFact$ را به تابعی با یک ورودی تبدیل کنیم که عمل‌گر $CN[sudoFact, P_1^1, P_1^1]$ این کار را برای ما انجام می‌دهد. پس تابع فاکتوریل را می‌توان به شکل زیر پیاده‌سازی کرد:
$$fact(n) = CN\big[sudoFact, P_1^1, P_1^1 \big]$$
د) ابتدا تابع $dec(x)$ را تعریف می‌کنیم که با گرفتن $x$، عدد $x-1$ را تحویل می‌دهد. البته در صورتی که $x=0$ باشد، تابع باید عدد ۰ را تحویل دهد. این تابع به شکل زیر می‌تواند پیاده‌سازی شود:
$$dec(x) = CN\Big[PR\big[z, P_2^3\big], P_1^1, P_1^1\Big]$$
حال تابع $sub(x, y)$ را تعریف می‌کنیم که در آن اگر $x \le y$ باشد، مقدار ۰ و در غیر این صورت مقدار $x-y$ باید برگردانده شود. با استفاده از تابع $dec$، تابع $sub$ (تفریق) می‌تواند به شکل زیر پیاده‌سازی شود:
$$sub(x, y) = PR\big[P_1^1, CN[dec, P_3^3]\big]$$
حال تابع $sign(x)$ را تعریف می‌کنیم. اگر $x=0$ باشد، این تابع عدد ۰ و در غیر این صورت ($x> 0$)، این تابع باید عدد ۱ را برگرداند. این تابع به شکل زیر می‌تواند پیاده‌سازی شود:
$$sign(x) = CN\big[sub, const_1, CN[sub, const_1, P_1^1]\big]$$
حال $\overline{sign}(x)$ را تعریف می‌کنیم که برعکس تابع $sign$ عمل می‌کند؛ یعنی اگر $x=0$ باشد، مقدار ۱ و در غیر این صورت مقدار ۰ را برمی‌گرداند. این تابع می‌تواند با استفاده از تابع $sign$ به صورت زیر نوشته شود:
$$\overline{sign}(x) = CN\big[sub, const_1, CN[sign, P_1^1]\big]$$
حال تابع خواسته‌شده ($min$) را پیاده‌سازی می‌کنیم. با تعریف‌های بالا، به راحتی می‌توان بررسی کرد که
$$min(x, y) = sign(x-y) \times x + \overline{sign}(x-y) \times y$$
$sign(x-y) \times x$ را به صورت
$$case1 = CN\Big[mul, CN\big[sign, CN[sub, P_1^2, P_2^2]\big], P_1^2\Big]$$
و $\overline{sign}(x-y) \times y$ را به صورت مشابه
$$case2 = CN\Big[mul, CN\big[\ \overline{sign}, CN[sub, P_1^2, P_2^2]\big], P_2^2\Big]$$
پیاده‌سازی می‌کنیم. پس:
$$min(x, y) = CN[sum, case1, case2]$$
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
