CodeFuEdit

Конечно го поставувам програмчево што го направив за парсирање на problem statements од www.codefu.com.mk. Изработено е уште пред година дена, не го објавив тогаш бидејќи има некои багови, не работи за сите типови на задачи, реков дека кога ќе можам ќе го средам ама некако не ми се навраќа кон стар код :) подобро би направил од ново CodeFu parser. Овој кој го поставувам овде е направен буквално за еден ден, не посветив многу време на тестирање и подобрување со менување на кодот и затоа однапред се извинувам доколку не функционира секогаш најдобро... Сепак врши работа, го користам на сите online codefu натпревари. Се користи едноставно, се копира целиот текст на problem statement заедно со примерите и се внесува. Програмата автоматски генерира почетен template за задачата заедно со код за тестирање. Начинот на кој се справувам со тестирањето во main медотот е "позајмен" од познатата алатка со иста функција но за Topcoder - kawagi.

Dowload CodeFuEdit

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

Верувам дека нема да ви биде тешко да се снајдете со алаткава.

Се надевам ќе ви послужи за codefu натпреварите.

Со среќа :)

Збир на елементи во подматрица

Се мислев како да го именувам денешново пишување. Даден ни е следниот проблем:

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

Ќе го дефинираме поимот подматрица.

Ќе го објаснам графички. На сликата ни е дадена матрица А, и нејзина подматрица B.

Се бара да се напише алгоритам кој на најефикасен начин би го пресметал збирот на елементите во подматрицата B.

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

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

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

ред 1: 1 2 3

ред 2: 4 5 6

ред 3: 7 8 9

Ги нумерирам редовите и колоните почнувајќи од еден наместо од нула заради полесна имплементација. Со анализа на кодот ќе биде појасно зошто.

Ние треба да напишеме функција sum(x1, y1, x2, y2) каде што (x1, y1) ни е горниот лев агол на подматрицата, а (x2, y2) ни е долниот десен агол на матрицата. Оваа функција треба да го врати збирот на елементите во овој потправоаголник (подматрица). Во нашиот пример:

sum(1, 1, 3, 3) = 45

sum(1, 1, 2, 3) = 27

sum(1, 1, 1, 3) = 12

sum(2, 1, 3, 3) = 33

sum(2, 1, 2, 1) = 2

...

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

Следна фаза, барање на решение на проблемот.

Најпрост алгоритам е следниот. Ја читаме цела матрица и потоа "со два фора" ги поминуваме сите елементи што се во подматрицата и ги собираме. Многу едноставно. Но се бара најефикасен начин. Претходниов начин би бил брз да речеме за матрица со 1000x1000 елементи, релативно брз затоа што тоа би се извршило за помалку од секунда по повик на функцијата sum(x1, y1, x2, y2). Оставам на вас да размислете зошто не е ефикасно, што би можело да се подобри овде, дали можеби некои пресметки би се вршеле по повеќе пати? На кој начин би можело ова да се оптимизира?

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

Прва оптимизација би била ако имаме една акумулациона матрица за колони (аналогно е за редови). Оваа матрица би имала ист број на елементи како и оригиналната матрица. Што е логиката на оваа акумулациона матрица за колони. Елементот со индекс (i, j) означува сума на сите вредности од оригиналната матрица кои што се наоѓаат во ј-тата колона, а кои се наоѓаат во ред со индекс <= i. Потоа во методот sum би имале само еден "for" т.е. би имале линеарна комплесност од една димензија на матрицата! Нема да навлегувам во детали како би се имплементирала функцијата sum во овој случај бидејќи не е тешко да се сфати доколку се размисли малку.

Откако ќе го сфатиме претходниот начин, се прашуваме дали можеме да одиме подалеку, т.е. дали можеме да ја оптимизираме функцијата толку многу што таа ќе работи во време O(C) каде што C е константа со мала вредност? Одговорот на ова прашање е да. Се служиме со сличен принцип како претходниот. Имаме две фази, имплементирање на акумулационата матрица и втора фаза имплементирање на методот sum.

Акумулациона матрица. Оваа матрица има исти димензии како и оригиналната матрица. Индексот (i, j) во матрицата означува дека вредноста поврзана со тој индекс е збир на сите елементи во матрицата кои се наоѓаат во ред со индекс <= i и во колона со индекс <= j.

Во примерот даден претходно, матрицата на акумулација би ги имала следниве вредности

ред 1: 1 3 6

ред 2: 5 12 21

ред 3: 12 27 45

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

Кратките и едноставни формули се добар показател дека користиме динамичко програмирање. Во зависност од тоа дали имаме bottom-to-up или up-to-bottom пристап, динамичкото програмирање можеме да го имплементираме итеративно или со рекурзија и мемоизација. Подетално за овие техники во друга прилика. Динамичкото програмирање овде е покарактеристично кај создавањето на акумулационата матрица, техниката за пресметка во методот sum би го нарекол само "математичка финта" :)

Значи при дадена акумулациона матрица М (да напоменеме дека во случајот x1 <= x2 и y1 <= y2),

sum(x1, y1, x2, y2) = m(x2, y2)-m(x1, y2)-m(x2, y1)+m(x2, y2)

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

area(E) = area(A)-area(B)-area(C)+area(D)

Акумулационата матрица може да се добие на сличен принцип. Тоа убаво се гледа од кодот, поточно во фукцијата generate(). Во програмата вметнав и една функција за тестирање.

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

Download source file

Проблемот би бил целосно поинаков доколку вредностите во матрицата се менуваат периодично. Во тој случај нема да важи опишаниот алгоритам бидејќи нашите пресметки се засноваа на почетната пресметка, периодичното менување на вредностите во матрицата би предизвикало и менување на акумулационата матрица, а токму постојаноста на акумулационата матрица беше факт врз кој ја градевме функцијата sum(x1, y1, x2, y2). Проблемот кога можеме да имаме промени на вредности и повикувања на функцијата sum се решава на принцип многу поразличен од претходно опишаниот, тој принцип не се вбројува во архетипот динамичко програмирање. Еден од начините за решавање на овој проблем е со користење на бинарни индексни стебла, многу ефикасни и навидум сложени, но сепак едноставни структури доколку се сфати принципот на кој тие функционираат. Овде нема да се задржувам на бинарните индексни стебла, но сигурно во некој од наредните post-ови ќе пишувам опширно.

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-и. Се надевам тоа ќе се поправи во иднина. Ајде сега да го тестираме системот. Производ на два броеви :) Напишете кодче и праќајте. Ќе се обидам наредниве денови да ставам некој попредизвикувачки проблем од областа на програмирањето.