Задаци: Однос суседних елемената серије¶
Алгоритми и програми у програмском језику C: Однос суседних елемената серије.
Максимална разлика суседних¶
Прочитај текст задатка.
Задатак решавамо применом алгоритма одређивања максимума серије бројева на серију апсолутних разлика суседних елемената низа.
Да бисмо одредили све апсолутне разлике суседних елемената, довољно је да у сваком тренутку помоћу две променљиве памтимо два суседна елемента оригиналне серије. Поступамо на један од следећа два начина, које ћемо употребљавати и у наредним задацима, када год је потребно да поредимо свака два суседна елемента у серијама.
Ако поступамо на први начин, на почетку први елемент учитавамо као текућу вредност, а затим, у петљи која ће се извршити \(n-1\) пута, пре учитавања нове текуће вредности тренутну текућу вредност памтимо као претходну, учитавамо текућу вредност и након тога обрађујемо претходну и текућу вредност.
ucitaj tekuci
ponovi n-1 puta:
prethodni = tekuci
ucitaj tekuci
obradi(prethodni, tekuci)
У овом конкретном задатку комбинујемо овај алгоритам са алгоритмом одређивања максимума. Пошто апсолутна разлика суседних елемената не може бити мања од 0, ову вредност, пре петље, постављамо као почетни максимум (који ће бити и крајњи резултат ако су сви елементи који се учитавају једнаки). У сваком кораку петље рачунамо апсолутну вредност разлике између претходног и текућег елемента и проверавамо да ли је она већа од текуће вредности максимума. Ако јесте, максимум добија вредност њихове апсолутне разлике, у противном не мења вредност.
Предложено решење задатка (1)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int n, p, t, max = 0;
scanf("%d%d", &n, &t);
for (int i = 2; i <= n; i++)
{
p = t;
scanf("%d", &t);
if (abs(t - p) > max)
max = abs(t - p);
}
printf("%d", max);
return 0;
}
Ако поступамо на други начин, на почетку први елемент учитавамо као претходну вредност, а затим, у петљи која ће се извршити \(n-1\) пута, учитавамо текућу вредност, обрађујемо претходну и текућу вредност и након тога текућу вредност памтимо као претходну, припремајући се тако за евентуалну наредну итерацију у којој ће текући елемент заиста бити претходни елементу који ће тада бити учитан.
ucitaj prethodni
ponovi n-1 puta:
ucitaj tekuci
obradi(prethodni, tekuci)
prethodni = tekuci
У том облику решење може бити испрограмирано на следећи начин.
Предложено решење задатка (2)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int n, p, t, max = 0;
scanf("%d%d", &n, &p);
for (int i = 2; i <= n; i++)
{
scanf("%d", &t);
if (abs(t - p) > max)
max = abs(t - p);
p = t;
}
printf("%d", max);
return 0;
}
Провера монотоности¶
Прочитај текст задатка.
Желимо да утврдимо да су елементи серије претрчаних растојања тркача поређани у строго растућем поретку, тј. да проверимо да ли су сви елементи серије од другог до последњег строго већи од свог претходника. Решење се, дакле, заснива на примени алгоритма претраге.
Довољно је упоредити свака два суседна елемента серије (претходни и текући) и
проверити да ли је текући већи од претходног. За чување претходног и текућег
елемента употребљавамо две променљиве. На пример, пре почетка петље, променљиву
која чува претходни елемент низа иницијализоваћемо на први елемент серије (он
постоји јер је серија по претпоставци задатка непразна). Затим у петљи чије се
тело извршава \(n-1\) пута учитавамо један по један елемент серије у променљиву
која чува текући eлемент серије. На крају тела петље, елемент који је био
текући проглашавамо претходним (да бисмо наредни елемент учитали у променљиву у
којој се памти текући елемент и упоредили га са тренутно текућим елементом који
постаје претходни). У телу петље поредимо претходни и текући. Ако је текући
већи, актуелна растућа серија се наставља и не мењамо логички индикатор тј.
променљиву r, коју иницијализујемо на вредност 1. Ако није, актуелна
растућа серија је завршена, те мењамо логички индикатор тј. променљиву r
поставимо на 0.
Пошто није неопходно учитати све елементе серије, чим установимо да низ није
растући можемо изаћи из петље (један начин да то урадимо је да услов петље
ојачамо додавањем логичког индикатора r, а други да употребимо наредбу
break). По завршетку петље испитујемо вредност индикатора rastuci и у
зависности од ње исписујемо одговарајућу поруку.
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, p, t, r = 1;
scanf("%d%d", &n, &p);
for (int i = 1; i < n && r; i++)
{
scanf("%d", &t);
if (p >= t)
r = 0;
p = t;
}
if (r)
printf("Da");
else
printf("Ne");
return 0;
}
Парно непарни¶
Прочитај текст задатка.
Овај задатак је поновљен у циљу увежбавања различитих техника решавања.
Један од начина да се провери дати услов је да се провери да ли остаци учитаних бројева при дељењу са два чине неопадајућу серију (серију у којој иду прво нуле, а затим јединице и никада се после јединице не јавља нула).
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int p, t, ok = 1;
scanf("%d", &p);
while (ok)
{
if(scanf("%d", &t) == EOF)
break;
if (p % 2 > t % 2)
ok = 0;
p = t;
}
printf(ok ? "da" : "ne");
return 0;
}
Растуће цифре¶
Прочитај текст задатка.
Решење задатка комбинује алгоритам одређивања серије цифара броја сдесна налево и алгоритам линеарне претраге којим проверавамо да ли у серији цифара броја постоји цифра која је није већа (већ је мања или једнака) од претходне.
Током претраге, потребно је да одржавати три променљиве - једну која садржи
вредност претходне, другу која садржи вредност текуће цифре броја и трећу
помоћну променљиву која је иницијализована са 1. Вредност претходне цифре
иницијализоваћемо пре петље. Најприродније решење је да се она иницијализује на
вредност последње цифре броја (одређене као остатак при дељењу броја са 10) и
да се пре уласка у петљу та последња цифра уклони (целобројним дељењем са 10).
У телу петље, које се извршава док број \(n\) има цифара тј. док не постане
једнак нули, одређује и уклања се текућа цифра (последња цифра у тренутној
вредности броја \(n\)). Ако се утврди да та цифра није већа од претходне, прекида
се извршавање петље и мења се вредност помоћне променљиве на 0 јер цифре нису
у растућем поретку. На крају петље, врши се припрема за следећу итерацију тако
што текућа цифра постаје претходна (вредност променљивe која чува текућу цифру
додељује се променљивој која чува претходну цифру). Ако се не прекине
извршавање петље зато што се појавила цифра која није већа од претходне, већ
зато што су све цифре броја уклоњене (након што су подвргнуте траженој
провери), вредност помоћне променљиве остаје 1 јер су цифре уређене у
растућем поретку.
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, r = 1;
scanf("%d", &n);
int p = n % 10;
n /= 10;
while (n > 0)
{
int t = n % 10;
n /= 10;
if (t <= p)
r = 0;
p + t;
}
printf(r ? "DA" : "NE");
return 0;
}
Поређани датуми¶
Прочитај текст задатка.
Потребно је проверити да ли у серији датума постоји неки који не долази после њему
претходног. За то примењујемо алгоритам линеарне претраге. Пошто се захтева
поређење свака два суседна датума, потребно је да одржавамо претходни и текући
датум. На почетку је могуће иницијализовати претходни датум првим учитаним, на
почетку петље учитавати текући датум, а онда на крају петље постављати
претходни на тај текући или иницијализовати текући датум првим учитаним, на
почетку петље постављати претходни датум на текући и након тога учитавати
текући датум. У телу петље, након учитавања сваког текућег датума провераваћемо
да ли је већи од претходног (да ли представља дан који долази хронолошки
касније). Током претраге уводимо помоћну променљиву која показује да ли су сви
до сада учитани датуми у исправном редоследу и коју иницијализујемо на 1. Ако
текући датум није већи од претходног, тада ту променљиву постављамо на 0 и
прекидамо петљу (на пример, наредбом break). На крају петље, резултат
пријављујемо у зависности од вредности те логичке променљиве.
Поредак између датума је лексикографски, ако се прво гледа година, затим месец и на крају дан. Један начин да се ово реализује је да се сваки датум представи са три одвојена броја.
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, dp, mp, gp, p = 1;
scanf("%d%d%d%d", &n, &dp, &mp, &gp);
for (int i = 1; i < n; i++)
{
int dt, mt, gt;
scanf("%d%d%d", &dt, &mt, >);
if (!((gt > gp) || (gt == gp && mt > mp) || (gt == gp && mt == mp && dt > dp)))
{
p = 0;
break;
}
dp = dt;
mp = mt;
gp = gt;
}
printf(p ? "DA" : "NE");
return 0;
}
Тестераст низ¶
Прочитај текст задатка.
Ово је још један од задатака у којима се проверава однос суседних елемената. Поново елементе читамо у петљи, одржавајући вредност претходног и текућег елемента серије и користимо алгоритам линеарне претраге да проверимо да ли у серији постоји елемент који нарушава задати однос. Разлика је у томе што уместо да стално проверавамо да ли је претходни елемент мањи од текућег, у овом случају наизменично проверавамо да ли је претходни елемент мањи од текућег, па да ли је претходни елемент већи од текућег итд.
Једно могуће решење је да се уведе помоћна променљива која одређује да ли у наредном поређењу текући елемент треба да буде мањи или већи од претходног. Почетну вредност ове променљиве одређујемо на основу односа прва два елемента серије (њих морамо обрадити пре петље), а онда је у сваком кораку петље негирамо (ако се у једном кораку очекивало да претходни број буде мањи од текућег, у наредном кораку се очекује да претходни корак треба да буде већи од текућег). Приликом претраге поређење елемената се врши на основу текуће вредности те променљиве.
Предложено решење задатка (1)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, p, t, r = 1, v;
scanf("%d%d%d", &n, &p, &t);
if (p > t)
v = 0;
else if (p < t)
v = 1;
else
r = 0;
for (int i = 2; i < n && r; i++)
{
p = t;
scanf("%d", &t);
if ((v && !(p > t )) || (!v && !(p < t)))
r = 0;
v = !v;
}
printf(r ? "DA" : "NE");
return 0;
}
Пошто се у низу налазе бројеви, можемо понудити и мало другачије решење. Наиме, важи да је \(x>y\) ако и само ако је \((-1)\cdot x<(-1)\cdot y\). Ако је \(a_1<a_2\), \(a_2>a_3\), \(a_3<a_4\) итд., тада је \(1\cdot a_1<1\cdot a_2\), \((-1)\cdot a_2<(-1)\cdot a_3\), \(1\cdot a_3<1\cdot a_4\) итд. Обратно, ако важи \(a_1>a_2\), \(a_2<a_3\), \(a_3>a_4\) итд., тада важи \((-1)\cdot a_1<(-1)\cdot a_2\), \(1\cdot a_2<1\cdot a_3\), \((-1)\cdot a_3<(-1)\cdot a_4\) итд. То значи да се провера да ли је низ тестераст своди на итеративно поређење релацијом мање узастопних елемената помножених наизменично са 1 па -1, односно -1 па 1 (те вредности памтимо у посебној бројевној променљивој чија почетна вредност зависи од односа прва два елемента низа, а која у сваком кораку петље мења знак). Нагласимо још и да је ово решење могло бити примењено зато што је условима задатка гарантовано да се на улазу не може јавити најмањи негативан број (проблем са њим је то што се множењем са -1 не може добити њему супротан број, јер се тај број обично не може исправно репрезентовати).
Предложено решење задатка (2)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, p, t, r = 1, z;
scanf("%d%d%d", &n, &p, &t);
if (p > t)
z = 1;
else if (p < t)
z = -1;
else
r = 0;
for (int i = 2; i < n && r; i++)
{
p = t;
scanf("%d", &t);
if (z * p >= z * t)
r = 0;
z = -z;
}
printf(r ? "DA" : "NE");
return 0;
}