Задаци: Линеарна претрага¶
Алгоритми и програми у програмском језику C: Линеарна претрага.
Негативан број¶
Прочитај текст задатка.
Потребно је испитати да ли међу учитаним бројевима постоји неки који је
негативан. Променљивом neg можемо пратити да ли смо учитали неки негативан
број. Пошто на почетку нисмо још учитали ни један број, нисмо видели ни један
негативан, и на почетку вредност променљиве neg поставимо на 0. Затим у петљи
редом учитавамо бројеве и за сваки број проверавамо да ли је негативан. Ако је
тренутно учитани број негативан вредност променљиве neg поставимо на 1 (јер
сада знамо да међу до сада учитаним бројевима постоји један који је негативан).
После читања свих бројева, на основу вредности променљиве neg исписујемо
одговарајућу поруку.
Нагласимо да је честа грешка да се унутар петље провери да ли је тренутно
учитани број негативан и да се, ако јесте, вредност променљиве постави на 1,
а да се у супротном она постави на 0 или (са истим ефектом) neg = (x < 0);.
Наилазак на негативан број одређује дефинитивно да у серији постоје негативни
бројеви, док наилазак на ненегативни број не указује на то да су у серији сви
бројеви ненегативни (зато грану else не треба писати). Исправно решење може
бити следеће.
Предложено решење задатка (1)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, neg = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
double x;
scanf("%lf", &x);
if (x < 0)
neg = 1;
}
printf(neg ? "da" : "ne");
return 0;
}
Приметимо да читање бројева можемо прекинути када прочитамо први негативан број
тј. када вредност променљиве neg постане 1 јер тада знамо да међу бројевима
постоји негативан број. Према томе, читамо бројеве и проверавамо да ли је
учитани број негативан, док не прочитамо све бројеве и док је вредност
променљиве neg једнака 0. Нагласимо да овакав ранији прекид петље не би био
могућ да је у неком случају било потребно учитати све бројеве. Рани прекид
петље можемо остварити на различите начине.
Један је да се услов петље ојача условом да је вредност променљиве једнака 0,
(на пример, да се тражи да је i < n && !neg).
Предложено решење задатка (2)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, neg = 0;
scanf("%d", &n);
for (int i = 0; i < n && !neg; i++)
{
double x;
scanf("%lf", &x);
if (x < 0)
neg = 1;
}
printf(neg ? "da" : "ne");
return 0;
}
Један начин да се оствари рани прекид приликом постављања променљиве neg на
1 је да се употреби наредба break.
Предложено решење задатка (3)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, neg = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
double x;
scanf("%lf", &x);
if (x < 0)
{
neg = 1;
break;
}
}
printf(neg ? "da" : "ne");
return 0;
}
Задатак можемо решити и без коришћења променљиве neg. У петљи читамо број по
број, и ако је учитани број негативан прекинемо извршавање петље коришћењем
наредбе break. После завршетка петље на основу вредности бројачке променљиве
можемо закључити да ли је међу учитаним бројевима постојао негативан број. Ако
је бројачка променљива имала почетну вредност 0 и ако је после завршетка петље
њена вредност мања од \(n\) онда је петља завршена пре читања свих бројева, према
томе постоји негативан број међу учитаним бројевима. Слично ако је почетна
вредност бројачке променљиве 1 и ако је после завршетка петље њена вредност
мања или једнака \(n\), постојао је негативан број међу учитаним бројевима. Важно
је напоменути да бројачка променљива мора бити декларисана пре петље (не сме
бити локална променљива петље), да бисмо је могли користити после петље.
Предложено решење задатка (4)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, i;
scanf("%d", &n);
for (i = 0; i < n; i++)
{
double x;
scanf("%lf", &x);
if (x < 0)
break;
}
printf(i < n ? "da" : "ne");
return 0;
}
Прва негативна температура¶
Прочитај текст задатка.
У овом задатку треба да одредимо прву позицију на којој се јавља неки негативан број. Задатак можемо решити алгоритмом линеарне претраге.
Уместо логичке променљиве којом региструјемо да ли се међу учитаним бројевима
налази неки негативан, користићемо целобројну променљиву којом ћемо
регистровати редни број (позицију тј. индекс) дана у којем се јавила негативна
температура. Вредност те променљиве иницијализујемо на -1 што указује да се
до тог тренутка још није учитала негативна вредност. Након тога, учитавамо
температуре једну по једну и ако је тренутна температура негативна,
региструјемо редни број дана (то ће бити вредност бројачке променљиве у петљи,
чије су вредности од 1 до \(n\)) и прекидамо петљу. На крају, штампамо променљиве
у којој се региструје редни број (ако се није наишло на негативну температуру,
она и даље има вредност -1).
Предложено решење задатка (1)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, d = -1;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
int t;
scanf("%d", &t);
if (t < 0)
{
d = i;
break;
}
}
printf("%d", d);
return 0;
}
Могуће је избећи коришћење помоћне променљиве. Редом читамо температуру по
температуру, а при томе бројачком променљивом пратимо редни број текућег дана
периода (почињемо бројање од 1). Приликом наиласка на негативну температуру,
петљу прекидамо наредбом break. Након петље проверавамо да је услов петље
испуњен (да ли је вредност бројачке променљиве мања или једнака броју дана
периода \(n\)) и ако јесте, значи да је дошло до раног прекида и тада вредност
бројачке променљиве садржи тражени број дана. У супротном можемо да прикажемо
-1, јер се дошло до краја петље и није извршен рани прекид, што значи да међу
учитаним температурама није постојала негативна.
Предложено решење задатка (2)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, i;
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
int t;
scanf("%d", &t);
if (t < 0)
break;
}
if (i <= n)
printf("%d", i);
else
printf("-1");
return 0;
}
Последња негативна температура¶
Прочитај текст задатка.
Након проналажења прве негативне температуре петља се не прекида, већ је увек неопходно учитати и обрадити све температуре. Целобројном променљивом пратимо редни број дана када је температура последњи пут међу учитаним температурама била негативна. На почетку вредност те променљиве је \(-1\), јер још није учитана ни једна негативна температура. У петљи чија бројачка променљива узима вредности од \(1\) до \(n\) тј. која представља редни број дана учитавамо редом температуре за сваки дан. За сваку учитану температуру проверавамо да ли је негативна и ако јесте коригујемо вредност променљиве којом памтимо редни број дана када је температура последњи пут била негативна. Корекцију вршимо постављањем вредности те променљиве на вредност бројачке променљиве (јер је то редни број дана периода у којем је била управо прочитана температура).
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, d = -1;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
int t;
scanf("%d", &t);
if (t < 0)
d = i;
}
printf("%d", d);
return 0;
}
Парно непарни¶
Прочитај текст задатка.
Током провере наш програм се налази у два стања. У почетку смо у стању у којем
прихватамо парне бројеве. Када се у том стању први пут појави неки непаран број
прелазимо у стање у којем надаље смемо да прихватамо само непарне бројеве. Ако
се у том стању појави неки паран број, онда низ не задовољава тражени услов.
Тренутно стање се може регистровати једном променљивом (на пример, променљива
nep која ће бити иницијализована на 0 и постављена на 1 први пут када се
учита непаран број). Дакле, у петљи учитавамо број по број све док не дођемо до
краја улаза. Променљивом ok коју иницијализујемо на 1 бележимо да ли
бројеви задовољавају услов задатка. У услову петље захтевамо да је вредност
променљиве ok једнака 1, јер у супротном знамо да бројеви не задовољавају
тражени распоред и нема потребе вршити даље провере. У телу петље, након
учитавања наредног броја проверавамо да ли смо наишли на непаран број у
тренутку док променљива nep има вредност 0. Када се то догоди вредност
променљиве nep постављамо на 1. Такође, проверавамо да ли је учитан
паран број док је вредност променљиве nep једнака 1 и у том случају
променљиву ok постављамо на 0 (јер знамо да се појавио паран број након
непарног). На крају резултат пријављујемо у зависности од вредности ok.
Приметимо да се овде заправо у две фазе примењује алгоритам линеарне претраге. У првом стању се врши претрага за непарним бројем и када се он нађе, прелази се у друго стање. У другом стању се врши претрага за парним бројем и ако се он нађе, пријављује се да низ не задовољава услов.
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int ok = 1, nep = 0, x;
while (scanf("%d", &x) != EOF && ok)
if (x % 2 != 0)
nep = 1;
else if (nep)
ok = 0;
printf(ok ? "da" : "ne");
return 0;
}
Провера тробојке¶
Прочитај текст задатка.
Током провере наш програм може бити у једном од три стања: читању негативног дела низа, читању нула и читању позитивног дела иза.
Ако се у стању читања негативног дела низа појави нула прелази се у стање читање нула, а ако се појави неки позитивни број прелази се у стање читања позитивних бројева.
Ако се у стању читања нула појави неки негативан број, улаз није исправан, а ако се појави неки позитиван број прелази се у стање читања позитивних бројева.
Ако се у стању читања позитивних бројева појави било шта осим позитивног броја, улаз није исправан.
Стање се може представити једном целобројном променљивом и током читања сваког броја гранањем можемо одредити како се мења стање. Променљивом можемо представити да ли је дошло до грешке и чим први пут дође до грешке, можемо прекинути петљу и пријавити да улаз није исправан.
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n;
scanf("%d", &n);
int neg = 0, nul = 1, poz = 2, ok = 1;
int s = neg;
for (int i = 0; i < n; i++)
{
int x;
scanf("%d", &x);
if (s == neg)
{
if (x == 0)
s = nul;
else if (x > 0)
s = poz;
}
else if (s == nul)
{
if (x < 0)
{
ok = 0;
break;
}
else if (x > 0)
s = poz;
}
else if (s = poz)
{
if (x <= 0)
{
ok = 0;
break;
}
}
}
printf(ok ? "da" : "ne");
return 0;
}