Задаци: Трансформације низова¶
Алгоритми и програми у програмском језику C: трансформације низова.
Избацивање елемената¶
Прочитај текст задатка.
Основу задатака чини филтрирање низа, тј. избацивање елемената из низа који задовољавају дато својство. Ако би се резултат памтио у другом низу, филтрирање би могли извршити тако што би пролазили кроз све елементе датог низа и сваки који не задовољава својство избацивања (у нашем случају сваки елемент који не дели димензију низа) додавали на крај резултата. Приликом грађења резултујућег низа можемо да одржавамо број елемената тренутно смештених у резултујући низ. Поступак се заправо не разликује много ни ако се филтрирање врши у месту (у истом низу). Наиме, резултат се уместо у посебан низ може смештати на почетак самог низа који се филтрира. Постављањем елемената низа у његов почетни део не постоји опасност да се пребрише неки елемент који још није обрађен.
Пошто се користи класичан, статички алоцирани низ, његова стварна димензија се не може променити након избацивања неких елемената, међутим, уз низ се одржава променљива која чува број његових попуњених елемената и скраћивање низа се постиже смањивањем вредности те променљиве.
Филтрирање елемената се понавља све док се његовом применом мења димензија низа. Кôд организујемо кроз бесконачну петљу, након филтрирања проверавамо да ли је број задржаних елемената једнак броју елемената низа, и ако јесте, петљу прекидамо.
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
unsigned short n, a[50000];
scanf("%hu", &n);
for (unsigned short i = 0; i < n; i++)
scanf("%hu", &a[i]);
while (1)
{
unsigned short k = 0;
for (unsigned short i = 0; i < n; i++)
if (n % a[i] != 0)
a[k++] = a[i];
if (n == k)
break;
n = k;
}
int s = 0;
for (unsigned short i = 0; i < n; i++)
s += a[i];
printf("%d", s);
return 0;
}
Различити елементи низа¶
Прочитај текст задатка.
Уклањање дупликата из низа се може извршити много ефикасније ако се низ претходно сортира, међутим, у овом задатку се инсистира на задржавају оригиналног редоследа елемената, тако да сортирање није могуће једноставно применити.
Једно могуће решење је да учитавамо један по један од n елемената и да за
сваки од њих проверавамо да ли се раније већ појавио. Можемо одржавати низ
елемената који су се до сада јавили и проширивати га текућим елементом ако и
само ако се он већ не налази у том низу.
Предложено решење задатка (1)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, a[10000], r[10000], ri = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
for (int i = 0; i < n; i++)
{
int ir = 1;
for (int j = 0; j < ri; j++)
if (a[i] == r[j])
{
ir = 0;
break;
}
if (ir)
{
r[ri] = a[i];
ri++;
}
}
for (int i = 0; i < ri; i++)
printf("%d\n", r[i]);
return 0;
}
Такво решење је елегантно, али се у тексту задатка наглашава да је потребно у
истом низу задржати само по једно појављивање сваког елемента. То значи да
оригинални низ a треба трансформисати.
Предложено решење задатка (2)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, a[10000], r[10000], ri = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
for (int i = 0; i < n; i++)
{
int ir = 1;
for (int j = 0; j < ri; j++)
if (a[i] == r[j])
{
ir = 0;
break;
}
if (ir)
{
r[ri] = a[i];
ri++;
}
}
for (int i = 0; i < n; i++)
a[i] = r[i] != 0xCCCCCCCC ? r[i] : 0xCCCCCCCC;
n = ri;
for (int i = 0; i < n; i++)
printf("%d\n", a[i]);
return 0;
}
Обртање низа¶
Прочитај текст задатка.
Обртање дела низа вршимо тако што размењујемо први елемент тог дела низа са последњим, други са претпоследњим, и тако редом, док не дођемо до средине тог дела низа.
Постоји неколико начина да се имплементира петља која ово ради. Једна варијанта је да се употребе две променљиве \(i\) и \(j\), и да се прва иницијализује на вредност \(p\), а друга на вредност \(q\). У сваком кораку петље се размењују елементи на позицијама \(i\) и \(j\), \(i\) се увећава за 1, а \(j\) се умањује за 1. Петља се извршава све док је \(i<j\).
Предложено решење задатка (1)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, a[50000];
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
while (1)
{
int p, q;
scanf("%d%d", &p, &q);
if (p > q)
break;
for (int i = p, j = q; i < j; i++, j--)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
for (int i = 0; i < n; i++)
printf("%d\n", a[i]);
return 0;
}
У једној варијанти петљу организујемо са само једном бројачком променљивом \(i\) и у сваком кораку размењујемо елементе на позицијама \(p+i\) и \(q-i\). Ово је потребно радити све док је \(p+i<q-i\), што може бити услов петље (када је \(p+i=q-i\) тада се елемент мења са самим собом, што се може, али и не мора урадити).
Број итерација је могуће израчунати и унапред. Број елемената у делу низа између позиција \(p\) и \(q\) је \(q-p+1\) па замену одговарајућих елемената (првог и последњег, другог и претпоследњег, итд.) треба обавити \(\left\lfloor{\frac{q-p+1}{2}}\right\rfloor\) пута и петља се извршава кренувши од вредности индекса 0 па све док је та вредност индекса строго мања од вредности \(\left\lfloor{\frac{q-p+1}{2}}\right\rfloor\). Заокруживање наниже је опет допуштено јер се у случају интервала непарне дужине средишњи елемент не мора мењати сам са собом. Заиста, ако је услов одржања петље \(p+i<q-i\), тада се петља прекида када је \(2i\geq q-p\) тј. када је \(i\geq\frac{q-p}{2}\). Најмањи цео број који тај услов задовољава је \(\left\lceil{\frac{q-p}{2}}\right\rceil\), а знамо да је то једнако \(\left\lfloor{\frac{q-p+1}{2}}\right\rfloor\).
Предложено решење задатка (2)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, a[50000];
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
while (1)
{
int p, q;
scanf("%d%d", &p, &q);
if (p > q)
break;
for (int i = 0; i < (q - p + 1) / 2; i++)
{
int temp = a[p + i];
a[p + i] = a[q - i];
a[q - i] = temp;
}
}
for (int i = 0; i < n; i++)
printf("%d\n", a[i]);
return 0;
}
Циклично померање за једно место¶
Прочитај текст задатка.
Учитаћемо број елемемената и све чланове низа. У петљи ћемо учитавати вредности \(p\) и \(q\). Након анализе вредности \(p\) и \(q\), ако је \(p<q\) позиваћемо вршиће се померање удесно, а ако је \(p>q\), померање улево, тј. вршиће се ротирање дела низа између позиција \(p\) и \(q\), укључујући и елементе на тим позицијама.
Циклично померање улево врши се на основу индекса левог краја \(q\) и индекса десног краја \(p\). Сви елементи са позиција од \(q+1\) до \(p\) се померају за једно место улево, док се елемент са позиције \(q\) уписује на крај низа, на позицију \(p\). При обради чланова низа полази се од индекса \(q\). Вредност са те позиције морамо сачувати у помоћној променљивој, пре уласка у петљу (у супротном би била преписана након померања елемента са позиције \(q+1\)). У петљи се врши померање вредности елемената низа са позиција \(i+1\) на \(i\). Петља почиње од индекса \(q\) и завршава се када се помери елемент низа са позиције \(p\). На позицију већег индекса \(p\) се тада уписује вредност помоћне променљиве.
Циклично померање удесно врши се веома слично, осим што је неопходно да се обрада врши од десног ка левом крају.
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, a[50000];
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
while (1)
{
int p, q;
scanf("%d%d", &p, &q);
if (p < q)
{
int pom = a[q];
for (int i = q; i > p; i--)
a[i] = a[i - 1];
a[p] = pom;
}
else if (p > q)
{
int pom = a[q];
for (int i = q; i < p; i++)
a[i] = a[i + 1];
a[p] = pom;
}
else
break;
}
for (int i = 0; i < n; i++)
printf("%d\n", a[i]);
return 0;
}