Очекувана вредност

Последниот SRM 448 ме натера да размислувам за една од моите омилени теми - Веројатност. Првата задача беше поврзана со оваа тема. Како прва и најлесна задача, решението се добиваше рекурзивно, со собирање на веројатностите за сите можни настани. Брзо го напишав ова затоа што инстинктот ми велеше дека ова мора да биде главниот начин за добивање на конечниот резултат. Требаше да се погоди очекуваниот број на карти кои ќе се извлечат, а кои ќе донесат победа. Нема да објаснувам што се бара во задачата, неа можете да ја погледнете на topcoder. Она што не знаев е како сите информации за веројатноста да се искористат за да се добие конечниот резултат. Брзо го искодирав кодот за пресметување на веројатноста. Прво размислував малку како да го искористам она што веќе го имав, но не ми доаѓаше идеја. Потоа на 40 минути до крај малку погуглав и за среќа најдов една страна каде што многу едноставно беше објаснето како се добива очекувана вредност. Формулата е следна:

очекувана вредност = Сума од на сите настани(веројатноста за настан i * вредноста за тој настан i)

Еве да објаснам за еден едноставен пример. Имаме коцка, таа има 6 страни и на секоја страна има по една вредност од 1 до 6. При фрлање на коцката која е очекуваната вредност што ќе ја добиеме?

Значи според формулата:

expected = (1/6)*1+(1/6)*2+(1/6)*3+(1/6)*4+(1/6)*5+(1/6)*6 = (1/6)*21 = 3.5

Можеби и малку е нелогичен примеров ама добро покажува како се применува формулата за пресметување на очекувана вредност.

Повеќе за ова можете да прочитате на wikipedia.

Инаку да се вратам на приказната со настапот на SRM 448. Го имплементирав ова, и програмата не ми ги даваше потребните резултати. Значи имаше две потенцијални работи кои се причина за грешното решение. Прво, алгоритмот не е точен, и второ, имам некоја грешка во кодот. Втората опција брзо ја елиминирав мислејќи дека во толку прост код и не може да има некоја грешка, скенирајќи го набрзина кодот за да имам време да размислувам за точноста на алгоритмот. Бидејќи малку бев скептичен во врска со точноста на формулата се обидував да наоѓам други малку поинакви пристапи во крајниот алгоритам и менував некои работи во кодот кои не ми донесоа успех. На крај се откажав. Моја среќа што имаше многу натпреварувачи со ниедна решена па не ми падна многу рејтингот, сега е 1224 и останувам во DIV 1.

Кога заврши натпреварот одлучив да одморам малку. Размислував што би можело да ми биде грешката и полека го анализирав мојот код во главата. Наеднаш дојдов до проблематичниот дел. Наместо for (j=0;j0) што е грешка при брзање... Оваа грешка ме чинеше добар пласман. Алгоритмот бил добар, но сум имал грешка во имплемнтацијата.

Поука за друг пат. Секогаш разгледувај ги сите потенцијални причинители на грешната програма, и никогаш не елиминирај ниедна од можните причини колку и да изгледа дека непотребно се губи време на некоја од нив.

Тест задача

Случајно најдов на еден многу интересен сајт http://www.scarky.com/ каде може да се постави задача по програмирање. Сите параметри се местат од страна на креаторот, кодот за натпреварот сам се генерира. Можеби тоа што не би го сметал за професионален начин за организирање на натпревари е што нема можност повеќе input-и. Се надевам тоа ќе се поправи во иднина. Ајде сега да го тестираме системот. Производ на два броеви :) Напишете кодче и праќајте. Ќе се обидам наредниве денови да ставам некој попредизвикувачки проблем од областа на програмирањето.