Задаци: Низови као репрезентација вектора, полинома и великих бројева¶

Алгоритми и програми у програмском језику C: низови као репрезентација вектора, полинома и великих бројева.

Скаларни производ¶

Скаларни производ вектора је збир производа одговарајућих координата вектора. Да бисмо израчунали њихов производ, морамо најпре прочитати векторе са стандардног улаза.

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

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

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int n, a[50], b[50], s = 0;
    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]);
        s += a[i] * b[i];
    }
    printf("%d", s);
    return 0;
}

Приметимо да за израчунавање производа није неопходно чувати у меморији оба низа, већ је довољно учитати само први вектор у низ, а затим учитавати једну по једну координату другог вектора, множити је са одговарајућом координатом првог вектора и додавати на текући збир.

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

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int n, a[50], b, s = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &b);
        s += a[i] * b;
    }
    printf("%d", s);
    return 0;
}

Вредност полинома¶

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

Вредност полинома

y = a_{n} \cdot x^{n} + a_{n - 1} \cdot x^{n - 1} + \dots + x \cdot a_{1} + a_{0}

се може израчунати без коришћења операције степеновања ако се полином представи у Хорнеровом облику:

y = \dots (((a_{n} \cdot x + a_{n - 1}) \cdot x + a_{n - 2}) \cdot x + \dots + a_{1}) \cdot x + a_{0}

Ако се $y$ иницијализује са $0$ , у $n + 1$ итерација се израчунава $y = y \cdot x + a_{n}$ , $y = y \cdot x + a_{n - 1}$ , $\dots$ , $y = y \cdot x + a_{0}$ .

Да би се вредност полинома израчунала у $k$ равномерно распоређених тачака интервала $[p, q]$ - вредност полинома се израчунава у тачкама $p + i \cdot h$ за $i = 0, 1, \dots, k - 1$ и $h = (q - p) / (k - 1)$ .

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

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int n, k;
    scanf("%d", &n);
    double a[100], p, q, x = 0.0;
    for (int i = n; i >= 0; i--)
        scanf("%lf", &a[i]);
    scanf("%d%lf%lf", &k, &p, &q);
    double h = (q - p) / (k - 1);
    int i;
    for (i = 0, x = p; i < k; i++, x += h)
    {
        double y = 0.0;
        for (int j = n; j >= 0; j--)
            y = y * x + a[j];
        printf("%.2lf\n", y);
    }
    return 0;
}

Уместо Хорнерове шеме може се употребити и класична дефиниција вредности. Тада се у сваком кораку израчунава степен $x^{i}$ . Израчунати степен се множи са коефицијентом $a_{i}$ (који се налази у низу коефицијената a на позицији i) и додаје на текући збир (који је иницијално постављен на нулу). Једна могућа оптимизација овог поступка (која избегава употребу степеновања) је да се одржава вредност степена (која се иницијализује на $1$ ) и да се у сваком кораку, након увећања збира вредност степена помножи са $x$ . Ипак, Хорнерова шема је најелегантније и најефикасније решење.

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

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

int main(void)
{
    int n, k;
    scanf("%d", &n);
    double a[100], p, q, x = 0.0;
    for (int i = n; i >= 0; i--)
        scanf("%lf", &a[i]);
    scanf("%d%lf%lf", &k, &p, &q);
    double h = (q - p) / (k - 1);
    int i;
    for (i = 0, x = p; i < k; i++, x += h)
    {
        double y = 0.0;
        for (int j = 0; j <= n; j++)
            y += a[j] * pow(x, j);
        printf("%.2lf\n", y);
    }
    return 0;
}

Збир два троцифрена¶

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

Сабирање се може уопштити и на случај вишецифрених бројева, ако се они представе низовима цифара и употреби се петља.

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

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int a[3], b[3];
    scanf("%d%d%d%d%d%d", &a[2], &a[1], &a[0], &b[2], &b[1], &b[0]);
    int z[4];
    int p = 0;
    for (int i = 0; i < 3; i++)
    {
        int zc = a[i] + b[i] + p;
        z[i] = zc % 10;
        p = zc / 10;
    }
    z[3] = p;
    int i;
    for (i = 3; i > 0 && z[i] == 0; i--)
        ;
    for (; i >= 0; i--)
        printf("%d", z[i]);
    return 0;
}