Задаци: Логички оператори¶

Алгоритми и програми у програмском језику C: Логички оператори.

Радно време¶

Мејл је стигао током радног времена ако и само ако је сат у интервалу $[9,17)$ тј. ако је већи или једнак $9$ и строго мањи од $17$ (број минута је небитан).

Иако математичка нотација допушта да се запише услов $a\leq c<b$, у програмским језицима такав запис најчешће није исправан. То је случај и у језику C и тај услов треба записати као a <= c && c < b. Додатно, треба бити веома обазрив јер је израз a <= c < b синтаксно исправан, али даје погрешну вредност (овде се истинитосна вредност израза a <= c тумачи као бројевна вредност 0 или 1 и она се онда пореди са бројевном вредношћу b).

Наравно, слично бисмо поступили и у случају потпуно отворених или потпуно затворених интервала, једино треба правилно одабрати одговарајући релацијски оператор ($<$ или $\leq$).

Предложено решење задатка

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int sat, minut;
    scanf("%d%d", &sat, &minut);
    if (9 <= sat && sat < 17)
        printf("da");
    else
        printf("ne");
    return 0;
}

Кућни ред¶

Прочитај текст задатка.

Једно решење можемо засновати на томе да су радови дозвољени ако и само ако сат припада интервалу $[6,13)$ или $[17,22)$.

Предложено решење задатка (1)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int sat;
    scanf("%d", &sat);
    if ((6 <= sat && sat < 13) || (17 <= sat && sat < 22))
        printf("moze");
    else
        printf("ne moze");
    return 0;
}

Друго решење можемо засновати на томе да радови нису дозвољени ако и само ако је сат мањи од шест, ако припада интервалу $[13,17)$ или је већи или једнак $22$.

Предложено решење задатка (2)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int sat;
    scanf("%d", &sat);
    if (sat < 6 || (13 <= sat && sat < 17) || (sat >= 22))
        printf("ne moze");
    else
        printf("moze");
    return 0;
}

Постоји ли троугао датих дужина страница¶

Прочитај текст задатка.

Познато је да је дужина сваке странице троугла мања од збира дужина друге две странице (ова особина се назива неједнакост троугла). Да би троугао са дужинама страница $a$, $b$ и $c$ постојао, довољно је да важи $a<b+c$, $b<a+c$ и $c<a+b$. Ако важе сва три услова постоји троугао са датим страницама, иначе не постоји такав троугао. Бројеви $a$, $b$ и $c$ су по претпоставци задатка позитивни, тако да тај услов није неопходно посебно проверавати.

Напоменимо и да се неједнакост троугла некада помиње и у облику у којем се тражи да је разлика дужина сваке две странице мања од дужине треће странице, но, тај услов није потребно посебно проверавати јер он следи из услова за збир страница (на пример, ако се покаже да је $a<b+c$, тада важи и да је $a-b<c$ и да је $a-c<b$).

Пошто сва три услова треба да важе, могуће је повезати их оператором логичке конјункције (оператором И тј. &&).

Предложено решење задатка

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    double a, b, c;
    scanf("%lf%lf%lf", &a, &b, &c);
    if (a < b + c && b < a + c && c < a + b)
        printf("da");
    else
        printf("ne");
    return 0;
}

Преступна година¶

Прочитај текст задатка.

По грегоријанском календару, који је у званичној употреби, година је преступна ако је дељива са 4, а није дељива са 100 или је дељива са 400. Тиме се постиже да је на 400 година тачно 97 преступних и да је трајање једне године 365,2425 дана, што је веома блиску трајању астрономске године. Проверу дељивости вршимо израчунавајући остатак при дељењу и провером да ли је он једнак нули.

Предложено решење задатка

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int godina;
    scanf("%d", &godina);
    if ((godina % 4 == 0 && godina % 100 != 0) || godina % 400 == 0)
        printf("da");
    else
        printf("ne");
    return 0;
}

Два броја истог знака¶

Прочитај текст задатка.

Бројеви $a$ и $b$ истог су знака ако су оба позитивна ($a>0$ и $b>0$) или оба негативна ($a<0$ и $b<0$), па задатак можемо решити постављањем тих услова. Подсетимо се да у језику C везник и можемо записати оператором логичке конјункције &&, а везник или можемо записати оператором логичке дисјункције ||.

Предложено решење задатка (1)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int a, b;
    scanf("%d%d", &a, &b);
    if ((a > 0 && b > 0) || (a < 0 && b < 0))
        printf("da");
    else
        printf("ne");
    return 0;
}

Још елегантније решење је да се услов да су два броја истог знака искаже као $a>0\Leftrightarrow b>0$ тј. да је број $a$ позитиван ако и само ако је број $b$ позитиван (то је оправдано јер бројеви нису једнаки нули). У програмским језицима не постоји посебан оператор еквиваленције, међутим, еквиваленција две логичке вредности се може заправо испитати њиховим поређењем оператором ==. Једнакост два логичка израза ће бити тачна ако су оба израза тачна или ако су оба израза нетачна, што је управо исто оно што је семантика њихове еквиваленције.

Предложено решење задатка (2)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int a, b;
    scanf("%d%d", &a, &b);
    if ((a > 0) == (b > 0))
        printf("da");
    else
        printf("ne");
    return 0;
}

Један трик да лако испитамо да ли су два броја истог знака је да приметимо то да су бројеви, различити од нуле, истог знака ако и само ако је њихов производ већи од 0. Према томе довољно је проверити да ли је $a\cdot b>0$. При томе морамо бити обазриви да ли производ бројева не доводи до прекорачења. У нашем задатку до прекорачења неће доћи јер су бројеви $a,b$ из интервала $[-10^4,10^4]$ па је њихов производ у интервалу $[-10^8,10^8]$ што може да се региструје коришћењем целобројног типа податка.

Предложено решење задатка (3)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int a, b;
    scanf("%d%d", &a, &b);
    if (a * b > 0)
        printf("da");
    else
        printf("ne");
    return 0;
}

Исти квадрант¶

Прочитај текст задатка.

Да тачке на осама нису обухваћене задатком или да је формулација била таква да осе не припадају ниједном квадранту могло би се рећи да су две тачке $A(x_1,y_1)$, $B(x_2,y_2)$ у истом квадранту ако су њихове $x$ координате истог знака (истовремено стриктно позитивне или истовремено стриктно негативне) и ако су њихове $y$ координате истог знака. Међутим, чињеница да су осе обухваћене и да припадају квадрантима који их додирују захтевају мало прилагођавање.

Можемо приметити да тачке припадају истом квадранту ако су истовремено испуњени следећи услови:

њихове $x$ координате су обе позитивне, или обе негативне, или је нека од њих једнака 0
њихове $y$ координате су обе позитивне, или обе негативне, или је нека од њих једнака 0

Дакле, задатак се може решити испитивањем истинитосне вредности следећег израза.

\[\begin{split}\begin{align*} \left(x_1=0 \ \vee \ x_2=0 \ \vee \ (x_1>0 \ \wedge \ x_2>0) \ \vee \ (x_1<0 \ \wedge \ x_2<0)\right)& \ \wedge \ \\ \left(y_1=0 \ \vee \ y_2=0 \ \vee \ (y_1>0 \ \wedge \ y_2>0) \ \vee \ (y_1<0 \ \wedge \ y_2<0\right)) \end{align*}\end{split}\]

Предложено решење задатка (1)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int x1, y1, x2, y2;
    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    if ((x1 == 0 || x2 == 0 || (x1 > 0 && x2 > 0) || (x1 < 0 && x2 < 0)) &&
        (y1 == 0 || y2 == 0 || (y1 > 0 && y2 > 0) || (y1 < 0 && y2 < 0)))
        printf("da");
    else
        printf("ne");
    return 0;
}

Овај израз се може мало поједноставити на разне начине.

На пример, можемо приметити да су тачке у истом квадранту ако су њихове $x$ координате истог знака или је једна од њих 0, и ако су $y$ координате истог знака или је једна од њих 0. Два броја a и b су истог знака или је један од њих 0 ако важи да је

\[a=0 \ \vee \ b=0 \ \vee \ (a>0)\Leftrightarrow(b>0)\]

што доводи до израза

\[\begin{split}\begin{align*} (x_1 = 0 \ \vee\ x_2 = 0 \ \vee\ (x_1 > 0) = (x_2 > 0)) & \ \wedge\ \\ (y_1 = 0 \ \vee\ y_2 = 0 \ \vee\ (y_1 > 0) = (y_2 > 0)) \end{align*}\end{split}\]

Напоменимо да услов

\[a\geq 0 \ \Leftrightarrow b\geq 0\]

није одговарајући (на пример, ако $a$ има вредност 0, а $b$ има вредност -1, његова вредност је нетачно, што је супротно од онога што би требало да буде).

Предложено решење задатка (2)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int x1, y1, x2, y2;
    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    if ((x1 == 0 || x2 == 0 || (x1 > 0) == (x2 > 0)) &&
        (y1 == 0 || y2 == 0 || (y1 > 0) == (y2 > 0)))
        printf("da");
    else
        printf("ne");
    return 0;
}

Можемо приметити да је полазни услов еквивалентан услову да су оба броја ненегативна или оба броја непозитивна.

\[(a\geq 0 \ \wedge \ b\geq 0) \ \vee \ (a\leq 0 \ \wedge \ b\leq 0)\]

Према томе задатак можемо решити испитивањем истинитосне вредности израза

\[\begin{split}\begin{align*} ((x_1\geq 0 \ \wedge \ x_2 \geq 0) \ \vee \ (x_1\leq 0 \ \wedge \ x_2\leq 0)) & \ \wedge \ \\ ((y_1\geq 0 \ \wedge \ y_2 \geq 0) \ \vee \ (y_1\leq 0 \ \wedge \ y_2\leq 0)) \end{align*}\end{split}\]

Предложено решење задатка (3)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int x1, y1, x2, y2;
    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    if (((x1 >= 0 && x2 >= 0) || (x1 <= 0 && x2 <= 0)) &&
        ((y1 >= 0 && y2 >= 0) || (y1 <= 0 && y2 <= 0)))
        printf("da");
    else
        printf("ne");
    return 0;
}

Приметимо даље и да тачке припадају истом квадаранту ако њихове $x$ координате нису различитог знака и њихове $y$ координате нису различитог знака. Бројеви a и b су различитог знака ако је први позитиван а други негативан или први негативан или је први негативан тј. ако важи

$(a>0 \ \wedge \ b<0) \ \vee \ (a<0 \ \wedge \ b>0)$$

На основу овога задатак можемо решити и испитивањем вредности израза

\[\begin{split}\begin{align*} \neg((x_1>0 \ \wedge \ x_2<0) \ \vee \ (x_1<0 \ \wedge \ x_2>0))& \ \wedge \ \\ \neg((y_1>0 \ \wedge \ y_2<0) \ \vee \ (x_1<0 \ \wedge \ x_2>0)) \end{align*}\end{split}\]

Напоменимо и да то што бројеви нису различитог знака не значи да су истог знака (јер је и вредност 0 укључена).

Још један начин да се провера изврши је да се производ бројева упореди са нулом. Ако њихов производ није негативан тј. ако је већи или једнак нули ($x_1\cdot x_2\geq 0$) координате нису различитог знака. Слично извршимо проверу за $y$ координате. Дакле, задатак се може решити следећим изразом

\[x_1\cdot x_2\geq 0 \ \wedge \ y_1\cdot y_2\geq 0\]

Напоменимо да, иако је веома кратко и елегантно, ово решење се може користити ако смо сигурни да производ координата неће довести до прекорачења (што је случај у нашем задатку).

Предложено решење задатка (4)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int x1, y1, x2, y2;
    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    if (x1 * x2 >= 0 && y1 * y2 >= 0)
        printf("da");
    else
        printf("ne");
    return 0;
}

Тачка у правоугаонику и кругу¶

Прочитај текст задатка.

Тачка $(x,y)$ припада кругу са центром у $(x_0,y_0)$ ако је њено растојање од центра круга мање или једнако полупречнику круга $r$. Растојање између тачака рачуна се применом Питагорине теореме. Дакле, потребно је испитати да ли важи да је $\sqrt{(x-x_0)^2+(y-y_0)^2}\leq r$, или, још једноставније, пошто су све величине ненегативне, њему еквивалентан услов $(x-x_0)^2+(y-y_0)^2\leq r^2$.

Правоугаоник се по $x$-координати простире између вредности $x_0-\frac{w}{2}$ и $x_0+\frac{w}{2}$, док се по $y$-координати простире између вредности $y_0-\frac{h}{2}$ и $y_0+\frac{h}{2}$ (пројекција правоугаоника на осу $x$ је интервал $[x_0-\frac{w}{2},x_0+\frac{w}{2}]$, а на осу $y$ интервал $[y_0-\frac{h}{2},y_0+\frac{h}{2}]$). Тачка $(x,y)$ припадала правоугаонику ако и само ако њене пројекције на $x$-осу и $y$-осу припадају наведеним интервалима. Ако тачка на правој има координату $c$ она припада интервалу $[a,b]$ ако и само ако је $a\leq c\leq b$.

Предложено решење задатка

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    double x, y, x0, y0, r, w, h;
    scanf("%lf%lf%lf%lf%lf%lf%lf", &x, &y, &x0, &y0, &r, &w, &h);
    if ((x - x0) * (x - x0) + (y - y0) * (y - y0) <= r * r)
        printf("jeste u krugu\n");
    else
        printf("nije u krugu\n");
    if (x0 - w / 2 <= x && x <= x0 + w / 2 && y0 - h / 2 <= y && y <= y0 + h / 2)
        printf("jeste u pravougaoniku");
    else
        printf("nije u pravougaoniku");
    return 0;
}

Статус објављен током школе¶

Прочитај текст задатка.

Да бисмо проверили да ли време објаве статуса припада времену од 8:30 до 13:50 часова, најједноставније је да свако време преведемо у минуте. Задатак се онда своди на проверу дисјункције (операције или тј. ||) три услова припадности интервалу.

Предложено решење задатка

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int s1, m1, s2, m2, s3, m3;
    scanf("%d%d%d%d%d%d", &s1, &m1, &s2, &m2, &s3, &m3);
    if (((8 * 60 + 30) <= (s1 * 60 + m1) && (s1 * 60 + m1) <= (13 * 60 + 50)) ||
        ((8 * 60 + 30) <= (s2 * 60 + m2) && (s2 * 60 + m2) <= (13 * 60 + 50)) ||
        ((8 * 60 + 30) <= (s3 * 60 + m3) && (s3 * 60 + m3) <= (13 * 60 + 50)))
        printf("da");
    else
        printf("ne");
    return 0;
}

Да ли се две даме нападају¶

Прочитај текст задатка.

Претпоставимо да се прва краљица налази на пољу $(x_1,y_1)$, а друга на $(x_2,y_2)$.

Провера да ли се даме налазе у истој врсти или истој колони је веома једноставна (довољно је проверити да ли важи да је $x_1=x_2$ или је $y_1=y_2$). Две даме се налазе на истој дијагонали ако и само ако је део дијагонале између њих хипотенуза једног једнакокраког правоуглог троугла (коме су катете паралелне ивицама табле). Тада је растојање између краљица по $x$-оси и по $y$ оси једнако. Та два растојања су редом $|x_1-x_2|$ и $|y_1-y_2|$ и краљице су на истој дијагонали ако и само ако су она међусобно једнака.

У језику C апсолутну вредност можемо израчунати библиотечком функцијом abs, декларисаној у заглављу stdlib.h.

Предложено решење задатка

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int x1, y1, x2, y2;;
    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    if (x1 == x2 || y1 == y2 || abs(x1 - x2) == abs(y1 - y2))
        printf("da");
    else
        printf("ne");
    return 0;
}