Nepriklausomai nuo to, ar esate profesionalūs programuotojai, ar tik šiek tiek išmanote programavimą, o gal tiesiog norėtumėte išmanyti, neišvengiamai teks susidurti ir įsisavinti įvairias programavimo technologijas. Programavimo technologijomis galime laikyti visas priemones ir būdus, kurių reikia norint sukurti veikiančią programą: pirminį matematinį algoritmo modelį; programinį algoritmą, pagal kurį veiks mūsų programa; programavimo kalbą; programavimo kalbą palaikančią ir kompiliavimą atliekančią programą; programavimo kodo formatą ir t.t. Dažnai manoma, jog profesionaliam programavimui užtenka geros programavimo kalbos išmanymo, tačiau kaip matome iš gilesnio žvilgsnio į programavimo technologiją, reikia kur kas platesnių žinių.

Kad būtų paprasčiau suprasti, kuo svarbus atskirų programavimo technologijų išmanymas, šiame straipsnyje pristatysiu vieną konkretų pavyzdį, iš kurio labai aiškiai matysis atskiros programavimo technologijos ir jų pritaikymo nauda. Paimkime labai paprastą užduotį, kurią paprastai gauna tik pradedantys mokytis programavimo jaunieji programuotojai. Tai yra pirminių skaičių radimas. Ir mūsų užduotys skambės taip: „Parašykite algoritmą, nustatantį ar duotasis natūralusis skaičius yra pirminis ar sudėtinis“.

Norint atlikti šią užduotį, visų pirma reikia išsiaiškinti, kas yra pirminis skaičius – kitaip tariant, sudaryti pirminį matematinį modelį.

Pirminis skaičius yra bet kuris natūralusis skaičius, didesnis už 1, kuris dalinasi tik iš vieneto ir savęs. O visi natūralus skaičiai, kurie nėra pirminiai skaičiai, vadinami sudėtiniais skaičiais. Vienetas nelaikomas nei pirminiu skaičiumi, nei sudėtiniu. Pirminio skaičiaus pavyzdys yra skaičius 11, nes jis be liekanos dalinasi tik iš 1 ir iš savęs. Tuo tarpu skaičius 8 nėra pirminis skaičius, nes jis dalinasi ne tik iš vieneto ir savęs, bet ir iš skaičių 2 ir 4.

Dabar, kai išsiaiškinome kas yra pirminis skaičius, galime pereiti prie programos algoritmo ir galiausiai pradėti rašyti pačią programą, kuri surastu pirminį skaičių. Šiam tikslui aš naudosiu C++ kalbą.

Tą patį rezultatą galima gauti rašant labai įvairų programinį kodą. Visą programą galima sutalpinti į vieną funkciją arba naudoti kelias funkcijas. Kaip rašyti kodą irgi yra vienas iš technologinių pasirinkimų. Nors iš pirmo žvilgsnio jis gali atrodyti ir nereikšmingas, bet iš tiesų jis yra labai svarbus programavime.

Funkcija yra programavimo kalbos vienas iš smulkiausių struktūrinių blokų. Kuo programa labiau struktūrizuota pagal jos loginį veikimą, tuo lengviau skaityti ir suprasti programinį kodą.

Žemiau yra visas veikiantis programos kodas, nustatantis ar duotasis skaičius yra pirminis.

#include <iostream> #include <math.h>

bool isPrime(unsigned number) {
    for (unsigned i = 2; i < number; ++i) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    unsigned x = 0;
    std::cout << "Enter a number: ";
    std::cin >> x;
    
    if (x < 2) {
        std::cout << "Invalid input. Number must be greater than 1" << std::endl;
    }
    else if (x == 2) {
        std::cout << x << " is a prime number." << std::endl;
    }
    
    if (isPrime(x)) {
        std::cout << x << " is a prime number." << std::endl;
    }
    else {
        std::cout << x << " is not a prime number." << std::endl;
    }
    
    return 0;
}

Šis programos kodas turi du struktūrinius blokus – main() ir isPrime(). Funkcija main() atsako už bendravimą su programos vartotoju, o isPrime() funkcija atsakinga už nustatymą ar duotasis skaičius yra pirminis ar ne. Galima butu sujungti main() ir isPrime() funkcijas į viena funkciją, bet kai kodas padalintas į atskirus funkcinius blokus, jį yra žymiai lengviau skaityti bei kaip pamatysime vėliau – tai taip pat padeda lengviau keisti ir tobulinti kodą.

Jei bandytume šioje programoje aprašytą algoritmą paaiškinti paprastais žodžiais, tai skambėtų taip: skaičius x yra pirminis, jei jis didesnis arba lygus 2 bei nesidalina iš natūraliųjų skaičių esančių intervale nuo 2 iki x-1. Šis algoritmas sėkmingai atlieka savo funkciją. Tai yra, nustato ar duotasis skaičius yra pirminis ar ne. Bet jis labai neefektyvus. Nes jei skaičius yra pirminis, algoritmas atliks x-2 skaičiavimų, kad pasakytų, jog tai pirminis skaičius. Bet algoritmą galima nesunkiai patobulinti, kad skaičiavimų sumažėtų dvigubai.

Jei tikrinsime ar skaičius 11 yra pirminis ar ne, naudodami aukščiau minėtą programą, algoritmas atliks 9 skaičiavimus, kad pasakytų, jog skaičius 11 yra pirminis. Pažiūrėkime kokie skaičiavimai atliekami.

1. 11 / 2 = 5,5
11 / 3 = 3,666
11 / 4 = 2,75
11 / 5 = 2,2
11 / 6 = 1,8333
11 / 7 = 1,571
11 / 8 = 1,375
11 / 9 = 1,222
11 / 10 = 1,1

Jei gerai įsižiūrėsime į dalybos rezultatus, pastebėsime, kad jei skaičių 11 daliname iš didesnio skaičiaus nei (11 / 2) tai dalybos rezultatas yra visada tarp 1 ir 2. Todėl norint nustatyti ar skaičius yra pirminis ar ne, dalyba iš skaičiaus, kuris yra didesnis nei pusė ieškomo skaičiaus, yra tik skaičiavimų švaistymas. Todėl norint padaryti efektyvesnį algoritmą, mums tereikia paredaguoti isPrime() funkciją. Paredaguota isPrime() funkcija atrodo taip:

bool isPrime(int number) {
    for (unsigned i = 2; i <= (number / 2); ++i) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}

Viskas ką pakeitėme – „for (unsigned i = 2; i < number; ++i)“ į „for (unsigned i = 2; i <= (number / 2); ++i)“. Ir mūsų algoritmas jau dvigubai greitesnis. O jei naująjį algoritmą bandysime paaiškinti paprasta kalbamąja kalba, jis skambės taip: „skaičius x yra pirminis skaičius, jei jis didesnis arba lygus dviem bei jei jis nesidalina iš natūraliųjų skaičių esančių intervale nuo 2 iki (x / 2)“.

Bet šis algoritmas vis tiek nėra toks efektyvus koks galėtų būti. Tačiau norint pamatyti, kur galima dar labiau patobulinti šitą algoritmą, mums reikia naujo pavyzdžio. Nors šį pavyzdį ir ankstesnieji algoritmai atliktų greitai, bet jis atskleidžia kaip galima dar labiau sumažinti skaičiavimų skaičių kol randamas pirminis skaičius.

1. 24 / 2 = 12
24 / 3 = 8
24 / 4 = 6
24 / 5 = 4,8
24 / 6 = 4
24 / 7 = 3,428
24 / 8 = 3
24 / 9 = 2,666
24 / 10 = 2,4
24 / 11 = 2,1818
24 / 12 = 2

Gerai įsižiūrėjus, kokius rezultatus gauname dalindami skaičių 24 iš natūraliųjų skaičių, esančių intervale nuo 2 iki (24 / 2) pastebėsime, kad kažkuriuo momentu daliklis ir dalmuo pasikeičia vietomis. Tai yra, skaičiavimai 1 ir 11 yra tapatūs ir tik dalmuo bei daliklis pasikeitę vietomis. Tokių skaičių poros šiame pavyzdyje yra: (2; 12), (3; 8) ir (4; 6). Kas reiškia, kad jei skaičius dalinasi iš 4 ir dalmuo yra 6, nebereikia tikrinti ar skaičius dalinasi iš 6. Nes skaičius tikrai iš jo dalinsis. Tai iki kokio skaičiaus mums reikia tikrinti dalybą?

Kur yra šis lūžio taškas geriausiai būtų matyti jei naudotume ne skaičių 24, o skaičių 25. Ir šis lūžis būtų ties eilute 25 / 5 = 5. Arba kitaip tariant, būtų ties skaičiaus 25 kvadratine šaknimi. Todėl vėl galime paredaguoti isPrime() funkciją ir gauti naują efektyvesnį skaičiavimų algoritmą:

bool isPrime(int number) {
    for (unsigned i = 2; i <= sqrt(number); ++i) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}

Nors ir vėl algoritmo greitį padvigubinome, lyginant su antruoju algoritmo variantu, vis tiek galima šį algoritmą dar patobulinti. Ir šis paskutinis patobulinimas labai gerai matosi iš pavyzdžio su skaičiumi 24. Jei skaičius dalinasi iš lyginio skaičiaus – tai jis dalinsis ir iš 2. Arba kitaip sakant, jei skaičius nesidalina iš 2 – tai jis nesidalins iš jokio lyginio skaičiaus. Todėl jei patikrinus gauname, kad skaičius nesidalina iš 2 – tai nebereikia tikrinti ar skaičius dalinasi iš 4, 6, 8 ir t.t. Todėl dar kartą galime patobulinti savo isPrime() funkciją:

bool isPrime(int number) {
    if (number % 2 == 0) {
        return false;
    }
    
    for (unsigned i = 3; i <= sqrt(number);) {
        if (number % i == 0) {
            return false;
        }
        i += 2;
    }
    return true;
}

Taigi, dabar jau turime keturis algoritmus, kurie randa ar pateiktas skaičius yra pirminis ar ne, bet jie vienas už kitą efektyvesni. Jei efektyvumu lygintume pirmąjį ir paskutinį algoritmus, jų efektyvumas skirtus apie 19 kartų arba 1900%. 

Nors šis pavyzdys labai paprastas, bet jis labai vaizdžiai parodo, kaip naujų skaičiavimo technologijų panaudojimas gali algoritmų efektyvumą padidinti šimtais procentų. Tuo pačiu tai parodo, kad iš pirmo karto parašytas kodas dažniausiai nėra toks idealus, kad jo jau nebūtu galima patobulinti.

Apibendrintai galima pasakyti, kad šiame straipsnyje vaizdžiai pristačiau kelias programavimo technologijas: matematikos ir programavimo žinių naudojimą algoritmų kūrime bei tobulinime, ir programos suskirstimo į atskirus funkcinius blokus.Į atskirus programinius blokus suskirstytą programą ne tik lengviau skaityti, bet ir lengviau redaguoti.

Komentarai (44)