Задаци: Eлементарно коришћење низова¶
Алгоритми и програми у програмском језику C: елементарно коришћење низова.
Испис у обратном редоследу¶
Прочитај текст задатка.
Да бисмо могли да испишемо учитане елементе у обратном редоследу, потребно је да их након учитавања све складиштмо у низ, који ћемо затим исписати у обратном редоследу. Пошто се унапред зна максимални број елемената (у тексту задатка је наведено да неће бити више од 1000 елемената), у језику C се може употребити класичан статички алоцирани низ.
Елементе учитавамо у петљи у којој се бројач \(i\) креће од \(0\) па до \(n-1\) (где је \(n\) број елемената низа), увећавајући се у сваком кораку за \(1\). Елементе исписујемо у петљи која се креће уназад тј. у петљи у којој бројач креће од \(n-1\) и у сваком кораку се умањује за \(1\) док не дође до вредности \(0\).
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, a[1000];
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
for (int i = n - 1; i >= 0; i--)
printf("%d\n", a[i]);
return 0;
}
Најнижа температура¶
Прочитај текст задатка.
Ако претпоставимо да су сви елементи учитани у низ, можемо имплементирати алгоритам одређивања минимума. Пошто је максимални број елемената унапред познат и веома мали (највише 50), можемо употребити класичан статички алоцирани низ.
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, a[50];
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
int min = a[0];
for (int i = 1; i < n; i++)
if (a[i] < min)
min = a[i];
printf("%d", min);
return 0;
}
Минимално одступање од просека¶
Прочитај текст задатка.
Просечну вредност не можемо одредити док не учитамо све бројеве. Међутим, када израчунамо ову вредност потребно је поново обрадити све бројеве, тј. израчунати њихово растојање до просека. Пошто смо све бројеве учитали током израчунавања просека, не можемо их поново читати да бисмо рачунали растојања. Зато је неопходно све учитане бројеве упамтити у програму и неопходно је да употребимо низ.
Када се бројеви учитају у меморију, тада је једноставно израчунати им просек \(p\) (као количник збира и броја елемената) и израчунати минимално одступање као минимум низа \(\left \lvert a_i-p\right \rvert\) за \(i=0,1,\ldots,n-1\) (користимо алгоритам минимума пресликаних вредности).
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
int main(void)
{
int n;
double a[100];
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%lf", &a[i]);
double s = 0;
for (int i = 0; i < n; i++)
s += a[i];
double p = s / n;
double min = fabs(a[0] - p);
for (int i = 1; i < n; i++)
min = min < fabs(a[i] - p) ? min : fabs(a[i] - p);
printf("%.2lf", min);
return 0;
}
Погођена комбинација¶
Прочитај текст задатка.
Да би задатак могао да се реши потребно је у меморију учитати бар елементе прве
комбинације. Поређење садржаја два низа није могуће коришћењем оператора ==
(њиме се пореде само адресе почетка, а не садржај тих низова). Проверу
једнакости можемо да реализујемо алгоритмом линеарне претраге тако што
проверавамо да ли постоји позиција на којој се у два низа налази различит
елемент. Користећи ову идеју, довољно је да чувамо само први низ, а елементе
другог обрађујемо док их учитавамо.
Предложено решење задатка (1)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, a[100], j = 1;
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
for (int i = 0; i < n; i++)
{
int x;
scanf("%d", &x);
if (a[i] != x)
{
j = 0;
break;
}
}
printf(j ? "da" : "ne");
return 0;
}
Ако елементе учитамо у два низа, у петљи можемо извршити проверу једнакости њихових елемената.
Предложено решење задатка (2)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, a[100], b[100], j = 1;
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
for (int i = 0; i < n; i++)
scanf("%d", &b[i]);
for (int i = 0; i < n; i++)
if (a[i] != b[i])
{
j = 0;
break;
}
printf(j ? "da" : "ne");
return 0;
}
Парни и непарни елементи¶
Прочитај текст задатка.
У програму ћемо чувати два низа - један у којем ћемо чувати парне, а други у којем ћемо чувати непарне елементе. Учитавамо елемент по елемент, проверавамо да ли је паран или непаран тако што израчунамо остатак при дељењу са 2 и у зависности од тога додајемо га у одговарајући низ. Приметимо да се и у овом задатку врши класификација (филтрирање) на основу својстава учитаних бројева, међутим, пошто је потребно исписати прво парне, па онда непарне бројеве, пре исписа је неопходно бројеве памтити у низу.
Низови могу бити алоцирани на основу максималног броја елемената (величина им
може бити 100 елемената, што је број наведен у тексту задатка). Тада је поред
низова потребно користити и променљиве које чувају њихов тренутни број
попуњених елемената (које се иницијализују на нулу). То је уједно и позиција
прве слободне позиције у низу тако да се додавање елемената у низ реализује
тако што се елемент упише на ту позицију, а затим се она увећа за 1.
Ове две ствари је могуће остварити и у једној наредби (на пример,
a[n++] = x).
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, a[100], b[100], c = 0, d = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
int x;
scanf("%d", &x);
if (x % 2 == 0)
a[c++] = x;
else
b[d++] = x;
}
for (int i = 0; i < c; i++)
printf("%d ", a[i]);
printf("\n");
for (int i = 0; i < d; i++)
printf("%d ", b[i]);
return 0;
}
Редни број максимума¶
Прочитај текст задатка.
Алгоритам за одређивање позиције максимума можемо применити и ако претпоставимо да су сви елементи учитани у низ (наравно, то у овом задатку није неопходно и тиме се троши више меморије него што је потребно).
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n;
double a[1000];
scanf("%d", &n);
int max = 0;
for (int i = 0; i < n; i++)
{
scanf("%lf", &a[i]);
if (a[i] > a[max])
max = i;
}
printf("%d", max + 1);
return 0;
}
Разлика сума до маx и од маx¶
Прочитај текст задатка.
Решење до којег се најједноставније долази је да се масе свих предмета учитају у низ, да се након тога пронађе позиција највећег елемента у низу (коришћењем алгоритма одређивања позиције максимума) и да се затим одреди збир елемената низа пре те позиције и збир елемената низа после те позиције (коришћењем алгоритма одређивања збира серије).
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
unsigned short n, a[50000];
scanf("%hu", &n);
unsigned short max = 0;
for (int i = 0; i < n; i++)
{
scanf("%hu", &a[i]);
if (a[i] > a[max])
max = i;
}
int b_max = 0;
for (unsigned short i = 0; i < max; i++)
b_max += a[i];
int a_max = 0;
for (unsigned short i = max + 1; i < n; i++)
a_max += a[i];
printf("%d", b_max - a_max);
return 0;
}
Просечно одступање од минималног¶
Прочитај текст задатка.
Један начин је да се након учитавања елемената (на пример, у класичан низ који има највише 200 елемената), пронађе минимална цена \(m\), а након тога просечно одступање сваке цене од пронађене минималне (одступање је разлика цене артикла и минималне цене), тј. да се израчуна
Минимум можемо пронаћи алгоритмом одређивања минимума, а просек, као количник суме одступања коју израчунавамо алгоритмом сабирања (овај пут пресликане) серије бројева и броја производа у продавници.
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <float.h>
int main(void)
{
int n;
scanf("%d", &n);
double a[200], min = DBL_MAX;
for (int i = 0; i < n; i++)
{
scanf("%lf", &a[i]);
if (a[i] < min)
min = a[i];
}
double s = 0.0;
for (int i = 0; i < n; i++)
s += a[i] - min;
s /= n;
printf("%.2lf", s);
return 0;
}
Максимална разлика суседних¶
Прочитај текст задатка.
Једно решење је да се приликом учитавања елемената у низ одреди и максимална разлика суседних елемената. Ово решење троши више меморије него што је неопходно.
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int n, a[100], r, r_max = 0;
scanf("%d", &n);
scanf("%d", &a[0]);
for (int i = 1; i < n; i++)
{
scanf("%d", &a[i]);
r = abs(a[i] - a[i - 1]);
if (r > r_max)
r_max = r;
}
printf("%d", r_max);
return 0;
}
Провера монотоности¶
Прочитај текст задатка.
Једно решење је да се приликом учитавања елемената у низ проверава да ли је низ сортиран растуће, тако што пореди свака два узастопна елемента низа. Ово решење троши више меморије него што је неопходно.
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, a[100], r = 1;
scanf("%d", &n);
scanf("%d", &a[0]);
for (int i = 1; i < n; i++)
{
scanf("%d", &a[i]);
if (a[i-1] >= a[i])
r = 0;
}
printf(r ? "Da" : "Ne");
return 0;
}