Tower of Hanoi

Проблемот на Ханојски кули (Tower of Hanoi) е позната математичка игра.

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

Во еден потег може да биде поместен само еден диск.

Секој потег се состои од земање на еден диск кој се наоѓа на врв на некое стапче и негово преместување најгоре врз другите дискови на некое друго стапче.

Не може еден диск да се постави врз друг помал диск.

Интересна игра со навистина едноставни правила. Најголем дел од вас ја сретнале загаткава како пример за рекурзија во основните курсеви за програмирање.

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

Рекурзивно многу е кратко решението, иако изгледа комплицирано на прв поглед.

#include<iostream>
using namespace std;

void hanoi(int N, char from, char to, char other) {
 if (N == 0) return;
 // we move N-1 disks from "from" to "other"
 hanoi(N-1, from, other, to);
 // we move the biggest disk from "from" to "to"
 cout<<"I moved "<<N<<" from "<<from<<" "<<to<<"\n";
 // we move N-1 disks from "other" to "to"
 hanoi(N-1, other, to, from);
}

int main() {
 int i,j,k;
 hanoi(4, 'A', 'C', 'B');
 cin>>i;
 return 0;
}

Еве го решението во C++. Како што можеме да забележиме, и без да ја сфатиме логиката гледаме дека е едноставна рекурзија која има почетен услов и рекурзивно двапати се повикува самата функција hanoi. Меѓувреме се печати нешто на екран.

Да го проучиме подлабоко проблемот.

Да ги дефинираме параметрите на функцијата и потоа преку опис на параметрите на функцијата да ја дефинираме почетната состојба.

void hanoi(int N, char from, char to, char other);

Првиот аргумент N претставува број на дискови кои сакаме да ги префлиме од дискот кој е обележан како from кон дискот обележан како to. Третиот параметар (иако може да се исфрли) го претставува третиот диск кој индиректно ќе биде искористен при поместувањето.

Значи ако функцијата hanoi ни го решава соодветниот генерален проблем на Ханојските кули, ние со повикување на оваа функција со параметри hanoi(N, 'A', 'C', 'B') го решаваме нашиот конкретен проблем, пренесување на N дискови од дискот обележан како 'A' кон дискот обележан како 'C'.

Сега да ја разгледаме "маѓијата" внатре во функцијата.

Клучната чекор кој го правиме е делењето на еден проблем на потпроблеми од ист тип.

Значи треба некако соодветниот проблем префрлање на N дискови од дискот from кон дискот to да го поедноставиме.

Ако сакаме да префлиме N дискови од дискот from, тогаш знаеме дека тие N дискови се наоѓаат најгоре на стапчето и се наредени по растечки редослед од горе кон доле. Притоа ако најгорниот диск го обележиме со 1, и како одиме надоле давајќи повисоки индекси, дискот обележан како N ќе биде најголем во оваа група од N дискови.

Кога добро ќе се сфати ова идеме на следна фаза.

Префрламе N дискови од A кон C така што прво префламе N-1 дискови од A кон B, потоа дискот кој што ќе остане најгоре на A го префрламе на C, потоа ги префрлуваме (N-1) -те дискови од B кон C.

Да повториме уште еднаш, овојпат наместо A ставаме from, наместо C ставаме to, наместо B ставаме other.

Префрламе N дискови од from кон to така што прво префламе N-1 дискови од from кон other, потоа дискот кој што ќе остане најгоре на from го префрламе на to, потоа ги префрлуваме (N-1) -те дискови од other кон to.

Имаме и почетен услов со кој прекинува рекурзијата, кога бројот на дискови кои треба да се префрлат е нула.

AVL стебла

AVL стебло е балансирано бинарно стебло. За AVL стеблата важи, висините на двете потстебла секој јазол се разликуваат најмногу за 1 па затоа се вели дека е балансирано по висина. Пребарување, додавање на елемент и бришење се со комплексност O(log N) време, ова е просечно време и најлошо време истовремено, кадe N е број на јазли во стеблото пред операцијата. Додавање и бришење на елемент како операции може да вклучат ребалансирање на стеблото со една или повеќе ротации на стеблото.

AVL е многу корисно за решавање на разни типови на проблеми кај кои се бара голема ефикасност. Следува мојата имплементација (во Java) и објаснување за секоја операција поединечно. Ви препорачувам пред да го разгледате кодот да прочитате повеќе за AVL стеблата, на крај има линкови.

class Node {
Node left;
Node right;
Node parent;
int value;
int height;

Node () {
 left = null;
 right = null;
 parent = null;
 height = 1;
}

Node (int value) {
 left = null;
 right = null;
 this.value = value;
 height = 1;
}

}

Јазелот е посебна класа која се состои од покажувачи кон левото и десното дете, покажувач кон родителот, вредноста што ја чува јазелот т.е. клучната информација според која се сортираат податоците (во овој случај е број) и висина на стеблото.

int getHeight(Node mom) {
if (mom == null) return 0;
return mom.height;
}

int ballanceFactor(Node mom) {
if (mom == null) return 0;
int lh = getHeight(mom.left);
int rh = getHeight(mom.right);
return rh-lh;
}

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

Следува објаснувањето за "најкомплицираниот" дел, ротацијата. На сликата се објаснети четирите случаи (кои воглавно се сведуваат на два симетрични).

Node rightRightCase(Node mom) {
if (mom == null) return null;

Node R = mom.right;
Node T2 = R.left;

if (mom.parent.left == mom) {
 mom.parent.left = R;
} else {
 mom.parent.right = R;
}

R.parent = mom.parent;

R.left = mom;
mom.parent = R;

mom.right = T2;
if (T2 != null) T2.parent = mom;

mom.height = Math.max(getHeight(mom.left), getHeight(mom.right))+1;
R.height = Math.max(getHeight(R.left), getHeight(R.right))+1;

return R;
}

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

R е десното дете, а Т2 е левото дете на јазелот mom. Она што во овој код го правиме е известување до родителот на mom дека дете веќе нема да му биде mom туку R. Потоа ги менуваме местата на mom и R, ротираме на лево. Потстеблото Т2 станува десно потстебло на Т2. Правиме ажурирање на висините на mom и R и како резултат функцијата враќа покажувач кон R, за да знае повикувачот на овој метод кој е јазелот кој си го сменил местото со mom.

Node rightLeftCase(Node mom) {
leftLeftCase(mom.right);
return rightRightCase(mom);
}

Овој случај е двојна ротација. Прво го ротираме на десно стеблото чиј корен е mom.right, па потоа вршиме ротација на лево со референтен јазел во mom.

Напомена: rightRightCase е аналогно со ротација на лево, а leftLeftCase е аналогно со ротација на десно.

Node leftLeftCase(Node mom) {
if (mom == null) return null;
Node L = mom.left;
Node T2 = L.right;

if (mom.parent.left == mom) {
 mom.parent.left = L;
} else {
 mom.parent.right = L;
}

L.parent = mom.parent;

L.right = mom;
mom.parent = L;

mom.left = T2;
if (T2 != null) T2.parent = mom;

mom.height = Math.max(getHeight(mom.left), getHeight(mom.right))+1;
L.height = Math.max(getHeight(L.left), getHeight(L.right))+1;

return L;
}

Node leftRightCase(Node mom) {
rightRightCase(mom.left);
return leftLeftCase(mom);
}

Овие два случаи се симетрични со rightRightCase(Node mom) и rightLeftCase(Node mom) и затоа нема повторно да ги објаснувам.

void ballanceTreeInsertion(Node root, Node mom) {
int a, p;

while (mom != root) {
 p = ballanceFactor(mom);
 if (p == 2) {
  // right subtree outweighs the left subtree
  // If the balance factor of R is +1, a left rotation is needed with P as the root.
  // If the balance factor of R is -1, a double left rotation is needed
 
  a = ballanceFactor(mom.right);
 
  if (a == 1) {
   mom = rightRightCase(mom);
  } else {
   if (a == -1) {
    mom = rightLeftCase(mom);
   }
  }
 
 } else {
  if (p == -2) {
   a = ballanceFactor(mom.left);
  
   if (a == -1) {
    mom = leftLeftCase(mom);
   } else {
    if (a == 1) {
     mom = leftRightCase(mom);
    }
   }
  }
 }

 mom = mom.parent;

 // we update the height of mom
 mom.height = Math.max(getHeight(mom.left), getHeight(mom.right))+1;

}

}

Во мојата имплементација, секое балансирано стебло има единствен корен root. Вистинскиот корен е во левото дете на root. Ова е со цел за да може да се претстави стебло со 0 елементи (root.left ќе биде null во тој случај). Исто така, ваква динамична структура често се менува внатрешно и root.left во различни моменти од времето може да има различни јазли, што е тешко да се претстави доколку не постои некој "поврховен" јазел како коренот со кој единствено се претставува и еднозначно се карактеризира секое стебло.

Оваа функција е клучна за добивање на балансираност на стеблото при додавање на нов елемент. Како аргумент се праќа корен на дрвото и јазелот од кој почнуваме да го балансираме дрвото. Го балансираме јазелот mom и потоа се качуваме нагоре по стеблото се додека не стигнеме до коренот. Алгоритмот за балансирање е следен: во p го сместуваме факторот на балансираност на јазелот кој го обработуваме. ДОколку овој број е 2 или -2, тоа значи дека стеблото во тој јазел е небалансирано (понатаму накратко ќе го употребувам поимот балансираност во јазел, наместо балансираност на стеблото чиј корен е конкретниот јазел). Во зависност од тоа дали десното (левото) дете има фактор на балансираност 1 или -1 се одвива единечна или двојна ротација. Пред да се качиме нагоре по хиерархијата ја ажурираме висината на јазелот кој моментално го обработуваме.

void ballanceTreeDeletion(Node root, Node mom) {
int a, p;

while (mom != root) {
 mom.height = Math.max(getHeight(mom.left), getHeight(mom.right))+1;

 p = ballanceFactor(mom);
 if (p == 2) {
  // right subtree outweighs the left subtree
  // If the balance factor of R is +1, a left rotation is needed with P as the root.
  // If the balance factor of R is -1, a double left rotation is needed
 
  a = ballanceFactor(mom.right);
 
  if ((a == 1)||(a == 0)) {
   mom = rightRightCase(mom);
  } else {
   if (a == -1) {
    mom = rightLeftCase(mom);
   }
  }
 
 } else {
  if (p == -2) {
   a = ballanceFactor(mom.left);
  
   if ((a == -1)||(a == 0)) {
    mom = leftLeftCase(mom);
   } else {
    if (a == 1) {
     mom = leftRightCase(mom);
    }
   }
  }
 }

 mom = mom.parent;

 // we update the height of mom
 mom.height = Math.max(getHeight(mom.left), getHeight(mom.right))+1;

}

}

Оваа функција е скоро идентична на претходната, со таа разлика што овде се применува ротација на лево доколку p = 2 и (а = 1 или а = 0), и ротација на десно доколку p = 2 и (а = -1 или а = 0). Првата функција ќе ја употребуваме за балансирање при додавање на елемент, втората при бришење на елемент. Доколку ве интересира зошто е ваква имплементацијата можете да прочитате повеќе во разни книги кои се занимаваат со тематика од областа на алгоритмите и структурите на податоци.

void addNode(Node root, int value) {
Node mom = root.left;
Node newnode = new Node(value);
Node prev = root;

while (mom != null) {
 if (value <= mom.value) {
  prev = mom;
  mom = mom.left;
 } else {
  prev = mom;
  mom = mom.right;
 }
}

newnode.parent = prev;

if (value <= prev.value) {
 prev.left = newnode;
} else {
 prev.right = newnode;
}

// now we need to balance the tree
mom = newnode;

ballanceTreeInsertion(root, mom);

}

addNode прима како аргумент корен и вредност која што сакаме да се смести во стеблото. Се изминува стеблото надоле додека не се дојде до некој "null елемент" и на негово место се сместува новиот. Овде важи правилото, сите лементи во левото потстебло на даден јазел се помали или еднакви на вредноста на тој јазел, а сите елементи во десното потстебло на јазелот се поголеми од неговата вредност. Откако ќе го внесеме јазелот, го балансираме новиот јазел т.е. ја повикуваме функцијата ballanceTreeInsertion која врши верижно балансирање на стеблото нагоре се до коренот.

void deleteNode(Node root, int value) {
Node mom = root.left;
Node prev = root;
Node T;
boolean found = false;

while (mom != null) {
 if (mom.value == value) {
  found = true;
  break;
 }
 if (value <= mom.value) {
  prev = mom;
  mom = mom.left;
 } else {
  prev = mom;
  mom = mom.right;
 }
}

if (found == false) {
 //System.out.println("The element was not found");
 return;
}

Node orig = mom;

if ((orig.left == null)&&(orig.right == null)) {
 // we remove the node
 mom = orig.parent;
 if (mom.left == orig) {
  mom.left = null;
 } else {
  mom.right = null;
 }
 orig = null;

 // we should be sure that the subtree with mom with it's main root element
 // has correct heights and as parametar we give valid element
 mom.height = 1;
 ballanceTreeDeletion(root, mom);
 return;
}

if ((orig.left == null)^(orig.right == null) == true) {
 // if there is exactly one subtree
 mom = orig.parent;
 if (orig.left != null) {
  T = orig.left;
  if (mom.left == orig) {
   mom.left = orig.left;
   orig.left.parent = mom;
  } else {
   mom.right = orig.left;
   orig.left.parent = mom;
  }
 } else {
  T = orig.right;
  if (mom.left == orig) {
   mom.left = orig.right;
   orig.right.parent = mom;
  } else {
   mom.right = orig.right;
   orig.right.parent = mom;
  }
 }
 orig = null;
 ballanceTreeDeletion(root, T);
 return;
}

// the node has 2 subtrees, we need to find the smallest element of the right subtree of mom
mom = orig.right;

if (mom.left == null) {
 // special case, it is more complicated to change the relations
 if (orig.parent.left == orig) {
  orig.parent.left = mom;
 } else {
  orig.parent.right = mom;
 }

 orig.left.parent = mom;
 mom.left = orig.left;
 mom.parent = orig.parent;
 orig = null;
 ballanceTreeDeletion(root, mom);
 return;
}

prev = mom;

while (mom != null) {
 prev = mom;
 mom = mom.left;
}

mom = prev;
prev = mom.parent;

// we are changing the relations instead of just changing the value

if (mom.right != null) {
 mom.right.parent = mom.parent;
}

T = mom.parent;
mom.parent.left = mom.right;

mom.parent = orig.parent;
mom.left = orig.left;
mom.right = orig.right;

if (orig.parent.left == orig) {
 orig.parent.left = mom;
} else {
 orig.parent.right = mom;
}

orig.left.parent = mom;
orig.right.parent = mom;

// now we need to balance the tree
T.height = Math.max(getHeight(T.left), getHeight(T.right))+1;
ballanceTreeDeletion(root, T);

}

Бришењето на јазел од стеблото е малку покомплицирано. Оваа функција како аргумент прима референца кон коренот и клучната вредност на јазелот што сакаме да биде избришан. Прво го пронаоѓаме јазелот во стеблото. Потоа разгледуваме неколку специјални случаи.

Доколку јазелот е лист, т.е. нема лево и десно потстебло, тогаш јазелот едноставно го бришеме, така што ги отстрануваме врските на неговиот родител кон него, и потоа ги балансираме сите јазли додека не стигнеме нагоре до коренот на стеблото.

Доколку јазелот Т има само едно потстебло, тогаш јазелот Т го отстрануваме, а притоа дете на неговиот родител ќе стане детето на Т.

Доколку јазелот Т има две потстебла, тогаш го бараме најмалиот елемент од неговото десно потстебло т.е. го бараме јазелот L (ја употребувам оваа ознака за да објаснам поубаво, во кодот е имплеменирано со променливи со друго име) кој се наоѓа "најлево" во неговото десно потстебло. Ја отстрануваме врската од неговиот родител кон L и овој јазел го ставаме на местото на Т. Т го отстрануваме. Разбирливо, потоа вршиме балансирање на стеблото од јазелот кој претходно беше родител на L. Овде разгледав специјален случај кога L e дете на T. Малку е покомплицирано да се менуваат врските доколку јазлите се директно поврзани. На крај се одвива балансираност која започнува од претходниот родител на L.

void inorder(Node mom) {
if (mom == null) return;

inorder(mom.left);
System.out.println(mom.value);
inorder(mom.right);
}

void inorderRoot(Node root) {
inorder(root.left);
}

Со повикувањето на inorderRoot(Node root) се врши inorder изминување на стеблото, а тоа значи дека ќе бидат отпечатени вредностите што ги содржи стеблото и тие ќе бидат сортирани во неопаѓачки редослед.

Се надевам дека сега некои работи ќе бидат појасни за AVL стеблата и ќе пробате самите да искодирате AVL стебло. За некои од можните примени на овие интересни и многу ефикасни структури во некоја следна прилика.

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

Доколку сакате повеќе да прочитате за AVL стеблата ви препорачувам:

Introduction to Algorightms
Algorithms in C
http://en.wikipedia.org/wiki/AVL_tree

и уште многу ресурси кои можете да ги најдете пребарувајќи на google
http://www.google.com/search?hl=en&source=hp&q=avl+tree&aq=f&oq=&aqi=g7g-s1g2

Кодот заедно со некои тестови кои ги правев можете да го симнете овде:

http://www.mediafire.com/?2vnjyn2nguj

Збор два за O(logN) и стеблата

Структурите секогаш одат заедно со алгоритмите. Ефикасна имплементација е збир од ефикасни податочни структури и ефикасен алгоритам. Некогаш треба и да се прави компромис. Кај многу решенија големата комплексност може да се намали со користење на добри податочни структури. На пример, кај сортирањето, комплексноста од O(N*N) значи дека за N = 1000000 програмата нема во разумно време да даде решение.

Проблемот на сортирање е добро проучен и познати се алгоритми кои даваат решение во време O(N*logN). Овде ќе ги спомнам merge sort и мојот омилен heap sort. Другите сортирања имаат комлексност од O(N*N) во најлош случај. Но, другите сортирања освен оригиналната низа не користат друга меморија и некои релативно комплицирани структури (со исклучок на некои променливи како бројачи и променливи во кои привремено се чуваат податоци).

Кај merge sort и heap sort приказната е поинаква. Merge sort користи две низи, значи оригиналната низа и уште една низа со иста мемориска големина (едно од следните мои пишувања ќе го посветам целосно на сортирања). Heap sort пак користи само една низа, но таа низа е организирана на друг начин кој овозможува сите операции како вметнување на елемент во структурата, бришење, наоѓање на максимум или минимум да се извршуваат во O(1) или O(logN), овие неколку операции индиректно придонесуваат во она што се бара, сортирање на низата.

Стеблото е структура или поим кој се поврзува со посакуваната комплексност O(logN). Значи директно или индиректно, доколку некој проблем бара решение кое е од ред O(logN), тогаш ние ќе треба да се занимаваме со стебло, иако понекогаш стеблото не е очигледно на прв поглед, овде мислам општо, на стебло како структура и стебло како поим, како логичка организација која во својата суштина го има гранењетo.

Очекувана вредност

Последниот SRM 448 ме натера да размислувам за една од моите омилени теми - Веројатност. Првата задача беше поврзана со оваа тема. Како прва и најлесна задача, решението се добиваше рекурзивно, со собирање на веројатностите за сите можни настани. Брзо го напишав ова затоа што инстинктот ми велеше дека ова мора да биде главниот начин за добивање на конечниот резултат. Требаше да се погоди очекуваниот број на карти кои ќе се извлечат, а кои ќе донесат победа. Нема да објаснувам што се бара во задачата, неа можете да ја погледнете на topcoder. Она што не знаев е како сите информации за веројатноста да се искористат за да се добие конечниот резултат. Брзо го искодирав кодот за пресметување на веројатноста. Прво размислував малку како да го искористам она што веќе го имав, но не ми доаѓаше идеја. Потоа на 40 минути до крај малку погуглав и за среќа најдов една страна каде што многу едноставно беше објаснето како се добива очекувана вредност. Формулата е следна:

очекувана вредност = Сума од на сите настани(веројатноста за настан i * вредноста за тој настан i)

Еве да објаснам за еден едноставен пример. Имаме коцка, таа има 6 страни и на секоја страна има по една вредност од 1 до 6. При фрлање на коцката која е очекуваната вредност што ќе ја добиеме?

Значи според формулата:

expected = (1/6)*1+(1/6)*2+(1/6)*3+(1/6)*4+(1/6)*5+(1/6)*6 = (1/6)*21 = 3.5

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

Повеќе за ова можете да прочитате на wikipedia.

Инаку да се вратам на приказната со настапот на SRM 448. Го имплементирав ова, и програмата не ми ги даваше потребните резултати. Значи имаше две потенцијални работи кои се причина за грешното решение. Прво, алгоритмот не е точен, и второ, имам некоја грешка во кодот. Втората опција брзо ја елиминирав мислејќи дека во толку прост код и не може да има некоја грешка, скенирајќи го набрзина кодот за да имам време да размислувам за точноста на алгоритмот. Бидејќи малку бев скептичен во врска со точноста на формулата се обидував да наоѓам други малку поинакви пристапи во крајниот алгоритам и менував некои работи во кодот кои не ми донесоа успех. На крај се откажав. Моја среќа што имаше многу натпреварувачи со ниедна решена па не ми падна многу рејтингот, сега е 1224 и останувам во DIV 1.

Кога заврши натпреварот одлучив да одморам малку. Размислував што би можело да ми биде грешката и полека го анализирав мојот код во главата. Наеднаш дојдов до проблематичниот дел. Наместо for (j=0;j0) што е грешка при брзање... Оваа грешка ме чинеше добар пласман. Алгоритмот бил добар, но сум имал грешка во имплемнтацијата.

Поука за друг пат. Секогаш разгледувај ги сите потенцијални причинители на грешната програма, и никогаш не елиминирај ниедна од можните причини колку и да изгледа дека непотребно се губи време на некоја од нив.

Тест задача

Случајно најдов на еден многу интересен сајт http://www.scarky.com/ каде може да се постави задача по програмирање. Сите параметри се местат од страна на креаторот, кодот за натпреварот сам се генерира. Можеби тоа што не би го сметал за професионален начин за организирање на натпревари е што нема можност повеќе input-и. Се надевам тоа ќе се поправи во иднина. Ајде сега да го тестираме системот. Производ на два броеви :) Напишете кодче и праќајте. Ќе се обидам наредниве денови да ставам некој попредизвикувачки проблем од областа на програмирањето.

USACO

USACO (http://ace.delos.com/usacogate) е тренинг сајт за програмирање каде секој може да се регистрира и да решава. Според мене, секој кој има елементарни познавања од програмирање и се интересира за решавање на проблеми мора задолжително да го посети сајтот. Вкупно има околу 100 задачи кои се групирани во 6 chapters. Секој chapter се состои од sections. Во секоја секција има околу 3-4 задачи. Убавата и интересната работа е тоа што задачите мора да се решаваат по ред. Не може да се решава задача од некоја повисока секција додека не се решат сите претходни задачи. Во почетокот задачите се лесни, а како се напредува задачите се се потешки. Покрај задачите има и посебни лекции наречени TEXTS. Во секој TEXT е обработена некоја одредена тема од областа на програмирањето и алгоритмите. Сите основни принципи на програмирање и најбитни и најосновни алгоритми се обработени во овој тренинг. Овој тренинг пред се е наменет за средношколци кои се спремаат за натпреварите по информатика, овде пред се мислам на IOI (International Olympiad in Informatics).

На овој тренинг сајт почнав да решавам кон крајот на четврта година средно (пред 2 години) кога се спремав за IOI 2007. Поради обврски кон факултетот пред се, решавав на сајтот со повремени прекини, па така дури денес можам да кажам дека ги решив сите задачи :) Сите задачи се предизвикувачки, но сепак најинтересни ми беа последните три од chapter 6. При решавање се вежба логиката и размислувањето. Некои задачи некогаш и би рекол дека се невозможни на почетокот но кога навистина добро ќе се размисли - за се има решение, само треба да се најде. Начин на решавање на задачите, прво добро да се прочита и да се сфати што е проблемот. Потоа анализа, разгледување на примери, размислување како да се тргне кон решавање. Разгледување на разни начини. Треба да се одбере најлогичниот начин кој претходно треба да е добро анализиран, прво умствено да се изврши па потоа тоа да се преточи во програмски код. Доколку некоја од овие фази се обидете да ја прескокнете или да ја поминете набрзина без добро размислување тоа најчесто се одразува на време и на нерви :) Кога ќе напишете неколку стотина линии код, гледате дека се грешка, па потоа пак од почеток - секако никој не го сака ова. Во кој програмски јазик ќе се програмира мислам дека е најмал проблем иако ова не е баш работа која може да се занемари. Предноста е кај оние кои знаат повеќе програмски јазици бидејќи ги знаат предностите и недостатоците на секој па во дадена ситуација ќе знаат да го искористат најдобриот избор. Во почетокот, кога почнав да навлегувам во водите на програмирањето кодирав во Pascal, тогаш за мене Pascal беше програмски јазик со кој можев буквално се да искодирам :) толку бев уверен и во себе и во моќта на Pascal. Потоа научив C, овој програмски јазик би го споредил во брзината и перформансите со брза спортска кола, но недостатокот е во тешкото управување со воланот :) За попрости проблеми лесно е да се пишува код во C, но кога ќе наидете на посложени проблеми кои бараат користење на посложени структури и кои имаат потреба од готови библиотеки доаѓа потреба од друг програмски јазик кој ќе ги надмине недостатоците на C, а сепак ќе ја задржи брзината. Погодувате, тоа е C++. Немам баш многу искуство во C++ bидејќи брзо мигрирав од C во Java, но тоа е јазикот кој ми беше алтернатива при решавањето доколку наидев на проблем кој го надминува временскиот лимит во Java. Иста програма напишана во Java и C++ не дава иста брзина на извршување. C++ e далеку побрз. Но сепак Java ми е омилен програмски јазик за програмирање пред се заради неговата едноставност и моќ. Во Java може да се напише буквално се и тоа процесот на кодирање е многу побрз затоа што нуди подршка од многу корисни библиотеки и добри IDE како Eclipse


It's time for a new challenge :)

Алгоритми. Вовед.

Многу луѓе кои се занимаваат со информатичка технологија малку знаат за тоа што се алгоритми. Напишав еден мал вовед во тоа што се алгоритми. Сите оние што се ентузијасти во полето на информатичката технологија е неопходно да имаат барем општи познавања од алгоритмите. Тоа е еден посебен свет на размислување, техники за решавање на проблеми, употреба на логика за да се стигне до резултат. Многу од помладите се скриени таленти за решавање на алгоритамски проблеми, но за жал, малку нашето образование посветува на тој дел од информатиката кој сепак е најбитен.

Ги земам за пример земјите од соседството. Хрватаска е одличен пример за тоа како треба да се едуцираат млади кадри и пример за тоа како државата се грижи за своите таленти, Бугарија редовно е меѓу првите 10 земји во свет, Романија отсекогаш ги имала едни од најдобрите програмери (зборувам во светски рамки). Наскоро планирам да напишам и за тоа кои земји колку имаат постигнато во полето на програмирањето. Во ова што го напишав и што го поставив овде се вклучени и мои размислувања. Некои од податоците се земени од Интернет (wikipedia).

Дури и доколку не разберете нешто ви советувам да го прочитате до крај, којзнае, можеби ќе откриете со што сакате да се занимавате во иднина... За се што ве интересира слободно контактирајте ме, оставајте коментари и прашувајте. Се надевам дека вие сте новиот талент во програмирање.

Algoritmi.pdf