C keeles faktoriaali arvutamine: Samm-sammult juhend ja praktilised näited

1. Mis on faktoriaali arvutamine C keeles?

Selles artiklis õpime faktoriaali arvutamise põhitõdesid C keeles. Faktoriaal (factorial) tähendab naturaalarvu n puhul kõigi arvude korrutist vahemikus 1 kuni n. Matemaatiliselt väljendatakse seda nii:

• n! = n × (n – 1) × (n – 2) × … × 1

Seda arvutust kasutatakse oluliselt kombinatoorikas, tõenäosusteoorias ja arvujadade arvutustes. Näiteks 3! (3 faktoriaal) on 3 × 2 × 1 = 6. Selles artiklis selgitame üksikasjalikult, kuidas seda C keeles programmeerida.

2. Faktoriaali arvutamise põhimeetod: for-tsükli kasutamine C keeles

Esmalt õpime, kuidas faktoriaali arvutada for-tsükliga. See meetod ei kasuta rekursiivseid funktsioone ning on suhteliselt lihtne ja arusaadav.

Põhiline for-tsükliga realiseerimine

Allpool on näide koodist, mis arvutab faktoriaali for-tsükli abil C keeles.

#include <stdio.h>

int main() {
    int n, i;
    unsigned long long factorial = 1;  // Muutuja faktoriaali tulemuse hoidmiseks

    printf("Sisestage täisarv: ");
    scanf("%d", &n);

    // Kui arv on negatiivne, kuvatakse veateade
    if (n < 0)
        printf("Negatiivse täisarvu faktoriaali ei eksisteeri.\n");
    else {
        // Faktoriaali arvutamine
        for (i = 1; i <= n; ++i) {
            factorial *= i;
        }
        printf("%d faktoriaal = %llu\n", n, factorial);
    }

    return 0;
}

Selgitus

• unsigned long long tüüpi kasutatakse, sest faktoriaali arvutamisel võivad tulemused olla väga suured. Tavaline int tüüp ei pruugi piisata, seega kasutatakse suurema vahemikuga tüüpi.
• Tsükkel kordub 1-st kuni n-ni ning igal iteratsioonil korrutatakse factorial muutujale praegune väärtus juurde.

See meetod on lihtne ja sobib faktoriaali arvutamise põhimõtte mõistmiseks. Järgmisena vaatleme rekursiivse funktsiooni kasutamist.

3. Faktoriaali arvutamine rekursiivse funktsiooniga

Faktoriaali saab arvutada ka rekursiivse funktsiooniga. Rekursiooni kasutades on kood lühem ja lähedasem faktoriaali matemaatilisele definitsioonile.

Rekursiivne teostus

Järgnevalt on näide koodist, mis arvutab faktoriaali rekursiivse funktsiooniga C keeles.

#include <stdio.h>

// Rekursiivse funktsiooni definitsioon
unsigned long long factorial(int n) {
    if (n == 0 || n == 1)
        return 1;  // Baastingimus: kui n on 0 või 1, tagasta 1
    else
        return n * factorial(n - 1);  // Rekursiivselt korruta n ja (n-1) faktoriaal
}

int main() {
    int n;
    printf("Sisestage täisarv: ");
    scanf("%d", &n);

    if (n < 0)
        printf("Negatiivse täisarvu faktoriaali ei eksisteeri.\n");
    else
        printf("%d faktoriaal = %llu\n", n, factorial(n));

    return 0;
}

Selgitus

• Rekursiivses funktsioonis on kõigepealt seatud baastingimus (kui n on 0 või 1). Selle puudumisel jätkuks rekursioon lõputult, seega on õige lõpetamistingimus oluline.
• Rekursiivne protsess vastab hästi faktoriaali matemaatilisele definitsioonile (n! = n × (n – 1)!). Seetõttu on seda intuitiivselt lihtne mõista.

Rekursiooni kasutamine muudab koodi loetavamaks ja lihtsamaks, kuid väga suurte väärtuste korral võib jõudlus langeda võrreldes tsükliga.

4. Veakäsitlus ja andmetüüpide valik

Faktoriaali arvutamisel võivad väärtused muutuda väga suureks ja põhjustada ülevoolu (overflow). Samuti tuleb arvestada negatiivsete arvude sisestamisega.

Ülevoolu vältimine

Kuna faktoriaali tulemus kasvab kiiresti, ei pruugi tavaline int tüüp piisata. Sellepärast kasutatakse unsigned long long tüüpi, mis võimaldab arvutada suuremaid väärtusi.

Kui sellestki jääb väheks, võib kasutada suuremate arvude teeke, näiteks GNU MP.

Veakäsitlus negatiivsete arvude puhul

Faktoriaal pole negatiivsete arvude puhul defineeritud, seega tuleb kasutajale kuvada veateade.

if (n < 0)
    printf("Negatiivse täisarvu faktoriaali ei eksisteeri.\n");

Nii saab kasutaja vigast sisestust vältida ning programm toimib ootuspäraselt.

5. Faktoriaali arvutuse rakendused

Faktoriaali arvutust kasutatakse laialdaselt matemaatikas ja algoritmides. Allpool mõned praktilised näited:

Kombinatsioonide arvutamine

Kombinatsioonid (combinations) tähendavad, mitmel moel saab valida teatud arvu elemente antud hulgast. Selleks kasutatakse faktoriaali järgmiselt:

• C(n, r) = n! / (r! * (n – r)!)

Seda saab lihtsalt C keeles faktoriaali funktsiooni abil teostada.

Tõenäosuste arvutamine

Tõenäosusteoorias kasutatakse faktoriaali sageli, eriti permutatsioonide ja kombinatsioonide puhul.

6. Jõudluse optimeerimine

Faktoriaali arvutamise jõudlust saab parandada mitmel moel. Rekursiooni kasutades võib jõudlus langeda sügava pesastuse tõttu, seega memotiseerimine ja tsükli optimeerimine on kasulikud.

Memotiseerimine

Memotiseerimine tähendab juba arvutatud tulemuste salvestamist ning nende uuesti kasutamist, et vältida dubleerivat arvutamist. Nii saab rekursiooni jõudlust parandada.

7. Kokkuvõte ja järgmised sammud

Selles artiklis õppisime C keeles faktoriaali arvutamise põhimõtteid, rekursiivsete funktsioonide kasutamist, veakäsitlust ning jõudluse optimeerimist. Faktoriaal on oluline mõiste matemaatilistes ja algoritmilistes probleemides. Proovige kindlasti ka ise kirjutada faktoriaali arvutavaid programme!

Järgmised sammud

Proovige kasutada faktoriaali arvutust mõnes praktilises projektis või rakenduses. Näiteks võite proovida:

• Keerukamad algoritmid
  Rakendage faktoriaali kombinatsioonide või tõenäosuste arvutamiseks – see on kasulik võistlusprogrammeerimisel ja matemaatikaülesannetes.
• Suurte andmete optimeerimine
  Kui töötlete suuri andmekogumeid, on oluline optimeerida faktoriaali arvutust. Katsetage memotiseerimise või dünaamilise programmeerimisega, et muuta kood efektiivsemaks.