====== سوالات ۲۳ تا ۲۵ ======



**پشته** یکی از داده ساختارهای پرکاربرد در علوم کامپیوتر است که دنباله‌ای از عناصر را ذخیره می‌کند. تغییرات در عناصر پشته فقط از دو نوع می‌تواند باشد:
  * یک عضو به انتهای پشته اضافه شود.
  * یک عضو از انتهای پشته حذف شود.
برای مثال فرض کنید پشته‌ای به صورت {١, ۵, ۴, ٣} باشد. با اضافه کردن عضوی با مقدار ٧ به انتها، پشته به صورت {٧, ١, ۵, ۴, ٣} خواهد شد. هم‌چنین اگر از انتهای پشته‌ی {٣, ١٠, ٢} یک عنصر را حذف کنیم، پشته به صورت {١٠, ٢} خواهد شد.

اکنون می‌خواهیم یکی از روش‌های ذخیره سازی پشته در کامپیوتر را شرح دهیم. در این روش، عمل‌های زیر را می‌توان انجام داد:
  * **عمل ساختن پشته**: با دستور $create(S)$ پشته‌ای با نام $S$ ساخته می‌شود و یک خانه در حافظه به آن اختصاص پیدا می‌کند که در ابتدا این خانه مقداری ندارد. اجرای این عمل یک واحد زمان مصرف می‌کند.
{{ :سوالات_المپیاد:مرحله_ی_اول:دوره_ی_۳۰:screenshot_from_2022-06-23_23-51-04.png?100 |}}
  * **عمل اضافه کردن به پشته**: با دستور $push(S, x)$ مقدار $x$ به انتهای پشته‌ی $S$ اضافه می‌شود. دو حالت داریم:
    * حافظه‌ی مربوط به $S$ دارای خانه‌ی خالی باشد؛ در این صورت عدد $x$ در نخستین خانه‌ی خالی حافظه‌ی مربوط به پشته‌ی $S$ قرار می‌گیرد. برای مثال اگر حافظه‌ی مربوط به $S$ به شکل سمت چپ باشد و دستور $push(S, 6)$ اجرا شود، حافظه‌ی مربوط به $S$ به شکل سمت راست در خواهد آمد:{{ :سوالات_المپیاد:مرحله_ی_اول:دوره_ی_۳۰:screenshot_from_2022-06-23_23-51-28.png |}}\\  اجرای عمل بالا یک واحد زمان مصرف می‌کند.
    *  حافظه‌ی مربوط به $S$ دارای خانه‌ی خالی نباشد؛ در این صورت جایی جدید از حافظه با دو برابر تعداد خانه‌های حافظه‌ی فعلی به $S$ اختصاص داده شده و سپس عمل اضافه کردن انجام می‌شود. برای مثال اگر حافظه‌ی مربوط به $S$ به شکل سمت چپ باشد و دستور $push(S, 10)$ اجرا شود، حافظه‌ی مربوط به $S$ به شکل سمت راست خواهد آمد:{{ :سوالات_المپیاد:مرحله_ی_اول:دوره_ی_۳۰:screenshot_from_2022-06-23_23-51-39.png |}} \\ اجرای چنین عملی به اندازه‌ی تعداد خانه‌های حافظه‌ی جدید اختصاص داده شده زمان مصرف می‌کند. برای نمونه، در مثال بالا ٨ واحد زمان مصرف می‌شود.
  * **عمل حذف کردن از پشته**: با دستور $pop(S)$ یک عنصر از انتهای پشته‌ی $S$ حذف می‌شود. برای مثال اگر حافظه‌ی مربوط به $S$ به شکل سمت چپ باشد و دستور $pop(S)$ اجرا شود، حافظه‌ی مربوط به $S$ به شکل سمت راست در خواهد آمد: {{ :سوالات_المپیاد:مرحله_ی_اول:دوره_ی_۳۰:screenshot_from_2022-06-23_23-51-47.png |}}\\ در حالتی که با خالی کردن آخرین خانه‌ی پر حافظه‌ی مربوط به $S$ ،دست کم نیمی از خانه‌ها خالی شود، حافظه‌ای جدید به $S$ اختصاص داده می‌شود که خانه‌های خالی آن حذف شده‌اند (مگر اینکه $S$ تنها یک خانه داشته باشد که در این صورت آن خانه حذف نمی‌گردد). برای مثال اگر حافظه‌ی مربوط به $S$ به شکل سمت چپ باشد و دستور $pop(S)$ اجرا شود، حافظه‌ی مربوط به $S$ به شکل سمت راست در خواهد آمد: {{ :سوالات_المپیاد:مرحله_ی_اول:دوره_ی_۳۰:screenshot_from_2022-06-23_23-51-55.png |}}\\ اجرای عمل حذف عنصر در حالاتی که تعداد خانه‌ی حافظه‌ی مربوط به $S$ تغییر کند (نصف شود)، به اندازه‌ی تعداد خانه‌های حافظه‌ی جدید اختصاص داده شده زمان مصرف می‌کند. برای نمونه در مثال بالا ۴ واحد زمان مصرف می‌شود. در حالاتی نیز که تعداد خانه‌های حافظه‌ی مربوط به S تغییر نمی‌کند، یک واحد زمان مصرف خواهد شد.
  *  **عمل کپی**: با دستور $copy(A, B)$ حافظه‌ای به اندازه‌ی حافظه‌ی پشته‌ی $A$ به پشته‌ی $B$ اختصاص می‌یابد و مقادیر خانه‌های حافظه‌ی $B$ نیز برابر مقادیر خانه‌های حافظه‌ی $A$ خواهند شد. اجرای این عمل به اندازه‌ی تعداد خانه‌های حافظه‌ی مربوط به $A$ زمان مصرف می‌کند.

توجه کنید قبل از عملیات روی پشته، باید آن پشته در خطوط قبلی برنامه با دستور $create$ ساخته شده باشد.




====== سوال ۲۳ ======




برنامه‌ی زیر چند واحد زمان مصرف می‌کند؟

$$create(X)$$
$$push(X, ١)$$
$$push(X, ١)$$
$$push(X, ١)$$
$$pop(X)$$
$$push(X, ١)$$
$$push(X, ١)$$
$$pop(X)$$
$$push(X, ١)$$

  - ۱۴
  - ۱۷
  - ۱۹
  - ۱۱
  - ۱۵


====== سوال ۲۴ ======


در برنامه‌ای ابتدا با دستور $create(S)$ پشته‌ی $S$ ساخته می‌شود. در ادامه‌ی این برنامه ١٣٩٨ دستور $push(S, 1)$ وجود دارد. این برنامه چند واحد زمان مصرف می‌کند؟

  - ۵۴۹۳
  - ۴۰۹۵
  - ۵۴۸۲
  - $2^{1398} + 1397$
  - $2^{1399} + 1399$

<راهنمایی>

بررسی کنید هزینه‌ی مصرفی در مراحل ‌$2^i + 1$ چقدر است.

</راهنمایی>
====== سوال ۲۵ ======

یک برنامه حداقل چند خط باید داشته باشد تا در انتهای آن دست کم ١٠٠ واحد حافظه (در مجموع برای پشته‌ها) وجود داشته باشد؟

  - ۲۷
  - ۳۵
  - ۵۱
  - ۲۲
  - ۲۳

<راهنمایی>

 ثابت کنید حالت بهینه‌ای وجود دارد که در آن تمام عملیات‌های ‌$push$ بر روی یک پشته انجام شده‌اند و همچنین هیچ عمل $push$‌ای ‌بعد از یک عمل $copy$ نیامده‌ است.

</راهنمایی>

  * [[سوالات ۲۰ تا ۲۲|سوال قبل]]