المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۰:برنامه نویسی:سوال ۵

کدنویسی

تابعی بنویسید که یک ‎+vector<int>+‎ را به عنوان ورودی بگیرد و عناصر این ‎vector‎ را برعکس reverse)‎) کند (‎‎یعنی اوّلی با آخری تعویض شود، دومی با یکی مانده به آخری و …). تابع شما نباید خروجی برگرداند بلکه باید عمل خواسته شده را روی همان ‎vector‎ ارسالی انجام بدهد.

تابع ‎strlen(char *s)‎ را شبیه‌سازی کنید. این تابع یه اشاره‌گر به ابتدای یک رشته‌ی کاراکتری می‌گیرد و طول رشته‌ی با شروع از آن اشاره‌گر را بر می‌گرداند.

برای هر عدد مثبت، میزان ‎«باینری دوستی‎» یا به‌صورت خلاصه «‎بایدو»ی آن عدد برابر است با توان عدد ‎۲‎، در تجزیه‌ی آن عدد به عوامل اوّل. برای مثال بایدوی عدد ‎۴۰‎ برابر ‎۳‎ است چرا که ‎$40=2^3\times 5$‎ و بایدوی اعداد ‎۱۳‎ و ‎۶۴‎ به‌ترتیب صفر و ‎۶‎ است. یک آرایه‌ی ‎int bd[128]‎ سراسری داریم و می‌خواهیم درایه‌ی ‎$0<i<128$\،‎اُم آن، مقدار بایدوی عدد ‎$i$‎ را در بر بگیرد. برای این منظور یک تابع بازگشتی‎ با حداکثر ‎۳‎ پارامتر بنویسید که این کار را انجام دهد. شما مجاز به استفاده از هیچ دستور حلقه‌ای (نظیر ‎for‎ یا while‎ و همچنین تعریف متغیر/تابع جدید نیستید. در تابع شما حداکثر از یک ‎if‎ یا عملگر :?‎ باید استفاده شده باشد. تابع شما نباید چیزی را به عنوان خروجی برگرداند.

تابعی بنویسید که عمل ‎Split‎ را انجام دهد. این تابع یک رشته‌ی طولانی به عنوان ورودی ‎($S$)‎ و یک رشته کوچک به عنوان جدا کننده ‎delimiter)‎) می‌گیرد. سپس رشته‌ی ورودی را به تکه‌هایی بر حسب جداکننده تقسیم می‌کند. نهایتاً این تکه‌ها را در یک ‎vector<string>‎ بر می‌گرداند. به عنوان مثال خروجی فراخوانی ‎Split(«Sib-Moz-Sib-Golabi»,»-»)‎ یک vector‎ شامل ‎۴‎ رشته‌ی ‎Sib‎ و ‎Moz‎ و ‎Sib‎ و ‎Golabi‎ است. و یا ‎Split(«abbccdd»‎, «‎bbc»)‎ یک vector‎ شامل دو رشته‌ی ‎a‎ و cdd‎ را بر می‌گرداند. فرض کنید که رشته ورودی در ابتدا و انتهایش مستقیماً جداکننده را در بر نمی‌گیرد. فرض کنید دفعات رخداد جداکننده در ورودی، هم‌پوشانی ندارد (یعنی امکان ندارد که جداکننده ‎aa‎ باشد و در ورودی ‎…aaa…‎ داشته باشیم‎.(‎ مجدداً یادآوری می‌شود که خروجی تابع شما یک ‎vector<string>‎ باید باشد.

تابعی بنویسید که یک ‎vector‎ به‌طول حداکثر ‎۲۰‎ بگیرد و تمام جایگشت‌های عناصر ‎vector‎ را در خروجی چاپ کند. تابع شما باید به صورت بازگشتی باشد. شما مجاز به استفاده از متغیرهای ‎global یا static‎ نیستید. پارامترهای تابع شما باید شامل خود ‎vector‎ عناصر به صورت ‎Const Reference‎ و حداکثر یک ‎vector‎ اضافه و حداکثر یک متغیر ساده‌ی دیگر باشد.

الگوریتم این برنامه‌ی شما باید به صورت کارا این عملیات را انجام دهد و از محاسبات اضافه بپرهیزد. الگوریتم شما باید بر مبنای ساخت جایگشت‌ها (با کمک ‎(for‎ باشد و نه ‎swap‎ کردن عناصر از روی یک جایگشت برای رسیدن به جایگشت بعدی.


ابزار صفحه