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

Алгоритми и програми у програмском језику 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}+\ldots+x\cdot a_1+a_0\]

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

\[y=\ldots(((a_n\cdot x+a_{n-1})\cdot x+a_{n-2})\cdot x+\ldots+a_1)\cdot x+a_0\]

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

Да би се вредност полинома израчунала у \(k\) равномерно распоређених тачака интервала \([p,q]\) - вредност полинома се израчунава у тачкама \(p+i\cdot h\) за \(i=0,1,\ldots,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;
}