Има ли отворени?

[JDFU]

xiT dai nqkva zadachka

[бат Ицо]

Ми то на мен не ми е хоби Нямам идея, кое би било трудно. Давайте ги вие.

[sasquatch]

Ето задачката за която говорех - в двусвързано дърво (всеки възел има указател към своя предшественик и към левия и десния си наследник), по зададени указателите към два възела да се напише функция, която приема като параметри само тези два указателя, и връща указател към общият предшественик на двата възела, към които сочат указателите.

Измислих едно решение, което обаче разчита на това, че всеки възел има поле в което е отбелязана неговата дълбочина в дървото. Това е структурата която използвам за възел от дървото, и самата функция, която след офертата на dinux беше редуцирана около 2.5 пъти като код, супер :

struct TreeNode{
TreeNode(){
 this->top = NULL;
 this->left = NULL;
 this->right = NULL;
 this->depth=0;
}
TreeNode(TreeNode * top){
 this->top = top;
 this->left = NULL;
 this->right = NULL;
 this->depth=top->depth + 1;
}
TreeNode * top;
TreeNode * left;
TreeNode * right;
long depth;
};

TreeNode * findTheClosestCommonAncestorDinux(TreeNode * firstNode, TreeNode * secondNode)
{
if(firstNode->depth < secondNode->depth) {
 TreeNode * tmp = firstNode;
 firstNode = secondNode;
 secondNode = tmp;
}
while(firstNode->depth > secondNode->depth) firstNode = firstNode->top;
if(firstNode == secondNode) return firstNode->top;
while(firstNode != secondNode) {
 firstNode = firstNode->top;
 secondNode = secondNode->top;
}
return firstNode;
}

Сега обмислям вариант в който да не използвам дълбочина на възел, записана в него и ако може и функцията да не е рекурсивна.

[sasquatch]

Измътих го май, или поне това е първоначален вариант някакъв

TreeNode * findTheClosestCommonAncestorV2(TreeNode * firstNode, TreeNode * secondNode)
{
TreeNode * first=firstNode,* second = secondNode;
while(first->top){
 first = first->top;
 if(first == second) return first->top;
}

first = firstNode;
while(second->top){
 second = second->top;
 if(first == second) return first->top;
}	
second = secondNode;
while(first->top){
 first = first->top;
 second = second->top ? second->top : second;
 if(first == second) return first;

 TreeNode * tmp = first;
 
 while(first->top){
	 first = first->top;
	 if(first == second) return first->top;
 }
 first = tmp;
 tmp = second;
 while(second->top){
	 second = second->top;
	 if(first == second) return first->top;
 }
 second = tmp;
}
return NULL;
}

[dok]

Ми ся не ми се занимава с задачи ама тук има всички задач, давани на националните състезания през годините. Който има мерак да решава ще се поозори доста.

[sasquatch]

  dok said:

Ми ся не ми се занимава с задачи ама тук има всички задач, давани на националните състезания през годините. Който има мерак да решава ще се поозори доста.

<{POST_SNAPBACK}>

В тоя дух, виждали ли сте задачата за разходката на коня?Колкото до горните задачи - изрових цялата книга за алгоритми на Преслав Наков("Програмиране = ++Алгоритми"), и нищо подобно не намерих.

[sasquatch]

  xiT said:

Не ми се пише програма, ама на един цикъл става xor

<{POST_SNAPBACK}>

Ама няма ли да трябва първо да се сортират и след тва xor ? Или числата които се повтарят са последователни?

[JDFU]

  sasquatch said:

Ама няма ли да трябва първо да се сортират и след тва xor ?

<{POST_SNAPBACK}>

Ne shtoto :

x xor x = 0

x xor y = y xor x

x xor (x xor y) = y

 

Zadachata q reshih ama she q napisha sled 1-2 chasa che sq nqmam vreme

[sasquatch]

Аре дай да го видим това решение.

[JDFU]

Eto q funkciqta! Ne sym q kompiliral i moje da ima nqkoq druga greshka, no smqtam che ideqta se vijda. Polzvam dopylnitelno char pole value, inicializirano s 0. Do kolkoto vidqh po-dobro (po vreme) reshenie s tozi tip predstavqne na dyrvoto nqma! Ne mislq che e chak tolkova strashno izpolzvaneto na dopylnitelniq bait (moje da se dokara i do bit s malka modifikaciq), kato se ima predvit kak se obyrzqva algorityma (do slojnost O(n) (n e raztoqnieto, na koito otstoi po-dalechniq element ot tyrseniq node))!

[B]EDIT:[/B]Mahnah pyrva versiq shot tyi i tyi ne bachka!

Versiq 2:) (dano da raboti)

TreeNode * findTheClosestCommonAncestorV2(TreeNode * firstNode, TreeNode * secondNode)
{
   TreeNode * first=firstNode,* second = secondNode;

   //temp->top = NULL;

   while (first || second)
   {     if (first != NULL)
         {  if (++(first->value) == 2) return first;
            first = first->top ? first->top : NULL;
         }
         if (second != NULL)
         {  if (++(second->value) == 2) return second;
            second = second->top ? second->top : NULL;
         }
   }
   return NULL;
}

 

Vijte i kajete, ako sym sgafil nqkade !

[sasquatch]

А това решение за коя задача беше?За дърветата ли?

[JDFU]

  sasquatch said:

А това решение за коя задача беше?За дърветата ли?

<{POST_SNAPBACK}>

DA!

[sasquatch]

  JDFU said:

DA!

<{POST_SNAPBACK}>

Не става нещо, тествам го в случая когато двата възела са на макс дълбочина функцията гърми на тоя ред:

temp->top = NULL;

temp не е инициализиран да сочи към нищо

Имам в предвид този случай:

Обратните връзки не съм ги правил, считам че чертата покзва права и обратна връзка.

[JDFU]

  sasquatch said:

Не става нещо, тествам го в случая когато двата възела са на макс дълбочина  функцията гърми на тоя ред:

temp->top = NULL;

temp не е инициализиран да сочи към нищо

<{POST_SNAPBACK}>

huu de, a kato go inicializirash stana li ne razbrah ili trqbva da opravq neshto po cikyla?

 

EDIT: razbrah za koi sluchai! misylta mi e dali problemite bqha 2 (temp-a i gyrmeneto)

[sasquatch]

  JDFU said:

huu de, a kato go inicializirash stana li ne razbrah ili trqbva da opravq neshto po cikyla?

 

EDIT: razbrah za koi sluchai! misylta mi e dali problemite bqha 2 (temp-a i gyrmeneto)

<{POST_SNAPBACK}>

Ами не мога да схвана идеята нещо, накъде трябва да сочи тоя temp?

[JDFU]

  sasquatch said:

Ами не мога да схвана идеята нещо, накъде трябва да сочи тоя temp?

<{POST_SNAPBACK}>

Gotoo, Promenih koda! Dano toq pyt da stane. Sega mahnah i temp-a.

 

Temp-a go polzvam prosto kato bufer (s cel da izbegna mnogokratnoto uvelichavane na broqcha na korena) v momenta v koito stigna vyrha!

[sasquatch]

Супер, но искам да ти кажа че когато напишеш

 

TreeNode * temp;

 

temp e равно на NULL, на следващия ред се опитваш да направиш следното:

 

temp->top = NULL;

 

т.е. да дадеш стойност на атрибут на обект който го няма, тоя указател temp не е инициализиран да сочи към обект, като се опитваш да access-неш свойството на обекта и гърмиш, защото указателя не сочи обект.

[JDFU]

  sasquatch said:

Супер, но искам да ти кажа че когато напишеш

 

TreeNode * temp;

 

temp e равно на NULL, на следващия ред се опитваш да направиш следното:

 

temp->top = NULL;

 

т.е. да дадеш стойност на атрибут на обект който го няма, тоя указател temp не е инициализиран да сочи към обект, като се опитваш да access-неш свойството на обекта и гърмиш, защото указателя не сочи обект.

<{POST_SNAPBACK}>

znam be prosto v byrzinata go izpusnah Inache 2-ra versiq raboti nali?

[sasquatch]

Ти под value какво разбираш - дълбочината на възела ли? Ако е така не работи. На мен идеята в моята функция ми беше следната:

 

1. Проверявм дали някой от възлите които са дадени не е наследник на другия. Ако да връщам top на предшественика. Ако не следвва (2).

 

2. Започвам да се изкачвам в дървото, проверявям дали не са съвпаднали възлите, ако да връщам един от тях (значи са били съседни, или са били наследници на тоя в който съм попаднал, и са били на еднаква дълбочина).

Ако не следва (3).

 

3. Проверявам дали след като съм се изкачил 1-о ниво нагоре някой от двата не е наследник на другия, ако е така връщам предшественика (т.е. възлите са били на различна дълбочина, не и не са се наследявали един друг).

Ако не следва (2).

[JDFU]

  sasquatch said:

Ти под value какво разбираш - дълбочината на възела ли? Ако е така не работи.

<{POST_SNAPBACK}>

NE! value mi e po-skoro count, koito broi kolko pyti sym minal prez vyzel. Tyi kato kachvaiki se ot vseki ot dvata vyzela nagore az poseshavam vseki vyzel ednokratno, to v slucheq,v koito veche sym minal za 2-ri pyt value trqbva da mi e 2! Tova che vyrvq stypka po stypka po stypka mi garantira, che pyrvoto sreshtane na 2 e tyrseniq vyzel

[sasquatch]

Значи първоначално value е нула за всички възли, ок разбрах Сега става наистина бачка, но проблема е да не разчиташ на стойността на възела, не знаеш какво друго има в един възел освен left, right и top.

Ако можеше да се ползва такава информация, тогава се използва дълбочината на възела и има две стъпки:

1. Изравняване на дълбочината на двата възела, проверка дали не са един и същ вече и т.н.

2. Намиране на общия наследник чрез не повече операции от дълбочината на дървото.

[JDFU]

Edno malko predlojenie za toq topic: Aide da slagame link kym raboteshta programa, na koqto prosto da slojim iskanata funkciq, za da mojem da proverqvame sami !

[JDFU]

  sasquatch said:

Значи първоначално value е нула за всички възли, ок разбрах Сега става наистина бачка, но проблема е да не разчиташ на стойноста на дървото, един вид ти не знаеш какво друго има в един възел освен left, right и top.

<{POST_SNAPBACK}>

Ami az naistina, ne znam nishto drugo. Az moga i da izveda tva value izvyn struct-a na dyrvoto v otdelen, v koito shte pazq pointer kym vyzela za koito stava vypros. Nqma kak da se razminesh bez da pazish dopylnitelna informaciq. V protiven sluchai poluchavash dosta po-losh(po vreme) algoritym!

[sasquatch]

  JDFU said:

Ami az naistina, ne znam nishto drugo. Az moga i da izveda tva value izvyn struct-a na dyrvoto v otdelen, v koito shte pazq pointer kym vyzela za koito stava vypros. Nqma kak da se razminesh bez da pazish dopylnitelna informaciq. V protiven sluchai poluchavash dosta po-losh(po vreme) algoritym!

<{POST_SNAPBACK}>

Въпроса е каква ще е тая структура Иначе не е лошо като идея.

[JDFU]

  sasquatch said:

Въпроса е каква ще е тая структура

<{POST_SNAPBACK}>

struct x

{ char value;

TreeNode *vyzel;

struct x * top;

}

Po-dobro ne mojah da izmislq! Shte pomislq oshte i ako se seta she go napisha.