tplsr20141107.cpp
#include "eval.hpp"
#include <climits>
#include <cstdlib>
#include <stack>
using namespace aed;
using namespace std;
/* COMIENZO DE DESCRIPCION
__USE_WIKI__
#isomorph Dos arboles binarios #B1,# #B2# son isomorfos
si se pueden aplicar una serie de inversiones entre los
hijos derechos e izquierdos de los nodos de #B2# de manera
que quede un arbol semejante a #B1#, es decir que tiene la
misma estructura.
#has-sum# Dado un #set<int># y un entero #M# determinar si
existe un subconjunto de #S# que sume exactamenet #M.#
#find-shift# Dadas dos listas #L1# #L2# tal que #L2# es
una permutacion ciclica de #L1# determinar el shift.
[Tomado en el Super Recup TPL
(TPLSR) de 2015-11-11].
keywords: lista, conjunto, arbol binario
FIN DE DESCRIPCION */
//---:---<*>---:---<*>---:---<*>---:---<*>---:---<*>
typedef btree<int>::iterator btn_t;
bool btisomorph(btree<int> &B1,btn_t n1,
btree<int> &B2,btn_t n2) {
if ((n1==B1.end()) != (n2==B1.end())) return false;
if (n1==B1.end()) return true;
btn_t
l1=n1.left(),
l2=n2.left(),
r1=n1.right(),
r2=n2.right();
if (btisomorph(B1,l1,B2,l2) && btisomorph(B1,r1,B2,r2)) return true;
if (btisomorph(B1,l1,B2,r2) && btisomorph(B1,r1,B2,l2)) return true;
return false;
}
//---:---<*>---:---<*>---:---<*>---:---<*>---:---<*>
bool btisomorph(btree<int> &B1,btree<int> &B2) {
return btisomorph(B1,B1.begin(),B2,B2.begin());
}
//---:---<*>---:---<*>---:---<*>---:---<*>---:---<*>
bool has_sum(set<int> &S, int M) {
if (S.find(M)!=S.end()) return true;
set<int>::iterator q = S.begin();
while (q!=S.end()) {
if (*q<M) {
set<int> S1 = S;
S1.erase(*q);
if (has_sum(S1,M-*q)) return true;
}
q++;
}
return false;
}
//---:---<*>---:---<*>---:---<*>---:---<*>---:---<*>
int find_shift(list<int> &L1,list<int> &L2) {
int N = L1.size();
assert(L2.size()==N);
for (int j=0; j<N; j++) {
list<int>::iterator
q1=L1.begin(),
q2=L2.begin();
for (int k=0; k<j; k++) q1++;
int ok=1;
while (q2!=L2.end()) {
if (*q1!=*q2) { ok=0; break;}
q1++; q2++; if (q1==L1.end()) q1 = L1.begin();
}
if (ok) return j;
}
assert(0);
}
//---:---<*>---:---<*>---:---<*>---:---<*>---:---<*>
int main() {
Eval ev;
int vrbs = 0;
int seed = 123;
int h1=0,h2=0,h3=0;
ev.eval1(btisomorph,vrbs);
ev.eval2(has_sum,vrbs);
ev.eval3(find_shift,vrbs);
for (int j=0; j<30; j++) {
seed = rand()%1000;
if (!j) seed = 123;
h1 = ev.evalr1(btisomorph,seed,0); // para SEED=123 debe dar H=759
h1 = ev.evalr1(btisomorph,seed,0); // para SEED=123 debe dar H=759
h2 = ev.evalr2(has_sum,seed,0); // para SEED=123 debe dar H=288
h3 = ev.evalr3(find_shift,seed,0); // para SEED=123 debe dar H=257
printf("S=%03d -> H1=%03d H2=%03d H3=%03d\n",
seed,h1,h2,h3);
}
return 0;
}
Generated by GNU Enscript 1.6.6.