Задаци: Минимум и максимум¶
Алгоритми и програми у програмском језику C: Минимум и максимум.
Најнижа температура¶
Прочитај текст задатка.
У решењу овог задатка применићемо уобичајени алгоритам за одређивање минимума, при чему ћемо, пошто број елемената серије није унапред фиксиран, елементе учитавати и обрађивати у петљи. Током извршавања алгоритма одржаваћемо вредност текућег минимума тј. најмању од свих до тада учитаних температура. Ту вредност можемо иницијализовати на први прочитани елемент серије тј. на температуру у првом граду. Затим, у сваком проласку кроз петљу читамо температуру у следећем граду и проверавамо да ли је њена вредност мања од текућег минимума. Ако јесте, ажурирамо вредност текућег минимума и постављамо га на температуру учитану у том кораку. На крају, када се учитају и обраде сви елементи серије, вредност текућег минимума биће уједно и вредност минимума целе серије тј. најнижа температура у свим градовима.
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, t;
scanf("%d%d", &n, &t);
int min = t;
for (int i = 1; i < n; i++)
{
scanf("%d", &t);
if (t < min)
min = t;
}
printf("%d", min);
return 0;
}
Најтоплији дан¶
Прочитај текст задатка.
Пошто је седам прилично велики број, алгоритам за одређивање позиције максимума има пуно понављања (практично копирања и лепљења истих наредби, уз мале измене). Боље решење се може добити уз употребу петљи.
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int t, br = 1, br_max = 1;
scanf("%d", &t);
int t_max = t;
for (int i = 2; i <= 7; i++)
{
scanf("%d", &t);
br++;
if (t > t_max)
{
t_max = t;
br_max = i;
}
}
printf("%d", br_max);
return 0;
}
Просек скокова¶
Прочитај текст задатка.
Резултат можемо добити тако што одредимо збир свих оцена, број унетих оцена, одредимо најмању и највећу оцену, па од добијеног збира одузмемо најмању и највећу оцену и одредимо просек. Број оцена није фиксиран и за рачунање збира, минимума и максимума користимо петље.
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int o;
scanf("%d", &o);
int s, i, min, max;
s = min = max = o;
i = 1;
while (scanf("%d", &o) != EOF)
{
i++;
s += o;
if (o < min)
min = o;
else if (o > max)
max = o;
}
s -= min + max;
double p = (double)s / (double)(i - 2);
printf("%.2lf", p);
return 0;
}
Најближи датом целом броју¶
Прочитај текст задатка.
Растојање између два броја једнако је њиховој апсолутној разлици. Две процене ученика се пореде тако што се прво упореди њихово растојање до тачне вредности \(x\), а ако су оне једнаке, онда се пореде по величини. Приметимо да се овде ради о лексикографском поретку. Број \(a\) представља бољу процену од броја \(b\) ако и само ако важи \(|a-x|<|b-x|\) или ако је \(|a-x|=|b-x|\) и \(a>b\).
Дакле, потребно је пронаћи максималну вредност међу бројевима који се пореде не
само на основу величине, већ на основу описане релације лексикографског
поретка. То је могуће урадити модификацијом алгоритма за одређивања максимума
тј. минимума серије бројева. Приликом поређења вредности тренутно учитаног
броја са тренутном вредношћу минимума, уместо обичне примене релације <
треба применити лексикографски поредак.
Предложено решење задатка (1)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
int main(void)
{
double x, n, br;
scanf("%lf%lf%lf", &x, &n, &br);
double nbr = br;
for (int i = 1; i < n; i++)
{
scanf("%lf", &br);
if (fabs(br - x) < fabs(nbr - x))
nbr = br;
if (fabs(br - x) == fabs(nbr - x) && br > nbr)
nbr = br;
}
printf("%.2lf", nbr);
return 0;
}
Поређење можемо реализовати и једним сложеним логичким изразом којим се врши лексикографско поређење.
Предложено решење задатка (2)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
int main(void)
{
double x, n, br, r;
scanf("%lf%lf%lf", &x, &n, &br);
double nbr = br;
double nr = fabs(x - nbr);
for (int i = 1; i < n; i++)
{
scanf("%lf", &br);
r = fabs(x - br);
if (r < nr || r == nr && br > nbr)
{
nbr = br;
nr = r;
}
}
printf("%.2lf", nbr);
return 0;
}
Број максималних¶
Прочитај текст задатка.
У овом задатку комбинује се одређивање максимума серије елемената (што радимо на уобичајени начин) и број појављивања неког елемента у серији.
Кључни увид који нам омогућава да задатак решимо само једним пролазом кроз елементе серије и да их не морамо памтити истовремено у меморији је то да се максимум у низу јавља онолико пута колико се јавља и у делу низа од првог свог појављивања па до краја. Дакле, када наиђемо на елемент који је максимум до тада обрађеног дела низа, он постаје нови кандидат за глобални максимум и од те тачке надаље бројимо његова појављивања (ако је строго већи од претходног кандидата за максимум, сигурни смо да се до ове тачке раније није јављао).
Да бисмо одредили број такмичара са најбољим резултатом морамо одредити и вредност најбољег резултата. Током рада програма ћемо у једној променљивој чувати максимум свих до сада учитаних поена такмичара, док ће друга променљива чувати број појављивања те највеће вредности међу до сада учитаним поенима такмичара. Максимум ћемо иницијализовати на вредност поена првог учитаног такмичара, док ћемо број његових појављивања иницијализовати на 1. Затим ћемо учитавати и анализирати поене осталих такмичара. Приликом анализе броја поена ученика могућа су три случаја:
број поена је строго већи од текућег максимума, и у том случају се поставља нови текући максимум и његов број појављивања се поставља на 1;
број поена је једнак текућем максимуму, и у том случају се његов број појављивања повећава за 1;
број поена је мањи од текућег максимума, у ком случају се не предузима никаква акција.
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, p;
scanf("%d%d", &n, &p);
int max = p;
int br_max = 1;
for (int i = 1; i < n; i++)
{
scanf("%d", &p);
if (p > max)
{
max = p;
br_max = 1;
}
else if (p == max)
br_max++;
}
printf("%d", br_max);
return 0;
}
Други на ранг листи¶
Прочитај текст задатка.
Задатак можемо решити тако што пратимо текућу највећу вредност и другу вредност на ранг листи међу учитаним бројевима. Читамо један по један број и упоређујемо га са текућим вредностима прва два елемента.
Ако је учитани број строго већи од вредности текућег максимума, друга вредност на ранг листи добија вредност текућег максимума, а текући максимум постаје број који смо учитали.
Иначе, ако је учитани број (строго) већи од текуће друге вредности на ранг листи, коригујемо другу вредност на ранг листи.
Остаје питање како иницијално поставити ове две вредности (наизглед није јасно
које су вредности првог и другог елемента по реду у празном или једночланом
скупу). Најприроднији начин је да се учитају два елемента, да се упореде и да
се на основу њиховог редоследа изврши иницијализација. Међутим, слично као и у
случају одређивања једног максимума, можемо употребити иницијализацију на неку
специјалну вредност која има улогу вредности \(-\infty\). Пошто су учитани
бројеви из интервала \([0,100]\), можемо иницијализовати обе вредности на -1.
Заиста, након учитавања првог броја, он ће сигурно бити већи од \(-1\) (вредности
првог максимума), па ће вредност првог елемента на ранг-листи бити постављена
на њега, а вредност другог елемента на ранг-лист на \(-1\). Након учитавања
другог елемента он ће бити или већи од првог елемента на ранг-листи и тада се
вредност првог елемента на ранг-листи поставити на тај, други по реду учитани
број, а вредност другог елемента на ранг-листи постаће једнака вредности првог
учитаног броја, или ће бити мањи од првог елемента на ранг-листи, али ће бити
строго већи од \(-1\), па ће вредности првог и другог елемента на ранг листи бити
редом први и други учитани број. Могуће је употребити и најмањи број који се
може репрезентовати типом int. У језику C он се може добити употребом макроа
INT_MIN декларисаног у заглављу limits.h.
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, x, max1 = -1, max2 = -1;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d", &x);
if (x > max1)
{
max2 = max1;
max1 = x;
}
else if (x > max2)
max2 = x;
}
printf("%d", max2);
return 0;
}
Друга вредност по величини¶
Прочитај текст задатка.
Одређивање другог по величини у серији од \(n\) целих бројева, можемо решити уређивањем бројева од највећег до најмањег. После уређења бројева највећи број је број \(x_1\), а други по величини је следећи број из уређене серије који је различит од \(x_1\). Ако такав број не постоји сви бројеви су једнаки. У овом случају до решења није могуће доћи једноставном применом парцијалног сортирања, јер не знамо на ком месту се у сортираном редоследу налази елемент који тражимо.
Задатак можемо решити модификацијом класичног поступка одређивања максималног елемента серије. Претпоставимо опет да знамо прву и другу вредност по величини (назовимо их првим и другим максимумом) у до сада обрађеном делу низа и размотримо како их ажурирати када се учита нови број.
Ако је учитани број строго већи од текуће вредности првог максимума, други максимум треба поставити на текућу вредност првог максимума, а први максимум треба поставити на учитани број.
Ако је учитани број мањи од текуће вредности првог максимума потребно га је упоредити са другим максимумом и ако је (строго) већи од текуће вредности другог максимума, потребно је други максимум поставити на учитани број.
Ако је учитани број једнак текућој вредности првог максимума, не радимо ништа.
Поново је проблематично питање иницијализације првог и другог максимума.
Почетну вредност оба максимума можемо поставити на неку вештачку вредност која има улогу вредности \(-\infty\) (то је обично најмања вредност целобројног типа, а у нашем задатку, пошто је допуштени интервал вредности \([1,1000]\), може се употребити \(0\) или \(-1\)). Уз овакву иницијализацију, све елементе можемо обрадити на начин који смо на почетку описали. После првог учитаног броја догодиће се да је он сигурно већи од првог максимума и тада ће вредност другог максимума постати стара вредност првог максимума (то је број који представља \(-\infty\)), док ће први максимум бити постављен на учитани број. Наредна промена ће се десити када се учита први елемент у серији који је различит од првог. Ако је строго већи од првог максимума, први максимум ће бити постављен на вредност тог броја, а други максимум на вредност првог учитаног броја, што су управо коректне иницијалне вредности за део серије који је до сада учитан. Ако је учитани елемент строго мањи од првог максимума, тада ће он остати непромењен, али ће други максимум бити постављен на тај учитани број и опет ће те две вредности бити коректно иницијализоване у односу на део серије који је до сада учитан.
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <limits.h>
int main(void)
{
int n, x, max1 = INT_MIN, max2 = INT_MIN;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d", &x);
if (x > max1)
{
max2 = max1;
max1 = x;
}
else if (x < max1 && x > max2)
max2 = x;
}
printf("%d\n%d", max1, max2);
return 0;
}
Победник у три дисциплине¶
Прочитај текст задатка.
У овом задатку је потребно одредити максимум серије елемената и његову позицију у серији, при чему су ти елементи сложеног типа (поени из три предмета) и релација поретка над њима је дефинисана на начин дефинисан условима задатка. Када мало боље размотримо дефиницију поретка између такмичара приметићемо да је у питању лексикографски поредак.
Приметимо да за одређивање победника није неопходно истовремено памтити податке о свим такмичарима, већ је могуће истовремено учитавати податке и одређивати максимум применом уобичајеног алгоритма за одређивања максимума тј. минимума.
Једно од основних питања у имплементацији решења је питање како представити податке о такмичару.
Најелементарније решење је оно у којем се подаци представљају помоћу три посебне променљиве (по једна за поене из свака три предмета). У том случају учитавамо 6 параметара (податке о два такмичара) и проверавамо да ли је један такмичар бољи од другог (тј. да ли је други лошији од првог). Поређење вршимо лексикографски, проверавајући редом један по један критеријум (прво укупан број поена, а онда, ако је укупан број поена једнак, број поена из програмирања, затим математике и на крају из физике). Када је дефинисана релација поретка, победник се одређује алгоритмом за одређивање максимума и његове позиције. Памтићемо број поена и редни број победника, прогласићемо првог такмичара за победника, а затим редом обрађивати остале такмичаре, и ако је дотадашњи кандидат за победника лошији од текућег такмичара, ажурираћемо податке о победнику.
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, p, m, f;
scanf("%d%d%d%d", &n, &p, &m, &f);
int pp = p;
int mp = m;
int fp = f;
int up = pp + mp + fp;
int np = 1;
for (int i = 2; i <= n; i++)
{
scanf("%d%d%d", &p, &m, &f);
int u = p + m + f;
if (up < u)
{
pp = p;
mp = m;
fp = f;
np = i;
up = u;
}
else if (up == u && pp < p)
{
pp = p;
mp = m;
fp = f;
np = i;
}
else if (up == u && pp == p && mp < m)
{
mp = m;
fp = f;
np = i;
}
}
printf("%d: %d %d %d", np, pp, mp, fp);
return 0;
}
Најмањи круг¶
Прочитај текст задатка.
Решење задатка је полупречник круга (са центром у координатном почетку) који је једнак растојању најудаљеније учитане тачке од координатног почетка. Растојање најудаљеније тачке од координатног почетка се одређује стандардним алгоритмом за одређивање најмањег елемента серије бројева. За прву учитану тачку треба израчунати растојање од координатног почетка и то растојање прогласити максималним. Алтернативно, пошто су сва растојања ненегативна, иницијализацију можемо извршити и на нулу (она је најмања могућа вредност растојања). Учитавање координата тачака се наставља и одређује се њиховим растојањем од координатног почетка, да би се кад год је то растојање веће од текућег максимума, максимум увећао на ту вредност. Растојање између две тачке рачуна се Питагорином теоремом.
Предложено решење задатка (1)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
int main(void)
{
int n;
scanf("%d", &n);
double cx = 0.0, cy = 0.0, max = 0.0;
for (int i = 0; i < n; i++)
{
double x, y;
scanf("%lf%lf", &x, &y);
double d = sqrt((x - cx) * (x - cx) + (y - cy) * (y - cy));
if (d > max)
max = d;
}
printf("%.5lf", max);
return 0;
}
Могуће је направити још једну додатну оптимизацију. Пошто је корена функција монотона (важи \(\sqrt{x}>\sqrt{y}\) ако и само ако важи \(x>y\)), уместо поређења растојања, можемо поредити њихове квадрате, чиме се програм мало убрзава јер се избегава скупа операција израчунавања квадратног корена.
Предложено решење задатка (2)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
int main(void)
{
int n;
scanf("%d", &n);
double cx = 0.0, cy = 0.0, max = 0.0;
for (int i = 0; i < n; i++)
{
double x, y;
scanf("%lf%lf", &x, &y);
double d = ((x - cx) * (x - cx) + (y - cy) * (y - cy));
if (d > max)
max = d;
}
double r = sqrt(max);
printf("%.5lf", r);
return 0;
}
Редни број максимума¶
Прочитај текст задатка.
У овом задатку се захтева одређивање редног броја (кажемо и позиције или износа) максималног елемента серије бројева. У овом случају број елемената серије није унапред фиксиран и потребно је употребити петљу. Овај алгоритам је проширење алгоритма одређивања вредности максималног тј. минималног елемента.
За одређивање редног броја купца који је понудио највећи износ морамо одредити
и вредност највећег износа. Током рада програма помоћу променљиве max
одржаваћемо вредност највеће понуде међу понудама које су до тог тренутка
учитане, а помоћу променљиве br одржаваћемо редни број те највеће понуде.
Променљиву max иницијализоваћемо на вредност прве учитане понуде, а br на
њен редни број 1. Након тога, у петљи ћемо учитавати износе које су остали
купци понудили. За сваки учитани износ, проверавамо да ли је тај износ већи од
текућег максимума и ако јесте, постављамо вредност променљиве max на тај
износ, док вредност променљиве br поставаљамо на редни број текућег купца (то
је тренутна вредност бројачке променљиве i).
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n;
double iznos;
scanf("%d%lf", &n, &iznos);
double max = iznos;
int br = 1;
for (int i = 2; i <= n; i++)
{
scanf("%lf", &iznos);
if (iznos > max)
{
max = iznos;
br = i;
}
}
printf("%d", br);
return 0;
}