Во многу примери кои ги разгледавме досега, работевме со броеви и правевме разни операции врз нив. Компјутерите се, на многу директен начин, поврзани со математиката. Ова веројатно не ве изненадува, имајќи во предвид се што знаете досега за програмирањето, и сите техники и примери кои ги разгледавме. Во некои области од компјутерската наука (како биоинформатиката, машинското учење и слично), потребно е инженерите да имаат исклучително високи познавања од разни математички поими и техники - за да може да придонесат во самата област. Во ова предавање, ќе зборуваме за неколку алгоритми кои ќе ви бидат од корист при решавањето на разни проблеми: проверка дали еден број е прост, пронаоѓање на најголем заеднички делител, ефикасно степенување, претворање на броеви од еден броен систем во друг, итн.

Прости броеви

За еден позитивен број N велиме дека е прост ако тој има само два делители: 1, и самиот тој број N. На пример, 5 е прост број, бидејќи единствените делители на тој број се 1 и 5. Од друга страна, 10 не е прост број, бидејќи е делив со 1, 2, 5 и 10. Првите неколку прости броеви се: 2, 3, 5, 7, 11, 13, 17, итн. По правило, 1 не е прост број (што може да се сфати и од фактот дека тој нема два делители).

Користејќи ја самата дефиниција за прости броеви, може да напишеме алгоритам кој проверува дали еден број N е прост: имено, ако постои број помеѓу 2 и N-1 кој го дели N, тогаш N не е прост (бидејќи, за бројот N да е прост, тој треба да е делив само со 1 и N, а да не е делив со ниту еден број помеѓу нив). Реализацијата на овој алгоритам е едноставна – имено, треба да напишеме само еден циклус кој ги изминува броевите помеѓу 2 и N-1, и проверува дали некој од нив е делител на N. За да знаеме дали некој број е делител на N, доволно е да провериме колку изнесува остатокот од делењето на N со тој број: ако остатокот е 0, ќе знаеме дека бројот е делител на N.

Но, дали постои поефикасен алгоритам за решавање на овој проблем? Пред да го откриеме истиот, да видиме кои се делители на бројот 200 (кој го земаме како пример):

1 2     4 5     8 10     20 25     40 50     100 200

Дали забележувате некоја шема? Обидете се да го разгледате производот на првиот број во листата (1) и последниот (200), вториот број (2) и претпоследниот (100), итн. Очигледно, за секој делител кој што е поголем од квадратниот корен на 200 (што е околу 14.142...), постои друг делител кој што е помал од квадратниот корен, и производот на тие делители е еднаков на 200 (1*200 = 200, 2*100 = 200, 4*50 = 200, итн). Ова е логично - имено, ако постојат два делители A и B, и нивниот производ А*B е еднаков на N, не може и двата броеви да се поголеми од квадратниот корен - бидејќи, во тој случај, нивниот производ ќе биде поголем од N. Земајќи во предвид дека целта на нашиот алгоритам е да провериме дали некој број е прост, нема потреба да ги тестираме сите броеви од 2 до N-1, и да проверуваме дали некој од нив е делител на N - туку доволно е да ги провериме само броевите до квадратниот корен на N. Ако не најдеме ниту еден делител до квадратниот корен на бројот, тогаш бројот е прост. Едноставно, ако постои некој делител поголем или еднаков на квадратниот корен, тогаш ќе постои и делител помал или еднаков на квадратниот корен - кој, ќе го пронајдеме со нашиот алгоритам.

Понатаму, пред да го имплементираме нашиот алгоритам, можеме да искористиме уште една идеја. Имено, ако N е број кој што е поголем од 2, и истиот е парен број (делив со 2), тогаш знаеме дека тој не е прост број (бидејќи е делив, покрај со 1 и со самиот себеси, и со 2). Од друга страна пак, ако бројот N е непарен број, тој не може да има делител кој е парен број (како 4, 8, 56, итн). Едноставно, ако N не е парен број (на пример, нека е еднаков на 159), однапред знаеме дека тој не е делив ниту со 4, ниту со 10, ниту со било кој друг парен број (имајќи предвид дека сите тие се деливи со 2). Користејќи ја оваа идеја, ако N е непарен број, при проверката дали е истиот прост број, нема потреба да бараме дали е тој делив со 4, 6, 8, 10, 12, 14, 16, 18, 20, итн. Едноставно, знаеме дека не е. На овој начин, можеме да го забрзаме нашиот алгоритам, проверувајќи ги како потенцијални делители само непарните броеви: 3, 5, 7, 9, 11, итн.

bool isPrime(int n)
{
     if(n < 2)
     {
          return false;       //nema prost broj pomal od 2
     }
     
     if(n == 2 || n == 3)
     {
          return true;        //2 i 3 se prosti broevi
     }
     
     if (n%2 == 0)
     {
          //tuka, znaeme deka N > 2 (drugite sluchai gi proverivme pogore).
          //ako istiot e deliv so 2, togash istiot ne e prost
          return false;
     }
     
     for(int i=3; i*i <= n; i+=2)    //namesto i<=sqrt(n), najchesto imame i*i <= n
     {
          if(n%i == 0)
          {
               //gi proveruvame samo neparnite broevi (i+=2 pogore)
               return false;
          }
     }
     
     return true;
}

Алгоритамот кој што го напишавме погоре проверува многу помалку делители од првобитната идеја која што ја наведовме (да ги провериме сите броеви од 2 до N-1). На пример, за да потврди дека N=104395301 е прост број, подобрениот алгоритам ќе провери само 5108 потенцијални делители, бидејќи ги проверуваме само непарните броеви (3, 5, 7, ...) кои се помали од квадратниот корен на бројот N.

Ератостеново сито

Доколку, за решавање на одреден проблем, има потреба да напишеме алгоритам со кој ќе изброиме колку прости броеви се наоѓаат во одреден опсег (на пример, колку прости броеви се помали од 100000), или решение во кое треба да ги најдеме сите прости броеви во одреден опсег, тогаш можеме да ја искористиме функцијата која што ја напишавме погоре - и, за секој број во опсегот, да провериме дали тој број е прост или не. Но, за овој проблем на пронаоѓање на повеќе прости броеви, можеме да искористиме еден алгоритам (Ератостеново сито) кој сите го имаме учено во училиште – (барем, идејата се учеше додека јас бев ученик).

Алгоритамот функционира на следниот начин. Најпрвин, создаваме низа со доволна големина за чување на сите броеви кои се наоѓаат до горната граница на опсегот. Идејата е, еден по еден, да ги поминеме сите броеви, и за секој број кој сеуште не е "пречкртан" (означен како број кој не е прост), да ги пречкртаме сите броеви на кои тој број им е делител - притоа, може да почнеме со разгледување само на вредностите кои се поголеми или еднакви на квадратот од тој број (сите останати ќе бидат "пречкртани" од некој од претходните броеви). По завршувањето на постапката, само простите броеви ќе останат непречкртани (неозначени). На пример, почнуваме со 2, и ги пречкртуваме сите броеви на кои 2 им е делител (почнувајќи од 2²): 4, 6, 8, 10, 12, 14, итн. Понатаму, одиме на 3, и ги пречкртуваме сите броеви на кои 3 им е делител (почнувајќи со квадратот): 9 (3²), 12 (3² + 3), 15 (3² + 6), 18 (3² + 9), итн. Бројот 4 е веќе пречкртан, па него го прескокнуваме (бидејќи, како што споменавме, пречкртувањето го правиме само почнувајќи од броеви кои сеуште не се пречкртани). Продолжувајќи со 5, ги означуваме броевите: 25 (5²), 30, 35, 40, 45, итн. На крајот од постапката, само броевите кои се прости ќе останат како непречкртани. Алгоритамот е едноставен за имплементација.

//odreduva kolku prosti broevi se pomali ili ednakvi na K
int sieve(int K)
{
     //niza, kade site vrednosti se 0 (nishto ne e prechkrtano)
     int marked[K+1];
     memset(marked, 0, sizeof(marked));
     
     marked[1] = 1; //1 ne e prost broj
     
     for(int i=2; i <= K; i++)
     {
          if(marked[i] == 0)     //brojot ne e prechkrtan
          {
               //prechkrtaj gi site broevi na koi "i" im e delitel
               for(int j=i*i; j <= K; j+=i)   //pochnuvame od "i*i", i zgolemuvame za "j+=i"
               {
                    marked[j] = true;
               }
          }
     }
     
     //tuka, marked[j] = 0, ako brojot e prost
     int counter = 0;
     for(int i=1; i<=K; i++)
     {
          if(marked[i] == 0)
          {
               counter++;
          }
     }
     
     return counter;
}

Овој алгоритам е исклучително ефикасен во откривањето на сите прости броеви до одредена горна граница, но истиот користи дополнителна меморија – за низата (во случајов, наречена marked) во која чуваме кои броеви се пречкртани, а кои не се. Зависно од самиот проблем кој го решаваме, како и колку меморија имаме на располагање, можеме да го користиме овој алгоритам, или да ги провериме сите броеви (еден по еден) за дали истите се прости, користејќи ја функцијата за проверка која беше дадена на почетокот на ова предавање. Најчесто, и двете решенија се доволно добри и ефикасни.

Претворање помеѓу бројни системи

При секојдневното решавање на математички задачи, правење на разни пресметки, плаќање со пари и слично, ги пишуваме и изговараме броевите во декаден броен систем - т.е. систем каде, за еден број, ако земеме дека цифрите се организирани во колони, тогаш секоја колона е 10 пати позначајна од претходната. На пример, кај бројот 3678 важи дека вредноста на тој број е 3*1000 + 6*100 + 7*10 + 8*1, односно имаме 3 илјадарки, 6 стотки, 7 десетки и 8 единици. За да ја добиеме вредноста на еден цел број, потребно е да ја помножиме цифрата на единиците со 10⁰=1, цифрата на десетките со 10¹=10, цифрата на стотките со 10²=100, цифрата на илјадарките со 10³=1000 итн, и така добиените вредности да ги собереме.

Но, покрај декадниот систем, постојат и други бројни системи. На пример, еден од нив е бинарниот броен систем, каде вредностите се претставуваат со помош на два симбола (две цифри): 0 и 1. Конкретно, во компјутерските системи се чуваат секакви податоци (нумерички вредности, знаци, реченици, слики, итн), само со користење на комбинации од нули и единици (кои може да бидат претставени преку разлика во напони, микроскопски точки кои различно одбиваат светлина - кај дисковите, или слично).

Бинарниот броен систем функционира на сличен начин како и декадниот броен систем, со таа разлика што наместо колоните да вредат десет пати повеќе од соодветните колони пред нив (10³, 10², 10¹, 10⁰), тие вредат два пати повеќе (2³, 2², 2¹, 2⁰). Нормално, наместо 10, сега ни се потребни само 2 цифри (0 и 1). На пример, 110 (запишано бинарно) има вредност 6, бидејќи 1*2² + 1*2¹ + 0*2⁰ = 1*4 + 1*2 + 0*1 = 6.

Покрај бинарниот броен систем, постојат и други системи, но тие се користат поретко. Интересно, само ќе наведеме дека е можно да се користат и бројни системи со повеќе од 10 знаци - и кај нив, за претставување на оние знаци кои вредат 10 или повеќе, користиме латинични букви за нивно претставување (па имаме, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f, итн). На пример, кај хексадецималниот броен систем, колоните вредат 16 пати повеќе од понезначајните колони пред нив - па, во тој систем, 3b (запишано во хексадецимален систем) има вредност 59, бидејќи имаме 3*(16¹) + 11*(16⁰) = 3*16 + 11 = 48 + 11. Бројот 11 доаѓа од фактот дека толку вреди знакот ‘b’, имајќи во предвид дека 9 има вредност 9, ‘a’ има вредност 10, па следна е ‘b’ со 11.

Нема да навлегуваме во повеќе детали за разните бројни системи (освен во примерите дадени подолу), бидејќи тие се учат и во училиште, за време на часовите по математика. Сепак, доколку сакате да дознаете повеќе, можете да го разгледате предавањето “Бинарен броен систем”, кое се наоѓа во другиот курс на овој веб-сајт (оној за основите на програмскиот јазик C++).

Веќе видовме како да ги добиеме вредностите на броевите запишани во друг броен систем. На пример, ако знаеме дека бројот 110 е запишан во бинарен броен систем, знаеме дека најдесната цифра треба да ја помножиме со 1, втората (од десно) со 2, третата (од десно) со 4, итн. Па, да напишеме функција која ќе го врши ова претворање на број (даден во одреден броен систем), така што вредноста на бројот ќе ја чуваме во променлива од целоброен тип (на пример, int), за да може да правиме други операции со самата вредност.

int to_integer(string number, int base)
{
     int value = 0;
     int factor = 1;
     
     //gi razgleduvame znacite od desno nalevo
     for(int pos=number.size() - 1; pos >= 0; pos--)
     {
          int digit;
          if(number[pos] >= 'a' && number[pos] <= 'z')
          {
               //’a’ ima vrednost 10, ‘b’ ima 11, itn.
               digit = (number[pos] - 'a') + 10;
          }
          else
          {
               //znak na cifra '0'-'9', dobij ja vrednosta kako broj
               digit = (number[pos] - '0');
          }
          
          //factor oznachuva kolku vredi ovaa cifra
          value += (digit * factor);
          
          //slednata cifra kje vredi "base" pati povekje
          factor *= base;
     }
     
     return value;
}

Се разбира, доколку работиме само со одреден броен систем (на пример, бинарниот броен систем, каде основата е base=2), нема потреба да го имаме делот каде проверуваме дали одреден знак е буква или бројка, и имплементацијата на функцијата ќе биде уште поедноставна. Слично, доколку сакате кодот да е уште пократок, можете да го искористите т.н. "условен оператор" (uslov ? izraz1 : izraz2), кој овозможува, зависно од исполнувањето или не на одреден услов (uslov), враќање на една од две можни вредности (izraz1 или izraz2). Па така, на пример, со "pogolemo=(a>b) ? a : b;" ја сместуваме поголемата вредност од a и b во променливата pogolemo. Во нашиот случај, целиот if/else исказ каде проверуваме дали вредноста е буква или не, можеме да го замениме со следната наредба:

int digit = (number[pos] >= 'a' && number[pos] <= 'z')
    ? (number[pos] - 'a') + 10
    : (number[pos] - '0');

Вториот (и последен) алгоритам кој ќе го разгледаме во овој дел од предавањето е како да запишеме одредена вредност (на пример, 6 - гледана во декадниот систем) во некој друг броен систем. На пример, сакаме на одредена функција да и ја испратиме вредноста 6, и информација дека сакаме истиот број да се претвори во бинарен броен систем, и на излез да добиеме 110. Накратко (доколку ова сеуште не сте го учеле на училиште, и не го прочитавте предавањето од другиот курс), алгоритамот за претворање во друг броен систем се сведува на делење на бројот со основата на бројниот систем (во овој пример, 2), и паметење на остатокот од делењето. Во случајот со 6, ќе имаме:

6 поделено со 2 = 3       и остаток 0
3 поделено со 2 = 1       и остаток 1
1 поделено со 2 = 0,      и остаток 1

Бидејќи дојдовме до 0, тука постапката завршува. Резултатот (бројот запишан во другиот броен систем) е листата од остатоци од делењето, прочитани во обратен редослед - од последниот остаток (тој од последното делење), па претпоследниот, итн. Значи, имаме 110. Како програмски код, имплементацијата изгледа вака:

string to_base(int value, int base)
{
     string result = "";
     
     while(value > 0)
     {
          int digit = (value % base);
          
          char character;  //koj e znakot za toj ostatok?
          if(digit >= 10)
          {
               //treba da go pretvorime vo bukva
               //ako digit=10 togash 'a', za 11 'b', itn
               character = (char)('a' + (digit - 10));
          }
          else
          {
               character = (char)('0' + (digit));
          }
          
          result += character;
          value /= base;   //(value = value/base) vo slednata iteracija
     }
     
     //bidejki znacite se zemaat od krajot
     reverse(result.begin(), result.end());
     return result;
}

На пример, доколку сакаме да го претвориме бројот 1935 во бинарен броен систем (основа 2), само ја повикуваме функцијата to_base(1935, 2). Повторно, доколку работиме само со специфичен броен систем (на пример, бинарниот) нема потреба да проверуваме (во имплементацијата на функцијата) дали остатокот е 10 или повеќе (за да користиме латинични букви). Во ова предавање, сакавме функцијата да е што покомплетна, и да работи со што повеќе бројни системи, па затоа имплементацијата е извршена на тој начин. Дополнително, слично како за претходниот алгоритам, да наведеме дека може да го искористиме условниот оператор “?:” за да добиеме уште пократок код.

Делење на броеви. Остаток

Веројатно, при пишувањето на разни програми, сте се сретнале со ситуација кога треба да поделите два цели броеви, или да проверите дали едниот број го дели другиот. Во ваквите задачи, често го користиме операторот ‘%’, каде резултатот од извршувањето на операцијата a%b е остатокот од делењето на бројот a со b. На пример, 10%3 е еднакво на 1 (10/3 e 3, со остаток 1 - бидејќи 10=3*3 + 1), 25%7 е еднакво на 4 (25/7 е 3, со остаток 4 - бидејќи 25=7*3+4), итн. Овој оператор се користи и при проверка на тоа дали еден цел број е делив со друг - во тој случај изразот a%b треба да е еднаков на 0 (бидејќи доколку b го дели а, нема да се појави остаток при нивното делење).

При решавањето на разни проблеми, користиме интересни својства на делењето и добиениот остаток. На пример, ако остатокот при делење со 2 е 0, тогаш имаме парен број (број делив со 2), а ако остатокот е 1, тогаш бројот е непарен. Слично, остатокот при делење со 10 ни ја дава последната цифра на бројот - па, на пример, остаток при делење на 1239237 со 10 е 7 - и, како што можете да забележите, 7 е последната цифра во 1239237. Најчесто, во дискусија, го користиме терминот “модул” наместо остаток, па велиме дека 1239237 е 7 по модул 10 (што значи дека, при делење на 1239237 со 10, имаме остаток 7), дека 19 е 1 по модул 2, итн.

Во овој дел од предавањето, сакаме да споменеме неколку интересни својства кај остатоците, бидејќи истите се користат кај разни задачи. Имено, доколку имаме два или повеќе броеви (на пример, A, B, C, D, и E), и истите треба да ги собереме (A+B+C+D+E), па да најдеме колку изнесува остатокот при нивно делење со некој број (на пример, 10), веројатно би го напишале следниот израз:

(A+B+C+D+E) % 10

Се разбира, овој израз ќе ни ја даде точната вредност, бидејќи тоа и беше побарано како пресметка: да се соберат броевите, па да се најде остатокот. Но, кај ваквите изрази можеме да го пресметаме остатокот и на делумните (помалите) изрази, па тие резултати да ги собереме, и повторно да побараме остаток. Со други зборови, можевме да го напишеме и следниот израз, добивајќи го истиот резултат:

(A%10 + B%10 + C%10 + D%10 + E%10) % 10

Забележете како пресметувавме остаток на секој чекор. Како поконкретен пример, ако некој побара од вас да ја пронајдете последната цифра на бројот кој се добива како збир на 12381 + 2183 + 54869 + 9514, сега знаете дека, покрај собирање на броевите па потоа разгледување на остатокот кој го има тој збир при делење со 10, можете и да го пресметате изразот:

(12381%10 + 2183%10 + 54869%10 + 9514%10)%10 = (1+3+9+4)%10=7

Се разбира, ова правило важи за било кој модул кој е позитивен цел број (не само 10). Слично, не моравме да пресметуваме остаток на секој чекор, туку (по наш избор) можеби само на некои места. Поконкретно, сите овие изрази ќе ни вратат идентична вредност (каде M е модулот):

(A+B+C+D+E) % M
(A%M + B+C + D%M + E%M) % M
((A+B)%M + (C+D+E)%M) % M, итн

Покрај за собирање, ова правило важи и кај множењето. Тука, можеме да видиме и зошто воопшто беше важно да ги споменеме овие својства. Имено, нека треба да пронајдеме кои се последните 2 цифри (што е идентично како барање на остаток при делење со 100) на бројот кој се добива со множење на 321357946, 149831191 и 435934376. Со други зборови, треба да го пресметаме изразот:

(321357946 * 149831191 * 435934376) % 100

Но, како што знаеме, постојат ограничувања на тоа колку големи броеви може да чуваме во променлива од целоброен тип (на пример, int). Производот на броевите кои ги имавме погоре е огромен (број со 26 цифри), кој не го собира во таква променлива. Но, бидејќи сега знаеме дека можеме да бараме остаток и претходно (за индивидуалните броеви), па потоа и за нивниот производ и слично, можеме да го пресметаме следниот израз:

((321357946%100) * (149831191%100) * (435934376%100)) % 100 = (46*91*76) % 100

По што добиваме резултат 36, што се и последните две цифри од производот на броевите 321357946 * 149831191 * 435934376, односно од 20989997731812202234349936. Ова својство на собирањето и множењето се користи во разни делови од компјутерската наука, како на пример во хеш табелите (каде пресметуваме вредности за тоа на која локација да се чува одредена вредност), итн. Слично, во натпреварите по информатика, често се среќаваме со проблеми каде, од нас, се бара да пресметаме одредена вредност по некој модул (т.е., колку изнесува остатокот при делењето на точната вредност, со тој модул), наместо од вас да се бара да користите (или да имплементирате) чудни податочни типови кои ќе чуваат броеви со илјадници цифри и слично. Едноставно, организаторите на тој натпревар сакаат да видат дали можете да напишете точен алгоритам - па, ако остатокот кој вие ќе го отпечатите е ист со остатокот од нивната (точна) програма, тогаш се знае дека вашиот алгоритам е точен.

Покрај за собирањето и множењето, оваа особина можеме да ја користиме и кај одземањето – но, со една разлика. Имено, кај одземањето сакаме пред секоја операција на одземање да ја додадеме вредноста M, каде M го означува модулот. Па така, доколку сакаме да ја пресметаме вредноста на изразот:

(A     -B     - C) % M

ќе имаме

(A%M   +M   -B%M     +M     -C%M) % M

Ова го правиме бидејќи не сакаме да го користиме операторот ‘%’ кога бројот од лево е негативен (а, при одземање, можеме да добиеме негативен број). Поради тоа, додаваме M пред секоја операција на одземање, бидејќи M нема да влијае на конечниот резултат (M е делител на M, па остатокот е 0), а ќе гарантираме дека вредностите од лево и десно на операторот ‘%’ нема да бидат негативни. Како пример, нека сакаме да пресметаме која е последната цифра ако од 159113, ги одземеме броевите 59 и 181. За да го пресметаме ова, можеме да го пресметаме изразот:

(159113%10     +10     - 59%10     +10     -181%10) % 10 =
(3 + 10 – 9 + 10 - 1) % 10 = 13 % 10 = 3.

Повеќе вакви примери ќе разгледаме во продолжение, каде ќе зборуваме за ефикасно степенување на броеви.

Најголем заеднички делител

Од основно училиште, знаеме дека најголем заеднички делител (НЗД) на два цели броеви A и B е најголемиот цел број кој е делител и на A и на B. На пример, најголем заеднички делител на 20 и 45 е 5, бидејќи 5 е најголемиот цел број кој е делител и на 20, и на 45. Постојат повеќе алгоритми за откривање на најголемиот заеднички делител на два броја, а наједноставниот од нив е да ги испробаме сите позитивни цели броеви (движејќи се надолу, кон 1), почнувајќи од помалиот од броевите А и B, се додека не дојдеме до број кој е делител на А и B. На пример, ако сакаме да го најдеме најголемиот заеднички делител на 20 и 45, можеме прво да пробаме дали 20 (помалиот број од 20 и 45) е делител на двата броја, па потоа да пробаме со 19, па 18, и така натаму, се додека не дојдеме до 5 и утврдиме дека тој број е делител и на двата броја.

Овој едноставен алгоритам функционира точно, но истиот е исклучително бавен кога броевите (А и B) се големи. Методот кој најчесто се користи за утврдување на најголем заеднички делител (НЗД) на два броја е т.н. Евклидов алгоритам. Имено, користејќи го овој алгоритам, за утврдување на најголемиот заеднички делител на броевите A и B потребно е да делиме броеви се додека не се појави остаток 0. Со други зборови, НЗД на броевите A и B е еднаков на НЗД(А, B)=НЗД(B, A%B), и ова правило го користиме се додека резултатот од операцијата за одредување остаток не стане еднаков на 0. Имплементацијата на оваа функција е исклучително едноставна:

int gcd(int a, int b)
{
     if(b == 0)
     {
          return a;
     }
     
     return gcd(b, a%b);
}

За примерот со 20 и 45, и наоѓањето на заеднички делител на тие два броја, најпрвин функцијата ќе се повика со аргументи a=20, и b=45. Во следниот повик, бидејќи остатокот од делењето на 20 и 45 е 20%45=20, функцијата ќе се повика со аргументи a=45 и b=20 (т.е. броевите ќе си ги сменат местата, што е случај кога првиот број е помал од вториот). Понатаму, во следниот чекор од рекурзијата (каде a=45, и b=20), остатокот од делењето на a%b е 5, па ќе се повика функцијата gcd(20, 5). Бидејќи 5 е делител на 20, остатокот од делењето на 20 со 5 е 0, па ќе имаме повик до gcd(5, 0), по што функцијата (имајќи предвид дека аргументот b=0) доаѓа до откритие дека најголемиот заеднички делител е бројот 5.

Покрај најголем заеднички делител, од основно училиште, сигурно се сеќавате и на поимот најмал заеднички содржател (НЗС). Имено, најмал заеднички содржател на два броеви A и B е најмалиот цел број кој е делив и со A, и со B - т.е., каде и A, и B, се делители на тој број. На пример, најмал заеднички содржател на броевите 20 и 45 е бројот 180, бидејќи 180 е најмалиот број за кој важи дека и 20, и 45, се делители на тој број. За откривање на најмалиот заеднички содржател, алгоритамот кој се користи се базира на фактот дека производот на броевите A и B е еднаков на производот на најголемиот заеднички делител (НЗД) и најмалиот заеднички содржател (НЗС) на тие броеви. Со други зборови, важи правилото дека A*B=НЗД(А, B)*НЗС(A, B). Од тука, лесно е да утврдиме дека НЗС на два броеви А и B е еднаков на (A*B)/НЗД(A, B). За откривање на најголемиот заеднички делител (НЗД), нормално, го користиме Евклидовиот алгоритам, кој го видовме претходно.

int lcm(int a, int b)
{
     return (a*b) / gcd(a, b);
}

Фактот дека најмалиот заеднички содржател (НЗС) можеме да го откриеме користејќи ја оваа формула е, донекаде, очигледно. Имено, најголемиот заеднички делител ги содржи елементите (факторите) на броевите A и B кои се појавуваат и во двата броја (бидејќи НЗД ги дели и двата броја), додека кај најмалиот заеднички содржател, баш овие делови се појавуваат само еднаш (бидејќи го бараме најмалиот број кој ги содржи и A и B, па нема потреба од повторување на тие делови од двата броја). Оттука, нивниот производ (на НЗД и НЗС) ги дава сите елементи од броевите A и B, па формулата A*B=НЗД(A, B)*НЗС(A, B) е логична, и истата е лесна за паметење.

Степенување на броеви

Степенување е математичка операција, каде одредена вредност x (наречена основа) се множи со себе n пати (каде n се нарекува експонент). Со други зборови, ако треба да го пресметаме изразот 3⁷, треба да пресметаме колку изнесува 3*3*3*3*3*3*3. Одговорот е 2187, па велиме дека 3⁷=2187. Но, што доколку експонентот претставува број кој има многу голема вредност - на пример, што доколку треба да пресметаме колку изнесува 3²⁹⁵¹?

Во ваков случај, имаме најмалку два проблеми. Првиот проблем е фактот дека вредноста на изразот е исклучително голема – во случајот со 3²⁹⁵¹, се работи за број со повеќе од 1000 цифри. Ваквите вредности не можеме да ги чуваме во променлива од тип int (која дозволува чување на вредности со големина до 2147483647), ниту пак во променлива од тип long long (која дозволува чување на вредности со големина до 9223372036854775807). Бидејќи, во пракса, ретко имаме потреба од чување на толку големи вредности, типовите int и long long се најчесто доволни за чување на сите броеви кои се среќаваат во реалноста. На пример, променлива од тип long long е доволна за чување на бројот на луѓе кои живеат на планетата, вкупниот буџет (во денари) на Република Македонија, итн. Наспроти тоа, кога работиме со степенување, најчесто ќе се бара од нас да ја пресметаме вредноста по одреден модул (остаток), па можеме да го искористиме наученото од претходните делови на ова предавање. Поради тоа, нема да се фокусираме на чувањето на толку големи броеви, бидејќи тие (едноставно) ретко се појавуваат во реалноста. Степенувањето и неговата вредност по одреден модул често се користи при хеширање, создавање на случајни броеви, итн.

Но, да го видиме сега вториот проблем. Нека треба да пресметаме колку изнесува вредноста 3²⁹⁵¹, по одреден модул (нека го крстиме MOD). Со други зборови, колку изнесува остатокот од 3²⁹⁵¹, кога таа вредност ќе се подели со MOD? Нормално, првата идеја која што ни паѓа на памет е да ги извршиме овие илјадници множења, и на тој начин да ја пресметаме вредноста. Со други зборови, можеме да го напишеме следниот алгоритам.

int power(int x, int n, int MOD)
{
     int result = 1;
     
     for(int i=0; i<n; i++)
     {
          result = (result * (x % MOD)) % MOD;
     }
     
     return result;
}

Остаток при делењето можеме да пресметуваме на секој чекор, како што видовме во претходниот дел од ова предавање - бидејќи резултатот ќе остане ист (важи за собирање, множење и одземање). Проблемот тука е што правиме огромен (и, како што ќе видиме, непотребен) број на множења. Компјутерите нема да имаат проблем да извршат илјадници множења (како во случајов), но што доколку експонентот е уште поголем? Дали постои попаметен (и поефикасен) начин да ја пресметаме бараната вредност? Интересно, постои попаметен начин, и истиот се фокусира на квадрирање (множење на еден број сам со себе), и паметење на тие вредности. Со други зборови, за да го пресметаме изразот 3²⁹⁵¹, можеме да ги пресметаме следните вредности, и потоа истите да ги искористиме за конечната пресметка:

3¹ = 3
3² = (3¹) * (3¹), т.е. со квадрирање на претходната вредност
3⁴ = (3²) * (3²), т.е. со квадрирање на претходната вредност
3⁸ = (3⁴) * (3⁴), т.е. со квадрирање на претходната вредност
3¹⁶ = (3⁸) * (3⁸), т.е. со квадрирање на претходната вредност
3³² = (3¹⁶) * (3¹⁶), т.е. со квадрирање на претходната вредност
3⁶⁴ = (3³²) * (3³²), т.е. со квадрирање на претходната вредност
3¹²⁸ = (3⁶⁴) * (3⁶⁴), т.е. со квадрирање на претходната вредност
3²⁵⁶ = (3¹²⁸) * (3¹²⁸), т.е. со квадрирање на претходната вредност
3⁵¹² = (3²⁵⁶) * (3²⁵⁶), т.е. со квадрирање на претходната вредност
3¹⁰²⁴ = (3⁵¹²) * (3⁵¹²), т.е. со квадрирање на претходната вредност
3²⁰⁴⁸ = (3¹⁰²⁴) * (3¹⁰²⁴), т.е. со квадрирање на претходната вредност

Сега, имајќи ги во предвид овие вредности, за пресметка на 3²⁹⁵¹ доволно е да почнеме со резултат=1, и потоа, тргнувајќи од најголемиот пресметан степен (во случајов, 3²⁰⁴⁸) надолу, да почнеме да го множиме тековниот резултат со вредностите (3²⁰⁴⁸, 3⁵¹², итн) кои се потребни за да дојдеме до точна пресметка на вредноста 3²⁹⁵¹. Во конкретниот случај, почнуваме од 3²⁰⁴⁸, и бидејќи 2048 е број кој е помал или еднаков на 2951, знаеме дека таа вредност (3²⁰⁴⁸) ни е потребна за точна пресметка на резултатот (па истата ја множиме со тековниот резултат). Понатаму, одземаме 2048 од 2951, бидејќи сега ни е потребно резултатот да го измножиме уште со степенот 2951-2048=903, за да дојдеме до конечната вредност (бидејќи 3²⁰⁴⁸ * 3⁹⁰³ = 3²⁹⁵¹). Оваа постапка ја продолжуваме разгледувајќи ги и останатите степени: 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, и 1.

//koristi C++11 - http://mendo.mk/Lecture.do?id=26

//ovaa funkcija gi sozdava stepenite -> x^0, x^1, x^2, x^4, x^8, x^16, itn.
vector<pair<int, int> > generatePowers(int x, int n, int MOD)
{
     vector<pair<int, int> > powers;
     powers.push_back({0, 1}); //x^0 = 1
     powers.push_back({1, x % MOD}); //x^1 = x
     
     int previousPower = x % MOD;
     for(int degree=2; degree <= n; degree *= 2)   //zabelezhete "degree *= 2"
     {
          int newPower = (previousPower * previousPower) % MOD;
          powers.push_back({degree, newPower});
          
          previousPower = newPower;
     }
     
     reverse(powers.begin(), powers.end());       //od najgolemite stepeni nadole
     return powers;
}

int power(int x, int n, int MOD)
{
     vector<pair<int, int> > powers = generatePowers(x, n, MOD);
     
     int result = 1;
     for(auto power : powers)
     {
          int degree = power.first;
          int value = power.second;
          
          if(degree <= n)
          {
               result = (result * value) % MOD;
               n -= degree;
          }
     }
     
     return result;
}

Забележете дека сите пресметки ги правевме по модулот MOD, бидејќи овие вредности (по степенувањето) стануваат огромни. Временската сложеност на овој алгоритам е O(logN), т.е. алгоритамот има логаритамска сложеност. За да пресметате одредена вредност, потребно е (само) да ја повикате функцијата power(). На пример, за да утврдиме кои се последните две цифри од вредноста 3²⁹⁵¹ (значи, не интересира таа вредност по модул 100), ја повикуваме функцијата со следните аргументи: power(3, 2951, 100).

Геометрија

Геометрија е дел од математиката, каде разгледуваме точки, форми, фигури, нивната релативна положба едни во однос на други, итн. Покрај поимите кои ги споменавме претходно, многу важен дел при дискусијата на геометриски проблеми игра т.н. координатен систем - каде користиме броеви (наречени координати) за утврдување на положбата на една или повеќе точки. Најчесто, користиме правоаголен координатен систем со две димензии (2Д), каде имаме хоризонтална оска (т.н. х-оска), и вертикална оска (т.н. y оска). На пример, на следната слика имаме две точки, каде точката A се наоѓа на позиција (-3, 2), а втората точка се наоѓа на позиција (4, 3). Притоа, првата координата во парот (x, y) ја покажува позицијата во однос на x оската, додека втората координата во парот (x, y) ја покажува позицијата во однос на y оската.

Во програмскиот јазик C++, бидејќи за чување на една точка ни е потребно да чуваме две вредности (за x, и за y координатата), за таа намена можеме да користиме пар од вредности pair<int, int> или pair<double, double>, зависно од тоа дали сите координати ќе бидат цели броеви или не. Покрај пар, можеме и да дефинираме нова структура (struct point), што ќе ни овозможи да ги нарекуваме координатите .x и .y, наместо .first и .second (ваков пример ќе видиме во продолжение). И двете опции се валидни, и се користат често. Доколку е потребно да чуваме повеќе точки, можеме да користиме низа од овие парови, или (многу почесто) низа со динамичка големина.

Доколку имаме две точки А и B, каде (x1, y1) се координатите на точката A, а (x2, y2) се координатите на точката B, можеме да го пресметаме растојанието помеѓу нив (што е многу честа операција при решавање на многу проблеми), со следната формула:

dist =   sqrt(     (x2-x1)² + (y2-y1)²     )

Како програмски код, ова би изгледало вака:

double dist(pair<int, int> A, pair<int, int> B)
{
     int x1 = A.first, y1 = A.second;
     int x2 = B.first, y2 = B.second;
     
     return sqrt(pow(x2-x1, 2) + pow(y2-y1, 2));
}

За крај, да разгледаме уште два интересни проблеми: утврдување дали одредена точка се наоѓа во внатрешноста на еден правоаголник, и дали два правоаголници се сечат или не. Правоаголниците ќе имаат страни кои се паралелни во однос на координатните оски. Ова се интересни и важни проблеми, бидејќи истите често се среќаваат во реалноста - каде одреден регион или град се организира плански, градиме згради или куќи кои се паралелни во однос на улиците, итн.

Најпрвин, да размислиме како да ја чуваме позицијата и изгледот на еден правоаголник. Дали ни е потребно да ја чуваме позицијата (во координатниот систем) на четири точки, или на помалку од тоа? Ако размислиме подобро, имајќи предвид дека знаеме дека сите страни на правоаголникот се паралелни со координатните оски, доволно ни е да ја чуваме позицијата на две темиња од правоаголникот кои се наоѓаат дијагонално едно наспроти друго. На пример, доволно е да ја чуваме позицијата на темето кое се наоѓа доле-лево и на темето кое се наоѓа горе-десно, како што можете да видите од сликата подолу. Само со чување на позициите на тие две темиња, можеме да го нацртаме правоаголникот во координатниот систем, бидејќи знаеме дека страните се паралелни со координатните оски - па лесно е да се утврди каде се наоѓаат и преостанатите две темиња од правоаголникот. На пример, од темето кое се наоѓа доле-лево, можеме да ја утврдиме y-координатата на темето кое се наоѓа доле-десно (бидејќи имаат иста y-координата, имајќи во предвид дека двете темиња се наоѓаат на долната страна). Слично, може да ја утврдиме x-координатата (на темето кое се наоѓа доле-десно) од темето кое се наоѓа горе-десно, бидејќи и двете темиња се наоѓаат на десната страна од правоаголникот.

Имајќи го ова во предвид, да пробаме да напишеме функција која ќе проверува дали една точка се наоѓа во внатрешноста на правоаголник, или не. Притоа, решението на овој проблем можеме да го напишеме на два начина. Со првиот начин, можеме да провериме дали точката се наоѓа помеѓу левата и десната страна на правоаголникот (за да е внатре во правоаголникот, точката треба да се наоѓа десно од левата страна на правоаголникот, и лево од десната страна), како и да провериме дали точката се наоѓа помеѓу горната и долната страна на правоаголникот. Ако се исполнети и двата услови, можеме да заклучиме дека точката се наоѓа во внатрешноста на правоаголникот. Притоа, ова е прилично лесно да се имплементира, имајќи во предвид дека веќе зборувавме како да ја чуваме позицијата на една точка (како пар од координати) и како да го чуваме правоаголникот (како два пара од координати, за темето кое се наоѓа доле-лево и за темето кое се наоѓа горе-десно).

Вториот начин на проверка се сведува на логично елиминирање на случаите кога точката се наоѓа надвор од правоаголникот. Имено, лесно можеме да провериме дали точката се наоѓа над горната страна на правоаголникот. Ако точката се наоѓа над горната страна на правоаголникот, тоа значи дека точката се наоѓа над самиот правоаголник, па веднаш можеме да заклучиме дека таа не е во внатрешноста на истиот. На ист начин, можеме да провериме дали точката се наоѓа лево од левата страна, подолу од долната страна, или десно од десната страна на правоаголникот – ако е исполнет било кој од овие услови, точката е надвор од правоаголникот. Ако ниту еден од условите не е исполнет, можеме да заклучиме дека точката се наоѓа во внатрешноста на правоаголникот.

//mozheme da koristime i pair<int, int> namesto nova struktura
struct point 
{
     int x, y;
};

bool inside(point lowerLeft, point upperRight, point point)
{
     if(point.x < lowerLeft.x)
     {
          //tockata e levo od pravoagolnikot, ima mala x koordinata
          return false;
     }
     
     if(point.y < lowerLeft.y)
     {
          //tockata e dolu od pravoagolnikot, ima mala y koordinata
          return false;
     }
     
     if(point.x > upperRight.x)
     {
          //tockata e desno od pravoagolnikot, ima golema x koordinata
          return false;
     }
     
     if(point.y > upperRight.y)
     {
          //tockata e gore od pravoagolnikot, ima golema y koordinata
          return false;
     }
     
     //inaku, tochkata e vnatre vo pravoagolnikot
     return true;
}

За крај, да наведеме дека, користејќи ја истата идеја, лесно е да провериме и дали два правоаголници имаат некоја заедничка точка (се сечат, или едниот се содржи во другиот). Ова е корисен пример, бидејќи при решавање на разни проблеми во реалноста, сакаме да провериме дали на некоја позиција има празен простор, или можеби таму веќе има некоја градба. Притоа, алгоритамот кој ќе го имплементираме се базира на слична идеја како и кај проверката дали една точка се наоѓа во правоаголник. Имено, веднаш е очигледно дека, ако долната страна на едниот правоаголник се наоѓа погоре од горната страна на другиот правоаголник, тогаш целиот прв правоаголник се наоѓа над другиот правоаголник. Слично, можеме да извршиме проверка и за левата, десната, и горната страна на правоаголникот. Ако ниту еден од овие услови не е исполнет (што би значело дека, во целост, првиот правоаголник не е ниту погоре, ниту полево, ниту подесно, ниту подолу од вториот правоаголник), тогаш правоаголниците се сечат или се препокриваат.

//lowerLeft1 i upperRight1 se tochkite koi go definiraat prviot pravoagolnik
//lowerLeft2 i upperRight2 se tochkite koi go definiraat vtoriot pravoagolnik
bool intersect(point lowerLeft1, point upperRight1, point lowerLeft2, point upperRight2)
{
     if(lowerLeft1.y > upperRight2.y)
     {
          //dolnata strana na prviot pravoagolnik e nad vtoriot pravoagolnik
          return false;
     }
     
     if(upperRight1.y < lowerLeft2.y)
     {
          //gornata strana na prviot pravoagolnik e pod vtoriot pravoagolnik
          return false;
     }
     
     if(lowerLeft1.x > upperRight2.x)
     {
          //levata strana na prviot pravoagolnik e desno od vtoriot pravoagolnik
          return false;
     }
     
     if(upperRight1.x < lowerLeft2.x)
     {
          //desnata strana na prviot pravoagolnik e levo od vtoriot pravoagolnik
          return false;
     }
     
     //imaat zaednichka tochka
     return true;
}

Ова предавање беше малку подолго од останатите, но целта ни беше да повториме што повеќе поими од математиката (дел од нив ги имате учено и во основно училиште), и да видиме како одредени операции може да се имплементираат ефикасно. Разгледувањето на што повеќе проблеми, и имплементацијата на нивните решенија, придонесува за подобрување на начинот на кој размислуваме кога се среќаваме со нов проблем - а разгледувањето на решенија напишани во одреден програмски јазик може да ви помогне да пишувате подобар програмски код.

Дозвола за користење: CC BY-NC 2.5 ©