Друга вежба¶

Основне алгоритамске структуре и типови података

Нерешени задаци

Неке белешке...¶

Задатак 1.¶

Нацртати структурни дијаграм тока алгоритма и на програмском језику C написати структурни програм који одређује и приказује све просте бројеве мање од \(N\). Целобројни параметар \(N\) уноси корисник. Уколико се при извршавању програма за \(N\) унесе вредност \(100\), шта ће програм приказати на излазу?

Териотисање¶

Нека је \(N\) цео број (\(N \in \Z\)) за који желимо да одредимо да ли је прост број.

Из математике знамо да се прост број дефинише као број који је дељив само самим собом и бројем \(1\). Број \(1\) се не сматра ни простим ни сложеним бројем, неки би рекли да јесте, а неки да није прост број. Дефиниција простих бројева налаже да је прост број онај број који има тачно два, међусобно различита фактора (делиоца), па онда \(1\) не би задовољавао услов у том случају.

Даћемо пример привх 10 простих бројева: \(2, 3, 5, 7, 11, 13, 17, 19, 23, 29\).
Приметимо да је први прост број \(2\), други је \(3\), и тако даље. Осим броја \(2\) који је и једини паран прост број, сви остали прости бројеви су заправо непарни (јер је сваки паран број дељив и бројем \(2\), па онда такви бројеви, сем броја \(2\), нису прости).

Претходно је речено да је први прост број \(2\), а други \(3\), ово може бити први услов – уколико је \(N = 3 \lor N = 2\), знамо да број \(N\) јесте прост.

Ако је број дељив са \(2\) или \(3\) (\(N \bmod 2 = 0 \lor N \bmod 3 = 0\)), број није прост и ово може бити други услов.

Негативни бројеви нису прости бројеви, јер су сви дељиви барем са \(-1\). \(0\), слично броју \(1\), није ни прост ни сложен број – број \(0\) подељен самим собом није дефинисано и сваки други број је могуће поделити са \(0\). Ово може бити трећи услов, бројеви мањи или једнаки \(1\) (\(N \leq 1\)) нису прости бројеви.

Други и трећи услов могу се објединити дисјункциом у један, дакле ако је \(N \leq 1 \lor N \bmod 2 = 0 \lor N \bmod 3 = 0\) онда \(N\) није прост број. Потребно је још проверити дељивост са осталим целим бројевима.

Све целе бројеве је могуће представити у облику \(6k+i\), за \(k \in \Z\) и \(i = -1, 0, 1, 2, 3, 4\). Број \(2\) дели бројеве облика \(6k\), \(6k+2\) и \(6k+4\), а број \(3\) дели бројеве облика \(6k+3\), што је већ покривено другим условом (ако је број дељив са \(2\) или \(3\) тај број није прост). Трећим условом су већ одбачени бројеви када је \(k \leq 0\), oстаје једино проверити да ли је провераван број \(N\) дељив са свим бројевима облика \(6k \pm 1\) за \(k \geq 1\).

Проверу не морамо да вршимо док не дођемо до крајњег броја \(N\). Сви делиоци броја \(N\) (без њега самог) биће мањи од или једнаки \(\frac{N}{2}\). Нпр. \(1, 2, 4, 5, 10, 20, 25, 50\) су делиоци броја \(100\), а највећи је \(50\). Додатно, можемо уочити понављање производа у факторизацији броја \(100\), \(2 \cdot 50, 4 \cdot 25, 5 \cdot 20, 10 \cdot 10, 20 \cdot 5, 50 \cdot 2\) – парови \(2 \cdot 50\) и \(50 \cdot 2\), \(4 \cdot 25\) и \(25 \cdot 4\), \(5 \cdot 25\) и \(25 \cdot 5\), су сачињени од истих бројева. Ово важи за било који број \(N\), тако да није потребно трагати даље од \(\sqrt{N}\) (што ће за дат пример броја \(100\) бити \(10\), факторизација у средини сачињена од два иста броја).

За решавање датог задатка, штампање простих бројева мањих од \(N\), прво нам је потребна петља која ће се кретати од \(2\) до \(N - 1\). Бројач петље потом биће број који подвргавамо провери да ли је прост, нека је бројач петље \(i\).

Употребићемо неки флег (енг. flag, променљива у којој чувамо неко стање програма) \(p\). Како програмски језик C тумачи вредност \(1\) као тачну вредност, а било коју другу вредност као нетачну - уколико смо одредили да је \(i\) прост, поставићемо вредност \(p\) на \(1\). У супротном ако смо одредили да \(i\) није прост број, \(p\) ће добити вредност \(0\), нпр. (може било који број различит од \(1\), \(0\) као нетачна вредност је више као нека конвенција).

Ако је \(i = 2 \lor i = 3\) онда је \(p = 1\).

Уколико је \(i \leq 1 \lor i \bmod 2 = 0 \lor i \bmod 3 = 0\) онда је \(p = 0\).

У супротном, у почетном тренутку можемо сматрати да је број прост уколико не докажемо супротно, нека је \(p = 1\). Употребом петље потребно је да прођемо кроз бројеве облика \(6k \pm 1\) мање од или једнаке \(\sqrt{i}\) за \(k \geq 1\). То би било исто као да је нпр. у почетном тренутку \(ј = 5\), први број тог облика. Поставити петљу док је \(ј \leq \sqrt{i}\) и у њој проверавати услов \(i \bmod 6ј = 0 \lor i \bmod 6ј+2 = 0\). Aко је услов задовољен, оповргавамо претпоставку да је број прост, \(p = 0\). \(ј\) увећавати за \(6\) при крају сваке итерације петље.

Дакле како је \(j = 6k-1\), повећавамо \(j\) за по \(6\) јер је то разлика између неког тренутног \(6k-1\) почетног броја и наредног \(6(k + 1) - 1\): \(6(k + 1) - 1 - (6k - 1) = 6k + 6 - 1 - 6k + 1 = 6\). При том услов \(i \bmod 6ј = 0 \lor i \bmod 6ј+2 = 0\) еквивалентан је са \(i \bmod 6k-1 = 0 \lor i \bmod 6k+1 = 0\) када се \(j\) замени бројем облика који замењује.

У случају да смо доказали да број није прост нема потребе проверавати даље дељивост тог броја са другим бројевима – услов петље можемо кореговати да петља ради док је и флег \(p\) тачан, тј. док сматрамо још увек да је број прост, \(p \land j \leq \sqrt{i}\).

Уколико је \(p = 1\), штампамо прост број \(i\).

Дијаграм тока алгоритма¶

Изворни код програма¶

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <stdio.h>

main() {
    int n, i, j, prost;

    printf("Unesite ceo broj N: ");
    scanf("%d", &n);

    for (i = 2; i < n; i++) {
        if (i == 2 || i == 3)
            prost = 1;
        else if (i <= 1 || i % 2 == 0 || i % 3 == 0)
            prost = 0;
        else {
            prost = 1;
            j = 5;
            while (prost && j * j <= i) {
                if (i % j == 0 || i % (j + 2) == 0) {
                    prost = 0;
                }

                j += 6;
            }
        }

        if (prost)
            printf("%d\n", i);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <stdio.h>

main() {
    int n, i, p;
    int primes[100];

    printf("Unesite ceo broj N: ");
    scanf("%d", &n);

    for (i = 0; i < n; i++) {
        primes[i] = 1;
    }

    for (p = 2; p * p < n; p++) {
        if (primes[p]) {
            for (i = p * p; i < n; i += p) {
                primes[i] = 0;
            }
        }
    }

    for (p = 2; p < n; p++) {
        if (primes[p]) {
            printf("%d\n", p);
        }
    }
}

Задатак 2.¶

Нацртати структурни дијаграм тока алгоритма и на програмском језику C написати структурни програм који одређује и приказује суму првих \(N\) парних чланова Фибоначијевог низа. Параметар \(N\) задаје корисник, подразумевати да је \(N \geq 3\). Елементи фибоначијевог низа су дати формулом \(f_i = f_{i-1} + f_{i-2}\) за \(i \geq 3\), где је \(f_1 = f_2 = 1\). Уколико се при извршавању програма за \(N\) унесе вредност \(10\), шта ће програм приказати на излазу?

Териотисање¶

Чланови Фибоначијевог низа су дати рекурзивном формулом. Како би било могуће израчунати неки члан Фибоначијевог низа, потребно је познавати вредности њему два претходна члана, чија вредност такође зависи од њима претходним члановима, и тако даље… Познато је (дато задатком) да први (\(f_1\)) и други (\(f_2\)) члан Фибоначијевог низа има вредност \(1\). За израчунавање трећег члана, применом формуле, добијамо \(f_3 = f_2 + f_1 = 1 + 1 = 2\). Сада када знамо и трећи члан, можемо наћи и четврти: \(f_4 = f_3 + f_2 = 2 + 1 = 3\)… Овај поступак се може понављати док се не дође до траженог \(N\)–тог, \(f_N\), члана.

Како редом одређујемо чланове Фибоначијевог низа у петљи, у тренутку када је тренутно нађени члан паран број (\(f_i \bmod 2 = 0\)), додати га суми и инкрементовати вредност неког бројача (\(c = c + 1\)). Овај процес се понавља све док је \(c < N\).

Дијаграм тока алгоритма¶

Изворни код програма¶

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <stdio.h>

main() {
    int n, c = 0;
    long f1 = 1, f2 = 1, f3, s = 0;

    printf("Unesite ceo broj N: ");
    scanf("%d", &n);

    while (c < n) {
        f3 = f2 + f1;
        f1 = f2;
        f2 = f3;

        if (f3 % 2 == 0) {
            s += f3;
            c++;
        }
    }

    printf("Suma %d parnih clanova Fibonacijevog niza iznosi %lld.\n", c, s);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <stdio.h>

main() {
    int n, i;
    long f1 = 1, f2 = 1, f3, s = 0;

    printf("Unesite ceo broj N: ");
    scanf("%d", &n);

    for (i = 0; i < 3 * n; i++) {
        f3 = f2 + f1;
        f1 = f2;
        f2 = f3;

        if (f3 % 2 == 0) {
            s += f3;
        }
    }


    printf("Suma %d parnih clanova Fibonacijevog niza iznosi %lld.\n", i / 3, s);
}

Задатак 3.¶

Нацртати структурни дијаграм тока алгоритма и на програмском језику C написати структурни програм којим се одређују и приказују сви троцифрени бројеви мањи од \(N\) чији је збир цифара прост број. Целобројни параметар \(N\) задаје корисник. Уколико се при извршавању програма за \(N\) унесе вредност \(120\), шта ће програм приказати на излазу?

Териотисање¶

Како би одредили збир цифара троцифреног броја, потребно је на неки начин раставити цифре из броја. Познато нам је да је троцифрен број симболички записан као \(SDJ\) могуће записати као \(S \cdot 100 + D \cdot 10 + J \cdot 1\), где је \(S\) стоти део, \(D\) десети део, \(J\) јединица броја. Нпр. \(834 = 8 \cdot 100 + 3 \cdot 10 + 4 \cdot 1\). Дељењем таквог броја са \(10\) добијамо број облика \(SD\), тј. одстранили смо \(Ј\), што је уједно и остатак при дељењу. Применом оператора дељења (\(:\), тј. \(/\)) и остатка при дељењу (\(\bmod\), тј. \(\%\)) можемо одвојити цифре броја.

Слично, могуће је исто применити за било који број, ма колико цифара он поседовао. Претходно дат пример се може записати и у облику \(S \cdot 10^2 + D \cdot 10^1 + J \cdot 10^0\). Можемо приметити да се цифра множи са бројем \(10\) (основом бројног система/различит број могућих цифара) на степену који одговара тежини цифре, почевши од тежине једнаке \(0\) за цифру јединице. С обзиром на то, добијен алгоритам можемо генералисати за било који \(N\)–тоцифрени број – кроз сваки пролазак петље одредити цифру најмање тежине броја \(N\) као \(N \bmod 10\), потом поделити \(N\) са \(10\) и сачувати резултат у \(N\) и понављати све док је \(N \gt 0\).

Важно је напоменути да се овим поступком мења вредност броја \(N\); Уколико би желели да сачувамо почетну вредност (коју је корисник унео), потребно је пре бројачке петље сачувати \(N\) у неку помоћну променљиву и потом користити \(N\) у петљи, а помоћну изван петље где нам треба уместо \(N\) или обрнуто.

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

Напослетку, потребно је одредити да ли је сума цифара прост број.

Из 1. задатка знамо како да одредимо да ли је број прост. Када знамо да су први прости бројеви бројеви \(2\) и \(3\), онда било шта са фактором \(2\) или \(3\) није прост број. Уколико претходни услови нису задовољени проверавамо даље петљом од наредног познатог простог броја \(5\) до корена траженог броја, \(\sqrt{N}\), са кораком од \(6\); Ако је остатак при дељењу броја \(N\) са \(k\) или \(k+2\) једнак \(0\), где је \(k\) бројач петље, број \(N\) није прост број. У супротном, ако је остатак при дељењу \(N\) са свако \(k\) и \(k+2\) различито од \(0\), онда је број \(N\) прост. Негативни бројеви нису прости (јер је сваки могуће поделити барем са \(-1\)), као и бројеви \(0\) и \(1\) (ни прости ни сложени).

Уколико је \(N > 999\) кореговати га на \(N = 1000\). Бројачком петљом од \(100\) до \(N - 1\) пролазимо кроз све троцифрене бројеве, мање од \(N\). Склапањем горе наведених елемената решења у петљи добијамо и крајњи програм за решавање овог задатка.

Дијаграм тока алгоритма¶

Изворни код програма¶

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include <stdio.h>

main() {
    int n, i, k, s, m, isPrime;

    printf("Unesite ceo broj N: ");
    scanf("%d", &n);

    if (n > 999)
        n = 1000;

    for (i = 100; i < n; i++) {
        s = 0;
        m = i;

        while (m > 0) {
            s += m % 10;
            m /= 10;
        }

        isPrime = 1;

        if (s == 2 || s == 3) {
            isPrime = 1;
        }

        else if (s <= 1 || s % 2 == 0 || s % 3 == 0) {
            isPrime = 0;
        }

        else {
            k = 5;
            while (k * k <= s && isPrime) {
                if (s % k == 0 || s % (k + 2) == 0) {
                    isPrime = 0;
                }

                k += 6;
            }
        }

        if (isPrime) {
            printf("%d\n", i);
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include <stdio.h>

int digitSum(int n)
{
    return n < 10 ? n : digitSum(n / 10) + n % 10;
}

int isPrime(int n)
{
    int k, isPrime = 1;

    if (n == 2 || n == 3) isPrime = 1;
    else if (n <= 1 || n % 2 == 0 || n % 3 == 0) isPrime = 0;
    else {
        k = 5;
        while (k * k <= n && isPrime) {
            if (n % k == 0 || n % (k + 2) == 0)
                isPrime = 0;
            k += 6;
        }
    }

    return isPrime;
}

main() {
    int n, i;

    printf("Unesite ceo broj N: ");
    scanf("%d", &n);

    if (n > 999)
        n = 1000;

    for (i = 100; i < n; i++) {
        if (isPrime(digitSum(i))) {
            printf("%d\n", i);
        }
    }
}

Задатак 4.¶

Нацртати структурни дијаграм тока алгоритма и на програмском језику C написати структурни програм којим се одређују и приказују сви троцифрени бројеви чији је збир цифара једнак 17, а притом су дељиви са \(K\). Целобројни параметар \(K\) задаје корисник. Уколико се при извршавању програма за \(K\) унесе вредност \(7\), шта ће програм приказати на излазу?

Териотисање¶

У претходном, 3. задатку, приказано је већ одређивање збир цифара троцифреног, као и \(N\)–тоцифреног броја. Одређивање дељивости два броја могуће је провером да ли је остатак при дељењу два броја једнак \(0\), што добијамо употребом \(\bmod\)–уло оператора (\(\%\) у C програмском језику). Пуштањем бројачке петље од \(100\) до \(999\) са провером да ли је збир цифара броја једнак \(17\) и да ли је тренутно посматран троцифрен број дељив са унетим бројем \(К\), и ако јесте исписом тог броја, је управо и решење овог задатка.

Дијаграм тока алгоритма¶

Изворни код програма¶

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <stdio.h>

main() {
    int k, n, s, m;

    printf("Unesite ceo broj K: ");
    scanf("%d", &k);

    for (n = 100; n < 1000; n++) {
        s = 0;
        m = n;

        while (m > 0) {
            s += m % 10;
            m /= 10;
        }

        if (s == 17 && n % k == 0) {
            printf("%d\n", n);
        }
    }
}

Задатак 5.¶

Нацртати структурни дијаграм тока алфоритма и на програмском језику C написати структурни програм који одређује збир цифара задатог целог броја \(B\). Број цифара броја није унапред познат. Показати модификације претходног решења помоћу којих се може одредити:
а) бинарна репрезентација задатог броја,
б) октална репрезентација задатог броја,
в) хексадекадна репрезентација задатог броја.

Уколико се при извршавању програма за \(B\) унесе вредност \(138\), шта ће програм приказати на излазу?

Териотисање¶

Збир цифара \(N\)–тоцифреног броја је већ обрађено у 3. задатку – идеја је једноставна, када поделимо неки број са \(10\) остатак при дељењу је цифра јединица (цифра најмање тежине, која се налази скроз десно), а количник је број са једном цифром мање. Понављањем поступка можемо редом одвајати цифре и сумирати их.

Модификација решења за проналажење бинарне, окталне или хексадекадне репрезентације броја је проста – уместо одвајања цифара са \(10\) (базом декадног бројног система), чинићемо то са \(2\), \(8\), односно \(16\), и потом уместо сумирање цифара, приказивати их. Цифре добијене на овакав начин биће у супротном редоследу него што би требале да буду превођењем броја у тражене бројне системе, што сам задатак и налаже да тако и треба бити из напомене.

Дијаграм тока алгоритма¶

Изворни код програма¶

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#include <stdio.h>

main() {
    int b, n, s = 0;

    printf("Unesite ceo broj B: ");
    scanf("%d", &b);

    n = b;
    while (n > 0) {
        s += n % 10;
        n /= 10;
    }

    printf("Zbir cifara: %d\n", s);

    printf("\na) binarna reprezentacija: ");
    n = b;
    while (n > 0) {
        printf("%d", n % 2);
        n /= 2;
    }

    printf("\nb) oktalna reprezentacija: ");
    n = b;
    while (n > 0) {
        printf("%d", n % 8);
        n /= 8;
    }

    printf("\nc) heksadekadna reprezentacija: ");
    n = b;
    while (n > 0) {
        int c = n % 16;
        if (c < 10) {
            printf("%d", c);
        } else {
            printf("%c", 'A' + c - 10);
        }
        n /= 16;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include <stdio.h>

main() {
    int b, n, s = 0;

    printf("Unesite ceo broj B: ");
    scanf("%d", &b);

    n = b;
    while (n > 0) {
        s += n % 10;
        n /= 10;
    }

    printf("Zbir cifara: %d\n", s);

    printf("\na) binarna reprezentacija: ");
    n = b;
    while (n > 0) {
        printf("%d", n % 2);
        n /= 2;
    }

    printf("\nb) oktalna reprezentacija: ");
    n = b;
    while (n > 0) {
        printf("%o", n % 8);
        n /= 8;
    }

    printf("\nc) heksadekadna reprezentacija: ");
    n = b;
    while (n > 0) {
        printf("%x", n % 16);
        n /= 16;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#include <stdio.h>

int digitSum(int n) {
    int sum;

    if (n < 10) {
        sum = n;
    } else {
        sum = digitSum(n / 10) + n % 10;
    }

    return sum;
}

void convert(int n, int b) {
    int c;

    if (n < b) {
        c = n;
    } else {
        convert(n / b, b);
        c = n % b;
    }

    if (c < 10) {
        printf("%d", c);
    } else {
        printf("%c", 'A' + c - 10);
    }
}

main() {
    int b;

    printf("Unesite ceo broj B: ");
    scanf("%d", &b);

    printf("Zbir cifara: %d\n", digitSum(b));

    printf("\na) binarna reprezentacija: ");
    convert(b, 2);

    printf("\nb) oktalna reprezentacija: ");
    convert(b, 8);


    printf("\nc) heksadekadna reprezentacija: ");
    convert(b, 16);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int digitSum(int n) {
    int sum;

    if (n < 10) {
        sum = n;
    } else {
        sum = digitSum(n / 10) + n % 10;
    }

    return sum;
}

char getChar(int c) {
    return c < 10 ? '0' + c : 'A' + c - 10;
}

char *appendChar(char *str, char c) {
    int i = 0;

    while (str[i] != '\0') {
        i++;
    }

    str[i] = c;
    str[i + 1] = '\0';

    return str;
}

char *convertStr(int n, int b) {
    char *str = malloc(32);
    char c;

    if (str == NULL) {
        printf("Failed to allocate memory!");
        exit(1);
    }

    if (n < b) {
        c = getChar(n);
    } else {
        c = getChar(n % b);
        strcat(str, convertStr(n / b, b));
    }

    appendChar(str, c);

    return str;
}

main() {
    int b;

    printf("Unesite ceo broj B: ");
    scanf("%d", &b);

    printf("Zbir cifara: %d\n\n", digitSum(b));

    printf("a) binarna reprezentacija: %s\n", convertStr(b, 2));
    printf("b) oktalna reprezentacija: %s\n", convertStr(b, 8));
    printf("c) heksadekadna reprezentacija: %s\n", convertStr(b, 16));
}

Задатак 6.¶

Нацртати структурни дијаграм тока алгоритма и на програмском језику C написати структурни програм који за првих \(N\) природних бројева одређује и приказује њихове факторијеле, као и факторијеле њихових квадрата. Параметар \(N\) задаје корисник. Уколико се при извршавању програма за \(N\) унесе вредност \(10\), шта ће програм приказати на излазу?

Дијаграм тока алгоритма¶

Изворни код програма¶

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <stdio.h>

main() {
    int n, i, j;
    long double fact = 1, factSquare = 1;
    /* Sa `long double` moze se precizno racunati do 25!
     * Za vece faktorijele su pogresne vrednost, ali su na prvi pogled slicne u ciframa vecih tezina.
     * Pojasnjenje - https://stackoverflow.com/a/53387530 */

    printf("Unesite ceo broj N: ");
    scanf("%d", &n);

    for (i = 1; i <= n; i++) {
        fact *= i;

        for (j = i * i; j > (i - 1) * (i - 1); j--) {
            factSquare *= j;
        }

        printf("%3d! = %26.0Lf, %3d! = %26.0Lf\n", i, fact, i * i, factSquare);
    }
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103

#include <stdio.h>

#define DIGITS 200

void clear(int a[DIGITS]) {
    int i;

    for (i = 0; i < DIGITS; i++) {
        a[i] = 0;
    }
}

void print(int a[DIGITS], int p) {
    int i;

    for (i = p - 1; i >= 0; i--) {
        printf("%d", a[i]);
        if (i % 3 == 0 && i > 2) {
            printf(" ");
        }
    }
    printf("\n");
}

int toDigits(int n, int a[DIGITS]) {
    int p = 0;

    clear(a);

    while (n > 0) {
        a[p++] = n % 10;
        n /= 10;
    }

    return p;
}

int countDigits(int a[DIGITS]) {
    int i = DIGITS - 1;

    while (i > 0 && a[i] == 0) {
        i--;
    }

    return i + 1;
}

int multiply(int a[DIGITS], int b[DIGITS], int p, int q, int prod[DIGITS]) {
    int i, j, carry;

    clear(prod);

    for (j = 0; j < q; j++) {
        carry = 0;
        for (i = 0; i < p; i++) {
            prod[i + j] += carry + a[i] * b[j];
            carry = prod[i + j] / 10;
            prod[i + j] %= 10;
        }

        prod[j + p] = carry;
    }

    return countDigits(prod);
}

int copy(int a[DIGITS], int p, int b[DIGITS]) {
    int i;

    for (i = 0; i < p; i++) {
        b[i] = a[i];
    }

    return p;
}

main() {
    int n, m, o, a[DIGITS], b[DIGITS], c[DIGITS], d[DIGITS], p, q, r, s;

    printf("Unesite ceo broj N: ");
    scanf("%d", &n);

    p = toDigits(1, a);
    q = toDigits(1, b);

    for (m = 1; m <= n; m++) {
        r = toDigits(m, c);
        s = multiply(a, c, p, r,d);
        p = copy(d, s, a);

        for (o = m * m; o > (m - 1) * (m - 1); o--) {
            r = toDigits(o, c);
            s = multiply(b, c, q, r, d);
            q = copy(d, s, b);
        }

        printf("%d! = ", m);
        print(a, p);
        printf("%d! = ", m * m);
        print(b, q);
        printf("\n");
    }
}

Задатак 7.¶

Нацртати структурни дијаграм тока алгоритма и на програмском језику C написати структурни програм којим се у бројачкој петљи за целобројне вредности аргумента \(x\) из интервала од \(-N\) до \(N\) израчунава вредност \(y\) као:

Целобројни параметар \(N\) уноси корисник. Уколико се при извршавању програма за \(N\) унесе вредност \(5\), шта ће програм приказати на излазу?

Дијаграм тока алгоритма¶

Изворни код програма¶

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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

main() {
    int n, x;
    double y;

    printf("Unesite ceo broj N: ");
    scanf("%d", &n);

    for (x = -n; x <= n; x++) {
        if (x < 0) {
            y = pow(x, 2);
        } else if (x < 1) {
            y = x;
        } else {
            y = sqrt(x);
        }

        printf("x = %d; y = %g\n", x, y);
    }
}