Основни алгоритми

У наставку ћемо научити неколико основних алгоритама. Већину њих Python већ подржава у облику уграђених функција (које смо већ раније разматрали) и њих је заправо најчешће боље користити него их изнова програмирати. Са друге стране, учењем ових основних алгоритама учимо се процесу програмирања и учимо се да размишљамо алгоритамски. Иако смо целу ову област обележили као мало напреднију, ако кренеш да је истражујеш, приметићеш да постоје алгоритми за које смо сигурни да ћеш веома једноставно да их разумеш и научиш.

Сабирање

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

Циљ овог задатка је да нас уведе у различите технике израчунавања збира неколико бројева. Да бисмо једноставније разумели технику која се користи за израчунавање збира бројева, олакшајмо мало задатак тако што ћемо уместо обима многоугла израчунавати обим троугла. Директан начин да се то уради је следећи:

Прво смо учитали сва три броја (зато су нам биле потребне три променљиве) и тек онда смо израчунали обим. Овај начин није директно применљив на случај многоугла јер не знамо колико ће нам променљивих бити потребно (чак иако знамо, њих може бити пуно и такав програм би био непотребно дугачак).

Други начин израчунавања обима троугла ће бити такав да ћемо мењати вредност збира након сваког учитавања дужине странице. У првом кораку поставићемо вредност збира (обима) на прву учитану вредност, а у сваком следећем кораку увећаваћемо текућу вредност збира за вредност учитану у том кораку (подсетимо се, вредности променљивих се могу мењати током извршавања програма).

Ако извршимо претходни програм корак-по-корак, можемо приметити да у првом кораку променљива obim има вредност дужине прве странице, у другом збира дужина прве и друге странице, а да у трећем збира дужина све три странице.

Приметимо да су други и трећи корак једнаки и могу се извршити у петљи.

Програм додатно можемо поједноставити ако и први корак сведемо на облик у којем су друга два и њега убацимо у петљу. Зато приметимо да важи да је \(a + b + c = ((0 + a) + b) + c\) (нула је сабирак који не утиче на вредност збира - каже се да је нула неутрални елемент приликом сабирања). Збир се, дакле, може на почетку поставити (кажемо иницијализовати) на нулу, и затим се на њега може додавати један по један сабирак. Кажемо са се у сваком кораку збир ажурира.

Претходни програм се може једноставније реализовати уз помоћ петље:

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

Каже се да је овај програм заснован на шаблону који се некада називa акумулатор, редукција или fold и видећемо га у разним алгоритмима који следе. Заснива се на томе да се променљива која треба да садржи коначан резултат иницијализује на неку вредност, а затим да се у сваком кораку петље ажурира и нова вредност јој се израчуна на основу њене тренутне вредности и тренутног елемента серије која се обрађује. У нашем примеру променљива која израчунава збир се иницијализује на нулу, а у сваком кораку нова вредност јој се израчунава тако што се на претходну вредност збира дода нови сабирак. Приметимо да и пре петље и током извршавања петље и након петље променљива садржи тачно збир свих до тада учитаних елемената серије тј. свих до тада учитаних дужина странице многоугла.

Ако је позната листа цена производа у корпи израчуна укупан рачун.

Овај задатак смо већ разматрали када смо причали о уграђеним функцијама за рад са листама, међу којима се налазила и функција sum која служи за израчунавање збира елемената листе.

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

Карел се налази испред пуно лоптица и жели да израчуна њихов укупан број. Сваки пут када се робот покрене, испред њега се лоптице распореде другачије. На сваком пољу је написан број лоптица на њему. Када је Карел на том пољу он број лоптица може сазнати позивом функције broj_loptica_na_polju(). Карел тренутно само изговара број лоптица на сваком пољу. Поправи програм тако да се исправно израчунава укупан број лоптица.

Please try loading this page in HTML5 enabled web browsers. All the latest versions of famous browsers such as Internet explorer, Chrome, Firefox, Opera support HTML5.

(карел_сабира)

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

Бројање

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

Ко је добро научио лекцију о листама вероватно се сећа да се дужина листе може (и треба) израчунати помоћу уграђене функције len. Међутим, кроз овај задатак желимо да прикажемо алгоритам бројања. На почетку петље бројач елемената иницијализоваћемо на нулу, а онда ћемо у сваком кораку петље која пролази кроз елементе листе бројач увећавати за један.

Приметимо сличност са алгоритмом сабирања (једина разлика је то што се уместо увећавања збира за вредност текућег елемента бројач увећава за један).

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

Пробај да допуниш наредни програм тако да коректно броји унета имена.

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

Сваки пут када се помери напред, Карел треба да увећа бројач за један.

Please try loading this page in HTML5 enabled web browsers. All the latest versions of famous browsers such as Internet explorer, Chrome, Firefox, Opera support HTML5.

(карел_broji)

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

Подсетимо се просечна вредност елемената листе може одредити тако што се збир свих елемената листе подели бројем елемената те листе. Најлакши и најбољи начин да се то уради је да се употребе уграђене функције sum и len.

Међутим, вежбе ради, хајде да урадимо овај задатак без примене уграђених функција, комбиновањем алгоритама сабирања и бројања. Приметимо да можемо у једној петљи проћи кроз елементе листе и истовремено рачунати и збир и број елемената листе.

Множење

Напиши програм који израчунава запремину квадра чије се дужине страница уносе (запремина квадра једнака је производу дужина његове три странице).

Овај задатак је веома сличан оном у којем се израчунавао обим троугла, једино што се уместо збира три броја захтева израчунавање производа три броја. Директно решење је зато веома слично:

И у овом случају желимо да стигнемо до решења у којем се бројеви учитавају и обрађују у петљи, како бисмо касније могли да га уопштимо и применимо на проблем проналажења производа више бројева. Производ се може поступно израчунавати тако што се помноже прво прва два броја, па се затим добијени производ помножи трећим бројем. Заиста, важи да је \(а \cdot b \cdot c = (a \cdot b) \cdot c\). Међутим, и у овом случају желимо да сва три броја обрађујемо на исти начин. Ако бисмо производ иницијализовали на нулу, он би до краја остао једнак нули јер важи да је \(((0 \cdot a) \cdot b) \cdot c = 0\). Међутим, ако производ иницијализујемо на један, добијамо тачно оно што нам треба (јер важи да је \(а \cdot b \cdot c = ((1 \cdot a) \cdot b) \cdot c\)). Као што је нула био број који не утиче на сабирање (који је неутрални елемент за сабирање), тако је један број који не утиче на множење (он је неутрални елемент за множење). Дакле, програм за израчунавање запремине, тј. производа три унета броја се може дефинисати на следећи начин.

Пошто се исте наредбе понављају три пута, још је боље решење да се употреби петља.

Дакле, производ можемо израчунати тако што се његова вредност у почетку иницијализује на 1, а затим ажурира тако што се у сваком кораку множи текућом вредношћу.

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

Када је \(n\) природан број, производ бројева \(n \cdot x\) означава збир који садржи \(n\) сабирака \(x\) тј. збир \(\underbrace{x + \ldots + x}_n\). Слично се може посматрати производ који садржи \(n\) чинилаца \(x\) тј. производ \(\underbrace{x \cdot \ldots \cdot x}_n\). У математици се такав производ назива степен и обележава се са \(x^n\). Тако је, на пример, \(2^4 = 2 \cdot 2 \cdot 2 \cdot 2 = 16\). Дефиниши функцију која за дате параметре \(x\) и \(n\) израчунава \(x^n\).

Рецимо да Python подржава директно операцију степеновања и она се изражава оператором ** и тражени степен се може једноставно изразити помоћу x ** n. Ипак, вежбе ради, желимо да степен дефинишемо применом алгоритма множења.

Напиши пограм који израчунава на колико начина се \(n\) деце може распоредити на \(n\) столица.

Једно дете може на једну столицу сести само на један начин. Двоје деце може на две столице сести на два начина: прво дете на прву столицу, друго на другу или друго дете на прву столицу, а прво на другу. Обележимо ове начине са 12 и 21. Три детета могу сести на три столице на шест начина: 123, 132, 213, 231, 312, 321. На пример, распоред 231 означава да друго дете седи на првој столици, треће на другој, а прво дете на првој столици. Размотримо како у општем случају можемо израчунати број начина. На прву столицу може да седне било које од \(n\) деце. Након тога остаје \(n-1\) дете и исто толико столица, па на другу столицу може стати било које од те деце. На трећу столицу може сести било које од преостала \(n-2\) детета и тако даље, све док на последњу столицу не седне последње преостало дете. Зато је број начина једнак је производу бројева \(n\), \(n-1\), \(n-2\) итд. све до \(1\), тј. производу \(n\cdot(n-1)\cdot(n-2)\cdot \ldots 2\cdot 1\). Тај производ се у математици често јавља, па има посебно име и ознаку - обележава се са \(n!\), а назива факторијел броја \(n\).

Дакле, овај број можемо решити тако што израчунамо производ свих бројева од \(1\) до \(n\).

Минимум, максимум

Размотримо сада проблем одређивања највећег или најмањег елемената између неколико датих бројева. Један начин да се то уради је коришћење уграђене функције min тј. max за одређивање минимума тј. максимума листе бројева.

Ако су познате висине четири другара, одреди висину највишег од њих.

Решење засновано на листама и функцији за рачунање максимума листе смо већ раније видели.

У наставкућемо видети како да ово постигнемо и без листа и уграђених функција. Функција max се може применити на листу, међутим, могуће је применити и на више бројева. Тако смо задатак могли решити и без коришћења листе.

Често програмски језици нуде само функцију за одређивање већег тј. мањег од два задата броја (није јој могуће навести више од два аргумента). Максимум више бројева се може свести на узастопну примену ове функције.

Приметимо да смо и збир више бројева рачунали тако што смо узастопно примењивали операцију сабирања два броја. Тако је збир a + b + c + d рачунат као ((a + b) + c) + d, тј. као zbir(zbir(zbir(a, b), c), d). Ово нам указује на то да и максимум више бројева можемо израчунати на сличан начин на који смо рачунали збир - максимум иницијализујемо на први елемент и онда га у сваком наредном кораку ажурирамо на већу вредност од досадашњег максимума и текућег елемента.

Изврши претходни програм корак по корак, и прати како се мења вредност променљиве najvisi.

Ако се елементи налазе у листи или се учитавају са улаза, онда можемо да употребимо и петље.

Програм можемо да уопштимо и на већи број особа.

У оба случаја први елемент је обрађиван пре петље, различито од свих осталих. У програму у којем смо рачунали збир и производ, видели смо да све елементе можемо да обрађујемо на исти начин ако за почетну вредност узмемо 0, тј. 1, јер су то вредности које не утичу на збир (рекли смо да се такве вредности називају неутралним). Наиме, важи да је \(a + b + c = ((0 + a) + b) + c\) тј. да је zbir(zbir(a, b), c) исто што и zbir(zbir(zbir(0, a), b), c), зато што за било који број a важи да је zbir(a, 0) једнак a. Питање је да ли нешто слично можемо да урадимо и за минимум тј. максимум. Потребно је да пронађемо вредност x тако да за било који број a важи да је max(x, a) = a, тј. број који је мањи или једнак било ком другом броју. То је у општем случају број минус бесконачно \(-\infty\), међутим, њега не умемо да запишемо у програму. Ако знамо да међу бројевима чији ћемо максимум рачунати неће бити бити негативних, онда за почетну вредност можемо узети нулу јер у том случају важи да је max(max(a, b), c) = max(max(max(0, a), b), c).

Слично, ако знамо да ће сви бројеви чији максимум рачунамо бити већи или једнаки неком броју x за почетну вредност можемо узети тај број (или било који број мањи од њега).

Када рачунамо минимум, за почетну вредност треба да узмемо вредност која је већа или једнака било ком другом броју, а то је вредност плус бесконачно \(+\infty\). Ако знамо да су сви бројеви чији минимум рачунамо мањи или једнаки неком броју x за почетну вредност можемо узети тај број (или било који број већи од њега).

Проналажење максимума тј. минимума може се реализовати и без употребе функције max тј. min. Функцију која рачуна већи од два броја можемо једноставно реализовати коришћењем гранања.

Ако то узмемо у обзир тада najvisi = max(visina, najvisi) можемо заменити следећом наредбом гранања.

Лако се примећује да je наредба гранања сувишна (јер не производи никакав видљив ефекат).

Тако се највећа висина може наћи на следећи начин, без употребе функције max (пошто знамо да су све висине позитивне, максимум иницијализујемо на нулу).

Слично можемо израчунати и најмању висину (минимум ћемо иницијализовати на први елемент листе).

Тражење максимума три или четири броја се може засновати и на испитивању свих могућих односа тих бројева. На пример,

Као што видите, сва ова решења су веома ружна и стога их треба избегавати.

Карел се налази испред поља са лоптицама и жели да сазна колики је највећи број лоптица на неком од поља испред њега. Број лоптица на пољу на којем се налази Карел може сазнати позивом функције broj_loptica_na_polju(). Карел тренутно само изговара број лоптица на сваком пољу. Поправи програм тако да се исправно израчунава највећи број лоптица.

Please try loading this page in HTML5 enabled web browsers. All the latest versions of famous browsers such as Internet explorer, Chrome, Firefox, Opera support HTML5.

(карел_тражи_максимум)

Некада нас не занима вредност максимума тј. минимума, већ позиција на којој се тај максимум тј. минимум налази. Да бисмо то израчунали, потребно је да уз текућу вредност максимума тј. минимума памтимо и текућу вредност његове позиције.

Радица је добијала џепарац током пет дана у недељи. Ког дана је добила највећи џепарац (ако је то понедељак онда испиши 1, ако је то уторак онда 2 и тако даље).

Лепше решење се може добити ако се употреби петља:

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

Ако се тражи позиција максималне вредности у листи, тада је довољно памтити само позицију текућег максимума, пошто се текућа вредност максимума може прочитати из листе када се позиција зна. Потребно је само обратити пажњу на то да се индекси (позиције елемената) у листи броје од нуле.

Пресликавање

У неким ситуацијама потребно је применити једну те исту формулу на више различитих вредности. На пример, желимо да направимо таблицу површина квадрата за све дужине странице од 1 до 10.

Један начин да се то уради је да у петљи прођемо кроз све вредности од 1 до 10 и да у телу петље за сваку ту вреднос израчунамо квадрат и испишемо га.

Израчунавање површине може бити и урађено уз помоћ посебне функције.

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

Приметимо један детаљ у претходном задатку. Функција прима три параметра, a, b и c, а чланови листе су уређене тројке. Да би се уређена тројка распаковала и да би се функцији проследила три параметра, употребљен је симбол *.

Током 1980-их година постојала је једна симпатична реклама за крем Ципирипи у којој је у тексту песмице сваки самогласник (а, е, и, о, у) мењан у и.

Напиши програм који извршава ту трансформацију текста.

Компрехенсија

Језик Python нуди и посебан начин да се нека формула примени на сваки елемент листе или скупа. У математици сте виђали запис \(\{a^2\ |\ a \in S\}\), који означава скуп квадрата бројева \(a\) за све вредности \(a\) које припадају скупу \(S\). Овоме одговара запис {a * a for a in S}, а уместо скупова могу се користити и листе [a * a for a in S]. Приметимо да спољашње заграде одређују да ли се гради скуп или листа вредности, да се уместо усправне црте користи реч for а уместо симбола \(\in\) реч in. На тај начин можемо одредити површине квадрата чије су странице дате у листи и без коришћења класичне петље.

Поново је могуће користити и помоћну функцију за израчунавање површине, а могуће је као изворну листу употребити и функцију range.

Филтрирање

У многим задацима је потребно одредити који од неколико датих елемената задовољавају неки дати услов. Посматрајмо, на пример, наредни задатак.

У аква-парку на тобоган могу да иду само ђаци који су високи бар 140 центиметара. Ако су познате висине неколико деце, испиши имена оних који могу да користе тобоган.

Ако је дат мали број деце (на пример, троје), јасно је да је ово само једноставна вежба гранања.

Додавањем грана else можемо уједно и пријавити ко од њих не може на тобоган.

Приметимо да се за свако дете понавља исти код, тако да је задатак много боље решити уз помоћ петље (чак и када је број деце мали). Исправи услов у наредном програму тако да ради исто као и претходни.

Као део софтвера који обучава децу елементарној математици постављен нам је задатак да напишемо део програма који одређује све парне бројеве у некој датој листи.

Структура програма је поново иста - петља која пролази кроз све елементе серије и гранање унутар петље којим се проверава да ли текући елемент задовољава услов. У овом примеру потребно је проверити да ли је број паран, што се, подсећамо те, може урадити тако што се провери да ли је његов остатак при дељењу са 2 једнак нули. Поправи наредни програм у складу са тим.

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

Структура програма је опет иста - у петљи пролазимо слово по слово речи и у телу петље за свако слово провервамо да ли је самогласник.

Алгоритам филтрирања се може једноставно комбиновати са алгоритмима које смо раније описали (сабирања, множења, бројања, налажења минимума и максимума).

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

На такмичењу су учествовали ђаци и позната је листа која садржи имена ученика и освојени број поена. На наредни ниво такмичења су се пласирали сви они ученици који су освојили 50 и више поена. Напиши програм који израчунава просечан број поена ученика који су се пласирали даље.

Основна структура програма је поново заснована на филтрирању. У петљи се пролази кроз листу парова, у телу петље се врши провера да ли се ученик пласирао (провером његовог броја поена) и ако јесте, онда се врши ажурирање броја пласираних и збира поена свих пласираних такмичара.

Компрехенсија

Слично као што смо за пресликавање користили запис који подсећа на скупове у математици и за филтрирање је могуће учинити нешто слично. У математици можемо користити запис \(\{x\ |\ x \in S, P(x)\}\) што означава скуп свих оних елемената \(x\) који припадају скупу \(S\) и уз то задовољавају и неко својство \(P\). На пример, скуп позитивних елемената скупа целих бројева \(Z\) се може означити са \(\{x\ |\ x \in Z, x > 0\}\). У језику Python подржан је веома сличан запис. {x for x in S if P(x)} означава скуп свих елемената x који припадају S и за које важи услов P. Слично, [x for x in S if P(x)] означава листу таквих елемената. На пример, листа парних елемената из листе l се може изградити са [x for x in l if x % 2 == 0].

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

Коришћењем овога задатак у којем се тражи израчунавање поена такмичара који су се пласирали на наредни ниво можемо решити још једноставније, тако што ћемо прво изградити листу поена такмичара који су се пласирали, а онда наћи просек елемената те листе (тако што ћеш збир елемената те листе поделити њеним бројем елемената, тј. њеном дужином) - тај последњи део задатака теби препуштамо да допуниш.

Претрага

Претрагом можемо проверити да ли у листи постоји елемент који задовољава неки услов (на пример, да ли међу бројевима постоји неки број који је паран или да ли међу речима постоји нека која почиње самогласником). Веома слични проблеми томе су да се провери да ли сви елементи листе задовољавају неки услов (на пример, да ли су сви бројеви позитивни), да ли постоји неки елемент који не задовољава услов или да ли ниједан од елемената не задовољава услов. Могуће је одређивати и на којој се позицији налази елемент који задовољава услов и слично.

На пример, да бисмо проверили да ли су сва три другара одлични ученици и могу да уђу бесплатно на базен, можемо употребити следећи услов.

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

Нагласимо једну важну особину израчунавања логичких услова који су повезани везником and тј. и или везником or тј. или - они су “лењи”. Услови се проверавају редом, један по један, сдесна налево. Пошто је у претходном програму Огњенов просек мањи од 4.50, још не знамо да ли је бар неко од ученика одличан и потребно је прећи на проверу наредног ученика. Међутим, када се утврди да је Мира одличан ученик (пошто је њен просек већи од 4.50), тада већ знамо да је бар један од три ученика одличан и нема потребе вршити даље провере (потпуно је небитно колики просек оцена има Јелица). Оператор or је дакле, лењ, што значи да када се приликом израчунавања израза облика a or b утврди да је први део a тачан, тада се други део b уопште ни не израчунава (цео израз има вредност тачно). Слично, ако бисмо приликом провере да ли су сви ученици одлични утврдили да неки од њих није одличан, знали бисмо да није тачно да су сви ученици одлични и даље провере не би требало вршити. Дакле, и опетатор and је лељ, што значи да када се приликом израчунавања израза облика a and b утврди да је први део a нетачан, тада се други део b уопште ни не израчунава (цео израз има вредност нетачно).

Претпоставимо сада да желимо да одредимо да ли су сви ученици чији су просеци оцена дати у једној листи одлични. Један од начина да се то уради је да се употреби библиотечка функција all која добија листу истинитосних вредности и враћа вредност True ако су све вредности у листи True тј. вредност False ако то није случај (тј. ако у листи постоји бар једна вредност False). Поређење редом свих просека са 4.50 тј. добијање листе логичких вредности које одговарају томе да ли је сваки од ученика одличан можемо остварити помоћу компрехенсије.

Слично, да бисмо проверили да ли постоји бар један одличан ученик можемо употребити библиотечку функцију any којом се проверава да ли је бар један елемент листе логичких вредности једнак True.

Прикажимо сада како да без употребе библиотечких функција проверимо да ли су сви ученици одлични. Чуваћемо логичку променљиву svi_odlicni која ће на крају примене алгоритма имати вредност True тј. тачно, ако и само ако су сви ученици одлични. На почетку претпостављамо да су сви ученици одлични (и у то ћемо веровати све док не пронађемо ученика који није одличан) и у складу са тим вредност променљиве svi_odlicni иницијализујемо на True. Након тога проверавамо један по један просек из листе и ако је мањи од 4.50, тада смо пронашли ученика који није одличан и у складу са тим вредност променљиве svi_odlicni мењамо на False. На крају, у зависности од вредности променљиве svi_odlicni исписујемо коначан резултат.

Приметимо да овај поступак донекле одговара поступку израчунавања збира, производа, минимума и максимума и слично. Проверу да ли су сва три ученика одлична извршили смо помоћу израза облика prosek1 >= 4.5 and prosek2 >= 4.5 and prosek3 >= 4.5. Дакле, комбинују се три истинитосне вредности применом оператора and, веома слично као што смо обим троугла израчунали комбиновањем три бројевне (нумеричке) вредности коршћењем оператора +. Један од начина да се израчуна обим био је да се његова вредност прво иницијализује на вредност 0, а да се затим на то додаје једна по једна дужина странице. Вредност 0 је одабрана као вредност која не утиче на збир (када додамо било који број на вредност 0 добија се баш тај број). Слични поступак може се применити и на проверу услова да ли су сви ученици одлични.

Иницијална вредност True је у овом случају опет таква да не утиче на резултат тј. таква вредност да када се она оператором and тј. логичким и искомбинује са било којим логичким изразом, добија се вредност тог логичког израза (вредност израза облика True and uslov је иста као и вредност израза uslov).

Ефекат доделе svi_odlicni = svi_odlicni and prosek >= 4.5 је такав да ако је променљива svi_odlicni имала вредност False, онда је и десна страна False и та додела нема никаквог ефекта. Ако променљива svi_odlicni има вредност True и ако је ученик одличан, онда је вредност десне стране True и додела ни тада нема никаквог ефекта. Једини случај у којем додела има ефекат је када променљива svi_odlicni има вредност True, а када ученик није одличан, јер се тада вредност променљиве svi_odlicni мења на False. Зато се претходни алгоритам може изразити и на следећи начин.

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

Постоји још један аспект који може да допринесе ефикаснијем извршавању. Наиме, већ смо причали да су оператори and и or лењи и да израчунавају само онолико колико им је потребно да би одредили коначан резултат. Када у петљи наиђемо на ученика који није одличан јасно је да нису сви ученици одлични и да нема потребе проверавати остале ученике. Дакле, чим се пронађе један ученик чији је просек оцена мањи од 4.50 и када се вредност променљиве svi_odlicni постави на false, петља може да се прекине. Један начин да се то уради је да се наведе наредба break.

Други начин је да се уместо петље for употреби петља while у којој ће се мењати индекси у листи. Основно решење уз употребу петље while може се формулисати на следећи начин.

Рани прекид (који одговара лењом израчунавању) можемо остварити тако што се услов петље ојача тиме да су сви до тада виђени ученици одлични чиме се обезбеђује да се петља заврши чим променљива svi_odlicni добије вредност false (или када индекс i достигне дужину листе).

Као што смо већ видели, провера да ли постоји бар један елемент који задовољава неки услов се формулише веома слично, једино што се уместо оператора and који представља логичко и користи оператор or који представља логичко или. Најједноставнији и најјдиректнији начин био је да се неколико услова повежу оператором or. Међутим, да бисмо обрадили већи број елемената, можемо употребити и логичку променљиву postoji_odlican и ажурирати је. Размисли о томе шта треба да буде њена иницијална вредност.

Слично као што је додела svi_odlicni = svi_odlicni and prosek >= 4.50 имала ефекта само ако променљива svi_odlicni имала вредност False и ако је просек мањи 4.50, тако и додела postoji_odlican = postoji_odlican or prosek >= 4.50 има ефекта само ако променљива postoji_odlican има вредност False и ако је ученик одличан тј. ако је просек већи или једнак 4.50. Измени претходни програм у складу са тим.

На крају, претходни програм можемо организовати и помоћу петље и тако га уопштити на већи број ученика.

Допуни претходни програм наребом break тако да се израчунавање прекине чим је могуће.

На крају, проверимо колико смо разумели претрагу тако што ћемо помоћи Карелу да провери да ли се на свим пољима испред њега налазе лоптице. Проверу да ли постоји лоптица на пољу на ком се робот налази можеш извршити позивом ima_loptica_na_polju().

Please try loading this page in HTML5 enabled web browsers. All the latest versions of famous browsers such as Internet explorer, Chrome, Firefox, Opera support HTML5.

(карел_проверава_1)

Покрени претходни програм неколико пута, да би се уверио да ради и у ситуацијама када су сва поља попуњена лоптицама и када нису.

Помози му сада да провери да ли постоји бар једно поље са лоптицом испред њега.

Please try loading this page in HTML5 enabled web browsers. All the latest versions of famous browsers such as Internet explorer, Chrome, Firefox, Opera support HTML5.

(карел_проверава_2)