Угнежђене петље - сегменти¶
Сегментом у серији елемената називамо подсерију која се састоји од узастопних елемената полазне серије. Тако на пример, у серији бројева {2, 8, 5, 1, 4, 9} један сегмент чине бројеви {5, 1, 4}, јер се налазе на узастопним местима у серији, а бројеви {8, 1, 4} не чине сегмент јер нису узастопни елементи полазне серије. У овој лекцији ћемо подразумевати да су сегменти непразни (мада се у општем случају и празна серија сматра сегментом).
Сегмент који садржи први елемент серије се назива префикс. На пример, сви префикси серије {2, 8, 5, 1, 4, 9} су {2}, {2, 8}, {2, 8, 5}, {2, 8, 5, 1}, {2, 8, 5, 1, 4} и {2, 8, 5, 1, 4, 9}.
Сегмент који садржи последњи елемент серије се назива суфикс. На пример, сви суфикси серије {2, 8, 5, 1, 4, 9} су {9}, {4, 9}, {1, 4, 9}, {5, 1, 4, 9}, {8, 5, 1, 4, 9} и {2, 8, 5, 1, 4, 9}.
Видимо да серија од \(n\) бројева има \(n\) префикса и \(n\) суфикса. Укупан број сегмената серије од \(n\) бројева је \({n \cdot (n+1)} \over 2\) (зашто?).
Да бисмо исписали елементе једног сегмента дате серије бројева, потребно је користити петљу. Да бисмо исписали све префиксе или све суфиксе дате серије, потребна је двострука петља, а за исписивање свих сегмената дате серије бројева чак трострука петља.
Пример - сви сегменти. Написати програм који за дато n исписује све сегменте серије {1, 2, 3, …, n}.
Све сегменте са истим почетним елементом исписати у истом реду излаза, раздвојене запетама. Елементе једног сегмента раздвојити само размаком. На пример, за n=4 треба исписати:
1, 1 2, 1 2 3, 1 2 3 4
2, 2 3, 2 3 4
3, 3 4
4
Променљива која се мења у спољњој петљи представља почетни елемент сегмента. За сваки изабрани почетак треба проћи све сегменте са тим почетком, а то постижемо другом петљом, чија променљива представља крај сегмента. Трећом петљом пролазимо све елементе тренутно актуелног сегмента (одређеног помоћу прве две петље).
Када уместо серије бројева имамо серију карактера, онда ту серију карактера можемо да сместимо у стринг. Сегмент стринга називамо подстринг или подреч. За издвајање подстринга из датог стринга можемо да користимо готове функције и тако поједноставимо програм. Тако подстринг стринга s који почиње на позицији p и има d елемената можемо да добијемо као резултат позива функције s.Substring(p, d)). На пример, „abcdefgh”.Substring(2,4) враћа као резултат стринг cdef (позиције у стрингу се броје од 0, па се на позицији 2 налази слово c).
Инкрементално рачунање¶
Када је потребно исписати све елементе сваког префикса дате серије, не можемо да избегнемо употребу више петљи (употребом функција можемо да преместимо унутрашњу петљу, али и даље имамо две петље које се извршавају једна у другој). Овакав начин употребе петљи треба увежбати јер ће нам у многим ситуацијама бити користан, али треба имати на уму да за извршавање двоструке петље може да буде потребно много више времена него за једну петљу. Зато, кад год је могуће двоструку петљу заменити једном петљом, то свакако треба учинити.
Пример - троугаони бројеви Написати програм који за унето n, у једном реду исписује првих n троугаоних бројева. Троугаони број је број објеката који формирају једнакостраничан троугао, овако:
*
* * *
* * * * * *
* * * * * * * * * *
* * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * ...
На пример, за n=6 треба исписати:
1 3 6 10 15 21
Видимо да су троугаони бројеви редом
\(T_1=1\),
\(T_2=1+2=3\),
\(T_3=1+2+3=6\),
\(T_4=1+2+3+4=10\), …`
Према томе, у задатку се тражи да се за дато n испише сума елемената сваког префикса серије {1, 2, 3, …, n}. Једно решење, по угледу на претходна, је да за сваки префикс саберемо његове елементе и испишемо збир.
Ипак, у овом случају постоји и много боље решење (иако врло слично). Ако смо претходно израчунали суму првих 99 бројева, нема потребе да терамо рачунар да суму првих 100 бројева рачуна од почетка. Уместо тога је довољно да на суму првих 99 бројева само додамо стоти број. Решење засновано на овој идеји изгледа овако:
Програм је једноставнији, а за велике вредности n и много бржи.
Приметимо узгред да смо троугаоне бројеве могли да рачунамо и по познатој Гаусовој формули, чиме бисмо задатак такође решили помоћу само једне петље. Решење које је овде дато је нешто боље и од употребе Гаусове формуле, јер не користи множење бројева (које се извршава нешто спорије него сабирање).
Пример - пирамидални бројеви Написати програм који за унето n, у једном реду исписује првих n пирамидалних бројева. У овом задатку, k-ти пирамидални број је збир првих k троугаоних бројева (види претходни пример). Рецимо, трећи пирамидални број је \(P_3 = T_1 + T_2 + T_3 = 1 + (1+2) + (1+2+3) = 1+3+6 = 10\).
Тако, на пример за n=6 треба исписати:
1 4 10 20 35 56
Искористићемо идеју из претходног примера. Уместо да сваки пирамидални број P рачунамо од почетка, можемо на претходно израчунати пирамидални број да додамо нови троугаони број T. Међутим, пошто је овај задатак сложенији од претходног, и даље изгледа као да не можемо избећи унутрашњу петљу за рачунање троугаоног броја (када бисмо сваки пирамидални број рачунали од почетка, имали бисмо троструку петљу)
Решење се ипак може написати помоћу само једне петље, у којој се упоредо рачунају троугаони и пирамидални бројеви.
Када при израчунавању више бројева, сваки нови број добијамо полазећи од претходног, кажемо да све те бројеве израчунавамо инкрементално.
У претходним примерима смо инкрементално израчунавали троугаоне и пирамидалне бројеве.
Многи задаци и реални проблеми се могу решити знатно ефикасније ако уместо независног рачунања сваког потребног броја искористимо инкрементално рачунање. О томе ће бити много више речи у курсу за други разред.
Следи квиз, а затим и задаци, на којима можете да проверите да ли сте разумели како се формирају различити сегменти серије бројева или серије слова.