Задаци: Подсерије¶
Алгоритми и програми у програмском језику C: Подсерије.
Ледене недеље¶
Прочитај текст задатка.
Задатак захтева да се серија улазних бројева подели на своје седмочлане подсерије и да се затим за сваку седмочлану подсерију провери да ли садржи само негативне бројеве (што се може урадити алгоритмом линеарне претраге).
Задатак је, могуће решити са две угнежђене петље. Спољна петља обезбеђује учитавање \(K\) недеља (њена бројачка променљива може да се мења од 0, па све док је мања од \(K\)), док се у унутрашњој петљи (њена бројачка променљива може да се мења од 1 до 7), учитавају температуре за сваки дан.
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int k;
scanf("%d", &k);
int brln = 0;
for (int i = 0; i < k; i++)
{
int ln = 1;
for (int j = 0; j < 7; j++) {
int t;
scanf("%d", &t);
if (t >= 0)
ln = 0;
}
if (ln)
brln++;
}
printf("%d", brln);
return 0;
}
Распоред пакета на полицама¶
Прочитај текст задатка.
Један начин да задатак решимо је да употребимо угнежђене петље, тако што у спољној петљи обрађујемо полицу по полицу, док у унутрашњој попуњавамо сваку појединачну полицу.
Унутрашња петља има задатак да прочита податке о предметима на текућој полици и
одреди њихов број, укупну масу и податак о томе да ли се током читања предмета
дошло до краја улаза или није. Tо можемо постићи аглоритмом сабирања учитаних
елемената. Пре унутрашње петље (на почетку тела спољашње петље) број предмета и
њихова укупна маса се иницијализују на нулу. Унутрашња петља се извршава све
док се не учита \(K\) предмета или док се не учита ознака за крај (предмет са
димензијом 0). Након сваке учитане масе предмета, проверава се да ли она
представља ознаку краја. Ако не, тада се број учитаних предмета увећава за 1,
док се укупна маса увећава за масу тог предмета. У супротном се помоћна
променљива која означава да ли се дошло до краја улаза, а која је на почетку
програма иницијализована на вредност 0, поставља на вредност 1. Та
променљива се употребљава и у услову спољашње и у услову унутрашње петље, тако
да ће њено постављање на 1 проузроковати да се обе петље прекину пре преласка
на њихову наредну итерацију.
Спољашња петља има задатак да одреди вредност и позицију максимума у серији израчунатих укупних тежина предмета на полицама. Пре петље уводе се променљиве у којима се памти највећа до сада виђена маса на полици и редни број полице на којој се та маса налази и иницијализују се на вредност нула. Након изласка из унутрашње петље (без обзира на то да ли је прочитано \(K\) предмета или је прочитана ознака за крај), проверава се да ли је на тој полици било предмета (да ли је њихов број израчунат унутрашњом петљом већи од нуле) и ако јесте, да ли је маса предмета на тој полици већа од до тада највеће виђене масе. Ако јесте, ажурира се вредност максимума и редни број полице на којој се тај максимум налази (он се поставља на редни број текуће полице који се увећава за 1 у сваком кораку спољашње петље). При том, ако на текућој полици има предмета, исписује се њихова укупна маса.
Предложено решење задатка (1)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int k, br_naj_pol = 1, naj_m = 0, tek_br_pol = 1, kraj = 0;
scanf("%d", &k);
while (!kraj)
{
int tek_m = 0, tek_br_pred = 0;
while (tek_br_pred < k && !kraj)
{
int m;
scanf("%d", &m);
if (m == 0)
kraj = 1;
else
{
tek_br_pred++;
tek_m += m;
}
}
if (tek_m > naj_m)
{
naj_m = tek_m;
br_naj_pol = tek_br_pol;
}
if (tek_br_pred > 0)
printf("%d ", tek_m);
tek_br_pol++;
}
printf("\n");
printf("%d", br_naj_pol);
return 0;
}
Други начин за решавање овог задатка избегава употребу угнежђених петљи. У
једној петљи се учитава један по један предмет, проверавајући да ли је учитана
ознака за крај. Ако јесте, логички индикатор краја, који је уједно и услов
петље, се поставља на вредност 1, чиме се проузрокује да се након завршетка
извршавања тела петље она прекине. Ако није учитана ознака краја, већ маса
неког предмета, број предмета на текућој полици се увећава за 1, а маса
предмета на текућој полици се увећава за ураво учитану масу. Након учитавања
проверава се да ли је завршена обрада текуће полице тј. да ли је броj предмета
на њој једнак \(K\) или је учитана ознака за крај (што можемо одредити помоћу
вредности логичког индикатора краја). Ако јесте, тада, ако на полици има
предмета (тј. ако је број предмета на текућој полици већи од нуле), тада се
исписује маса предмета на њој и она се упоређује са тежином до тада најтеже
полице и ако је управо учитана полица тежа, ажурира се максимум (уједно
ажурирајући и редни број полице). Након тога, ако се није дошло до краја, тада
се врши припрема за обраду наредне полице тако што се за један увећа редни број
полице, а текућа маса и број предмета на полици поставе на нулу.
Предложено решење задатка (2)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int k, br_naj_pol = 1, naj_m = 0, tek_br_pol = 1, tek_br_pred = 0, tek_m = 0, kraj = 0;
scanf("%d", &k);
while (!kraj)
{
int m;
scanf("%d", &m);
if (m == 0)
kraj = 1;
else
{
tek_br_pred++;
tek_m += m;
}
if (tek_br_pred == k || kraj)
{
if (tek_br_pred > 0)
{
printf("%d ", tek_m);
if (tek_m > naj_m)
{
naj_m = tek_m;
br_naj_pol = tek_br_pol;
}
}
if (!kraj)
{
tek_br_pol++;
tek_br_pred = 0;
tek_m = 0;
}
}
}
printf("%d", br_naj_pol);
return 0;
}
Збирови сегмената низа између нула¶
Прочитај текст задатка.
Oснову решења чини алгоритам сабирања серије елемената. Дакле, одржаваћемо променљиву у којој се памти збир (у овом случају ће то бити збир текућег сегмента) и увећаваћемо је за учитане елементе текућег низа који су различити од нуле (они продужавају текући сегмент). Итерацију можемо организовати на један од следећа два начина.
Један начин је да употребимо угнежђене петље. Спољна петља ће вршити итерацију кроз све сегменте, док ће се у унутрашњој учитавати и сабирати елементи појединачних сегмената. Помоћу променљиве \(i\) одржаваћемо број учитаних елемената и у условима обе петље водићемо рачуна да он не премаши укупан број елемената \(n\). У телу спољашње петље биће реализован алгоритам учитавања и сабирања елемената серије бројева све до прве учитане нуле или до задатог броја елемената. На почетку, пре унутрашње петље иницијализоваћемо суму на нулу. У унутрашњој петљи ћемо учитавати текући елемент и увећавати број прочитаних елемената. Ако је учитани елемент различит од нуле, тада он продужава текући сегмент и додаје се на суму. Ако је учитани елемент једнак нули, текући сегмент се завршава, петља се прекида и након унутрашње петље се исписује сума. Ако је последњи учитани елемент био нула (тј. ако се последњи сегмент завршио нулом), на основу дефиниције задатка иза њега долази још један, празан, сегмент, тако да се након спољашње петље проверава овај специјалан случај (због тога променљива која чува текући елемент мора бити декларисана ван спољашње петље).
Предложено решење задатка (1)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, s = 0, i = 0;
scanf("%d", &n);
while (1)
{
s = 0;
int k = 0;
while (1)
{
if (i == n)
{
k = 1;
break;
}
int x;
scanf("%d", &x);
i++;
if (x == 0)
break;
s += x;
}
printf("%d\n", s);
if (k)
break;
}
return 0;
}
Други начин је да у само једној петљи чије се тело извршава \(n\) пута учитавамо један по један број. Када је учитани број различит од нуле, текући сегмент се продужава и тај број додајемо на суму елемената текућег сегмента. Када се учита нула, текући сегмент се завршава. Тада је потребно исписати текућу суму текућег сегмента (јер је он управо завршен) и након тога јој вредност поново поставити на нулу (чиме се она припрема за израчунавање суме наредног сегмента). Пошто се последњи сегмент не мора завршити нулом, његову суму треба исписати по завршетка уноса свих елемената.
Предложено решење задатка (2)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, s = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
int x;
scanf("%d", &x);
if (x == 0)
{
printf("%d\n", s);
s = 0;
}
else
s += x;
}
printf("%d\n", s);
return 0;
}
Најдужа серија победа¶
Прочитај текст задатка.
За сваку позицију i одређујемо дужину најдужег сегмента победа који почиње на позицији \(i\). Једном када одредимо да је то сегмент \([i,j]\), време значајно можемо уштедети тако што приметимо да ни један сегмент победа који почиње на позицијама након \(i\), а закључно са \(j\) не може бити дужи од сегмента који почиње на позицији \(i\) (јер ако позиција \(j\) није последња у низу, на позицији иза ње се налази пораз). Зато је након ширења сегмента који почиње на позицији \(i\) надесно и одређивања серије победа који почињу на позицији \(i\) могуће директно прећи на израчунавање најдужег сегмента победа који почиње на позицији \(j+1\) (ако таква постоји) и прескачемо анализу сегмената који почињу на позицијама између \(i+1\) и \(j\) (вршимо одсецање).
Овај алгоритам је заправо и врло интуитиван и вероватно је први алгоритам који би програмер са мало искуства имплементирао: крећемо од почетка, проналазимо серију победа који почиње на почетку, након тога тражимо наредну серију победа која наступа након те прве серијe, затим серију победа која наступа након те друге серије итд. Дакле, цео низ делимо на мање сегменте, такве да је сваки од њих оптималан у смислу да га није могуће продужити (ни на лево, ни на десно) и анализирамо само њих.
Током имплементације није неопходно да памтимо резултате свих утакмица истовремено у низу. У једној петљи ћемо читати резултате мечева и у сваком тренутку одржавати дужину текуће и дужину најдуже до тада пронађене серије (сегмента) победа. Пошто на почетку нисмо видели још ни један резултат, обе променљиве иницијализујемо на нулу. Затим, у петљи, учитавамо и обрађујемо резултате утакмица. Ако је тим победио, тада текућа утакмица продужава текућу серију победа и њену дужину увећавамо за један. Ако је тим изгубио, тада се прекида евентуална серија победа и текућа серија победа има дужину 0 (јер је утакмица којом та серија почиње изгубљена).
Након завршетка читања сваке серије победа потребно је ажурирати дужину најдуже серије (ако је дужина текуће серије дужа од до тада најдуже, потребно је дужину најдуже поставити на дужину текуће). То се дешава или када се наиђе на утакмицу у којој је тим поражен или након петље, када је последња евентуална серија победа завршена. Треба бити веома обазрив да се не заборави на последњу серију победу, тј. да се не заборави поређење текуће и најдуже серије након завршетка петље.
Предложено решење задатка (1)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, dt = 0, dn = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
int r;
scanf("%d", &r);
if (r == 1)
dt++;
else
{
if (dt > dn)
dn = dt;
dt = 0;
}
}
if (dt > dn)
dn = dt;
printf("%d", dn);
return 0;
}
Још један начин да имплементирамо поделу низа на серије победа и пораза је да употребимо угнежђене петље, при чему је задатак унутрашње петље да учита елементе и израчуна дужину текуће серије победа. У унутрашњој петљи се чита резултат по резултат, све док се не наиђе на пораз или се не дође до краја низа свих резултата. Након учитавања пораза унутрашња петља се завршава и прелази се на следећу итерацију спољашње петље. Тај пораз није део неке серије победа, тако да се он може једноставно занемарити.
Предложено решење задатка (2)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, i = 0, dn = 0;
scanf("%d", &n);
while (i < n)
{
int dt = 0;
while (i < n)
{
int r;
scanf("%d", &r);
i++;
if (r != 1)
break;
dt++;
}
if (dt > dn)
dn = dt;
}
printf("%d", dn);
return 0;
}
Најдужу серију победа можемо одредити тако што се за сваку позицију у низу одреди најдужи низ победа који се завршава на тој позицији и тако што се пронађе максимум свих тако добијених дужина.
У једној петљи читамо резултате мечева и у сваком тренутку одржавамо дужину текуће и дужину најдуже до тада пронађене серије (сегмента) победа. Пошто на почетку нисмо видели још ни један резултат, обе променљиве иницијализујемо на нулу. Затим, у петљи, учитавамо и обрађујемо резултате утакмица. Ако је тим победио, тада текућа утакмица продужава текућу серију победа и њену дужину увећавамо за један. Ако је тим изгубио, тада се прекида евентуална серија победа и текућа серија победа има дужину 0 (јер ниједна серија победа не може да садржи пораз).
У сваком кораку вредност текуће дужине серије победа је управо дужина најдуже серије победа закључно са текућом утакмицом. Зато у сваком кораку ту дужину поредимо са дотадашњим максимумом и ако је потребно ажурирамо максимум. Ажурирање максимума је могуће урадити и само након продужавања текуће серије, јер након постављања дужине серије на нулу не можемо добити серију која је дужа од до тада најдуже. На крају исписујемо дужину најдуже пронађене серије.
Предност оваквог решења у односу на оно у ком се рачунају најдуже серије победа за текући леви крај сегмента, је то што не захтева посебну обраду завршне серије победа и кôд је мало униформнији (по цену евентуално чешћег ажурирања максимума).
Предложено решење задатка (2)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, dt = 0, dn = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
int r;
scanf("%d", &r);
if (r == 1)
{
dt++;
if (dt > dn)
dn = dt;
}
else
dt = 0;
}
printf("%d", dn);
return 0;
}
Серија сјајних партија¶
Прочитај текст задатка.
Прилично је очигледно да није неопходно проверавати све серије дужине \(k\), да би се проверило да ли постоји серија дужине \(k\). Можемо за сваку позицију \(i\) рачунати дужину најдуже серије сјајних партија која почиње на позицији \(i\) (при чему \(i\) креће од нуле) и проверити да ли је нека од тих серија дужине бар \(k\). Дужину серије рачунамо инкрементално, проширујући је од позиције \(i\) надесно, све док су партије сјајне (ако су све партије у некој серији сјајне и ако се након тога одигра сјајна партија, све партије у проширеној серији су такође сјајне). Ако се најдужа серија сјајних партија која почиње на позицији \(i\) завршава на позицији \(j\) и ако је та серија дужа од потребне дужине \(k\), успешно завршавамо поступак (поступак може бити прекинут и чим та серија достигне дужину \(k\)). У супротном знамо да су све њене подсерије (оне које крећу на позицијама између \(i+1\) и \(j\)) такође краће од \(k\), па анализу можемо наставити од позиције \(i=j+1\). Дакле, када се заврши нека серија сјајних партија која је краћа од \(k\), проверу одмах треба наставити од позиције иза партије која је прекинула серију. Овим једноставним одсецањем добијамо ефикасан алгоритам. Потребно је само бити пажљив и не заборавити проверу последње серије.
Предложено решење задатка (1)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int pp, pds, n, ps = 0, dts = 0;
scanf("%d%d%d", &pp, &pds, &n);
for (int i = 0; i < n; i++)
{
int bp;
scanf("%d", &bp);
if (bp > pp)
dts++;
else
{
if (dts >= pds)
ps = 1;
dts = 0;
}
}
if (dts >= pds)
ps = 1;
printf(ps ? "da" : "ne");
return 0;
}
Можемо рачунати дужину најдуже серије узастопних сјајних партија анализирајући инкрементално дужину најдуже серије сјајних партија која се завршава на свакој позицији и пријавити успех ако и само ако у неком тренутку та дужина достигне вредност \(k\).
Предложено решење задатка (2)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int pp, pds, n, ps = 0, dts = 0;
scanf("%d%d%d", &pp, &pds, &n);
for (int i = 0; i < n; i++)
{
int bp;
scanf("%d", &bp);
if (bp >= pp)
{
dts++;
if (dts >= pds)
{
ps = 1;
break;
}
}
else
dts = 0;
}
printf(ps ? "da" : "ne");
return 0;
}
Серије бројева исте парности¶
Прочитај текст задатка.
Најједноставнији начин да се задатак уради је читање једног по једног елемента (у једној петљи), уз одржавање укупног броја прочитаних елемената, текућег елемента, првог елемента у текућој серији парних тј. непарних елемената и збира елемената у тој текућој серији.
Пре почетка петље учитавамо први елемент, иницијализујемо збир текуће серије на његову вредност, и број прочитаних елемената на један, при чему морамо водити рачуна о специјалном случају када је улазни низ празан (у том случају је потребно једноставно изаћи из програма, без читања и једног елемента).
Након тога, у петљи која се извршава све док нису учитани сви елементи читамо текући елемент (увећавајући при том број учитаних елемената) и проверавамо да ли је исте парности као први елемент текуће серије (провера да ли су два броја исте парности може се извршити упоређивањем њихових остатака при дељењу са 2).
Ако су текући број и први елемент текуће серије исте парности, тада тај елемент продужава текућу серију и додаје се на текући збир.
У супротном, серија је завршена и исписује се њен збир. Број који је прочитан започиње нову серију, тако да се први елемент серије и збир постављају на његову вредност.
Након читања свих елеменатa променљива збир садржи вредност збира последње серије и потребно је засебно је исписати након петље.
Предложено решење задатка (1)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n;
scanf("%d", &n);
if (!n)
return 0;
int p;
scanf("%d", &p);
int s = p;
int bp = 1;
while (bp < n)
{
int t;
scanf("%d", &t);
bp++;
if (p % 2 == t % 2)
s += t;
else
{
printf("%d\n", s);
p = t;
s = p;
}
}
printf("%d", s);
return 0;
}
Током рада одржаваћемо елемент којим почиње текућа серија и његов редни број (бројања ћемо започињати од нуле). На самом почетку програма, пре петље, учитаћемо први елемент прве серије и његов редни број ћемо иницијализовати на нулу. Спољна петља се извршава све док се не заврши са обрадом свих серија, што ће бити случај када год је редни број првог елемента текуће серије мањи од укупног броја елемената.
У телу спољашње петље одржаваћемо наредни елемент текуће серије и његов редни
број, који ћемо иницијализовати на вредност редног броја првог елемента текуће
серије увећану за један. Унутрашњу петљу ћемо извршавати све док је редни број
наредног елемента мањи од укупног броја елемената или док се у њеном телу не
установи да је прочитан елемент који не припада текућој серији. На почетку тела
унутрашње петље учитавамо наредни елемент (јер је на основу услова петље
установљено да он постоји) и проверавамо да ли он припада текућој серији (да ли
је исте парности као први елемент текуће серије). Ако не припада, унутрашња
петља се прекида (наредбом break), а ако припада, он се додаје текућој серији
тако што се увећава њен збир елемената и редни број наредног елемента. По
завршетку унутрашње петље се исписује збир елемената текуће серије.
Редни број првог елемента наредне серије се поставља на редни број наредног елемента. Aко је тај редни број мањи од укупног броја елемената, онда је наредни елемент већ учитан и установљено је да је различите парности од првог елемента управо завршене серије, тако да први елемент наредне серије постављамо на њега. Ако се дошло до краја, овај корак је сувишан (наредни елемент, заправо није ни учитан), али, с обзиром на то да се неће вршити наредне итерације спољашње петље, овај корак ништа не квари.
Приметимо да је овај приступ прилично сличан приступу са низом елемената истовремено учитаних у меморију и да променљива \(i\) у том коду одговара редном броју првог елемента у серији, а променљива \(j\) редном броју наредног елемента у серији.
Предложено решење задатка (2)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, p;
scanf("%d%d", &n, &p);
int bp = 0;
while (bp < n)
{
int s = p, bn = ++bp, r = 0;
while (bn < n)
{
scanf("%d", &r);
if (!(p % 2 == r % 2))
break;
s += r;
bn++;
}
printf("%d\n", s);
bp = bn;
p = r;
}
return 0;
}
Планирање изградње продавница¶
Прочитај текст задатка.
Серију кућа у селу поделићемо на подсерије кућа које опслужују појединачне
продавнице. Првој подсерији припада прва кућа и све оне иза ње које су на
растојању највише R од ње, наредна кућа започиње другу серију итд.
Елементи сваке подсерије се одређују као елементи који су у некој релацији са првим елементом серије, док први елемент који није у тој релацији започиње наредну серију. У овом задатку тражи се одређивање дужине сваке серије и укупан број серија.
Предложено решење задатка (1)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, r, br_prod = 0, poc_kuca, br_blis = 1;
scanf("%d%d%d", &n, &r, &poc_kuca);
for (int i = 1; i < n; i++)
{
int tek_kuca;
scanf("%d", &tek_kuca);
if (tek_kuca - poc_kuca <= r)
br_blis++;
else
{
printf("%d\n", br_blis);
br_prod++;
poc_kuca = tek_kuca;
br_blis = 1;
}
}
printf("%d\n", br_blis);
br_prod++;
printf("%d", br_prod);
return 0;
}
Задатак се може решити и угнежђеним петљама.
Предложено решење задатка (2)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, r, br_prod = 0, poc_kuca, br_poc = 0;
scanf("%d%d%d", &n, &r, &poc_kuca);
while (br_poc < n)
{
int br_nar = br_poc + 1;
int nar_kuca;
while (br_nar < n)
{
scanf("%d", &nar_kuca);
if (nar_kuca - poc_kuca > r)
break;
br_nar++;
}
printf("%d\n", br_nar - br_poc);
br_prod++;
br_poc = br_nar;
poc_kuca = nar_kuca;
}
printf("%d", br_prod);
return 0;
}
Утовар транспортног брода¶
Прочитај текст задатка.
У решењу одржавамо:
редни број текуће серије (редни број колица),
број њених елемената (број предмета на колицима)
њихов збир (укупну масу предмета на колицима),
податке о вредности и редном броју максимума (највећем до тада виђеном броју предмета на колицима и редном броју тих колица).
У петљи учитавамо податке о предметима и након учитавања сваког, проверавамо да ли је учитана ознака за крај (нула). Ако јесте постављамо индикатор краја којим ће петља бити прекинута након завршетка извршавања њеног тела.
Након тога, проверавамо да ли се завршило са попуњавањем текућих колица. То се дешава у два случаја: када је учитана ознака за крај или када је збир текуће масе предмета на колицима и управо учитаног предмета већа од носивости. Тада се исписује број и маса пакета на њима и, ако је потребно, ажурира се максимум. Ако се није стигло до краја, припремају се нова колица тиме што се увећа њихов редни број, а број и маса пакета на текућим колицима поставе на нулу.
Ако се није стигло до краја, учитани предмет се поставља на колица тиме што се увећа број и маса предмета на колицима. Ово ће се десити и у случају када предмет стаје на текућа колица, а и у случају када предмет није стајао на текућа колица и када су зато започета нова колица (ово ће бити први предмет на тим новим).
Не би била грешка ни да су се нова колица започела и број и маса предмета на њима ажурирали и у случају када је учитана ознака краја - пошто се наредна итерација петље неће извршавати, ирелевантно је како ће се мењати вредности променљивих у текућој итерацији.
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, br_kol = 1, m_kol = 0, br_pak = 0, max_kol = 1, max_pak = 0, k = 0;
scanf("%d", &n);
while (!k)
{
int m_pak;
scanf("%d", &m_pak);
if (m_pak == 0)
k = 1;
if (k || m_kol + m_pak > n)
{
printf("%d %d\n", br_pak, m_kol);
if (br_pak > max_pak)
{
max_pak = br_pak;
max_kol = br_kol;
}
if (!k)
{
br_kol++;
br_pak = 0;
m_kol = 0;
}
}
if (!k)
{
m_kol += m_pak;
br_pak++;
}
}
printf("%d", max_kol);
return 0;
}
Најдужа растућа серија¶
Прочитај текст задатка.
Није довољно посматрати појединачна времена пливача, већ је потребно
проверавати однос времена у суседним данима (да ли су елементи низа поређани у
растућем поретку утврђујемо поређењем суседних елемената). Зато, у петљи
одржавамо две променљиве у којима се чувају претходни и текући елемент серије,
при чему се први елемент пре петље учитава у променљиву p, док се на крају
тела петље текући елемент проглашава за претходни, како бисмо се припремили за
наредну итерацију у петљи (алтернативно, могли бисмо текући елемент учитавати
пре петље, а онда на почетку тела петље текући елемент доделити претходном и
учитати нову вредност текућег елемента).
У програму ћемо одржавати и променљиве у којима се памти почетак и дужина текуће растуће серије, као и почетак и дужина најдуже до тада пронађене растуће серије. Када се учита први елемент низа, он сам за себе представља једночлану растућу серију и стога се дужина текуће серије и дужина најдуже серије иницијализују на 1. Пошто та серија почиње на самом почетку, а бројање креће од 1, почетак текуће и почетак најдуже серије такође иницијализујемо на 1.
У телу петље учитавамо текући елемент и поредимо га са претходним. Ако је текући већи, текућа растућа серија се наставља и њену дужину повећавамо за 1. Након тога можемо да проверимо да ли се тиме добила серија дужа од најдуже и, ако јесте, тада ажурирамо почетак и дужину најдуже серије (примењујемо, дакле, и алгоритам одређивање максимума серије бројева, тј. прецизније, алгоритам одређивања позиције максимума серије бројева). Ажурирање вршимо само ако је нова серија строго дужа од дотада најдуже, јер се у случају постојања више серија исте дужине тражи приказ прве од њих. Ако текући није већи, тада он започиње нову растућу серију (за сада једночлану), чији је почетак на текућој позицији. Пошто смо једночлану серију већ срели (на самом почетку), ова серија не може бити дужа од текуће и стога нема је потребе упоређивати са најдужом.
Опет се, дакле, решење добија као максимум бројева \(d_i\) који представљају дужине најдуже растуће серије елемената која се завршава елементом на позицији \(i\) (позиције овај пут бројимо од 0). Можемо, дакле, дати и формулацију решења у облику динамичког програмирања. Важи да је \(d_0=1\) (пошто по условима задатка постоји бар један елемент тј. \(n\geq 1\), а једночлана серија се по дефиницији датој у задатку може сматрати растућом). Ако је \(a_i>a_{i-1}\) тада је \(d_i=d_{i-1}+1\), док је у супротном \(d_i=1\).
Предложено решење задатка (1)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, p, t, poc_t = 1, duz_t = 1, poc_n = 1, duz_n = 1;
scanf("%d%d", &n, &p);
for (int i = 2; i <= n; i++)
{
scanf("%d", &t);
if (t > p)
{
duz_t++;
if (duz_t > duz_n)
{
duz_n = duz_t;
poc_n = poc_t;
}
}
else
{
duz_t = 1;
poc_t = i;
}
p = t;
}
printf("%d\n%d", poc_n, duz_n);
return 0;
}
Напоменимо и да је позицију почетка текуће растуће серије могуће израчунати током извршавања петље, тако што се од индекса текућег елемента одузме дужина текуће растуће серије и дода 1, тако да није било неопходно памтити почетак текуће серије.
Предложено решење задатка (2)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, p, t, duz_t = 1, poc_n = 1, duz_n = 1;
scanf("%d%d", &n, &p);
for (int i = 2; i <= n; i++)
{
scanf("%d", &t);
if (t > p)
{
duz_t++;
}
else
{
if (duz_t > duz_n)
{
duz_n = duz_t;
poc_n = i - duz_t;
}
duz_t = 1;
}
p = t;
}
if (duz_t > duz_n)
{
duz_n = duz_t;
poc_n = n - duz_t + 1;
}
printf("%d\n%d", poc_n, duz_n);
return 0;
}
Најдужи сегмент узастопних бројева¶
Прочитај текст задатка.
Ово је још један у низу задатака у којем се тражи дужина најдуже серије узастопних елемената који задовољавају неки дати услов.
Оптимално решење се може добити ако се примени инкременталност и ако се дужина најдуже серије узастопних бројева која се завршава на некој позицији одреди на основу познате дужине најдуже серије узастопних бројева која се завршава на претходној позицији.
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, p, duz_tek = 1, duz_naj = 1;
scanf("%d%d", &n, &p);
for (int i = 1; i < n; i++)
{
int t;
scanf("%d", &t);
if (t == p + 1)
duz_tek++;
else
duz_tek = 1;
if (duz_tek > duz_naj)
duz_naj = duz_tek;
p = t;
}
printf("%d", duz_naj);
return 0;
}
Најстабилнији температурни период¶
Прочитај текст задатка.
У овом задатку сматра се да текући елемент продужава серију ако је апсолутна разлика између њега и њему претходног елемента мања или једнака задатом броју.
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int n, k, t, duz_tek = 1, poc_naj = 1, duz_naj = 1;
scanf("%d%d%d", &n, &k, &t);
for (int i = 2; i <= n; i++)
{
int p = t;
scanf("%d", &t);
if (abs(t - p) <= k)
{
duz_tek++;
if (duz_tek >= duz_naj)
{
duz_naj = duz_tek;
poc_naj = i - duz_tek + 1;
}
}
else
duz_tek = 1;
}
printf("%d\n%d", poc_naj, duz_naj);
return 0;
}