Free C# / Java / JavaScript / Python / C++ Programming Books » Глава 23. Как да решаваме задачи по програмиране?

В тази тема...

В настоящата тема ще дискутираме един препоръчителен подход за решаване на задачи по програмиране и ще го илюстрираме нагледно с реални примери. Ще дискутираме инженерните принципи, които трябва да следваме при решаването на задачи по програмиране (които важат в голяма степен и за задачи по математика, физика и други дисциплини) и ще ги покажем в действие. Ще опишем стъпките, през които преминаваме при решаването на няколко примерни задачи и ще демонстрираме какви грешки се получават, ако не следваме тези стъпки. Ще обърнем внимание на някои важни стъпки от решаването на задачи, които обикновено се пропускат, като например тестването. Надяваме се да успеем да ви докажем чрез много примери, че за решаването на задачи по програмиране си има "рецепта" и да ви убедим колко много помага тя.

Съдържание

Видео

Презентация

23. Methodology of Problem Solving from Intro C# Book

Мисловни карти

Основни принципи при решаване на задачи по програмиране

Сигурно си мислите, че сега ще ви напълним главата с празни приказки в стил "първо мисли, след това пиши" или "внимавайте като пишете, че да не пропуснете нещо". Всъщност тази тема няма да е толкова досадна и ще ви даде практически насоки как да подхождате при решаването на задачи, независимо дали са алгоритмични или други.

Без да претендираме за изчерпателност, ще ви дадем няколко важни препоръки, базирани на опита на Светлин Наков, който повече от 10 години подред е участвал редовно по български и международни състезания по програмиране, а след това е обучавал на програмиране и решаване на задачи студенти в Софийски университет "Св. Климент Охридски" (ФМИ на СУ), в Нов Български Университет (НБУ), в Национална академия по разработка на софтуер (НАРС), както и в Telerik Academy.

Нека започнем с първата важна препоръка.

Използвайте лист и химикал!

Захващането на лист и химикал и скицирането на примери и разсъждения по дадения проблем е нещо съвсем нормално и естествено – нещо, което всеки опитен математик, физик или софтуерен инженер прави, когато му поставят нетривиална задача.

За съжаление, от опита си с обучението на софтуерни инженери в НАРС можем да споделим, че повечето начинаещи програмисти въобще не си носят лист и химикал. Те имат погрешното съзнание, че за да решават задачи по програмиране им е достатъчна само клавиатурата. На повечето им трябват доста време и провали по изпитите, за да достигат до важния извод, че използването на някаква форма на чертеж, скица или визуализация на проблема е от решаваща полза за неговото разбиране и за конструиране на правилно решение.

Който не ползва лист и химикал, ще бъде силно затруднен при решаването на задачи по програмиране. Винаги скицирайте идеите си на хартия или на дъската преди да започнете да пишете на клавиатурата!

Наистина изглежда старомодно, но ерата на хартията все още не е отминала! Най-лесният начин човек да си скицира идеите и разсъжденията е като хване лист и химикал, а без да скицирате идеите си, е много трудно да разсъждавате. Чисто психологически това е свързано с визуалната система за представяне на информацията в човешкия мозък, която работи изключително бързо и е свързана силно с творческия потенциал и с логическото мислене. Хората с развита визуална система първо си представят решението и го "виждат" по някакъв начин в своето съзнание, а след това го развиват като идея и накрая стигат до реализация. Те използват активно визуалната си памет и способността си визуално да конструират образи, което им дава възможност много бързо да разсъждават. Такива хора за секунди могат да прехвърлят през съзнанието си десетки идеи и да си представят алгоритмите и решенията на задачите. Независимо дали сте от "визуалния" тип хора или не, да си скицирате проблема или да си го нарисувате ще ви помогне на разсъжденията, с които да достигнете до решението му, защото всеки има способност да си представя нещата визуално.

Помислете например колко усилия ви трябват, за да умножавате петцифрени числа на ум и колко по-малко са усилията, ако имате лист и химикал (изключваме възможността да използваме електронни устройства). По същия начин е с решаването на задачи – когато трябва да измислите решение, ви трябва лист хартия за да си драскате и рисувате. Когато трябва да проверите дали решението ви е вярно, ви трябва отново хартия, за да си разпишете един пример. Когато трябва да измисляте случаи, които вашето решение изпуска, отново ви трябва нещо, на което да си разписвате и драскате примери и идеи. Затова ползвайте лист и химикал!

Измислете идеи и ги пробвайте!

Решаването на дадена задача винаги започва от скицирането на някакъв пример върху лист хартия. Когато имате конкретен пример, можете да разсъждавате, а когато разсъждавате, ви хрумват идеи за решение на задачата.

Когато вече имате идея, ви трябват още примери, за да проверите дали идеята е добра. Тогава можете да нарисувате още няколко примера на хартия и да пробвате вашата идея върху тях. Уверете се, че идеята ви е вярна. Проследете идеята стъпка по стъпка, така, както ще я изпълни евентуална компютърна програма и вижте дали няма някакви проблеми.

Опитайте се да "счупите" вашата идея за решение – да измислите пример, при който тя не работи (контра-пример). Ако не успеете, вероятно сте на прав път. Ако успеете, помислете как да се справите с неработещия пример: измислете "поправка" на вашата идея за алгоритъм или измислете напълно нова идея.

Не винаги първата идея, която ви хрумва, е правилна и може да се превърне в решение на задачата. Решаването на задачи е итеративен процес, при който последователно измисляте идеи и ги пробвате върху различни примери докато не стигнете до идея, която изглежда, че е правилна и може успешно да реши задачата. Понякога могат да минат часове в опитите ви да измислите алгоритъм за решаването на дадена задача и да пробвате десетки различни идеи. Това е нормално. Никой няма способността да измисля моментално решение на всяка задача, но със сигурност колкото по-голям опит имате при решаването на задачи, толкова по-бързо ще ви идват добри идеи. Ако сте решавали подобна задача, бързо ще се сетите за нея и за начина по който сте я решили, тъй като едно от основните свойства на човешкия мозък е да разсъждава с аналогии. Опитът от решаването на даден тип задачи ви научава бързо да измисляте решение по аналогия с друга подобна задача.

За да измисляте идеи и да ги проверявате ви трябват лист, химикал и различни примери, които да измисляте и да визуализирате чрез скица, рисунка, чертеж или друг способ. Това ви помага много бързо да пробвате различни идеи и да разсъждавате върху идеите, които ви хрумват. Основното действие при решаването на задачи е да разсъждавате логически, да търсите аналогии с други задачи и методи, да обобщавате или да прилагате обобщени идеи и да конструирате решението си като си го визуализирате на хартия. Когато имате скица или чертеж вие можете да си представяте визуално какво би се случило, ако извършим дадено действие върху данните от картинката. Това може да ни даде и идея за следващо действие или да ни откаже от нея. Така може да стигнем до цялостен алгоритъм, чиято коректност можем да проверим като го разпишем върху конкретен пример.

Решаването на задачи по програмиране започва от измислянето на идеи и проверяването им. Това става най-лесно като хванете лист и химикал и скицирате разсъжденията си. Винаги проверявайте идеите си с подходящи примери!

Горните препоръки са много полезни и в още един случай: когато сте на интервю за работа. Всеки опитен интервюиращ може да потвърди, че когато даде алгоритмична задача на кандидат за работа, очаква от него да хване лист и химикал и да разсъждава на глас като предлага различни идеи, които му хрумват. Хващането на лист и химикал на интервю за работа дава признаци за мислене и правилен подход за решаване на проблеми. Разсъждаването на глас показва, че можете да мислите. Дори и да не стигнете до правилно решение подходът към решаване на задачи ще направи добро впечатление на интервюиращия!

Разбивайте задачата на подзадачи!

Сложните задачи винаги могат да се разделят на няколко по-прости. Ще ви покажем това в примерите след малко. Нищо сложно на този свят не е направено наведнъж. Рецептата за решаване на сложни задачи е да се разбият логически на няколко по-прости (по възможност максимално независими една от друга). Ако и те се окажат сложни, разбиването на по-прости може да се приложи и за тях. Тази техника е известна като "разделяй и владей" и е използвана още в Римската империя.

Разделянето на проблема на части звучи просто на теория, но на практика не винаги е лесно да се направи. Тънкостта на решаване на алгоритмични задачи се крие в това да овладеете добре техниката на разбиването на задачата на по-прости подзадачи и, разбира се, да се научите да ви хрумват добри идеи, което става с много, много практика.

Сложните проблеми винаги могат да се разделят на няколко по-прости. Когато решавате задачи, разделяйте сложната задача на няколко по-прости задачи, които можете да решите самостоятелно.

Разбъркване на тесте карти – пример

Нека дадем един пример: трябва да разбъркаме тесте карти в случаен ред. Да приемем, че тестето е дадено като масив или списък от N на брой обекти (всяка карта е обект). Това е задача, която изисква много стъпки (някаква серия от изваждания, вмъквания, размествания или преподреждания на карти). Тези стъпки сами по себе си са по-прости и по-лесни за реализация, отколкото цялостната задача за разбъркване на картите. Ако намерим начин да разбием сложната задача на множество простички стъпки, значи сме намерили начин да я решим. Именно в това се състои алгоритмичното мислене: в умението да разбиваме сложен проблем на серия по-прости проблеми, за които можем да намерим решение. Това, разбира се, важи не само за програмирането, но и за решаването на задачи по математика, физика и други дисциплини. Точно алгоритмичното мислене е причината математиците и физиците много бързо да напредват, когато се захванат с програмиране.

Нека се върнем към нашата задача и да помислим кои са елементарните действия, които са нужни, за да разбъркаме в случаен ред картите?

Ако хванем в ръка тесте карти или си го нарисуваме по някакъв начин на лист хартия (например като серия кутийки с по една карта във всяка от тях), веднага ще ни хрумне идеята, че е необходимо да направим някакви размествания или пренареждания на някои от картите.

Разсъждавайки в този дух стигаме до заключението, че трябва да направим повече от едно разместване на една или повече карти. Ако направим само едно разместване, получената подредба няма да е съвсем случайна. Следователно ни трябват много на брой по-прости операции за единични размествания.

Стигнахме до първото разделяне на задачата на подзадачи: трябват ни серия размествания и всяко разместване можем да разгледаме като по-проста задача, част от решението на по-сложната.

Първа подзадача: единично разместване

Как правим "единично разместване" на карти в тестето? На този въпрос има стотици отговори, но можем да вземем първата идея, която ни хрумва. Ако е добра, ще я ползваме. Ако не е добра, ще измислим друга.

Ето каква може да е първата ни идея: ако имаме тесте карти, можем да се сетим да разделим тестето на две части по случаен начин и да разменим едната част с другата. Имаме ли идея за "единично разместване" на картите? Имаме. Остава да видим дали тази идея ще ни свърши работа (ще я пробваме след малко на практика).

Нека се върнем на началната задача: трябва да получим случайно размесено тестето карти, което ни е дадено като вход. Ако хванем тестето и много на брой пъти го разцепим на две и разменим получените две части, ще получим случайно размесване, нали? Изглежда нашата първа идея за "единично разместване" ще свърши работа.

Втора подзадача: избор на случайно число

Как избираме случаен начин за разцепване на тестето? Ако имаме N карти, ни трябва начин да изберем число между 1 и N-1, нали?

За да решим тази подзадача, ни трябва или външна помощ, или да знаем, че тази задача в .NET Framework е вече решена и можем да ползваме вградения генератор на случайни числа наготово.

Ако не се сетим да потърсим в Интернет как със C# се генерират случайни числа, можем да си измислим и наше собствено решение, например да въвеждаме един ред от клавиатурата и да измерваме интервала време между стартирането на програмата и натискането на [Enter] за край на въвеждането. Понеже при всяко въвеждане това време ще е различно (особено, ако можем да отчитаме с точност до наносекунди), ще имаме начин да получим случайно число. Остава въпросът как да го накараме да бъде в интервала от 1 до N-1, но вероятно ще се сетим да ползваме остатъка от деление на (N-1) и да си решим проблема.

Виждате, че дори простите задачи могат да имат свои подзадачи или може да се окаже, че за тях вече имаме готово решение. Когато намерим решение, приключваме с текущата подзадача и се връщаме към оригиналната задача, за да продължим да търсим идеи и за нейното решаване. Нека направим това.

Трета подзадача: комбиниране на разместванията

Да се върнем пак на началната задача. Чрез последователни разсъждения стигнахме до идеята много пъти да извършим операцията "единично разместване" в тестето карти докато тестето се размести добре. Това изглежда коректно и можем да го пробваме.

Сега възниква въпросът колко пъти да извършим операцията "единично разместване". 100 пъти достатъчно ли е? А не е ли много? А 5 пъти достатъчно ли е, не е ли малко? За да дадем добър отговор на този въпрос трябва да помислим малко. Колко карти имаме? Ако картите са малко, ще ни трябват малко размествания. Ако картите са много, ще ни трябват повече размествания, нали? Следователно броят размествания изглежда зависи от броя карти.

За да видим колко точно трябва да са тези размествания, можем да вземем за пример стандартно тесте карти. Колко карти има в него? Всеки картоиграч ще каже, че са 52. Ами тогава да помислим колко разцепвания на тестето на две и разменяния на двете половини ни трябват, за да разбъркаме случайно 52 карти. Дали 52 е добре? Ако направим 52 "единични размествания" изглежда, че ще е достатъчно, защото заради случайния избор ще сцепим средно по 1 път между всеки две карти (това е видно и без да четем дебели книги по вероятности и статистика). А дали 52 не е много? Можем да измислим и по-малко число, което ще е достатъчно, например половината на 52. Това също изглежда достатъчно, но ще е по-трудно да се обосновем защо.

Някои биха тръгнали с дебелите формули от теорията на вероятностите, но има ли смисъл? Числото 52 не е ли достатъчно малко, за да търсим по-малко. Цикъл, извършващ разцепването 52 пъти, минава мигновено, нали? Картите няма да са един милиард, нали? Следователно няма нужда да мислим в тази посока. Приемаме, че правим толкова "единични размествания", колкото са картите и това хем е достатъчно, хем не е прекалено много. Край, тази подзадача е решена.

Още един пример: сортиране на числа

Нека разгледаме накратко и още един пример. Даден е масив с числа и трябва да го сортираме по големина, т.е. да подредим елементите му в нарастващ ред. Това е задача, която има десетки концептуално различни методи за решаване и вие можете да измислите стотици идеи, някои от които са верни, а други – не съвсем.

Ако имаме тази задача и приемем, че е забранено да се ползват вградените в .NET Framework методи за сортиране, е нормално да вземем лист и химикал, да си направим един пример и да започнем да разсъждаваме. Можем да достигнем до много различни идеи, например:

- Първа идея: можем да изберем най-малкото число, да го отпечатаме и да го изтрием от масива. След това можем да повторим същото действие многократно докато масивът свърши. Разсъждавайки по тази идея, можем да разделим задачата на няколко по-прости задачки: намиране на най-малко число в масив; изтриване на число от масив; отпечатване на число.

- Следваща идея: можем да вземем най-малкото число и да го преместим най-отпред (чрез изтриване и вмъкване). След това в останалата част от масива можем пак да намерим най-малкото число и да го преместим веднага след първото. На k-тата стъпка ще имаме първите k най-малки числа в началото на масива. При този подход задачата се разделя по естествен начин на няколко по-малки задачки: намиране на най-малко число в част от масив и преместване на число от една позиция на масив в друга. Последната задачка може да се разбие на две по-малки: "изтриване на елемент от дадена позиция в масив" и "вмъкване на елемент в масив на дадена позиция").

- Поредна нова идея, която се базира на коренно различен подход: да разделим масива на две части с приблизително равен брой елементи, след което да сортираме първата част, да сортираме втората част и накрая да обединим двете части. Можем да приложим същото рекурсивно за всяка от частите докато не достигнем до част с големина един елемент, който очевидно е сортиран. При този подход пак имаме разделяне на сложната задача на няколко по-прости подзадачи: разделяне на масив на две равни (или почти равни) части; сливане на сортирани масиви.

Няма нужда да продължаваме повече, нали?. Всеки може да измисли още много идеи за решаване на задачата или да ги прочете в някоя книга по алгоритми. Показахме ви, че винаги сложната задача може да се раздели на няколко по-малки и по-прости задачки. Това е правилният подход при решаване на задачи по програмиране – да мислим за големия проблем като за съвкупност от няколко по-малки и по-прости проблема. Това е техника, която се усвоява бавно с времето, но рано или късно ще трябва да свикнете с нея.

Проверете идеите си!

Изглежда не остана нищо повече за измисляне. Имаме идея. Тя изглежда, че работи. Остава да проверим дали наистина работи или само така си мислим и след това да се ориентираме към имплементация.

Как да проверим идеята си? Обикновено това става с един или с няколко примера. Трябва да подберете такива примери, които в пълнота покриват различните случаи, които вашият алгоритъм трябва да преодолее. Примерите трябва хем да не са лесни за вашия алгоритъм, хем да са достатъчно прости, за да ги разпишете бързо и лесно. Такива примери наричаме "добри представители на общия случай".

Например ако реализираме алгоритъм за сортиране на масив в нарастващ ред, удачно е да вземем пример с 5-6 числа, сред които има 2 еднакви, а останалите са различни. Числата трябва първоначално да са подредени в случаен ред. Това е добър пример, понеже покрива много голяма част от случаите, в които нашият алгоритъм трябва да работи.

За същата задача за сортиране има множество неподходящи примери, с които няма да можете ефективно да проверите дали вашата идея за решение работи коректно. Например можем да вземем пример само с 2 числа. За него алгоритъмът може да работи, но по идея да е грешен. Можем да вземем пример само с еднакви числа. При него всеки алгоритъм за сортиране ще работи. Можем да вземем пример с числа, които са предварително подредени по големина. И за него алгоритъмът може да работи, но да е грешен.

Когато проверявате идеите си подбирайте подходящи примери. Те трябва хем да са прости и лесни за разписване, хем да не са частен случай, при който вашата идея би могла да работи, но да е грешна в общия случай. Примерите, които избирате, трябва да са добри представители на общия случай – да покриват възможно повече случаи, без да са големи и сложни.

Разбъркване на карти: проверка на идеята

Нека измислим един пример за нашата задача за разбъркване на карти, да кажем с 6 карти. За да е добър примерът, картите не трябва да са малко (да кажем 2-3), защото така примерът е прекалено лесен, но не трябва и да са много, за да можем бързо да проиграем нашата идея върху него. Добре е картите да са подредени първоначално по големина или даже за по-лесно да са поредни, за да може накрая лесно да видим дали са разбъркани – ако се запазят поредни или частично подредени, значи разбъркването не работи добре. Може би е най-хитро да вземем 6 карти, които са поредни, без значение на боята.

Вече измислихме пример, който е добър представител на общия случай за нашата задача. Нека да го нарисуваме на лист хартия и да проиграем върху него измисления алгоритъм. Трябва 6 пъти подред да сцепим на случайно място поредицата карти и да разменим получените 2 части. Нека картите първоначално са наредени по големина. Очакваме накрая картите да са случайно разбъркани. Да видим какво ще получим:

Няма нужда да правим 6 разцепвания. Вижда се, че след 3 размествания се върнахме в изходна позиция. Това едва ли е случайно. Какво стана? Открихме проблем в алгоритъма. Изглежда, че нашата идея е грешна. Като се замислим малко, се вижда, че всяко единично разместване през случайната позиция k всъщност ротира наляво тестето карти k пъти и след общо N ротации стигаме до изходна позиция. Добре, че тествахме на ръка алгоритъма преди да сме написали програмата, нали?

Сортиране на числа: проверка на идеята

Ако вземем проблема за сортирането на числа по големина и първия алгоритъм, който ни хрумна, можем лесно да проверим дали е верен. При него започваме с масив от N елемента и N пъти намираме в него най-малкото число, отпечатваме го и го изтриваме. Дори и без да я разписваме на хартия тази идея изглежда безпогрешна. Все пак нека вземем един пример и да видим какво ще се получи. Избираме 5 числа, като 2 от тях са еднакви: 3, 2, 6, 1, 2. Имаме 5 стъпки:

1) 3, 2, 6, 1, 2 → 1

2) 3, 2, 6, 2 → 2

3) 3, 6, 2 → 2

4) 3, 6 → 3

5) 6 → 6

Изглежда алгоритъмът работи коректно. Резултатът е верен и нямаме основание да си мислим, че няма да работи и за всеки друг пример.

При проблем измислете нова идея!

Нормално е, след като намерим проблем в нашата идея, да измислим нова идея, която би трябвало да работи. Това може да стане по два начина: или да поправим старата си идея, като отстраним дефектите в нея, или да измислим напълно нова идея. Нека видим как това работи за нашата задача за разбъркване на карти.

Измислянето на решение на задача по програмиране е итеративен процес, който включва последователно измисляне на идеи, изпробването им и евентуално замяната им с по-добри идеи при откриване на проблем. Понякога още първата идея е правилна, а понякога пробваме и отхвърляме една по една много различни идеи докато стигнем до такава, която да ни свърши работа.

Да се върнем на нашата задача за разбъркване на тесте карти. Първото нещо, което ни хрумва, е да видим защо е грешна нашата първа идея и да се опитаме да я поправим, ако това е възможно. Проблемът лесно се забелязва: последователното разцепване на тестето на две части и размяната им не води до случайна наредба на картите, а до някаква тяхна ротация (изместване наляво с някакъв брой позиции).

Как да поправим алгоритъма? Необходим ни е по-умен начин да правим единичното разместване, нали? Хрумва ни следната идея: взимаме две случайни карти и ги разменяме една с друга? Ако го направим N на брой пъти, сигурно ще се получи случайна наредба. Идеята изглежда по-добра от предната и може би работи. Вече знаем, че преди да мислим за реализация на новия алгоритъм трябва да го проверим дали работи правилно. Започваме да скицираме на хартия какво ще се случи за нашия пример с 6 карти.

В този момент ни хрумва нова, като че ли по-добра идея. Не е ли по-лесно на всяка стъпка да вземем случайна карта и да я разместим с първата? Изглежда по-просто и по-лесно за реализация, а резултатът би трябвало пак да е случаен. Първоначално ще разменим карта от случайна позиция k₁ с първата карта. Ще имаме случайна карта на първа позиция и първата карта ще бъде на позиция k₁. На следващата стъпка ще изберем случайна карта на позиция k₂ и ще я разменим с първата карта (картата от позиция k₁). Така вече първата карта си е сменила позицията, картата от позиция k₁си е сменила позицията и картата от позиция k₂ също си е сменила позицията. Изглежда, че на всяка стъпка по една карта си сменя позицията със случайна. След такива N стъпки можем да очакваме всяка карта средно по веднъж да си е сменила мястото и следователно картите би трябвало да са добре разбъркани.

Дали това наистина е така? Да не стане като предния път? Нека проверим старателно тази идея. Отново можем да вземем 6 карти, които представляват добре подбран пример за нашата задача (добър представител на общия случай), и да ги разбъркаме по новия алгоритъм. Трябва да направим 6 последователни размествания на случайна карта с първата карта от тестето. Ето какво се получава:

От примера виждаме, че резултатът е правилен – получава се наистина случайно разбъркване на нашето примерно тесте от 6 карти. Щом нашият алгоритъм работи за 6 карти, би трябвало да работи и за друг брой. Ако не сме убедени в това, е хубаво да вземем друг пример, който изглежда по-труден за нашия алгоритъм.

Ако сме твърдо убедени, че идеята е вярна, може и да си спестим разписването на повече примери на хартия и направо продължим напред с решаването на задачата.

Да обобщим какво направихме до момента и как чрез последователни разсъждения стигнахме до идея за решаването на задачата. Следвайки всички препоръки, изложени до момента, минахме през следните стъпки:

- Използвахме лист и химикал, за да си скицираме тесте карти за разбъркване. Нарисувахме си последователност от кутийки на лист хартия и така успяхме визуално да си представим картите.

- Имайки визуална представа за проблема, ни хрумнаха някои идеи: първо, че трябва да правим някакви единични размествания и второ, че трябва да ги правим много на брой пъти.

- Решихме да правим единични размествания чрез цепене на картите на случайно място и размяна на двете половини.

- Решихме, че трябва да правим толкова размествания, колкото са картите в тестето.

- Сблъскахме се и с проблема за избор на случайно число, но избрахме решение наготово.

- Разбихме оригиналната задача на три подзадачи: единично разместване; избор на случайно число; повтаряне на единичните размествания.

- Проверихме дали идеята работи и намерихме грешка. Добре, че направихме проверка преди да напишем кода!

- Измислихме нова стратегия за единично разместване, която изглежда по-надеждна.

- Проверихме новата идея с подходящи примери и имаме увереност, че е правилна.

Вече имаме идея за решение на задачата и тя е проверена с примери. Това е най-важното за решаването на една задача – да измислим алгоритъма. Остава по-лесното – да реализираме идеята си. Нека видим как става това.

Подберете структурите от данни!

Ако вече имаме идея за решение, която изглежда правилна и е проверена с няколко надеждни примера, остава да напишем програмния код, нали? Какво изпуснахме? Измислихме ли всичко необходимо, за да можем бързо, лесно и безпроблемно да напишем програма, която реализира нашата идея за решаване на задачата?

Това, което изпуснахме, е да си представим как нашата идея (която видяхме как работи на хартия) ще бъде имплементирана като компютърна програма. Това не винаги е елементарно и понякога изисква доста време и допълнителни идеи. Това е важна стъпка от решаването на задачи: да помислим за идеите си в термините на компютърното програмиране. Това означава да разсъждаваме с конкретни структури от данни, а не с абстракции като "карта" и "тесте карти". Трябва да подберем подходящи структури от данни, с които да реализираме идеите си.

Преди да преминете към имплементация на вашата идея помислете за структурите от данни. Може да се окаже, че вашата идея не е толкова добра, колкото изглежда. Може да се окаже, че е трудна за реализация или неефективна. По-добре да откриете това преди да сте написали кода на програмата!

В нашия случай говорихме за "размяна на случайна карта с друга", а в програмирането това означава да разместим два елемента в някаква структура от данни (например масив, списък или нещо друго). Стигнахме до момента, в който трябва да изберем структурите от данни и ще ви покажем как се прави това.

В каква структура да пазим тестето карти?

Първият въпрос, който възниква, е в каква структура от данни да съхраняваме тестето карти. Могат да ни хрумнат всякакви идеи, но не всички структури от данни са подходящи. Нека разсъждаваме малко по въпроса. Имаме съвкупност от карти и наредбата на картите в тази структура е от значение. Следователно трябва да използваме структура, която съхранява съвкупност от елементи и запазва наредбата им.

Можем ли да ползваме масив?

Първото, което можем да се сетим, е да използваме "масив". Това е най-простата структура за съхранение на съвкупност от елементи. Масивът може да съхранява съвкупност от елементи, в него елементите имат наредба (първи, втори трети и т.н.) и са достъпни по индекс. Масивът не може да променя първоначално определения му размер.

Подходяща структура ли е масивът? За да си отговорим на този въпрос, трябва да помислим какво трябва да правим с тестето карти, записано в масив и да проверим дали всяка от необходимите ни операции може да се реализира ефективно с масив.

Кои са операциите с тестето карти, които ще ни се наложи да реализираме за нашия алгоритъм? Нека ги изброим:

- Избор на случайна карта. Понеже в масива имаме достъп до елементите по индекс, можем да изберем случайно място в него чрез избор на случайно число k в интервала от 1 до N-1.

- Размяна на карта на позиция k с първата карта (единично разместване). След като сме избрали случайна карта, трябва да я разменим с първата. И тази операция изглежда проста. Можем да направим размяната на три стъпки чрез временна променлива.

- Въвеждане на тестето, обхождане на картите от тестето, отпечатване на тестето – всички тези операции биха могли да ни потрябват, но изглежда тривиално да ги реализираме с масив.

Изглежда, че обикновен масив може да ни свърши работа за съхранение на тесте карти.

Можем ли да ползваме друга структура?

Нормално е да си зададем въпроса дали масив е най-подходящата структура от данни за реализиране на операциите, които нашата програма трябва да извършва върху тестето карти. Изглежда, че всички операции могат лесно да се реализират с масив.

Все пак, нека помислим дали можем да изберем по-подходяща структура от масив. Нека помислим какви са възможностите ни:

- Свързан списък – нямаме директен достъп по номер на елемент и ще ни е трудно да избираме случайна карта от списъка.

- Масив с променлива дължина (List<T>) – изглежда, че притежава всички предимства на масивите и може да реализира всички операции, които ни трябват, по същия начин, както с масив. Печелим малко удобство – в List<T> можем лесно да трием и добавяме, което може да улесни въвеждането на картите и някои други помощни операции.

- Стек / опашка – тестето карти няма поведение на FIFO / LIFO и следователно тези структури не са подходящи.

- Множество (TreeSet<Т> / HashSet<Т>) – в множествата се губи оригиналната наредба на елементите и това е съществена пречка, за да ги използваме.

- Хеш-таблица – структурата "тесте карти" не е от вида ключ-стойност и следователно хеш-таблицата не може да го съхранява и обработва ефективно. Освен това хеш-таблиците не запазват подредбата на елементите си.

Общо взето изчерпахме основните структури от данни, които съхраняват и обработват съвкупности от елементи и стигнахме до извода, че масив или List<T> ще ни свършат работа, а List<T> е по-гъвкав и удобен от обикновения масив. Взимаме решение да ползваме List<T> за съхранението и обработката на тестето карти.

Изборът на структура данни започва с изброяване на ключовите операции, които ще се извършват върху нея. След това се анализират възможните структури, които могат да бъдат използвани и от тях се избира тази, която най-лесно и ефективно реализира тези операции. Понякога се прави компромис между леснота на реализация и ефективност.

Как да пазим другите информационни обекти?

След като решихме първия проблем, а именно как да представяме в паметта тесте от карти, следва да помислим дали има и други обекти, с които боравим, за които следва да помислим как да ги представяме. Като се замислим, освен обектите "карта" и "тесте карти", нашият алгоритъм не използва други информационни обекти.

Възниква въпросът как да представим една карта? Можем да я представим като символен низ, като число или като клас с две полета – лице и боя. Има, разбира се и други варианти, които имат своите предимства и недостатъци.

Преди да навлезем в дълбоки разсъждения кое представяне е най-добро, нека се върнем на условието на задачата. То предполага, че тестето карти ни е дадено (като масив или списък) и трябва да го разместим. Какво точно представлява една карта няма никакво значение за тази задача. Дори няма значение дали разместваме карти за игра, фигури за шах, кашони с домати или някакви други обекти. Имаме наредена последователност от обекти и трябва да я разбъркаме в случаен ред. Фактът, че разбъркваме карти, няма значение за нашата задача и няма нужда да губим време да мислим как точно да представим една карта. Нека просто се спрем на първата идея, която ни хрумва, примерно да си дефинираме клас Card с полета Face и Suit. Дори да изберем друго представяне (примерно число от 1 до 52), това не е съществено. Няма да дискутираме повече този въпрос.

Сортиране на числа – подбор на структурите данни

Нека се върнем на задачата за сортиране на съвкупност от числа по големина и изберем структури от данни и за нея. Нека сме избрали да използваме най-простия алгоритъм, за който сме се сетили: да взимаме докато може най-малкото число, да го отпечатваме и да го изтриваме. Тази идея лесно се разписва на хартия и лесно се убеждаваме, че е коректна.

Каква структура от данни да използваме за съхранение на числата? Отново, за да си отговорим на този въпрос, е необходимо да помислим какви операции трябва да извършваме върху тези числа. Операциите са следните:

- Търсене на най-малка стойност в структурата.

- Изтриване на намерената най-малка стойност от структурата.

Очевидно използването на масив не е разумно, защото не разполагаме с операцията "изтриване". Използването на List<Т> изглежда по-добре, защото и двете операции можем да реализираме сравнително просто и лесно. Структури като стек и опашка няма да ни помогнат, защото нямаме LIFO или FIFO поведение. От хеш-таблица няма особен смисъл, защото в нея няма бърз начин за намиране на най-малка стойност, въпреки че изтриването на елемент би могло да е по-ефективно.

Стигаме до структурите HashSet<Т> и TreeSet<Т>. Множествата имат проблема, че не поддържат възможност за съхранение на еднакви елементи. Въпреки това, нека ги разгледаме. Структурата HashSet<Т> не представлява интерес, защото при нея отново нямаме лесен начин да намерим най-малкия елемент. Обаче структурата TreeSet<Т> изглежда обещаваща. Нека я разгледаме.

Класът TreeSet<Т> по идея държи елементите си в балансирано дърво и поддържа операцията "изваждане на най-малкия елемент". Колко интересно! Хрумва ни нова идея: вкарваме всички елементи в TreeSet<Т> и изкарваме от него итеративно най-малкия елемент докато елементите свършат. Просто, лесно и ефективно. Имаме наготово двете операции, които ни интересуват (търсене на най-малък елемент и изтриването му от структурата).

Докато си представяме конкретната имплементация и се ровим в документацията се сещаме нещо още по-интересно: класът TreeSet<Т> държи вътрешно елементите си подредени по големина. Ами нали това се иска в задачата: да наредим елементите по големина. Следователно, ако ги вкараме в TreeSet<Т> и след това обходим елементите му (чрез неговия итератор), те ще бъдат подредени по големина. Задачата е решена!

Докато се радваме, се сещаме за един забравен проблем: TreeSet<Т> не поддържа еднакви елементи, т.е. ако имаме числото 5 няколко пъти, то ще се появи в множеството само веднъж. В крайна сметка при сортирането ще загубим безвъзвратно някои от елементите.

Естествено е да потърсим решение на този проблем. Ако има начин да пазим колко пъти се среща всеки елемент от множеството, това ще ни реши проблема. Тогава се сещаме за класа SortedDictionary<K,T>. Той съхранява множество ключове, които са подредени по големина и във всеки ключ можем да имаме стойност. В стойността можем да съхраняваме колко пъти се среща даден елемент. Можем да преминем с един цикъл през елементите на масива и за всеки от тях да запишем колко пъти се среща в структура SortedDictionary<K,T>. Изглежда това решава проблема ни и можем да го реализираме, макар и не толкова лесно, колкото с List<T> или с TreeSet<T>.

Ако прочетем внимателно документацията за SortedDictionary<K,T>, ще се убедим, че този клас вътрешно използва червено-черно дърво и може някой ден да се досетим, че неусетно чрез разсъждения сме достигнали до добре известния алгоритъм "сортиране чрез дърво" (http://en.wikipedia. org/wiki/Binary_tree_sort).

Видяхте до какви идеи ви довеждат разсъжденията за избор на подходящи структури от данни за имплементация на вашите идеи. Тръгвате от един алгоритъм и неусетно измисляте нов, по-добър. Това е нормално да се случи в процеса на обмисляне на алгоритъма и е добре да се случи в този момент, а не едва когато сте написали вече 300 реда код, който ще се наложи да преправяте. Това е още едно доказателство, че трябва да помислите за структурите от данни преди да започнете да пишете кода.

Помислете за ефективността!

За пореден път изглежда, че най-сетне сме готови да хванем клавиатурата и да напишем кода на програмата. И за пореден път е добре да не избързваме. Причината е, че не сме помислили за нещо много важно: ефективност и бързодействие.

За ефективността трябва да се помисли още преди да се напише първия ред програмен код! Иначе рискувате да загубите много време за реализация на идея, която не върши работа!

Да се върнем на задачата за разбъркване на тесте карти. Имаме идея за решаване на задачата (измислили сме алгоритъм). Идеята изглежда коректна (пробвали сме я с примери). Идеята изглежда, че може да се реализира (ще ползваме List<Card> за тестето карти и клас Card за представянето на една карта). Обаче, нека помислим колко карти ще разбъркваме и дали избраната идея, реализирана с избраните структури от данни, ще работи достатъчно бързо.

Как оценяваме бързината на даден алгоритъм?

Бърз ли е нашият алгоритъм? За да си отговорим на този въпрос, нека помислим колко операции извършва той за разбъркването на стандартно тесте от 52 карти.

За 52 карти нашият алгоритъм прави 52 единични размествания, нали така? Колко елементарни операции отнема едно единично разместване? Операциите са 4: избор на случайна карта; запазване на първата карта във временна променлива; запис на случайната карта на мястото на първата; запис на първата карта (от временната променлива) на мястото, където е била случайната карта. Колко операции прави общо нашият алгоритъм за 52 карти? Операциите са приблизително 52 * 4 = 208.

Много операции ли са 208? Замислете се колко време отнема да завъртите цикъл от 1 до 208. Много ли е? Пробвайте! Ще се убедите, че цикъл от 1 до 1 000 000 при съвременните компютри минава неусетно бързо, а цикъл до 208 отнема смешно малко време. Следователно нямаме проблем с производителността. Нашия алгоритъм ще работи супер бързо за 52 карти.

Въпреки, че в реалността рядко играем с повече от 1 или 2 тестета карти, нека се замислим колко време ще отнеме да разбъркаме голям брой карти, да кажем 50 000? Ще имаме 50 000 единични размествания по 4 операции за всяко от тях или общо 200 000 операции, които ще се изпълнят на момента, без да се усети каквото и да е забавяне.

Ефективността е въпрос на компромис

В крайна сметка правим извода, че алгоритъмът, който сме измислили е ефективен и ще работи добре дори при голям брой карти. Имахме късмет. Обикновено нещата не са толкова прости и трябва да се прави компромис между бързодействие на алгоритъма и усилията, които влагаме, за да го измислим и имплементираме. Например ако сортираме числа, можем да го направим за 5 минути с първия алгоритъм, за който се сетим, но можем да го направим и много по-ефективно, за което ще употребим много повече време (да търсим и да четем из дебелите книги и в Интернет). В този момент трябва да се прецени струва ли си усилията. Ако ще сортираме 20 числа, няма значение как ще го направим, все ще е бързо, дори с най-глупавия алгоритъм. Ако сортираме 20 000 числа вече алгоритъмът има значение, а ако сортираме 20 000 000 числа, задачата придобива съвсем друг характер. Времето, необходимо да реализираме ефективно сортиране на 20 000 000 числа е далеч повече от времето да сортираме 20 числа, така че трябва да помислим струва ли си.

Ефективността е въпрос на компромис – понякога не си струва да усложняваме алгоритъма и да влагаме време и усилия, за да го направим по-бърз, а друг път бързината е ключово изискване и трябва да й обърнем сериозно внимание.

Сортиране на числа – оценяване на ефективността

Видяхме, че подходът към въпроса с ефективността силно зависи от изискванията за бързодействие. Нека се върнем сега на задачата за сортирането на числа, защото искаме да покажем, че ефективността е пряко свързана с избора на структури от данни.

Да се върнем отново на въпроса за избор на структура от данни за съхранение на числата, които трябва да сортираме по големина в нарастващ ред. Дали да изберем List<T> или SortedDictionary<K,T>? Не е ли по-добре да ползваме някаква проста структура, която добре познаваме, отколкото някоя сложна, която изглежда, че ще ни свърши работата малко по-добре. Вие познавате ли добре червено-черните дървета (вътрешната имплементация на SortedDictionary<K,T>)? С какво са по-добри от List<T>? Всъщност може да се окаже, че няма нужда да си отговаряте на този въпрос.

Ако трябва да сортирате 20 числа, има ли значение как ще го направите? Взимате първия алгоритъм, за който се сетите, взимате първата структура от данни, която изглежда, че ще ви свърши работа и готово. Няма никакво значение колко са бързи избраните алгоритми и структури от данни, защото числата са изключително малко.

Ако, обаче трябва да сортирате 300 000 числа, нещата са съвсем различни. Тогава ще трябва внимателно да проучите как работи класът SortedDictionary<K,T> и колко бързо става добавянето и търсенето в него, след което ще трябва да оцените ориентировъчно колко операции ще са нужни за 300 000 добавяния на число и след това колко още операции ще отнеме обхождането. Ще трябва да прочетете документацията, където пише, че добавянето отнема средно log₂(N) стъпки, където N е броят елементи в структурата. Чрез дълги и мъчителни сметки (за които ви трябват допълнителни умения) може да оцените грубо, че ще са необходими около 5-6 милиона стъпки за цялото сортиране, което е приемливо бързо.

По аналогичен път, можете да се убедите, че търсенето и изтриването в List<Т> с N елемента отнема N стъпки и следователно за 300 000 елемента ще ни трябват приблизително 2 * 300 000 * 300 000 стъпки! Всъщност това число е силно закръглено нагоре, защото в началото нямате 300 000 числа, а само 1, но грубата оценка е пак приблизително вярна. Получава се екстремално голям брой стъпки и простичкият алгоритъм няма да работи за такъв голям брой елементи (програмата мъчително ще "увисне").

Отново стигаме до въпроса с компромиса между сложния и простия алгоритъм. Единият е по-лесен за имплементиране, но е по-бавен. Другият е по-ефективен, но е по-сложен за имплементиране и изисква да четем документация и дебели книги, за да разберем колко бързо ще работи. Въпрос на компромис.

Естествено, в този момент можем да се сетим за някоя от другите идеи за сортиране на числа, които ни бяха хрумнали в началото, например идеята да разделим масива на две части, да ги сортираме поотделно (чрез рекурсивно извикване) и да ги слеем в един общ масив. Ако помислим, ще се убедим, че този алгоритъм може да се реализира ефективно с обикновен динамичен масив (List<T>) и че той прави в най-лошия случай n*log(n) стъпки при n елемента, т.е. ще работи добре за 300 000 числа. Няма да навлизаме повече в детайли, тъй като всеки може да прочете за MergeSort в Уикипедия (http://en.wikipedia.org/wiki/Merge_sort).

Имплементирайте алгоритъма си!

Най-сетне стигаме до имплементация на нашата идея за решаване на задачата. Вече имаме работеща и проверена идея, подбрали сме подходящи структури от данни и остава да напишем кода. Ако не сме направили това, трябва да се върнем на предните стъпки.

Ако нямате измислена идея за решение, не започвайте да пишете код! Какво ще напишете, като нямате идея за решаване на задачата? Все едно да отидете на гарата и да се качите на някой влак, без да сте решили за къде ще пътувате.

Типично действие за начинаещите програмисти: като видят задачата да почнат веднага да пишат и след като загубят няколко часа в писане на необмислени идеи (които им хрумват докато пишат), да се сетят да помислят малко. Това е грешно и целта на всички препоръки до момента е да ви предпази от такъв лекомислен и крайно неефективен подход.

Ако не сте проверили дали идеите ви са верни, не почвайте да пишете код! Трябва ли да напишете 300 реда код и тогава да откриете, че идеята ви е тотално сбъркана и трябва да почнете отначало?

Писането на кода при вече измислена и проверена идея изглежда просто и лесно, но и за него се изискват специфични умения и най-вече опит. Колкото повече програмен код сте писали, толкова по-бързо, ефективно и без грешки се научавате да пишете. С много практика ще постигнете лекота при писането и постепенно с времето ще се научите да пишете не само бързо, но и качествено. За качеството на кода можете да прочетете в главата "Качествен програмен код", така че, нека се фокусираме върху правилния процес за написването на кода.

Считаме, че би трябвало вече да сте овладели начални техники, свързани с писането на програмен код: как да работите със средата за разработка (Visual Studio), как да ползвате компилатора, как да разчитате грешките, които той ви дава, как да ползвате подсказките (auto complete), как да генерирате методи, конструктори и свойства, как да поправяте грешки и как да изпълнявате и дебъгвате програмата. Затова съветите, които следват, са свързани не със самото писане на програмни редове код, а с цялостния подход при имплементиране на алгоритми.

Пишете стъпка по стъпка!

Случвало ли ви се е да напишете 200-300 реда код, без да опитате поне веднъж да компилирате и да тествате дали нещо работи? Не правете така! Не пишете много код на един път, а вместо това пишете стъпка по стъпка.

Как да пишем стъпка по стъпка? Това зависи от конкретната задача и от начина, по който сме я разделили на подзадачи. Например ако задачата се състои от 3 независими части, напишете първо едната част, компилирайте я, тествайте я с някакви примерни входни данни и след като се убедите, че работи, преминете към следващите части. След това напишете втората част, компилирайте я, тествайте я и когато и тя е готова, преминете към третата част. Когато сте написали и последната част и сте се убедили, че работи правилно, преминете към обстойно тестване на цялата програма.

Защо да пишем на части? Когато пишете на части, стъпка по стъпка, вие намалявате обема код, над който се концентрирате във всеки един момент. По този начин намалявате сложността на проблема, като го разглеждате на части. Спомнете си: големият и сложен проблем винаги може да се раздели на няколко по-малки и по-прости проблема, за които лесно ще намерите решение.

Когато напишем голямо количество код, без да сме опитали да компилираме поне веднъж, се натрупват голямо количество грешки, които могат да се избегнат чрез просто компилиране. Съвременните среди за програмиране (като Visual Studio) се опитват да откриват синтактичните грешки автоматично още докато пишете кода. Ползвайте тази възможност и отстранявайте грешките възможно най-рано. Ранното отстраняване на проблеми отнема по-малко време и нерви. Късното отстраняване на грешки и проблеми може да коства много усилия, дори понякога и цялостно пренаписване на програмата.

Когато напишете голямо количество код, без да го тествате и след това решите наведнъж да го изпробвате за някакви примерни входни данни, обикновено се натъквате на множество проблеми, изсипващи се един след друг, като колкото повече е кодът, толкова по-трудно е те да бъдат оправени. Проблемите могат да са причинени от необмислено използване на неподходящи структури от данни, грешен алгоритъм, необмислено структуриране на кода, грешно условие в if-конструкция, грешно организиран цикъл, излизане извън граници на масив и много, много други проблеми, които е можело да бъдат отстранени много по-рано и с много по-малко усилия. Затова не чакайте последния момент. Отстранявайте грешките възможно най-рано!

Пишете програмата на части, а не наведнъж! Напишете някаква логически отделена част, компилирайте я, отстранете грешките, тествайте я и когато тя работи, преминете към следващата част.

Писане стъпка по стъпка – пример

За да илюстрираме на практика как можем да пишем стъпка по стъпка, нека се захванем с имплементация на алгоритъма за разбъркване на карти, който измислихме следвайки препоръките за решаване на алгоритмични задачи, описани по-горе.

Стъпка 1 – Дефиниране на клас "карта"

Тъй като трябва да разбъркваме карти, можем да започнем с дефиницията на класа "карта". Ако нямаме идея как да представяме една карта, няма да имаме и как да представяме тесте карти, следователно няма да има и как да дефинираме метода за разбъркване на картите. Вече споменахме, че представянето на картите не е от значение за поставената задача, така че всякакво представяне би ни свършило работа.

Ще дефинираме клас "карта" с полета лице и боя. Ще използваме символен низ за лицето (с възможни стойности "2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K" или "А") и изброен тип за боята (с възможни стойности "спатия", "каро", "купа" и "пика"). Класът Card би могъл да изглежда по следния начин:

Card.cs

class Card

{

public string Face { get; set; }

public Suit Suit { get; set; }

public override string ToString()

{

String card = "(" + this.Face + " " + this.Suit +")";

return card;

}

enum Suit

{

CLUB, DIAMOND, HEART, SPADE

}

За удобство дефинирахме и метод ToString() в класа Card, с който можем по-лесно да отпечатваме дадена карта на конзолата. За боите дефинирахме изброен тип Suit.

Изпробване на класа "карта"

Някои от вас биха продължили да пишат напред, но следвайки принципа "програмиране стъпка по стъпка", трябва първо да тестваме дали класът Card се компилира и работи правилно. За целта можем да си направим малка програмка, в която създаваме една карта и я отпечатваме:

static void Main()

{

Card card = new Card() { Face="A", Suit=Suit.CLUB };

Console.WriteLine(card);

}

Стартираме програмката и проверяваме дали картата се е отпечатала коректно. Резултатът е следният:

(A CLUB)

Стъпка 2 – Създаване и отпечатване на тесте карти

Нека преди да преминем към същината на задачата (разбъркване на тесте карти в случаен ред) се опитаме да създадем цяло тесте от 52 карти и да го отпечатаме. Така ще се убедим, че входът на метода за разбъркване на карти е коректен. Според направения анализ на структурите данни, трябва да използваме List<Card>, за да представяме тестето. Нека създадем тесте от 5 карти и да го отпечатаме:

CardsShuffle.cs

class CardsShuffle

{

static void Main()

{

List<Card> cards = new List<Card>();

cards.Add(new Card() { Face = "7", Suit = Suit.HEART });

cards.Add(new Card() { Face = "A", Suit = Suit.SPADE });

cards.Add(new Card() { Face = "10", Suit = Suit.DIAMOND });

cards.Add(new Card() { Face = "2", Suit = Suit.CLUB });

cards.Add(new Card() { Face = "6", Suit = Suit.DIAMOND }); cards.Add(new Card() { Face = "J", Suit = Suit.CLUB });

PrintCards(cards);

}

static void PrintCards(List<Card> cards)

{

foreach (Card card in cards)

{

Console.Write(card);

}

Console.WriteLine();

}

Отпечатване на тестето – тестване на кода

Преди да продължим напред, стартираме програмата и проверяваме дали сме получили очаквания резултат. Изглежда, че няма грешки и резултатът е коректен:

(7 HEART)(A SPADE)(10 DIAMOND)(2 CLUB)(6 DIAMOND)(J CLUB)

Стъпка 3 – Единично разместване

Нека реализираме поредната стъпка от решаването на задачата – подзадачата за единично разместване. Когато имаме логически отделена част от програмата е добра идея да я реализираме като отделен метод. Да помислим какво приема методът като вход и какво връща като изход. Като вход би трябвало да приема тесте карти (List<Card>). В резултат от работата си методът би трябвало да промени подадения като вход List<Card>. Методът няма нужда да връща нищо, защото не създава нов List<Card> за резултата, а оперира върху вече създадения и подаден като параметър списък.

Какво име да дадем на метода? Според препоръките за работа с методи трябва да дадем "описателно" име – такова, което описва с 1-2 думи какво прави метода. Подходящо за случая е името PerformSingleExchange. Името ясно описва какво прави методът: извършва единично разместване.

Нека първо дефинираме метода, а след това напишем тялото му. Това е добра практика, тъй като преди да започнем да реализираме даден метод трябва да сме наясно какво прави той, какви параметри приема, какъв резултат връща и как се казва. Ето как изглежда дефиницията на метода:

static void PerformSingleExchange(List<Card> cards)

{

// TODO: Implement the method body

}

Следва да напишем тялото на метода. Първо трябва да си припомним алгоритъма, а той беше следният: избираме случайно число k в интервала от 1 до дължината на масива минус 1 и разменяме първия елемент на масива с k-тия елемент. Изглежда просто, но как в C# получаваме случайно число в даден интервал?

Търсете в Google!

Когато се натъкнем на често срещан проблем, за който нямаме решение, но знаем, че много хора са се сблъсквали с него, най-лесният начин да се справим е да потърсим информация в Google. Трябва да формулираме по подходящ начин нашето търсене. В случая търсим примерен C# код, който връща случайно число в даден интервал. Можем да пробваме следното търсене:

C# random number example

Сред първите резултати излиза C# програмка, която използва класа System.Random, за да генерира случайно число. Вече имаме посока, в която да търсим решение – знаем, че в .NET Framework има стандартен клас Random, който служи за генериране на случайни числа.

След това можем да се опитаме да налучкаме как се ползва този клас (често пъти това отнема по-малко време, отколкото да четем документацията). Опитваме да намерим подходящ статичен метод за случайно число, но се оказва, че такъв няма. Създаваме инстанция и търсим метод, който да ни върне число в даден диапазон. Имаме късмет, методът Next(minValue, maxValue) е връща каквото ни трябва.

Да опитаме да напишем кода на целия метод. Получава се нещо такова:

static void PerformSingleExchange(List<Card> cards)

{

Random rand = new Random();

int randomIndex = rand.Next(1, cards.Count - 1);

Card firstCard = cards[1];

Card randomCard = cards[randomIndex];

cards[1] = randomCard;

cards[randomIndex] = firstCard;

}

Единично разместване – тестване на кода

Следва тестване на кода. Преди да продължим нататък, трябва да се убедим, че единичното разместване работи коректно. Нали не искаме да открием евентуален проблем, едва когато тестваме метода за разбъркване на цялото тесте? Искаме, ако има проблем, да го открием веднага, а ако няма проблем, да се убедим в това, за да продължим уверено напред. Действаме стъпка по стъпка – преди да започнем следващата стъпка, проверяваме дали текущата е реализирана коректно. За целта си правим малка тестова програмка, да кажем с три карти (2♣, 3♥ и 4♠):

static void Main()

{

List<Card> cards = new List<Card>();

cards.Add(new Card() { Face = "2", Suit = Suit.CLUB });

cards.Add(new Card() { Face = "3", Suit = Suit.HEART });

cards.Add(new Card() { Face = "4", Suit = Suit.SPADE });

PerformSingleExchange(cards);

PrintCards(cards);

}

Нека изпълним няколко пъти единичното разместване с нашите 3 карти. Очакваме първата карта (двойката) да бъде разменена с някоя от другите две карти (с тройката или с четворката). Ако изпълним програмата много пъти, би следвало около половината от получените резултати да съдържат (3♥, 2♣, 4♠), а останалите – (4♠, 3♥, 2♣), нали така? Да видим какво ще получим. Стартираме програмата и получаваме следния резултат:

(2 CLUB)(3 HEART)(4 SPADE)

Ама как така? Какво стана? Да не сме забравили да изпълним единичното разместване преди да отпечатам картите? Има нещо гнило тук. Изглежда програмата не е направила нито едно разместване на нито една карта. Как стана тая работа?

Единично разместване – поправяне на грешките

Очевидно имаме грешка. Да сложим точка на прекъсване и да проследим какво се случва чрез дебъгера на Visual Studio:

Видно е, че при първо стартиране случайната позиция се случва да има стойност 1. Това е допустимо, така че продължаваме напред. Като погледнем кода малко по-надолу, виждаме, че разменяме случайния елемент с индекс 1 с елемента на позиция 1, т.е. със себе си. Очевидно нещо бъркаме. Сещаме се, че индексирането в List<Т> започва от 0, а не от 1, т.е. първият елемент е на позиция 0. Веднага поправяме кода:

static void PerformSingleExchange(List<Card> cards)

{

Random rand = new Random();

int randomIndex = rand.Next(1, cards.Count - 1);

Card firstCard = cards[0];

Card randomCard = cards[randomIndex];

cards[0] = randomCard;

cards[randomIndex] = firstCard;

}

Стартираме програмата няколко пъти и получаваме пак странен резултат:

(3 HEART)(2 CLUB)(4 SPADE)

Изглежда случайното число не е съвсем случайно. Какво има пък сега? Не бързайте да обвинявате .NET Framework, CLR, Visual Studio и всички други заподозрени виновници! Може би грешката е отново при нас. Да разгледаме извикването на метода Next(…). Понеже cards.Count е 3, то винаги викаме NextInt(1, 2) и очакваме да ни върне число между 1 и 2. Звучи коректно, обаче ако прочетем какво пише в документацията за метода Next(…), ще забележим, че вторият параметър трябва да е с единица по-голям от максималното число, което искаме да получим.

Сбъркали сме с единица диапазона на случайната карта, която избираме. Поправяме кода и за пореден път тестваме дали работи. След втората поправка получаваме следната реализация на метода за единично разместване:

static void PerformSingleExchange(List<Card> cards)

{

Random rand = new Random();

int randomIndex = rand.Next(1, cards.Count);

Card firstCard = cards[0];

Card randomCard = cards[randomIndex];

cards[0] = randomCard;

cards[randomIndex] = firstCard;

}

Ето какво би могло да се получи след няколко изпълнения на горния метод върху нашата поредица от три карти:

(3 HEART)(2 CLUB)(4 SPADE)

(4 SPADE)(3 HEART)(2 CLUB)

(3 HEART)(2 CLUB)(4 SPADE)

(4 SPADE)(3 HEART)(2 CLUB)

(3 HEART)(2 CLUB)(4 SPADE)

Вижда се, че след достатъчно изпълнения на метода на мястото на първата карта отива всяка от следващите две карти, т.е. наистина имаме случайно разместване и всяка карта освен първата има еднакъв шанс да бъде избрана като случайна. Най-накрая сме готови с метода за единично разместване. Хубаво беше, че открихме двете грешки сега, а не по-късно, когато очакваме цялата програма да заработи.

Стъпка 4 – Разместване на тестето

Последната стъпка е проста: прилагаме N пъти единичното разместване:

static void ShuffleCards(List<Card> cards)

{

for (int i = 1; i <= cards.Count; i++)

{

PerformSingleExchange(cards);

}

Ето как изглежда цялата програма:

CardsShuffle.cs

using System;

using System.Collections.Generic;

class CardsShuffle

{

static void Main()

{

List<Card> cards = new List<Card>();

cards.Add(new Card() { Face = "2", Suit = Suit.CLUB });

cards.Add(new Card() { Face = "6", Suit = Suit.DIAMOND });

cards.Add(new Card() { Face = "7", Suit = Suit.HEART });

cards.Add(new Card() { Face = "A", Suit = Suit.SPADE });

cards.Add(new Card() { Face = "J", Suit = Suit.CLUB });

cards.Add(new Card() { Face = "10", Suit = Suit.DIAMOND });

Console.Write("Initial deck: ");

PrintCards(cards);

ShuffleCards(cards);

Console.Write("After shuffle: ");

PrintCards(cards);

}

static void PerformSingleExchange(List<Card> cards)

{

Random rand = new Random();

int randomIndex = rand.Next(1, cards.Count);

Card firstCard = cards[0];

Card randomCard = cards[randomIndex];

cards[0] = randomCard;

cards[randomIndex] = firstCard;

}

static void ShuffleCards(List<Card> cards)

{

for (int i = 1; i <= cards.Count; i++)

{

PerformSingleExchange(cards);

}

static void PrintCards(List<Card> cards)

{

foreach (Card card in cards)

{

Console.Write(card);

}

Console.WriteLine();

}

Разместване на тестето – тестване

Остава да пробваме дали целият алгоритъм работи. Ето какво се получава след изпълнение на програмата:

Initial deck: (7 HEART)(A SPADE)(10 DIAMOND)(2 CLUB)(6 DIAMOND)(J CLUB)

After shuffle: (7 HEART)(A SPADE)(10 DIAMOND)(2 CLUB)(6 DIAMOND)(J CLUB)

Очевидно отново имаме проблем: тестето карти след разбъркването е в началния си вид. Дали не сме забравили да извикаме метода за разбъркване ShuffleCards? Поглеждаме внимателно кода: всичко изглежда наред. Решаваме да сложим точка на прекъсване (breakpoint) веднага след извикването на метода PerformSingleExchange(…) в тялото на цикъла за разбъркване на картите. Стартираме програмата в режим на постъпково изпълнение (дебъгване) с натискане на [F5]. След първото спиране на дебъгера в точката на прекъсване всичко е наред – първата карта е разменена със случайна карта, точно както трябва да стане. След второто спиране на дебъгера отново всичко е наред – случайна карта е разменена с първата. Странно, изглежда, че всичко работи както трябва:

Защо тогава накрая резултатът е грешен? Решаваме да сложим точка на прекъсване и в края на метода ShuffleCards(…). Дебъгерът спира и на него и отново резултатът в момента на прекъсване на програмата е какъвто трябва да бъде – картите са случайно разбъркани. Продължаваме да дебъгваме и стигаме до отпечатването на тестето карти. Преминаваме и през него и на конзолата се отпечатва разбърканото в случаен ред тесте карти. Странно: изглежда всичко работи. Какъв е проблемът?

Стартираме програмата без да я дебъгваме с [Ctrl+F5]. Резултатът е грешен – картите не са разбъркани. Стартираме програмата отново в режим на дебъгване с [F5]. Дебъгерът отново спира на точките на прекъсване и отново програмата се държи коректно. Изглежда, че когато дебъгваме програмата, тя работи коректно, а когато я стартираме без дебъгер, резултатът е грешен. Странна работа!

Решаваме да добавим един ред, който отпечатва тестето карти след всяко единично разместване:

static void ShuffleCards(List<Card> cards)

{

for (int i = 1; i <= cards.Count; i++)

{

PerformSingleExchange(cards);

PrintCards(cards);

}

Стартираме програмата през дебъгера (с [F5]), проследяваме постъпково нейното изпълнение и установяваме, че работи правилно:

Initial deck: (7 HEART)(A SPADE)(10 DIAMOND)(2 CLUB)(6 DIAMOND)(J CLUB)

(A SPADE)(7 HEART)(10 DIAMOND)(2 CLUB)(6 DIAMOND)(J CLUB)

(6 DIAMOND)(7 HEART)(10 DIAMOND)(2 CLUB)(A SPADE)(J CLUB)

(J CLUB)(7 HEART)(10 DIAMOND)(2 CLUB)(A SPADE)(6 DIAMOND)

(2 CLUB)(7 HEART)(10 DIAMOND)(J CLUB)(A SPADE)(6 DIAMOND)

(A SPADE)(7 HEART)(10 DIAMOND)(J CLUB)(2 CLUB)(6 DIAMOND)

(10 DIAMOND)(7 HEART)(A SPADE)(J CLUB)(2 CLUB)(6 DIAMOND)

After shuffle: (10 DIAMOND)(7 HEART)(A SPADE)(J CLUB)(2 CLUB)(6 DIAMOND)

Стартираме отново програмата без дебъгера (с [Ctrl+F5]) и получаваме отново грешния резултат, който се опитваме да разберем как и защо се получава:

Initial deck: (7 HEART)(A SPADE)(10 DIAMOND)(2 CLUB)(6 DIAMOND)(J CLUB)

(6 DIAMOND)(A SPADE)(10 DIAMOND)(2 CLUB)(7 HEART)(J CLUB)

(7 HEART)(A SPADE)(10 DIAMOND)(2 CLUB)(6 DIAMOND)(J CLUB)

(6 DIAMOND)(A SPADE)(10 DIAMOND)(2 CLUB)(7 HEART)(J CLUB)

(7 HEART)(A SPADE)(10 DIAMOND)(2 CLUB)(6 DIAMOND)(J CLUB)

(6 DIAMOND)(A SPADE)(10 DIAMOND)(2 CLUB)(7 HEART)(J CLUB)

(7 HEART)(A SPADE)(10 DIAMOND)(2 CLUB)(6 DIAMOND)(J CLUB)

After shuffle: (7 HEART)(A SPADE)(10 DIAMOND)(2 CLUB)(6 DIAMOND)(J CLUB)

Непосредствено се вижда, че на всяка стъпка, в която се очаква да се извърши единично разместваме, реално се разместват едни и същи карти: 7♥ и 6♦. Има само един начин това да се случи – ако всеки път случайното число, което се пада, е едно и също. Изводът е, че нещо не е наред с генерирането на случайни числа. Веднага ни хрумва да погледнем документацията на класа System.Random(). В MSDN можем да прочетем, че при създаване на нова инстанция на генератора на псевдослучайни числа с конструктора Random() генераторът се инициализира с начална стойност, извлечена спрямо текущото системно време. В документацията пише още, че ако създадем две инстанции на класа Random в много кратък интервал от време, те най-вероятно ще генерират еднакви числа. Оказва се, че проблемът е в неправилното използване на класа Random.

Имайки предвид описания проблем, бихме могли да коригираме проблема като създадем инстанция на класа Random само веднъж при стартиране на програмата. След това при нужда от случайно число ще използваме вече създадения генератор на псевдослучайни числа. Ето как изглежда корекцията в кода:

class CardsShuffle

{

...

static Random rand = new Random();

static void PerformSingleExchange(List<Card> cards)

{

int randomIndex = rand.Next(1, cards.Count);

Card firstCard = cards[0];

Card randomCard = cards[randomIndex];

cards[0] = randomCard;

cards[randomIndex] = firstCard;

}

...

}

Изглежда програмата най-сетне работи коректно – при всяко стартиране извежда различна подредба на картите:

Initial deck: (7 HEART)(A SPADE)(10 DIAMOND)(2 CLUB)(6 DIAMOND)(J CLUB)

After shuffle: (2 CLUB)(A SPADE)(J CLUB)(10 DIAMOND)(7 HEART)(6 DIAMOND)

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

Initial deck: (7 HEART)(A SPADE)(10 DIAMOND)(2 CLUB)(6 DIAMOND)(J CLUB)

After shuffle: (6 DIAMOND)(10 DIAMOND)(J CLUB)(2 CLUB)(A SPADE)(7 HEART)

Пробваме още няколко примера и виждаме, че работи правилно и за тях. Едва сега можем да кажем, че имаме коректна имплементация на алгоритъма, който измислихме в началото и тествахме на хартия.

Стъпка 5 – Вход от конзолата

Остава да реализираме вход от конзолата, за да дадем възможност на потребителя да въведе картите, които да бъдат разбъркани. Забележете, че оставихме за накрая тази стъпка. Защо? Ами много просто: нали не искаме всеки път при стартиране на програмата да въвеждаме 6 карти само за да тестваме дали някаква малка част от кода работи коректно (преди цялата програма да е написана докрай)? Като кодираме твърдо входните данни си спестяваме много време за въвеждането им по време на разработка.

Ако задачата изисква вход от конзолата, реализирайте го задължително най-накрая, след като всичко останало работи. Докато пишете програмата, тествайте с твърдо кодирани примерни данни, за да не въвеждате входа всеки път. Така ще спестите много време и нерви.

Въвеждането на входните данни е хамалска задача, която всеки може да реализира. Трябва само да се помисли в какъв формат се въвеждат картите, дали се въвеждат една по една или всички на един път и дали лицето и боята се задават наведнъж или поотделно. В това няма нищо сложно, така че ще го оставим за упражнение на читателите.

Сортиране на числа – стъпка по стъпка

До момента ви показахме колко важно е да пишете програмата си стъпка по стъпка и преди да преминете на следващата стъпка да се убедите, че предходната е реализирана качествено и работи коректно.

Да разгледаме и задачата със сортиране на числа в нарастващ ред. При нея нещата не стоят по-различно. Отново правилният подход към имплементацията изисква да работим на стъпки. Нека видим накратко кои са стъпките. Няма да пишем кода, но ще набележим основните моменти, през които трябва да преминем. Да предположим, че реализираме идеята за сортиране чрез List<int>, в който последователно намираме най-малкото число, отпечатваме го и го изтриваме от списъка с числа. Ето какви биха могли да са стъпките:

Стъпка 1. Измисляме подходящ пример, с който ще си тестваме, например числата 7, 2, 4, 1, 8, 2. Създаваме List<int> и го запълваме с числата от нашия пример. Реализираме отпечатване на числата.

Стартираме програмата и тестваме.

Стъпка 2. Реализираме метод, който намира най-малкото число в масива и връща позицията му.

Тестваме метода за търсене на най-малко число. Пробваме различни поредици от числа, за да се убедим, че търсенето работи коректно (слагаме най-малкия елемент в началото, в края, в средата; пробваме и когато най-малкия елемент се повтаря няколко пъти).

Стъпка 3. Реализираме метод, който намира най-малкото число, отпечатва го и го изтрива.

Тестваме с нашия пример дали методът работи коректно. Пробваме и други примери.

Стъпка 4. Реализираме метода, който сортира числата. Той изпълнява предходния метод N пъти (където N е броят на числата).

Задължително тестваме дали всичко работи както трябва.

Стъпка 5. Ако е необходим вход от конзолата, реализираме го най-накрая, когато всичко е тествано и работи.

Виждате, че подходът с разбиването на стъпки е приложим при всякакви задачи. Просто трябва да съобразим кои са нашите елементарни стъпки при имплементацията и да ги изпълняваме една след друга, като не забравяме да тестваме всяко парче код възможно най-рано. След всяка стъпка е препоръчително да стартираме програмата, за да се убедим, че до този момент всичко работи правилно. Така ще откриваме евентуални проблеми още при възникването им и ще ги отстраняваме бързо и лесно, а не когато сме написали стотици редове код.

Тествайте решението си!

Това звучи ли ви познато: "Аз съм готов с първа задача. Веднага трябва да започна следващата."? На всеки му е хрумвала такава мисъл, когато е бил на изпит. В програмирането обаче, тази мисъл означава следното:

1. Аз съм разбрал добре условието на задачата.

2. Аз съм измислил алгоритъм за решаването на задачата.

3. Аз съм тествал на лист хартия моя алгоритъм и съм се уверил, че е правилен.

4. Аз съм помислил за структурите от данни и за ефективността на моя алгоритъм.

5. Аз съм написал програма, която реализира коректно моя алгоритъм.

6. Аз съм тествал обстойно моята програма с подходящи примери, за да се уверя, че работи коректно, дори в необичайни ситуации.

Неопитните програмисти почти винаги пропускат последната точка. Те смятат, че тестването не е тяхна задача, което е най-голямата им грешка. Все едно да смятаме, че Майкрософт не са длъжни да тестват Windows и могат да оставят той да "гърми" при всяко второ натискане на мишката.

Тестването е неразделна част от програмирането! Да пишеш код, без да го тестваш, е като да пишеш на клавиатурата без да виждаш екрана на компютъра – мислиш си, че пишеш правилно, но най-вероятно правиш много грешки.

Опитните програмисти знаят, че ако напишат код и той не е тестван, това означава, че той още не е завършен. В повечето софтуерни фирми е недопустимо да се предаде код, който не е тестван.

В софтуерната индустрия дори е възприета концепцията за unit testing – автоматизирано тестване на отделните единици от кода (методи, класове и цели модули). Unit testing означава за всяка програма да пишем и още една програма, която я тества дали работи коректно. В някои фирми дори първо се измислят тестовите сценарии, пишат се тестовете за програмата и най-накрая се пише самата програма. Темата за unit testing е много сериозна и обемна, но с нея ще се запознаете по-късно, когато навлезете в дълбините на професията "софтуерен инженер". Засега, нека се фокусираме върху ръчното тестване, което всеки един програмист може да извърши, за да се убеди, че неговата програма работи коректно.

Как да тестваме?

Една програма е коректна, ако работи коректно за всеки възможен валиден набор от входни данни. Тестването е процес, който цели да установи наличие на дефекти в програмата, ако има такива. То не може да установи със сигурност дали една програма е коректна, но може да провери с голяма степен на увереност дали в програмата има дефекти, които причиняват некоректни резултати или други проблеми.

За съжаление всички възможни набори входни данни за една програма обикновено са неизброимо много и не може да се тества всеки от тях. Затова в практиката на софтуерното тестване се подготвят и изпълняват такива набори от входни данни (тестове), които целят да обхванат максимално пълно всички различни ситуации (случаи на употреба), които възникват при изпълнение на програмата. Този набор има за цел с минимални усилия (т. е. с минимален брой и максимална простота на тестовете) да провери всички основни случаи на употреба. Ако при тестването по този начин не бъдат открити дефекти, това не доказва, че програмата е 100% коректна, но намалява в много голяма степен вероятността на по-късен етап да се наблюдават дефекти и други проблеми.

Тестването може да установи само наличие на дефекти. То не може да докаже, че дадена програма е коректна! Програмите, които са тествани старателно имат много по-малко дефекти, отколкото програмите, които изобщо не са тествани или не са тествани качествено.

Тестването е добре да започва от един пример, с който обхващаме типичния случай в нашата задача. Той най-често е същият пример, който сме тествали на хартия и за който очакваме нашият алгоритъм да работи коректно.

След написване на кода обикновено следва отстраняване на поредица от дребни грешки и най-накрая нашият пример тръгва. След това е нормално да тестваме програмата с по-голям и по-сложен пример, за да видим как се държи тя в по-сложни ситуации. Следва тестване на граничните случаи и тестване за бързодействие. В зависимост от сложността на конкретната задача могат да се изпълнят от един-два до няколко десетки теста, за да се покрият всички основни случаи на употреба.

При сложен софтуер, например продуктът Microsoft Word броят на тестовете би могъл да бъде няколко десетки, дори няколко стотици хиляди. Ако някоя функция на програмата не е старателно тествана, не може да се твърди, че е реализирана коректно и че работи. Тестването при разработката на софтуер е не по-малко важно от писането на кода. В сериозните софтуерни корпорации на един програмист се пада поне един тестер. Например в Microsoft на един програмист, който пише код (software engineer) се назначават средно по двама души, които тестват кода (software quality assurance engineers). Тези разработчици също са програмисти, но не пишат основния софтуер, а пишат тестващи програми за него, които позволяват цялостно автоматизирано тестване.

Тестване с добър представител на общия случай

Както вече споменахме, нормално е тестването да започне с тестов пример, който е добър представител на общия случай. Това е тест, който хем е достатъчно прост, за да бъде проигран ръчно на хартия, хем е достатъчно общ, за да покрие общия случай на употреба на програмата, а не някой частен случай. Следвайки този подход най-естественото нещо, което някой програмист може да направи е следното:

1. Да измисли пример, който е добър представител на общия случай.

2. Да тества примера на ръка (на хартия).

3. Да очаква примера да тръгне успешно и от имплементацията на неговия алгоритъм.

4. Да се убеди, че примерът му работи коректно след написване на програмата и отстраняване на грешките, които възникват при писането на кода.

За съжаление много програмисти спират с тестването в този момент. Някои по-неопитни програмисти правят дори нещо по-лошо: измислят какъв да е пример (който е прост частен случай на задачата), не го тестват на хартия, пишат някакъв код и накрая като тръгне този пример, решават, че са приключили. Не правете така! Това е като да ремонтираш лека кола и когато си готов, без да запалиш двигателя да пуснеш колата леко по някой наклон и ако случайно тръгне надолу да се произнесеш компетентно и безотговорно: "Готова е колата. Ето, движи се надолу без никакъв проблем."

Какво още да тестваме?

Тестването на примера, който сте проиграли на хартия е едва първата стъпка от тестването на програмата. Следва да извършите още няколко задължителни теста, с които да се убедите, че програмата ви работи коректно:

- Сериозен тест за обичайния случай. Целта на този тест е да провери дали за по-голям и по-сложен пример вашата програма работи коректно. За нашата задача с разбъркването на картите такъв тест може да е тесте от 52 карти.

- Тестове за граничните случаи. Те проверяват дали вашата програма работи коректно при необичаен вход на границата на допустимото. За нашата задача такъв пример е разбъркването на тесте, което се състои само от една карта.

- Тестове за бързодействие. Тези тестове поставят програмата в екстремални условия като й подават големи по размерност входни данни и проверяват бързодействието.

Нека разгледаме горните групи тестове една по една.

Сериозен тест на обичайния случай

Вече сме тествали програмата за един случай, който сме измислили на ръка и сме проиграли на хартия. Тя работи коректно. Този случай покрива типичния сценарий за употреба на програмата. Какво повече трябва да тестваме? Ами много просто, възможно е програмата да е грешна, но да работи по случайност за нашия случай.

Как да подготвим по-сериозен тест? Това зависи много от самата задача. Тестът хем трябва да е с по-голям обем данни, отколкото ръчния тест, но все пак трябва да можем да проверим дали изхода от програмата е коректен.

За нашия пример с разбъркването на карти в случаен ред е нормално да тестваме с пълно тесте от 52 карти. Лесно можем да произведем такъв входен тест с два вложени цикъла. След изпълнение на програмата също лесно можем да проверим дали резултатът е коректен – трябва картите да са разбъркани и разбъркването да е случайно. Необходимо е още при две последователни изпълнения на този тест да се получи тотално различно разбъркване. Ето как изглежда кодът, реализиращ такъв тест:

static void TestShuffle52Cards()

{

List<Card> cards = new List<Card>();

string[] allFaces = new string[] { "2", "3", "4", "5",

"6", "7", "8", "9", "10", "J", "Q", "K", "A" };

Suit[] allSuits = new Suit[] { Suit.CLUB, Suit.DIAMOND,

Suit.HEART, Suit.SPADE };

foreach (string face in allFaces)

{

foreach (Suit suit in allSuits)

{

Card card = new Card() { Face = face, Suit = suit };

cards.Add(card);

}

ShuffleCards(cards);

PrintCards(cards);

}

Ако го изпълним получаваме примерно такъв резултат:

(4 DIAMOND)(2 DIAMOND)(6 HEART)(2 SPADE)(A SPADE)(7 SPADE)(3 DIAMOND)(3 SPADE)(4 SPADE)(4 HEART)(6 CLUB)(K HEART)(5 CLUB)(5 DIAMOND)(5 HEART)(A HEART)(9 CLUB)(10 CLUB)(A CLUB)(6 SPADE)(7 CLUB)(7 DIAMOND)(3 CLUB)(9 HEART)(8 CLUB)(3 HEART)(9 SPADE)(4 CLUB)(8 HEART)(9 DIAMOND)(5 SPADE)(8 DIAMOND)(J HEART)(10 DIAMOND)(10 HEART)(10 SPADE)(Q HEART)(2 CLUB)(J CLUB)(J SPADE)(Q CLUB)(7 HEART)(2 HEART)(Q SPADE)(K CLUB)(J DIAMOND)(6 DIAMOND)(K SPADE)(8 SPADE)(A DIAMOND)(Q DIAMOND)(K DIAMOND)

Ако огледаме внимателно получената подредба на картите, ще забележим, че много голяма част от тях си стоят на първоначалната позиция и не са променили местоположението си. Например сред първите 4 карти половината не са били разместени при разбъркването: 2♦ и 2♠.

Никога не е късно да намерим дефект в програмата и единственият начин да направим това е да тестваме сериозно, задълбочено и систематично кода с примери, които покриват най-разнообразни практически ситуации. Полезно беше да направим тест с реално тесте от 52 карти, нали? Натъкнахме се на сериозен дефект, който не може да бъде подминат.

Сега как да оправим проблема? Първата идея, която ни хрумва, е да правим по-голям брой случайни единични размествания (очевидно N на брой са недостатъчни). Друга идея е N-тото разместване да разменя N-тата поред карта от тестето със случайна друга карта, а не винаги първата. Така ще си гарантираме, че всяка карта ще бъде разменена с поне една друга карта и няма да останат позиции от тестето, които не са участвали в нито една размяна (това се наблюдава в горния пример с разбъркването на 52 карти). Втората идея изглежда по-надеждна. Нека я имплементираме. Получаваме следните промени в кода:

static void PerformSingleExchange(List<Card> cards, int index)

{

int randomIndex = rand.Next(1, cards.Count);

Card firstCard = cards[index];

Card randomCard = cards[randomIndex];

cards[index] = randomCard;

cards[randomIndex] = firstCard;

}

static void ShuffleCards(List<Card> cards)

{

for (int i = 0; i < cards.Count; i++)

{

PerformSingleExchange(cards, i);

}

Стартираме програмата и получаваме много по-добро разбъркване на тестето от 52 карти, отколкото преди:

(9 HEART)(5 CLUB)(3 CLUB)(7 SPADE)(6 CLUB)(5 SPADE)(6 HEART)(4 CLUB)(10 CLUB)(3 SPADE)(K DIAMOND)(10 HEART)(8 CLUB)(A CLUB)(J DIAMOND)(K SPADE)(9 SPADE)(7 CLUB)(10 DIAMOND)(9 DIAMOND)(8 HEART)(6 DIAMOND)(8 SPADE)(5 DIAMOND)(4 HEART)(10 SPADE)(J CLUB)(Q SPADE)(9 CLUB)(J HEART)(K CLUB)(2 HEART)(7 HEART)(A HEART)(3 DIAMOND)(K HEART)(A SPADE)(8 DIAMOND)(4 SPADE)(3 HEART)(5 HEART)(Q HEART)(4 DIAMOND)(2 SPADE)(A DIAMOND)(2 DIAMOND)(J SPADE)(7 DIAMOND)(Q DIAMOND)(2 CLUB)(6 SPADE)(Q

CLUB)

Изглежда, че най-сетне картите са подредени случайно и са различни при всяко изпълнение на програмата. Няма видими дефекти (например повтарящи се или липсващи карти или карти, които често запазват началната си позиция). Програмата работи бързо и не зависва. Изглежда сме се справили добре.

Нека вземем другата примерна задача: сортиране на числа. Как да си направим сериозен тест за обичайния случай? Ами най-лесното е да генерираме поредица от 100 или дори 1000 случайни числа и да ги сортираме. Проверката за коректност е лесна: трябва числата да са подредени по големина. Друг тест, който е удачен при сортирането на числа е да вземем числата от 1000 до 1 в намаляващ ред и да ги сортираме. Трябва да получим същите числа, но сортирани в нарастващ ред. Би могло да се каже, че това е най-трудният възможен тест за тази задача и ако той работи за голям брой числа, значи програмата най-вероятно е коректна.

Нека разгледаме и другите видове тестове, които е добре винаги да правим при решението на задачи по програмиране.

Гранични случаи

Най-честото нещо, което се пропуска при решаването на задачи, пък и въобще в програмирането, е да се помисли за граничните ситуации. Граничните ситуации се получават при входни данни на границата на нормалното и допустимото. При тях често пъти програмата гърми, защото не очаква толкова малки или големи или необичайни данни, но те все пак са допустими по условие или не са допустими, но не са предвидени от програмиста.

Как да тестваме граничните ситуации? Ами разглеждаме всички входни данни, които програмата получава и се замисляме какви са екстремните им стойности и дали са допустими. Възможно е да имаме екстремно малки стойности, екстремно големи стойности или просто странни комбинации от стойности. Ако по условие имаме ограничения, например до 52 карти, стойностите около това число 52 също са гранични и могат да причинят проблеми.

Граничен случай: разбъркване на една карта

Например в нашата задача за разбъркване на карти граничен случай е да разбъркаме една карта. Това е съвсем валидна ситуация (макар и необичайна), но нашата програма би могла да не работи коректно за една карта поради някакви особености. Нека проверим какво става при разбъркване на една карта. Можем да напишем следния малък тест:

static void TestShuffleOneCard()

{

List<Card> cards = new List<Card>();

cards.Add(new Card() { Face = "A", Suit = Suit.CLUB });

CardsShuffle.ShuffleCards(cards);

CardsShuffle.PrintCards(cards);

}

Изпълняваме го и получаваме напълно неочакван резултат:

Unhandled Exception: System.ArgumentOutOfRangeException: Index was out of range. Must be non-negative and less than the size of the collection. Parameter name: index

at System.ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument argument, ExceptionResource resource)

at System.ThrowHelper.ThrowArgumentOutOfRangeException()

at System.Collections.Generic.List`1.get_Item(Int32 index)

at CardsShuffle.PerformSingleExchange(List`1 cards, Int32 index) in D:\Projects\Cards\CardsShuffle.cs:line 61

…

Ясно е какъв е проблемът: генерирането на случайно число се счупи, защото му се подава невалиден диапазон. Нашата програма работи добре при нормален брой карти, но не работи за една карта. Открихме лесен за отстраняване дефект, който бихме пропуснали с лека ръка, ако не бяхме разгледали внимателно граничните случаи. След като знаем какъв е проблемът, поправката на кода е тривиална:

static void ShuffleCards(List<Card> cards)

{

if (cards.Count > 1)

{

for (int i = 0; i < cards.Count; i++)

{

PerformSingleExchange(cards, i);

}

Тестваме отново и се убеждаваме, че проблемът е решен.

Граничен случай: разбъркване на две карти

Щом има проблем за 1 карта, сигурно може да има проблем и за 2 карти. Не звучи ли логично? Нищо не ни пречи да проверим. Стартираме програмата с 2 карти няколко пъти и очакваме да получим различни размествания на двете карти. Ето примерен код, с който можем да направим това:

static void TestShuffleTwoCards()

{

List<Card> cards = new List<Card>();

cards.Add(new Card() { Face = "A", Suit = Suit.CLUB });

cards.Add(new Card() { Face = "3", Suit = Suit.DIAMOND });

CardsShuffle.ShuffleCards(cards);

CardsShuffle.PrintCards(cards);

}

Стартираме няколко пъти и резултатът винаги е все един и същ:

(3 DIAMOND)(A CLUB)

Изглежда пак нещо не е наред. Ако разгледаме кода или го пуснем през дебъгера, ще се убедим, че всеки път се правят точно два размествания: разменя се първата карта с втората и веднага след това се разменя втората карта с първата. Резултатът винаги е един и същ. Как да решим проблема? Веднага можем да се сетим за няколко решения:

- Правим единичното разместване N+K брой пъти, където K е случайно число между 0 и 1.

- При разместванията допускаме случайната позиция, на която отива първата карта да включва и нулевата позиция.

- Разглеждаме случая с точно 2 карти като специален и пишем отделен метод специално за него.

Второто решение изглежда най-просто за имплементация. Да го пробваме. Получаваме следния код:

static void PerformSingleExchange(List<Card> cards, int index)

{

int randomIndex = rand.Next(0, cards.Count);

Card firstCard = cards[index];

Card randomCard = cards[randomIndex];

cards[index] = randomCard;

cards[randomIndex] = firstCard;

}

Тестваме отново разбъркването на две карти и този път изглежда, че програмата работи коректно: картите се разместват понякога, а понякога запазват началната си подредба.

Щом има проблем за 2 карти, може да има проблем и за 3 карти, нали? Ако тестваме програмата за 3 карти, ще се убедим, че тя работи коректно. След няколко стартирания получаваме всички възможни разбърквания на трите карти, което показва, че случайното разбъркване може да получи всички пермутации на трите карти. Този път не открихме дефекти и програмата няма нужда от промяна.

Граничен случай: разбъркване на нула карти

Какво още може да проверим? Има ли други необичайни, гранични ситуации. Да помислим. Какво ще стане, ако се опитаме да разбъркаме празен списък от карти? Това наистина е малко странно, но има едно правило, че една програма трябва или да работи коректно или да сигнализира за грешка. Нека да видим какво ще върне нашата програма за 0 карти. Резултатът е празен списък. Коректен ли е? Ами да, ако разбъркаме 0 карти в случаен ред би трябвало да получим пак 0 карти. Изглежда всичко е наред.

При грешни входни данни програмата не трябва да връща грешен резултат, а трябва или да върне верен резултат или да съобщи, че входните данни са грешни.

Какво мислите за горното правило? Логично е нали? Представете си, че правите програма, която показва графични изображения (снимки). Какво става при снимка, която представлява празен файл. Това е също необичайна ситуация, която не би трябвало да се случва, но може да се случи. Ако при празен файл вашата програма зависва или хвърля необработено изключение, това би било много досадно за потребителя. Нормално е празният файл да бъде изобразен със специална икона или вместо него да се изведе съобщение "Invalid image file", нали?

Помислете колко гранични и необичайни ситуации има в Windows. Какво става ако печатаме празен файл на принтера? Дали Windows забива в този момент и показва небезизвестния "син екран"? Какво става, ако в калкулаторът на Windows направим деление на нула? Какво става, ако копираме празен файл (с дължина 0 байта) с Windows Explorer? Какво става, ако в Notepad се опитаме да създадем файл без име (с празен низ, зададен като име)? Виждате, че гранични ситуации има много и навсякъде. Наша задача като програмисти е да ги улавяме и да мислим за тях преди още да се случат, а не едва когато неприятно развълнуван потребител яростно ни нападне по телефона с неприлични думи по адрес на наши близки роднини.

Да се върнем на нашата задача за разбъркване на картите. Оглеждайки се за гранични и необичайни случаи се сещаме дали можем да разбъркаме -1 карти? Понеже няма как да създадем масив с -1 елемента, считаме, че такъв случай няма как да се получи.

Понеже нямаме горна граница на картите, няма друга специална точка (подобна на ситуацията с 1 карта), около която да търсим за проблемни ситуации. Прекратяваме търсенето на гранични случаи около броя на картите. Изглежда предвидихме всички ситуации.

Остава да се огледаме дали няма други стойности от входните данни, които могат да причинят проблеми, например невалидна карта, карта с невалидна боя, карта с отрицателно лице (примерно -1 спатия) и т.н. Като се замислим, нашият алгоритъм не се интересува какво точно разбърква (карти за игра или яйца за омлет), така че това не би трябвало да е проблем. Ако имаме съмнения, можем на си направим тест и да се убедим, че при невалидни карти резултатът от разбъркването им не е грешен.

Оглеждаме се за други гранични ситуации във входните данни и не се сещаме за такива. Остава единствено да измерим бързодействието, нали? Всъщност пропуснахме нещо много важно: да тестваме всичко наново след поправките.

Повторно тестване след корекциите (regression testing)

Често пъти при корекции на грешки се получават незабелязано нови грешки, които преди не са съществували. Например, ако поправим грешката за 2 карти чрез промяна на правилата за размяна на единична карта, това би могло да доведе до грешен резултат при 3 или повече карти. При всяка промяна, която би могла да засегне други случаи на употреба, е задължително да изпълняваме отново тестовете, които сме правили до момента, за да сме сигурни, че промяната не поврежда вече работещите случаи. За тази цел е добре да запазваме тестовете на програмата, които сме изпълнявали, като методи (например започващи с префикс Test), а не да ги изтриваме.

Идеята за повторяемост на тестовете лежи в основата на концепцията unit testing. Тази тема, както вече споменахме, е за по-напреднали и затова я оставяме за по-нататък във времето (и пространството).

В нашия случай с разбъркването на карти след всички промени, които направихме, е редно да тестваме отново разбъркването на 0 карти, на 1 карта, на 2 карти, на 3 карти и на 52 карти.

Когато сте открили и сте поправили грешка в кода, отнасяща се за някой специфичен тест, уверете се, че поправката не засяга всички останали тестове. За целта е препоръчително да запазвате всички тестове, които изпълнявате.

Тестове за производителност

Нормално е винаги, когато пишете софтуер, да имате някакви изисквания и критерии за бързодействие на програмите или модулите, които пишете. Никой не обича машината му да работи бавно, нали? Затова трябва да се стремите да не пишете софтуер, който работи бавно, освен, ако нямате добра причина за това.

Как тестваме бързодействието (производителността) на програмата? Първият въпрос, който трябва да си зададем, когато стигнем до тестване на бързодействието, е имаме ли изисквания за скорост. Ако имаме, какви са те? Ако нямаме, какви ориентировъчни критерии за бързодействие трябва да спазим (винаги има някакви общоприети)?

Разбъркване на карти – тестове за производителност

Нека да разгледаме за пример нашата програма за разбъркване на тесте карти. Какви изисквания за бързодействие би могла да има тя? Първо имаме ли по условие такива изисквания? Нямаме изрично изискване в стил "програмата трябва да завършва за една секунда или по-бързо при 500 карти на съвременна компютърна конфигурация". Щом нямаме такива изрични изисквания, все пак трябва някак да решим въпроса с оценката на бързодействието, неформално, по усет.

Понеже работим с карти за игра, считаме, че едно тесте има 52 карти. Вече пускахме такъв тест и видяхме, че работи мигновено, т.е. няма видимо забавяне. Изглежда за нормалния случай на употреба бързината не създава проблеми.

Нормално е да тестваме програмата и с много повече карти, примерно с 52 000, защото в някой специален случай някой може да реши да разбърква много карти и да срещне проблеми. Лесно можем да си направим такъв пример като добавим 1 000 пъти нашите 52 карти и след това ги разбъркаме. Нека пуснем един такъв пример:

static void TestShuffle52000Cards()

{

List<Card> cards = new List<Card>();

string[] allFaces = new string[] {"2", "3", "4", "5",

"6", "7", "8", "9", "10", "J", "Q", "K", "A"};

Suit[] allSuits = new Suit[] { Suit.CLUB, Suit.DIAMOND,

Suit.HEART, Suit.SPADE};

for (int i = 0; i < 1000; i++)

{

foreach (string face in allFaces)

{

foreach (Suit suit in allSuits)

{

Card card = new Card() { Face = face, Suit = suit };

cards.Add(card);

}

ShuffleCards(cards);

PrintCards(cards);

}

Стартираме програмата и забелязваме, че машината леко се успива за около пет-десет секунди. Разбира се при по-бавни машини успиването е за по-дълго. Какво се случва? Би трябвало при 52 000 карти да направим приблизително същия брой единични размествания, а това би трябвало да отнеме частица от секундата. Защо имаме секунди забавяне? Опитните програмисти веднага ще се сетят, че печатаме големи обеми информация на конзолата, а това е бавна операция. Ако коментираме реда, в който отпечатваме резултата и измерим времето за изпълнение на разбъркването на картите, ще се убедим, че програмата работи достатъчно бързо дори и за 52 000 карти. Ето как можем да замерим времето:

static void TestShuffle52000Cards()

{

...

DateTime oldTime = DateTime.Now;

ShuffleCards(cards);

DateTime newTime = DateTime.Now;

Console.WriteLine("Execution time: {0}", newTime - oldTime);

//PrintCards(cards);

}

Можем да проверим точно колко време отнема изпълнението на метода за разбъркване на картите:

Execution time: 00:00:00.0156250

Една милисекунда изглежда напълно приемливо. Нямаме проблем с бързодействието.

Сортиране на числа – тестове за производителност

Нека разгледаме другата от нашите примерни задачи: сортиране на масив с числа. При нея бързодействието може да се окаже много по-проблемно, отколкото разбъркването на тесте карти. Нека сме направили просто решение, което работи така: намира най-малкото число в масива и го разменя с числото на позиция 0. След това намира сред останалите числа най-малкото и го поставя на позиция 1. Това се повтаря докато се стигне до последното число, което би трябвало да си е вече на мястото. Няма да коментираме верността на този алгоритъм. Той е добре известен като "метод на пряката селекция" (http://en.wikipedia.org/wiki/Selection_sort).

Сега да предположим, че сме минали през всички стъпки за решаването на задачи по програмиране и накрая сме стигнали до този пример, с който се опитваме да сортираме 10 000 случайни числа:

Sort10000Numbers.cs

using System;

public class Sort10000Numbers

{

static void Main()

{

int[] numbers = new int[10000];

Random rnd = new Random();

for (int i=0; i<numbers.Length; i++)

{

numbers[i] = rnd.Next(2 * numbers.Length);

}

SortNumbers(numbers);

PrintNumbers(numbers);

}

static void SortNumbers(int[] numbers)

{

for (int i = 0; i < numbers.Length - 1; i++)

{

int minIndex = i;

for (int j=i+1; j<numbers.Length; j++)

{

if (numbers[j] < numbers[minIndex])

{

minIndex = j;

}

int oldNumber = numbers[i];

numbers[i] = numbers[minIndex];

numbers[minIndex] = oldNumber;

}

static void PrintNumbers(int[] numbers)

{

Console.Write("[");

for (int i = 0; i < numbers.Length; i++)

{

Console.Write(numbers[i]);

if (i < numbers.Length - 1)

{

Console.Write(", ");

}

Console.WriteLine("]");

}

Стартираме го и изглежда, че той работи за под секунда на нормална съвременна машина. Резултатът (със съкращения) би могъл да е нещо такова:

[0, 14, 19, 20, 20, 22, ..., 19990, 19993, 19995, 19996]

Сега правим още един експеримент за 300 000 случайни числа и виждаме, че програмата като че ли зависва или работи прекалено бавно, за да я изчакаме. Това е сериозен проблем с бързодействието.

Преди да се втурнем да го решаваме трябва, обаче, да си зададем един много важен въпрос: дали ще имаме реална ситуация, при която ще се наложи да сортираме 300 000 числа. Ако сортираме примерно оценките на студентите в един курс, те не могат да бъдат повече от няколко десетки. Ако, обаче, сортираме цените на акциите на голяма софтуерна компания за цялата й история на съществуване на фондовата борса, можем да имаме огромен брой числа, защото цената на акциите й може да се променя всяка секунда. За десетина години цените на акциите на тази компания биха могли да се променят няколкостотин милиона пъти. В такъв случай трябва да търсим по-ефективен алгоритъм за сортиране.

Как да правим ефективно сортиране на цели числа можем да прочетем в десетки сайтове в Интернет и в класическите книги по алгоритми. Конкретно за тази задача най-подходящо е да използваме алгоритъма за сортиране "radix sort" (http://en.wikipedia.org/wiki/Radix_sort), но тази дискусия е извън темата и ще я пропуснем.

Нека припомним доброто старо правило за ефективността:

Винаги трябва да правим компромис между времето, което ще вложим, за да напишем програмата, и бързодействието, което искаме да постигнем. Иначе може да изгубим време да решаваме проблем, който не съществува или да стигнем до решение, което не върши работа.

Трябва да имаме предвид и че за някои задачи изобщо не съществуват бързи алгоритми и ще трябва да се примирим с ниската производителност. Например за задачата за намиране на всички прости делители на цяло число (вж. http://en.wikipedia.org/wiki/Integer_factorization) няма известно бързо решение.

За някои задачи нямаме нужда от бързина, защото очакваме входните данни да са достатъчно малки и тогава е безумно да търсим сложни алгоритми с цел бързодействие. Например задачата за сортиране на оценките на студентите от даден курс може да се реши с произволен алгоритъм за сортиране и при всички случаи ще работи бързо, тъй като броят на студентите се очаква да е достатъчно малък.

Генерални изводи

Преди да започнете да четете настоящата тема сигурно сте си мислили, че това ще е най-скучната и безсмислена до момента, но вярваме, че сега мислите по съвсем различен начин. Всички си мислят, че знаят как да решават задачи по програмиране и че за това няма "рецепта" (просто трябва да го можеш), но въобще не е така. Има си рецепти и то най-различни. Ние ви показахме нашата и то в действие! Убедихте се, че нашата рецепта дава резултат, нали?

Само се замислете колко грешки и проблеми открихме докато решавахме една много лесна и проста задача: разбъркване на карти в случаен ред. Щяхме ли да напишем качествено решение, ако не бяхме подходили към задачата по рецептата, изложена по-горе? А какво би се случило, ако решаваме някоя много по-сложна и трудна задача, примерно да намерим оптимален път през сутрешните задръствания в София по карта на града с актуални данни за трафика? При такива задачи е абсолютно немислимо да подходим хазартно и да се хвърлим на първата идея, която ни дойде на ум. Първата стъпка към придобиване на умения за решаване на такива сложни задачи е да се научите да подхождате към задачата систематично и да усвоите рецептата за решаване на задачи, която ви демонстрирахме в действие. Това, разбира се, съвсем няма да ви е достатъчно, но е важна крачка напред!

За решаването на задачи по програмиране си има рецепта! Ползвайте систематичен подход и ще имате много по-голям успех, отколкото, ако карате по усет. Дори професионалистите с десетки години опит ползват в голяма степен описания от нас подход. Ползвайте го и вие и ще се убедите, че работи! Не пропускайте да тествате сериозно и задълбочено решението.

Упражнения

1. Използвайки описаната в тази глава методология за решаване на задачи по програмиране решете следната задача: дадени са N точки (N < 100 000) в равнината. Точките са представени с целочислени координати (x_i, y_i). Напишете програма, която намира всички възможни хоризонтални или вертикални прави (отново с целочислени координати), които разделят равнината на две части, така че двете части да съдържат по равен брой точки (точките попадащи върху линията не се броят).

2. Използвайки описаната в тази глава методология за решаване на задачи по програмиране решете следната задача: дадено е множество S от n цели числа и положително цяло число k (k <= n <= 10). Алтернативна редица от числа е редица, която алтернативно сменя поведението си от растяща към намаляваща и обратно след всеки неин елемент. Напишете програма, която генерира всички алтернативни редици s₁, s₂, …, s_k състояща се от k различни елемента от S. Пример: S={ 2, 5, 3, 4 }, K=3: {2, 4, 3}, {2, 5, 3}, {2, 5, 4}, {3, 2, 4}, {3, 2, 5}, {3, 4, 2}, {3, 5, 2}, {3, 5, 4}, {4, 2, 3}, {4, 2, 5}, {4, 3, 5}, {5, 2, 3}, {5, 2, 4}, {5, 3, 4}

3. Използвайки описаната в тази глава методология за решаване на задачи по програмиране решете следната задача: разполагаме с карта на един град. Картата се състои от улици и кръстовища. За всяка улица на картата е отбелязана нейната дължината. Едно кръстовище свързва няколко улици. Задачата е да се намери и отпечата най-късият път между двойка кръстовища (измерен като суми от дължините на улиците, през които се преминава).

Ето как изглежда схематично картата на един примерен град:

На тази карта най-късият път между кръстовища A и D е с дължина 70 и е показан на фигурата с удебелени линии. Както виждате, между A и D има много пътища с най-различна дължина. Не винаги най-късото начало води към най-късия път и не винаги най-малкият брой улици води до най-къс път. Между някои двойки кръстовища дори въобще не съществува път. Това прави задачата доста интересна.

Входните данни се задават в текстов файл map.txt. Файлът започва със списък от улици и техните дължини, след което следва празен ред и след него следват двойки кръстовища, между които се търси най-кратък път. Файлът завършва с празен ред. Ето пример:

A B 20

A H 30

B H 5

...

L M 5

(празен ред)

A D

H K

A E

(празен ред)

Резултатът от изпълнението на програмата за всяка двойка кръстовища от списъка във входния файл трябва да е дължината на най-късия път, следвана от самия път. За картата от нашия пример изходът трябва да изглежда така:

70 ABJCFD

No path!

35 ABHE

4. * В равнината са дадени са N точки с координати цели, положителни числа. Тези точки представляват дръвчета в една нива. Стопанинът на нивата иска да огради дръвчетата, като използва минимално количество ограда. Напишете програма, която намира през кои точки трябва да минава оградата. Използвайте методологията за решаване на задачи по програмиране!

Ето как би могла да изглежда градината:

Входните данни се четат от файл garden.txt. На първия ред на файла е зададен броят на точките. Следват координатите на точките. За нашия пример входният файл би могъл да има следното съдържание:

60 50

100 30

40 40

20 70

50 20

30 70

10 10

110 70

90 60

80 20

70 80

20 20

30 60

Изходните данни трябва да се отпечатат на конзолата в като последователност от точки, през които оградата трябва да мине. Ето примерен изход:

(10, 10) - (20, 70) - (70, 80) - (110, 70) - (100, 30) - (80, 20) - (10, 10)

Решения и упътвания

1. Първо намерете подходящ кариран лист хартия, на който да можете да си разчертаете координатната система и точките върху нея докато разписвате примери и мислите за конкретно решение. Помислете за различни решения и сравнете кое от тях е по-добро от гледна точка на качество, бързина на работа и време необходимо за реализацията.

2. Отново хванете първо лист и химикалка. Разпишете много примери и помислете върху тях. Какви идеи ви идват? Нужни ли са ви още примери за да се сетите за решение? Обмислете идеи, разпишете ги първо на хартия, ако сте сигурни в тях ги реализирайте. Помислете за примери, върху които вашата програма няма да работи коректно. Винаги е добра идея първо да измислите особените примери, чак след това да реализирате решението си. Помислете как ще работи вашето решение при различни стойности на K и различни стойности и брой елементи в S.

3. Следвайте стриктно методологията за решаване на задачи по програмиране! Задачата е сложна и изисква да й отделите достатъчно внимание. Първо си нарисувайте примера на хартия. Опитайте се да измислите сами правилен алгоритъм за намиране на най-къс път. След това потърсете в Интернет по ключови думи "shortest path algorithm". Много е вероятно бързо да намерите статия с описание на алгоритъм за най-къс път.

Проверете дали алгоритъмът е верен. Пробвайте различни примери.

В каква структура от данни ще пазите картата на града? Помислете кои са операциите, които ви трябват в алгоритъма за най-къс път. Вероятно ще стигнете до идеята да пазите списък от улиците за всяко кръстовище, а кръстовищата да пазите в списък или хеш-таблица.

Помислете за ефективността. Ще работи ли вашият алгоритъм за 1 000 кръстовища и 5 000 улици?

Пишете стъпка по стъпка. Първо направете четенето на входните данни. (В случая входът е от файл и затова можете да започнете от него. Ако входът беше от конзолата, трябваше да го оставите за най-накрая). Реализирайте отпечатване на прочетените данни. Реализирайте алгоритъма за най-къс път. Ако можете, разбийте реализацията на стъпки. Например като за начало можете да търсите само дължината на най-късия път без самия път (като списък от кръстовища), защото е по-лесно. Реализирайте след това и намирането на самия най-къс път. Помислете какво става, ако има няколко най-къси пътя с еднаква дължина. Накрая реализирайте отпечатването на резултатите, както се изисква в условието на задачата.

Тествайте решението си! Пробвайте с празна карта. Пробвайте с карта с 1 кръстовище. Пробвайте случай, в който няма път между зададените кръстовища. Пробвайте с голяма карта (1 000 кръстовища и 5 000 улици). Можете да си генерирате такава с няколко реда програмка. За имената на кръстовищата трябва да използвате string, а не char, нали? Иначе как ще имате 1 000 кръстовища? Работи ли вашето решение бързо? А работи ли вярно?

Внимавайте с входните и изходните данни. Спазвайте формата, който е указан в условието на задачата!

4. Ако не сте много силни в аналитичната геометрия, едва ли ще измислите решение на задачата сами. Опитайте търсене в Интернет по ключовите думи "convex hull algorithm". Знаейки, че оградата, която трябва да построим се нарича "изпъкнала обвивка" (convex hull) на множество точки в равнината, ще намерим стотици статии в Интернет по темата, в някои дори има сорс код на C#. Не преписвайте грешките на другите и особено сорс кода! Мислете! Проучете как работи алгоритъмът и си го реализирайте сами.

Проверете дали алгоритъмът е верен. Пробвайте различни примери (първо на хартия). Какво става, ако има няколко точки на една линия върху изпъкналата обвивка? Трябва ли да включвате всяка от тях? Помислете какво става, ако има няколко изпъкнали обвивки. От коя точка започвате? По часовниковата стрелка ли се движите или обратното? В условието на задачата има ли изискване как точно да са подредени точките в резултата?

В каква структура от данни ще пазите точките? В каква структура ще пазите изпъкналата обвивка?

Помислете за ефективността. Ще работи ли вашият алгоритъм за 1 000 точки?

Пишете стъпка по стъпка. Първо направете четенето на входните данни. Реализирайте отпечатване на прочетените точки. Реализирайте алгоритъма за изпъкнала обвивка. Ако можете, разбийте реализацията на стъпки. Накрая реализирайте отпечатването а резултата, както се изисква в условието на задачата.

Тествайте решението си! Какво става, ако имаме 0 точки? Пробвайте с една точка. Пробвайте с 2 точки. Пробвайте с 5 точки, които са на една линия. Работи ли алгоритъмът ви? Какво става, ако имаме 10 точки и още 10, които съвпадат с първите 10? Какво става, ако имаме 10 точки, всичките една върху друга? Какво става, ако имаме много точки, примерно 1 000. Работи ли бързо вашият алгоритъм? Какво става, ако координатите на точките са големи числа, примерно (100 000 000, 200 000 000)? Влияе ли това на вашия алгоритъм? Имате ли грешки от загуба на точност?

Внимавайте с входните и изходните данни. Спазвайте формата, който е указан в условието на задачата! Не си измисляйте сами формата на входния файл и на изхода. Те са ясно дефинирани и трябва да се спазват.

Ако имате мерак, направете си визуализация на точките и изпъкналата обвивка като графика с Windows Forms или WPF. Направете си и генератор на случайни тестови данни и си тествайте многократно решението, като гледате визуализацията на обвивката – дали коректно обвива точките и дали е минимална.

Дискусионен форум

Коментирайте книгата и задачите в нея във: форума на софтуерната академия.

Коментирай

Трябва да сте влезнали, за да коментирате.