Задаци: Гранање на основу припадности интервалима¶
Алгоритми и програми у програмском језику C: Гранање на основу припадности интервалима.
Агрегатно стање¶
Прочитај текст задатка.
Из формулације задатка произилази да имамо три агрегатна стања, која настају у следећим температурним интервалима:
ако температура није виша од \(0^{\circ}\,C\) - агрегатно стање је чврсто;
ако је температура виша од \(0^{\circ}\,C\) и нижа од \(100^{\circ}\,C\) - агрегатно стање је течно;
ако температура није нижа од \(100^{\circ}\,C\) - агрегатно стање је гасовито.
Одавде произилази кôд са три међусобно независна услова, којима се у произвољном редоследу проверава припадност температуре једном од три интервала \((-\infty,0]\), \((0,100)\) и \([100,\infty)\).
Предложено решење задатка (1)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int t;
scanf("%d", &t);
if (t <= 0)
printf("cvrsto");
if (t > 0 && t < 100)
printf("tecno");
if (t >= 100)
printf("gasovito");
return 0;
}
Међутим, до решења се може доћи и уз коришћење такозване конструкције
else-if, следећим поступком:
ако температура „није виша” од \(0^{\circ}\,C\) - агрегатно стање је чврсто;
у противном (температура је виша од \(0^{\circ}\,C\)): ако је температура нижа од \(100^{\circ}\,C\) (припада другом интервалу) - агрегатно стање je течно;
у противном (температура је виша или једнака \(100^{\circ}\,C\)): агрегатно стање је гасовито.
Предложено решење задатка (2)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int t;
scanf("%d", &t);
if (t <= 0)
printf("cvrsto");
else if (t < 100)
printf("tecno");
else
printf("gasovito");
return 0;
}
Аналогно, претходном решењу можемо проверавати припадност температуре интервалу, али идући здесна од интервала \([100,\infty)\).
Предложено решење задатка (3)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int t;
scanf("%d", &t);
if (t >= 100)
printf("gasovito");
else if (t > 0)
printf("tecno");
else
printf("cvrsto");
return 0;
}
Успех ученика¶
Прочитај текст задатка.
Одређивање успеха врши се на основу припадности датог просека интервалима.
Један начин за решавање задатка је да за сваки успех, независно један од другог, проверимо да ли просек припада одговарајућем интервалу. Проверу да ли ученик има одличан успех вршимо утврђујући да ли је просек већи или једнак 4,5, за врло добар успех проверавамо да ли је просек већи или једнак 3,5 а мањи од 4,5, и слично за остале успехе.
Предложено решење задатка (1)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
double prosek;
scanf("%lf", &prosek);
if (prosek >= 4.5)
printf("odlican");
if (prosek >= 3.5 && prosek < 4.5)
printf("vrlodobar");
if (prosek >= 2.5 && prosek < 3.5)
printf("dobar");
if (prosek >= 2 && prosek < 2.5)
printf("dovoljan");
if (prosek == 1)
printf("nedovoljan");
return 0;
}
Можемо приметити неке недостатке таквог решења:
када утврдимо да ученик има један успех, нема потребе да проверавамо да ли ученик постиже неки други успех;
када утврдимо да ученик не постиже успех који смо проверавали онда то можемо искористити за проверу следећег успеха.
Наведене недостатке превазилазимо тако што провере не вршимо независно једну од
друге. Проверавамо редом успехе од одличног до недовољног (можемо и од
недовољног до одличног) и при томе у следећој провери увек користимо оно шта
смо закључили у претходној, коришћењем конструкције else-if. Прво проверимо
да ли је ученик постигао одличан успех тј. да ли му је просек већи или једнак
4,5, ако јесте прикажемо одговарајућу поруку, а ако није настављамо даљу
проверу. Сада знамо да је просек ученика мањи од 4,5 па при провери да ли је
ученик постигао врло добар успех тај услов не проверавамо већ само да ли је
просек већи или једнак 3,5. На исти начин настављамо по потреби провере за
добар и довољан успех, и на крају ако ниједан услов није испуњeн ученик има
недовољан успех.
Предложено решење задатка (2)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
double prosek;
scanf("%lf", &prosek);
if (prosek >= 4.5)
printf("odlican");
else if (prosek >= 3.5)
printf("vrlodobar");
else if (prosek >= 2.5)
printf("dobar");
else if (prosek >= 2)
printf("dovoljan");
else
printf("nedovoljan");
return 0;
}
Одмор на пола пута¶
Прочитај текст задатка.
Пошто се на свакој деоници путник кретао равномерно, пређени пут на свакој
деоници може се израчунати на основу формулa \(s_1=v_1\cdot t_1\),
\(s_2=v_2\cdot t_2\), \(s_3=v_3\cdot t_3\). Зато је половина пређеног пута на
растојању \(s_{pola}=(s_1+s_2+s_3)/2\). Да бисмо израчунали после колико времена
је дошао до те половине, анализираћемо да ли та средина пута лежи на првој,
другој или трећој деоници. Ако је на првој (ако је \(s_{pola}\leq s_1\)), тада се
време може израчунати као \(s_{pola}/v_1\). Ако је на другој (ако је
\(s_1<s_{pola}\leq s_1+s_2\)), тада се време може израчунати као
\(t_1+(s_{pola}-s_1)/v_2\) (прву деоницу је прешао за време \(t_1\), а онда је у
другој прешао пут \(s_{pola}-s_1\) крећући се брзином \(v_2\)). На крају, ако је на
трећој (ако је \(s_1+s_2<s_{pola}\leq s_1+s_2+s_3\)), тада се време може
израчунати као \(t_1+t_2+(s_{pola}-(s_1+s_2))/v_3\) (прву и другу деоницу је
прешао за време \(t_1+t_2\), а онда је у трећој деоници прешао пут
\(s_{pola}-(s_1+s_2)\) крећући се брзином \(v_3\)). Одређивање на којој деоници је
средина пута врши се одређивањем интервала ком израчуната вредност припада, што
се може урадити конструкцијом else-if.
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
double t1, v1, t2, v2, t3, v3;
scanf("%lf%lf%lf%lf%lf%lf", &t1, &v1, &t2, &v2, &t3, &v3);
double s1 = t1 * v1;
double s2 = t2 * v2;
double s3 = t3 * v3;
double sp = (s1 + s2 + s3) / 2.0;
double tp;
if (sp <= s1)
tp = sp / v1;
else if (sp <= s1 + s2)
tp = t1 + (sp - s1) / v2;
else
tp = t1 + t2 + (sp - (s1 + s2)) / v3;
printf("%.3lf", tp);
return 0;
}
Растојање од тачке до дужи¶
Прочитај текст задатка.
Посматрајмо дуж \(A_0A_1\) за тачке \(A_0(x_0,0)\) и \(A_1(x_1,0)\) и поделу равни на три дисјунктна подскупа:
Свим тачкама \(A\in S_l\) најближа тачка дужи \(A_0A_1\) је тачка \(A_0\). Докажимо ово тако што ћемо претпоставити супротно, тј. претпоставити да је нека тачка \(A'\in A_0A_1\) ближа тачки \(A\) него тачка \(A_0\). У троуглу \(AA_0A'\) страница \(AA'\) која лежи наспрам тупог угла \(\angle AA_0A'\) већа је од странице \(AA_0\) која лежи наспрам оштрог угла \(\angle AA'A_0\), што је контрадикција у односу на нашу претпоставку.
Аналогно, свим тачкама \(A\in S_d\) најближа је тачка \(A_1\).
Тачкама \(A\in S_s\) најближа је њихова нормална пројекција \(A_n\) на дуж \(A_0A_1\). Докажимо то тако што ћемо претпоставити супротно, да постоји нека тачка \(A'\in A_0A_1\) која је ближа тачки \(A\) него тачка \(A_n\). У троуглу \(AA_nA'\) дуж \(AA'\) је хипотенуза и лежи наспрам правог угла, па мора бити дужа од катете \(AA_n\) која лежи наспрам оштрог угла, што је контрадикција.
Ако тачка \(A\) има координате \((x,y)\), тада је њено растојање од тачке \(A_0\)
једнако \(\sqrt{(x-x_0)^2+y^2}\), а од тачке \(A_1\) једнако је
\(\sqrt{(x-x_1)^2+y^2}\) (ово следи на основу Питагорине теореме). Пројекција
\(A_n\) има координате \((x,0)\) тако да је њено растојање од тачке \(A\) једнако
\(\sqrt{(x-x)^2+(y-0)^2}=|y|\). Припадност тачке скуповима \(S_l\), \(S_s\) или \(S_d\)
врши се гранањем на основу интервала реалне праве којима припада тачка \(x\),
обично конструкцијом else-if.
Предложено решење задатка (1)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
int main(void)
{
double x0, x1, x, y;
scanf("%lf%lf%lf%lf", &x0, &x1, &x, &y);
double rastojanje;
if (x < x0)
rastojanje = sqrt((x0 - x) * (x0 - x) + (0 - y) * (0 - y));
else if (x <= x1)
rastojanje = fabs(y);
else
rastojanje = sqrt((x1 - x) * (x1 - x) + (0 - y) * (0 - y));
printf("%.5lf", rastojanje);
return 0;
}
Анализа би била једноставнија ако бисмо заједно померили (транслирали) тачку \(A\) и дуж \(A_0A_1\) (не мењајући њихов међусобни положај), тако да се дуж нађе на \(x\) оси са средиштем у координатном почетку, а тачка \(A\) у првом квадранту или на његовој граници. Ово можемо да постинемо у неколико корака.
Најпре дуж \(A_0A_1\) и тачку \(A\) померамо за вектор \((-x_0-\frac{d_x}{2},0)\), где је \(d_x=x_1-x_0\) дужина дужи \(A_0A_1\). Ово чинимо тако што на координате крајњих тачака дужи \(A_0A_1\) и тачке \(A\) додамо координате поменутог вектора. Тиме смо средиште дужи довели у координатни почетак.
Ако је \(x\) координата тачке \(A\) након транслације негативна, можемо да пресликамо тачку \(A\) симетрично у односу на \(y\) осу. То постижемо тако што \(x\) координату тачке \(A\) заменимо њеном апсолутном вредношћу. Тиме се растојање тачке \(A\) од дужи \(A_0A_1\) неће променити, а \(x\) координата ће бити већа или једнака нули.
На крају, ако је \(y\) координата тачке \(A\) негативна, можемо да пресликамо тачку \(A\) симетрично у односу на \(x\) осу, тј. \(y\) координату тачке \(A\) заменимо њеном апсолутном вредношћу (растојање тачке и дужи ће и даље бити исто).
После описаних померања тачке и дужи, дате тачке имају нове координате: \(A_0'=(x_0',y_0')=(-\frac{d_x}{2},0)\), \(A_1'=(x_1',y_1')=(\frac{dx}{2},0)\) и \(A'=(x',y')=(|x-x0-\frac{dx}{2}|,|y|)\). Сада је анализа случајева једноставнија. Ако је \(x'\leq x_1'\), тада је најближа тачка тачки \(A'\) њена нормална пројекција на дуж \(A_0'A_1'\) и растојање је једнако \(y'\), а ако је \(x'>x_1'\) тада је најближа тачка тачка \(A_1'\) и растојање се може израчунати као растојање између тачака \(A'\) и \(A_1'\).
Предложено решење задатка (2)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
int main(void)
{
double x0, x1, x, y;
scanf("%lf%lf%lf%lf", &x0, &x1, &x, &y);
double dx = x1 - x0;
double x0t = -dx / 2;
double x1t = dx / 2;
double xt = fabs(x - x0 + (-dx / 2));
double yt = fabs(y);
double rastojanje;
if (xt <= x1t)
rastojanje = yt;
else
rastojanje = sqrt((x1t - xt) * (x1t - xt) + (0 - yt) * (0 - yt));
printf("%.5lf", rastojanje);
return 0;
}
Школарина¶
Прочитај текст задатка.
Потребно је одредити износ попуста уколико постоји и одузети га од пуног износа школарине. Како се попуст може остварити на основу успеха или на основу такмичења, треба утврдити износе попуста на основу оба критеријума а затим, по условима задатка, применити већи попуст.
Да би одредили износ попуста на основу успеха анализираћемо ком интервалу припада просечна оцена:
одличан \([4.5,5]\)
врлодобар \([3.5,4.5)\)
добар \([2.5,3.5)\)
Попуст на основу такмичења или постоји, ако је остварен успех на такмичењу, или не.
Коначна цена се добија одузимањем добијеног износа попуста од цене школарине.
Пошто се тражи целобројни резултат, а попуст може бити реалан број, пре исписа
је потребно извршити заокруживање на најближи цео број. У језику C то можемо
урадити помоћу функције round декларисане у заглављу math.h.
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
int main(void)
{
double s, p, popust = 0;
int t;
scanf("%lf%lf%d", &s, &p, &t);
if (p >= 4.5)
popust = s * 0.4;
else if (t)
popust = s * 0.3;
else if (p >= 3.5)
popust = s * 0.2;
else if (p >= 2.5)
popust = s * 0.1;
printf("%lg", round(s - popust));
return 0;
}
Солидарни порез¶
Прочитај текст задатка.
У задатку су дефинисане три стопе пореза (\(s_0=0\), \(s_1=0.2\) и \(s_2=0.25\)) и два прага (\(p_1=60000\) и \(p_2=100000\)) динара. За бруто плате \(B\) које су мање или једнаке првом прагу износ после пореза (нето износ) се израчунава тако што се на цео износ плате примени стопа \(s_0\), тј. нето плата једнака је \(B\cdot(1-s_0)\). За плате које су између два прага, износ до првог прага (а то је \(p_1\)) се опорезује стопом \(s_0\), а износ преко првог прага (а то је \(B-p_1\)) се опорезује стопом \(s_1\), тако да је нето плата једнака \(p_1\cdot(1-s_0)+(B-p_1)\cdot(1-s_1)\). За плате које су веће од другог прага, износ до првог прага (а то је \(p_1\)) се опорезује стопом \(s_0\), износ од првог прага до другог прага (а то је \(p_2-p_1\)) се опорезује стопом \(s_1\), а износ преко другог прага (а то је \(B-p_2\)) се опорезује стопом \(s_2\), тако да је нето плата једнака \(p_1\cdot(1-s_0)+(p_2-p_1)\cdot(1-s_1)+(B-p_2)\cdot(1-s_2)\). Дакле, задатак можемо решити тако што гранањем одређујемо ком интервалу припада износ нето плате, и у зависности од интервала примењујемо одговарајућу формулу за израчунавање пореза.
Предложено решење задатка (1)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
const double s0 = 0;
const double p1 = 60000.0;
const double s1 = 0.2;
const double p2 = 100000.0;
const double s2 = 0.25;
double b, n;
scanf("%lf", &b);
if (b < p1)
n = b * (1.0 - s0);
else if (b < p2)
n = p1 * (1.0 - s0) + (b - p1) * (1.0 - s1);
else
n = p1 * (1.0 - s0) + (p2 - p1) * (1.0 - s1) + (b - p2) * (1.0 - s2);
printf("%.2lf", n);
return 0;
}
Mогуће је приметити да три формуле деле заједничке сабирке. Имајући ово у виду могуће је нето плату иницијализовати на нулу и затим додавати један по један износ. Ако је бруто плата мања од првог прага нето плата се увећава за \(B\cdot(1-s_0)\) и израчунавање се прекида. У супротном се нето износ увећава за \(p_1\cdot(1-s_0)\) и наставља се израчунавање. Ако је бруто плата мања од другог прага нето плата се увећава за \((B-p_1)\cdot(1-s_1)\) и израчунавање се прекида, а у супротном се увећава за \((p_2-p_1)\cdot(1-s_1)\), а затим и за \((B-p_2)\cdot(1-s_2)\).
Предложено решење задатка (2)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
const double s0 = 0;
const double p1 = 60000.0;
const double s1 = 0.2;
const double p2 = 100000.0;
const double s2 = 0.25;
double b, n = 0.0;
scanf("%lf", &b);
if (b < p1)
n += b * (1.0 - s0);
else
{
n += p1 * (1.0 - s0);
if (b < p2)
n += (b - p1) * (1.0 - s1);
else
{
n += (p2 - p1) * (1.0 - s1);
n += (b - p2) * (1.0 - s2);
}
}
printf("%.2lf", n);
return 0;
}
Правоугаони прстен¶
Прочитај текст задатка.
Подебљана ивица одређује правоугаони прстен који одређује два правоугаоника - унутрашњи и спољашњи (који је унија унутрашњег и ивице). Тачка припада унутрашњости правоугаоног прстена ако и само ако припада унутрашњем правоугаонику, припада прстену ако и само ако припада спољашњем, а не припада унутрашњем правоугаонику, а припада спољашњости ако и само ако не припада ни унутрашњем ни спољашњем правоугаонику. Овим се имплементација своди на имплементацију припадности тачке правоугаонику, а то се веома једноставно своди на проверу да ли је \(x\)-координата тачке између \(x\)-координата леве и десне ивице правоугаоника и да ли је \(y\)-координата тачке између \(y\)-координата горње и доње ивице правоугаоника.
Ако су координате горњег левог темена полазног правоугаоника \(x_0\) и \(y_0\), толеранција са сваке стране \(\varepsilon\), тада су координате горњег левог темена унутрашњег правоугаоника \(x_0+(\varepsilon+1)\) и \(y_0+(\varepsilon+1)\), ширина му је \(w-2(\varepsilon+1)\), a висина \(h-2(\varepsilon+1)\), док су координате горњег левог темена спољашњег правоугаоника \(x_0-\varepsilon\) и \(y_0-\varepsilon\), ширина му је \(w+2\varepsilon\), a висина \(h+2\varepsilon\).
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
const int eps = 5;
int x, y, x0, y0, w, h;
scanf("%d%d%d%d%d%d", &x, &y, &x0, &y0, &w, &h);
if ((x0 + (eps + 1)) <= x && x <= (x0 + (eps + 1)) + (w - 2 * (eps + 1)) &&
(y0 + (eps + 1)) <= y && y <= (y0 + (eps + 1)) + (h - 2 * (eps + 1)))
printf("UNUTRA");
else if ((x0 - eps) <= x && x <= (x0 - eps) + (w + 2 * eps) &&
(y0 - eps) <= y && y <= (y0 - eps) + (h + 2 * eps))
printf("NA IVICI");
else
printf("SPOLJA");
return 0;
}
Оцена на испиту¶
Прочитај текст задатка.
Једно решење се може засновати на гранању и оцена се може одредити на основу тога ком од интервала \([0,50]\), \([51,60]\), \([61,70]\), \([71,80]\), \([81,90]\) или \([91,100]\) припада број поена. Један начин да се ово уради је да се независно провери припадност сваком од ових интервала.
Предложено решење задатка (1)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int poeni, ocena = 0;
scanf("%d", &poeni);
if (poeni < 51)
ocena = 5;
if (51 <= poeni && poeni <= 60)
ocena = 6;
if (61 <= poeni && poeni <= 70)
ocena = 7;
if (71 <= poeni && poeni <= 80)
ocena = 8;
if (81 <= poeni && poeni <= 90)
ocena = 9;
if (91 <= poeni && poeni <= 100)
ocena = 10;
printf("%d", ocena);
return 0;
}
Задатак може да се реши и употребом конструкције else-if, поређењем броја
поена редом са бројевима 51, 61, 71, 81 и 91 и проверавањем да ли је број поена
строго мањи од њих.
Предложено решење задатка (2)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int poeni, ocena = 0;
scanf("%d", &poeni);
if (poeni < 51)
ocena = 5;
else if (poeni < 61)
ocena = 6;
else if (poeni < 71)
ocena = 7;
else if (poeni < 81)
ocena = 8;
else if (poeni < 91)
ocena = 9;
else
ocena = 10;
printf("%d", ocena);
return 0;
}
Једно могуће решење се заснива на посебној провери да ли је студент пао испит (добио оцену 5) и затим на коришћењу аритметике да би се одредила оцена ако је положио. Најмањи број поена потребан за оцену 6 је 51, за оцену 7 је 61 итд. Дакле, најмањи број поена потребан да би се добила оцена \(o\) је \(10\cdot(o-1)+1\). Ако је познат број поена \(p\), одговарајућа оцена је највећа оцена \(o\) таква да је \(10\cdot(o-1)+1\leq p\) тј. да је \(10\cdot(o-1)\leq p-1\), где је \(o=\left\lfloor{\frac{p-1}{10}}+1\right\rfloor\). Заиста, целобројним дељењем бројем 10, интервал \([50,59]\) се пресликава у број 5, интервал \([60,69]\) у број 6 и слично. Зато, ако се од од бројева из интервала \([51,60]\) одузме 1, одреди целобројни количник са 10 и на резултат дода 1, добија се тражена оцена 6. Слично важи и за све наредне интервале, тако да се оцена може израчунати тако што се од броја поена одузме 1, израчуна целобројни количник са 10 и на то дода 1.
Предложено решење задатка (3)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int poeni;
scanf("%d", &poeni);
int ocena = poeni < 51 ? 5 : (poeni - 1) / 10 + 1;
printf("%d", ocena);
return 0;
}