Как да станете шампион по програмиране на Урал - Bookshelf
Минаха години. Смениха се поколенията; в USU, както и в други университети, напълно различни хора играят ACM програмиране. Нашите възгледи за спортното програмиране са излъскани от времето и безкрайните битки. Максимализмът отстъпи място на зрелия опит. Няма да пишем за това, в което не можем да се считаме за експерти - нека го оставим на Андрей Лопатин и Николай Дуров. Нека напишем за това, което всеки от нас успя три пъти: как да стане шампион на Урал по програмиране.
Сега, уви, работим в различни градове и статията трябваше да бъде сглобена от различни фрагменти, написани от първо лице. Когато финализирахме текста, отначало искахме да заменим всяко „Аз“ с „Аз“ (Н.Ш.) или „Аз“ (Л.В.). Но през годините на игра в един и същи отбор, ние развихме доста общ поглед върху нещата, които ще бъдат обсъдени по-долу, и затова решихме да оставим всички „I“ в текста непроменени. Ще считаме, че това е нашето колективно „Аз“, един вид разпределен Санкт Екатеринбург „Аз“ разказва за опита си от участие в първите пет шампионата по програмиране на Урал.
КАКВО Е „БЪДИ ПО-ДОБЪР“
Правилата ясно определят условията за спечелване на олимпиадата по програмиране съгласно правилата на ACM. Отборът трябва да реши повече задачи от другите отбори и ако броят на решените задачи е равен, те трябва да спечелят по-малко наказателно време. Така че, за да спечелите на олимпиадата по програмиране, трябва да сте по-добри от другите. И това много „по-добро“ се състои от много фактори. За да спечелите състезанието върху набор от много различни проблеми, е необходимо да намерите решение на възможно най-много проблеми и да програмирате всеки от решените с високо качество, чисто и бързо.
КАК ДА РЕШИМ ПРОБЛЕМА
Не знам,как да решаваме проблемите. Знам само, че след като решиш много от тях, започваш да го правиш по-добре, започваш да виждаш по-добри възможни подходи за решаване на проблемите, започваш да ги усещаш по-добре. И все пак факторът „способности“, „талант“ играе важна роля тук. Това, което не може да се определи с думи и не може да се измери с никакъв аршин. Фактор на несигурност, който в крайна сметка класира отбори, които са абсолютно равностойни като подготовка. Следователно в бъдеще ще приемем, че всички отбори, влизащи в началото на следващото състезание, са абсолютно равни по отношение на способностите си. Сега ще се опитаме да покажем как можете да увеличите максимално останалите параметри, които определят успеха на екипа. В края на краищата, решаването на проблема е половината битка, вие също трябва да програмирате решението.
ТУХЛЕН ПЛОСТ
Внедряването е в известен смисъл по-малко креативно от реалното решаване на проблема. Казвайки това, ние ни най-малко не искаме да обидим талантливите кодери, които намират истинско удоволствие във виртуозното използване на езикови ресурси за оптимална реализация на на пръв поглед банални неща. Просто искаме да подчертаем, че способността за качествено внедряване на решение е много по-податлива на обучение и усъвършенстване в сравнение със способността за решаване на проблеми.
Единственият начин да спечелите при висококачествено изпълнение е да възпитате машина в себе си, която много рядко се отнася до главата при програмиране. При кодиране главата може да се свърже с процеса само в критични моменти и, разбира се, не в момента, когато енкодерът е на компютъра. По принцип енкодерът трябва да може да сглоби програмата от подготвените тухли. Колкото повече готови шаблони са под ръка, толкова по-бързо и по-надеждно ще се сглоби програмата. Ако трябва да разберете как да направите този или онзи блок, човекът, койтовече съществува - седи в пръстите, както се казва - несъмнено ще ви изпревари в изпълнението.
Тук на помощ може да дойде следната практическа препоръка: сглобете проблем от тухли, преди да седнат на колата. Следното правило трябва да стане норма: всички задачи, започвайки от втората, трябва да бъдат кодирани чрез препечатване от лист хартия. По този начин получаваме, че първата задача трябва да бъде някаква технически очевидна задача - но не е задължително да е най-лесната.
Силата на подхода, базиран на програмиране от готови шаблони, се крие във факта, че внедряването на готови алгоритми се довежда до автоматизма и в този случай големи и сложни участъци от код веднага се отстраняват. След това трябва да дебъгвате само свързващите секции на кода - и те почти винаги са по-малки и освен това логически по-прости.
КЛОНИГ НА СЕБЕ СИ
За да формирате по-ясна представа за това какво е добро и какво е лошо, трябва да решите много проблеми на съдия и време. Препоръчително е да се свържете с други участници и да ги помолите да изпратят решения на тези проблеми, чийто код не ви удовлетворява. Още по-полезно е да изтеглите решенията на журито на полуфиналните състезания. Особено добри са задачите традиционно в Санкт Петербург, Чехословакия, Канада и Германия. След като решите тези задачи, сравнете своите решения с тези на журито. Ако вашите решения са по-добри (по-кратки, по-елегантни, по-ясни) - поздравления. Ако не, разберете защо вашите решения са по-лоши и се преквалифицирайте. Анализът на кода не е ровене в мръсното пране, а много полезна дейност, която може да ви научи на много. Опитайте се да пишете едни и същи неща по АБСОЛЮТНО еднакъв начин. Това е необходимо, за да не се правят грешки в прости случаи. Ако обаче намерите по-добър начин да го приложите, преквалифицирайте се. Аз лично научих много от канадцитеидеи.
Ако вече имате нещо в пръстите си, не забравяйте да го опреснявате и повтаряте редовно. Върнете се отново към задачите, които сте решавали някога. Ако някой ден можете да напишете решение, което повтаря байт по байт от миналата година, това е повод за радост.
Следващият етап, към който трябва да се стремим, е стандартизирането на възгледите в екипа. Отстъп, правила за използване на функции, вход и изход, именуване на променливи и функции - всичко трябва да е унифицирано. Тогава кръстосаното отстраняване на грешки ще бъде по-бързо, защото има по-малко нужда да се обясняваме един на друг. Много е полезно да вземете програма и да обясните на друг човек как работи. Цялостният стил е нещо, към което трябва да се стремите постоянно.
Спомням си много добре момента, когато успоредихме проблема с доминото в Санкт Петербург и без да кажем нито дума, назовахме същата функция, чрез която нашите модули бяха свързани. Точно в този момент, 25 минути преди края на надпреварата, вярвах, че ще сме на финал.
ТЕХМИНИМУМ
Що се отнася до конкретните алгоритми, които трябва да знаете: трябва да знаете всичко! Вярно е, че е по-добре да ги изучавате в ред на нарастваща сложност. Какъв е смисълът да знаеш как да програмираш унгарския алгоритъм, ако не знаеш как да разложиш число на прости множители. Втората задача ще се среща сто пъти по-често. В това отношение е много полезно да се решават задачи от книгата на Матюхин, Пономарев.
Въпреки това е невъзможно да се обхване необятността. Ето защо преди много време нашият екип разработи практика, която смятам за много полезна. А именно, очертана е определена гама от задачи, които сме приели като технически минимум, задължителен за всички. Останалите видове задачи бяха разпределени между членовете на екипа за специално проучване. Техническият минимум включва основни, добре познати алгоритми и, което е важно,градивни елементи, които неизбежно възникват при програмиране на алгоритми с всякаква сложност.
ТРЕНИРОВКА
Опитайте се да разнообразите тренировките си. Не се ограничавайте до моделиране на типично състезание. Достатъчно лесно е да се измислят различни видове обучение, лично, екипно и лично-екипно, които помагат да се усъвършенстват определени аспекти на уменията.
Например, след работен ден рядко остава сила за пълноценна тренировка. Да, и няма да има голям смисъл от такова обучение. В тази ситуация е полезно да вземете 2-3 трудни задачи за 1,5-2 часа и това могат да бъдат задачи, за които вече сте мислили преди. По този начин ситуацията на финала е идеално симулирана (и работният ден след това добавя естественост), което толкова често е препъни камък за много екипи.
Отлично обучение е измислянето на задачи, подготовката на състезания за ученици, измислянето на тестове за задачи. И накрая, полезно е да се решават изследователски проблеми, които изискват потапяне в специализирана литература и няколко дни размисъл.
НАСЛАДИ СЕ
Психологическият аспект също е много важен; Спомням си много примери, когато силен отбор „изгоря“ във важни състезания поради психологическа тежест на плещите си. Страхотно е, когато екипът е екип от съмишленици. Ако не, работете върху морала на екипа. Не е много добре, когато екипът има ясно изразен лидер, който носи отговорност за всички решения; много по-добре – но по-трудно – е да се възпитава екипно аз, което може да взема правилните решения дори в най-трудните ситуации.
Опитайте се да се насладите на самия процес на игра - това е много важно. Бъдете страстни, бъдете уверени. Ако сте се научили да се наслаждавате на играта, тогаване трябва да тренирате в последните дни преди важно състезание: тогава няма да изпитате ситост, но ще можете да се втурнете в битка.
Ако искате да се научите да програмирате, програмирайте. Постоянно се оглеждайте, докато хората програмират, това няма да ви позволи да се заблудите.
Те съдържат огромен брой идеи. Доведете своите реализации на тези алгоритми до автоматизм.
Постигнете същия възглед за качествения код във вашия екип.
Професионалистът винаги е по-добър от аматьор. Станете професионалист.
Основното нещо е победата, но участието също не е лошо.
Почивка. Елате на състезанието като на празник. Опитайте се да се отпуснете и да се насладите колкото е възможно повече.
P.S. Офисът на Дон Кнут не е на същия етаж като моя офис. Не ям скариди с изглед към Тихия океан. Но спечелих шампионата на Урал три пъти и взех бронз на световното първенство, въпреки че никога не съм показвал нищо специално в училищните олимпиади и не мога да се похваля с изключителни способности. Преди време дори ми беше трудно да разбера защо се случи това. Но погледнато назад всеки е силен. Сега разбирам: просто се опитах да следвам принципите, описани по-горе.
шампион на Урал 1998-2000,
програмист в Transas Software House, световен лидер в ИТ решенията за морската индустрия, Санкт Петербург.
шампион на Урал 1999-2001,
ръководител на лабораторията за интернет технологии на компанията "СКБ Контур", Екатеринбург,