آزمون مقدماتی برنامه‌نویسی + برنامه‌نویسی + سوال

یا لطیف

سلام بچه‌ها! حالتون خوبه؟ ما هم خوبیم. خداروشکر!

این پست در موردآزمون مقدماتی برنامه نویسیاست. قبول دارم یه کم دیر این پست رو می‌زینم. راستش ما، هم درگیر امتحان نهایی هستیم هم منتظر بودیم تا کمیته نوع و سطح سوالات این امتحان رو معلوم کنه بعد پست بزنیم اما فعلا خبری نیست. قراره وقتی کمیته درمورد نوع سوالات و نحوه امتحان تصمیم قطعی گرفت، توضیحاتش رو تو سایتhttp://www.inoi.irبذاره. ما هم اگه خبردار شدیم اینجا می‌نویسیم. حالا فعلا تو این پست یه سری توضیحات کلی درمورد آزمون‌های برنامه نویسی و خود برنامه نویسی می‌نویسم تا ببینیم چی می‌شه.

------------------------------------------------------------------------------------------------------

به طور کلی تو امتحان‌های برنامه نویسی شما مثلا ۵ ساعت وقت دارید و به شما چندتا سوال داده می‌شه که هر کدوم به این شکل هستند:

برنامه ای بنویسید که از ورودی استاندارد (همون صفحه کلید) ورودی مسئله را بخواند و با توجه به صورت سوال خروجی برنامه را محاسبه کند و آن را در خروجی استاندارد (همون صفحه نمایشگر) چاپ کند! (می‌بینید که چقدر سوال‌ها ساده است!)

این لینک۳ تا سوال برنامه نویسی به زبان فارسی داره که البته سوالاش خیلی سخته و امتحان شماخیلیاز این آسون‌تر خواهد بود. این لینک رو گذاشتم فقط برای اینکه ببینید قالب کلی سوال ها چی‌جوریه. (راستش لینک دیگه‌ای دم دستم نبود که سوال‌هاش فارسی باشه).

زمان ما همه امتحان ها تو linux بود اما از سال ما به بعد تو دوره تابستون با بچه‌ها تو windows کار می‌کردن و تو دوره نقره-طلا بهشون linux یاد می‌دادند. احتمالا این امتحان شما هم توی windows هستش. برنامه‌هاتون رو هم باید به زبان ++C بنویسید.

------------------------------------------------------------------------------------------------------

اما درمورد برنامه نویسی. من اول می‌خواستم بیام یه کم مقدمات برنامه‌نویسی رو توضیح بدم ولی دیدم تو وبلاگ خیلی سخته. اما به طور کلی اگه شما می‌خواید برنامه نویسی رو از صفر شروع کنید بهتره از یکی که بلده بخواید بهتون مقدماتش رو یاد بده. منظورم اینه که اگه بخواید خودتون از رو کتاب یا با اینترنت یاد بگیرید خیلی وقت‌تون رو می‌گیره و بهتره که یکی (مثلا یکی از دوستاتون یا یکی از معلم‌هاتون) پای کامپیوتر مقدماتش رو بهتون یاد بده. اما اگه چیزای اولیه رو بلدید، دیگه باید کم‌کم خودتون بقیه چیزها رو با اینترنت و کتاب یاد بگیرید. یعنیبایدیاد بگیرید که چگونه از کتاب و مخصوصا اینترنت جواب سوال‌ها‌تون رو پیدا کنید. در مورد ++C هم سایت فت‌و‌فراوونه که اینجا دوتا از خوباش رو می‌گم(البته به نظر من خوبن):

سایتwww.cppreference.com: یکی از سایت‌های خوبه که توش در مورد کتاب‌خونه‌ها و چیزای دیگه‌ی ++C خیلی خوب و مختصر توضیح داده.

سایتhttp://www.cplusplus.com: توش هم یه بخش داره برایآموزشهم یهمرجع برای کتابخانه‌های ++Cداره، هم یهforumداره که توش می‌تونید سوال بپرسید.

معمولا تو امتحان‌ها یه مرجع ++C در اختیار مسابقه‌دهنده‌ها هست. مثلا تو جهانی پارسال و توی امتحان انتخاب تیم امسال همین سایتwww.cppreference.comبه عنوان مرجع در طول امتحان در اختیار مسابقه‌دهنده‌ها بود. (البته این به معنی دسترسی به اینترنت نیست. بلکه صفحه‌های این سایت روی کامپیوتر ذخیره شده و ملت می‌تونن ازش استفاده کنن). تو این امتحان‌ها یه PDF هم بود که برای آموزش ++C بود واینجابراتون آپلودش کردم (به نظرم این PDF همونقسمت آموزشی http://www.cplusplus.comهستش که به صورت PDF در آوردنش).

یه نکته مهم در مورد ++C، کتابخانه STL هست. این کتابخونه توش هم یه سری تابعبسیاربه درد بخور داره و هم یه سری ظرف (ترجمه container!) . این توابع و ظروف! این‌قدر زیادن که من بعد عمری! کار کردن با این کتابخونه هنوز توش چیزای جدید پیدا می‌کنم. البته اگه این‌ اسم‌ها براتون جدیده اصلا نگران نشید. چون به نظرم خیلی بعیده تو این امتحان سوالی بدن که نیاز به استفاده از این ها مخصوصا container ها داشته باشین. اما به نظر من درمورد تابعمرتب‌سازیاین کتاب‌خونه اگه استفاده ازش رو بلد باشین خیلی خوبه. از اسمش معلومه که چی‌کار می‌کنه و احتمالا خودتون هم می‌تونید بدون استفاده از STL این تابع رو بنویسید، ولی به هرحال یاد گرفتنش خیلی کارو راحت تر می‌کنه. اسم این تابعsortهستش و نحوه استفاده‌اش این‌طوریه:

فرض کنید شما یه آرایه از اعداد (مثلا از نوع int) به اسم num دارید که توش n تا عدد ذخیره کردید و حالا می‌خواید اعدادش رو مرتب کنید. کافیه از تابعsortبه شکل زیر استفاده کنید:

sort(num, num + n);       // num esme arayatoone va n tedad adade tooshe.

شاید تو پست‌های دیگه در مورد سایر توابع پرکاربرد STL هم نوشتیم. خب این هم درمورد برنامه‌نویسی و STL. وقتی معلوم شد که امتحان‌‌تون چی‌جوریه و در چه سطحی باید الگوریتم بلد باشید، احتمالا در مورد الگوریتم‌ها هم پست بذاریم. اما فعلا یه سوال برنامه نویسی می‌گم(از کتاب مسئله های الگوریتمی) که روش فکر کنید.

------------------------------------------------------------------------------------------------------

کتاب مسئله‌های الگوریتمی، مسئله ۸۰. متوسط زمان پاسخ یک ماشین:

n کار را می‌خواهیم روی یک ماشین اجرا کنیم. اجرای کار شماره ‌i به اندازه‌ی t_iزمان می‌گیرد. ماشین در هر لحظه حداکثر می‌تواند یکی از کارها رو انجام دهد. برنامه‌ای بنویسید که ترتیبی برای اجرای این کارها پیدا کند، به طوری که متوسط زمان پایان یافتن کارها مینیمم شود.

ورودی: در سطر اول ورودی n و در سطر بعدی t_iها نوشته شده‌اند. فرض کنید n iها صحیح و مثبت اند.

خروجی: در سطر اول فایل خروجی متوسط زمان پایان یافتن کارها و در سطر دوم ترتیب انجام کارها رو بنویسید.

مثال:

ورودی نمونه:

5

34  23  52  13  42

خروجی نمونه:

79

4  2  1  5  3

------------------------------------------------------------------------------------------------------

اگه حلش کردید کدش رو هم بزنید. خب دیگه من باید برم فیزیک بخونم!

موفق باشید

فعلا خداحافظ!

تیم ملی المپیاد کامپیوتر ایران

سلام دوستان ، اینم پست جدید ، دیگه چی می خواین؟!

بعد از چند دوره امتحانات طاقت فرسا و تنگاتنگ! و خداحافظی با بقیه شرکت کنندگان در مراحل مختلف ، بالاخره تیم ملی المپیاد کامپیوتر برای شرکت درالمپیاد جهانی که توی واترلوی کانادابرگزار می شه ، انتخاب شد!

اعضای تیم ، به ترتیب الفبا اینا هستن:

1- علی بابایی چشمه احمد رضایی - علامه حلی تهران!

2- سید مهران خلدی - علامه حلی تهران!

3- بهروز ربیعی - علامه حلی تهران!

4- مهرداد طهماسبی - علامه حلی تهران!

به همه شون تبریک می گم و امیدوارم موفق باشن. (واسه من هم تی شرت یادشون نره بیارن!)

به کسایی هم که توی مراحل مختلف بودن و باهاشون خداحافظی شد خسته نباشید میگم!

به دوستانی هم که جایی غیر از علامه حلی هستن ، می گم که نا امید نشین! امسال استثنائی بود.

کلید جدید

سلام خسته نباشید مرحله دوم خوب بود ؟
اینم کلیدی که قول داده بودم... (با کمک بهروز)
سوال ۱:
حقوق هر فرد را در وضعیتی که iنفر در شرکت اول بروند Pi و در وضعیتی که به شرکت دوم بروند Fi می نامیم... برهان خلف می زنیم... فرض کنیم وضعیت جواب نداریم
اگر nنفر به شرکت اول بروند،   F1 > Pn است، (وگرنه وضعیت جواب بود)، ‌حالا اگر n-1 نفر به شرکت اول بروند Pn-1

تناقض است. ‍‍‍پس این بین یکی از نامساوی ها غلط بوده و حالت جواب بوده.
//=================================================
سوال ۲:
گراف جایگشت را می کشیم،‌طوری که از i به πi یالی جهت دار می کشیم. گراف افرازی از چند دور است. در هر عمل طول هر دور نصف می شود، (چرا ؟) پس از k مرحله همه دور ها طولشان یک می شود.
ب) جایگشت 2, 3, 4, ..., n-1, n, 1را در نظر بگیرید و پس از هر مرحله جای یک را بررسی کنید...
//==================================================
سوال ۳:
الف) درخت را از یک راس آویزان می کنیم،‌حالا پایین ترین یال خراب (یالی که عوارض دو سرش یکسان شده اند) را در نظر بگیرید (و آن را uv بنامید، طوری که u پدر v باشد.) یکی از بچه‌های v مانند w را انتخاب می‌کنیم. عوارض یال vw را عوض می‌کنیم. با این حساب uv دیگر خراب نیست. از طرفی ممکن است چند یال مانند vx یا wy خراب شده باشند. (که همگی پایین‌تر از uv هستند.) ، و ... استقرا
پایه‌ی استقرا: برگ. چون عوارض صفر نداریم، ...
ب) *ها شهرها هستند. عوارض جاده‌ها درون پرانتز نوشته شده است.
*-(a,b)-*-(0,1)-*-(a,b)-*-(0,1)-*-(a,b)-*
بررسی کنید.
//==================================================
سوال ۴:
یک «وضعیت» را برای مسئله اینگونه تعریف می‌کنیم:
«جاده‌ی خروجی هر میدان کدام است؟ و ما کجا هستیم؟»
واضح است که تعداد حالات متناهی است. پس اگر از وضعیت ابتدایی شروع کنیم، بعد از طی چند مرحله به یک وضعیت تکراری برمی‌گردیم. دور حاصل از وضعیت‌ها (در گراف وضعیت) را در نظر می‌گیریم. ادعا می‌کنیم با پیمودن این دور، از همه‌ی شهرها گذشته‌ایم.
برهان خلف: شهری را در نظر بگیرید که در گراف وضعیت بازدید شده باشد و دارای حداقل یک همسایه‌ی بازدید‌نشده باشد. (آن را v بنامید) این دور را d_v (تعداد همسایه‌های v) بار طی می‌کنیم. حتما یک بار پلیس جاده‌ی منتهی به شهر بازدید نشده را باز می‌کند. تناقض...
//==================================================
سوال ۵:
توضیح بیشتر در مورد الگوریتم داده شده:
در ابتدا n دسته‌ی ۱ عضوی داریم. هر بار، دو دسته‌ی دلخواه را انتخاب می‌کنیم، و همه‌ی اعضای دسته‌ی کوچکتر را در دسته بزرگ می‌ریزیم و به اندازه‌ی تعداد اعضای دسته‌ی کوچک پول خرج می‌کنیم (به b اضافه می‌کنیم)
الف) در هر مرحله، اگر x دسته داشته باشیم، به x/2 تا دسته ۲تایی تقسیم می‌کنیم. و دو به دو با هم تلفیق می‌کنیم.
ب) هر عدد حداکثر در k عملیات جابه‌جایی شرکت داشته. (چرا؟) پس در کل k * 2^k تا عمل انجام شده.
(برای اطلاعات بیشتر در مورد کاربرد این الگوریتم، در مورد داده‌ساختار DisjointSet تحقیق کنید. منابع: ویکی‌پدیا، CLRS، Creative و JBL)

[پس از بررسی حل خود برای تخمین بهتر کف حتما در نظرسنجی شرکت کنید.]

کلید مرحله ۲

سلام
مرحله دوم خوب بود ؟ من که به شخصه  خیلی خوشم نیومد .

من یه کلید به سرعت در اوردم امیدوارم درست  باشه. 
سوال مربع و ۱۳۸۹ پارهخط میشه ۴۱۶۸ 
سوال  ۲۰۱۰ عدد کمتر از ۲ به توان ۱۳۸۹ میشه ۱۳۹۹
سوال ۲۰ سکه ی طلا  میشه ۱۰
سوال مکعب ۳*۳*۳ میشه ۶
سوال اشباع شده میشه 42
سوال سکه ها و پرتاب میشه ۱/۸
سوال مربع ۳*۳ میشه ۹ تا
سوال پست خونه میشه ۳۶ تا .
سوال n سکه میشه ۱۳۹۱

سوال مرتب کردن سکه میشه ۵ تا 
سوال دزد و تابلو ها میشه p(i)=max(vi+p(i-2),p(i-1)) in
سوال دانشجو و استاد میشه ۶
سوال راننده و جا ی پارک میشه ۱،۳،۲۹۹
سوال الگریتم s  و b  میشه ۷
سوال لیگ فوتبال میشه ۹
سوال طرح سوال میشه ۱۶۸
سوال الگوریتم رو a1 a2 a3 a4 میشه ۲۶
سوال مقدار کمینه s  میشه ۳۵
سوال ۶ لامپ میشه ۲۹

ادامه ی پست قبلی

یه سری توصیه به دردبخور هم بود که گفتم بزارم اینجا به درد مرحله ۲ تون میخوره.
احمد خواجه نژاد:
من می خوام یه نکاتی در مورد نوشتن توی امتحان های تئوری بگم:
اولا پیش میاد (شاید زیاد) که یه نفر به خاطر بد نوشتن، نمره ی یه سوال رو کم میشه. اصلا چند روز پیش داشتم با خودم فکر می کردم که واقعا شاید الآن خوب باشه که بچه ها برن یه مقداری روی نوشتنشون برای مرحله 2 تمرین کنن.

دوم این که یه جاهایی که خوبه، یه مفاهیمی رو تعریف کنید. مثلا بگید که "تعریف: برای یک جایگشت p از اعداد طبیعی 1 تا n، مرتبه ی p برابر است با تعداد اعضای p که عضو آخر نیستند و از عضو بعدی خود کوچکترند"

سوم این که قبل از این که بنویسید، سعی کنید مفاهیمی که می خواید تعریف کنید، لم هایی که می خواین ثابت کنید، و چیزهایی که توی متن نوشته هاتون (نه به صورت لم) می خواید ثابت کنید رو دقیق مشخص کنید، و اون ها رو به یه ترتیبی در بیارید که توی بیان یا اثبات هر کدوم، فقط از موارد قبلی استفاده بشه. مثلا در نظر می گیرید که اول لم1 رو می نویسم و ثابت می کنم، بعد لم 2 رو، و بعد لم 3 رو که توی اثباتش از لم 1 و 2 استفاده میشه. بعد فلان چیزها رو تعریف می کنم. بعد کلیت راه حلم رو توضیح می دم و بعد فلان چیز رو همون وسط (یعنی نه به صورت لم) می گم و با استفاده از لم 1 و لم 3 ثابت می کنم. کلا سعی کنید قبل از نوشتن، یه طرح کلی از ترتیب چیزهایی که می خواید بگید، روی کاغذ بنویسید (در حد 3-4 دقیقه)

چهارم این که گاهی، این که نمی تونید جوابتون رو درست بیان کنید، معنی اش اینه که سوال رو درست یا کامل حل نکردید.

پنجم این که گاهی، اگه یه خرده بیانتون رو فنی تر کنید (مثلا با استقرا بیان کنید، یا با برهان خلف بیان کنید) یا یه خرده حکم مساله رو قوی تر کنید (مثلا گفته ثابت کنید فلان گراف خاصیت A رو داره، شما ثابت می کنید خاصیت B رو داره، که در نتیجه خاصیت A رو هم داره)

ششم این که هر سوالی رو که حل می کنید، همون موقع بنویسید. این طوری اگه راه حلتون غلط باشه می فهمید. ضمنا اگه بذارید آخر کار بنویسید، ممکنه با عجله و بد بنویسید.

هفتم این که اگه یه سوال رو حل نکردید هم، تا هرجایی که حلش کردید و هر نتیجه ای که در موردش به دست آوردید و هر ایده ای که دارید بنویسید.

هشتم این که پایه ی استقرا، یا حالت های خاص هم یه نمره ای داره. مثلا اگه گفته در گراف های n راسی فلان چیز چقدره، و برای همه ی گرافها، به غیر از گراف بدون یال، فلان چیز n+5 هست، ولی برای گراف بدون یال مثلا 0 هست، این که این حالت خاص رو ذکر کنید هم لازمه و یه نمره ی کمی داره.

نهم این که من تجربه ی این رو داشتم که توی مرحله دوم ریاضی یه سالی که شرکت کردم، یه سوالی غلط بود. (فکر کنم توی یه مرحله دوممون هم این جوری بود). توی ریاضیه یادمه که تمره دهی این جوری بود که اگه ثابت می کردی غلطه، نصف نمره رو می گرفتی، اگه سوال رو درست می کردی و حلش می کردی تمام نمره رو می گرفتی.