Prijavi problem


Obeleži sve kategorije koje odgovaraju problemu

Još detalja - opišite nam problem


Uspešno ste prijavili problem!
Status problema i sve dodatne informacije možete pratiti klikom na link.
Nažalost nismo trenutno u mogućnosti da obradimo vaš zahtev.
Molimo vas da pokušate kasnije.

Programiranje u Pajtonu, priručnik za šesti razred

Час 16 - Основни алгоритми - пресликавање, филтрирање, претрага

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

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

Површине свих квадрата

Напиши програм који исписује таблицу површина квадрата за све дужине странице од 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 једнак нули. Поправи наредни програм у складу са тим.

Сви самогласници

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

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

Филтрирање помоћу компрехенсије

Слично као што смо за пресликавање користили запис који подсећа на скупове у математици и за филтрирање је могуће учинити нешто слично. У математици можемо користити запис \(\{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].

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

Комбиновање елементарних алгоритама

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

Број самогласника

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

Број лоптица испред Карела

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

Робот се помера једно по једно поље све до краја лавиринта. За свако поље се проверава да ли на њему постоји лоптица и ако постоји, тада је робот yзима и увећава бројач лоптица за један.

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_loptice)

Просечан број поена такмичара који су се квалификовали

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

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

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

Претрага

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

Да ли су сви одлични?

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

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

Нагласимо једну важну особину израчунавања логичких услова који су повезани везником 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)