wczesny, chwilowy etap pre-s.a. -- kod
Wlodzimierz Holsztynski
się zerwał ze snu, by w piżamie
wyjść na balkon i powitać znajomych.
Ale trudno. Będziecie mogli sprawdzić
moje eksperymenty, ewentualnie spróbować
nowych. Program nazwałem barsa.cpp.
Po skomilowaniu jako barsa, woła się
go następująco:
barsa [a1] [a2] < plik.inp
Prawdopodobnie zechcecie zachować
output w pliku, wołając tak:
barsa [a1] [a2] < plik.inp > plik.out
Argumenty a1 oraz a2 są opcjonalne.
Ale, żeby odczytać plik w formacie:
vBb_plik.inp
czyli zawierający bazę barokową +
początkowy wierzchołek, to muszą
wystąpić oba. Istotne są w tych argumentach
tylko pierwsze ich charaktery (więc
można uczynić je 1-znakowymi). Można
dać za a1 też odstęp, tak:
barsa ' ' [a2] < plik.inp > plik_blank.out
Ten pierwszy znak zmiennej a1 wpływa
na "seed" oraz także na liczbę pętli,
którą program wykona.
Za a2 najlepiej dać '3' lub inną niską cyfrę.
Od niej zależy co będzie drukowane do
outputu. Zawsze drukowany jest postęp
czyli wierzchołek początkowy (z pliku),
następny wierzchołek, oraz te które dają
postęp, czyli mają coraz mniejszą karę.
Oprócz tego drukowane są wszystkie
wierzchołki, których kara jest mniejsza
lub równa a2 - '0'. Na przykład a2 = '0' da
tylko liczby barokowe; a2 = '1' -- prawie
barokowe; itd. Ma sens dać nawet '3',
ale już '4', przy nośnikowej karze dałoby
na ogół za wielki output.
Minimalna zmiana komentująco-
odkomentywująca zmienia karę z nośnikowej
na sumaryczną, i na odwrót. Oczywiście,
trzeba wtedy jeszcze skopilować
zmodyfikowaną barsa.cpp na nowo.
Przy karze sumarycznej, ma sens
próbować wyższą wartość a2, np. '4'
lub '5'.
Wywołanie barsa raz z karą nośnikową,
drugi raz z sumaryczną, przy tym samym
pliku inputowym, oraz z tymi samymi a1 a2,
spowoduje liczenie TYCH SAMYCH wierzchołków
w obu wypadkach, ale wydrukowane mogą być
inne, bo to zależy od kary. Zatem warto robić
takie doświadczenia, więcej wiedzieć
o przestrzeni C(wkd).
Żeby nie wydłużać postu, kod dam jednak
w następnym. (Zwlekam jak mogę :-)
Pozdrawiam,
Włodek
Wlodzimierz Holsztynski
//
// Pozdrawiam,
//
// Włodek
//
// *********************************
//
// program barsa.cpp
//
// author: Wlodzimierz Holsztynski
// date: 2007-June
#include <iostream>
#include <time.h>
using namespace std;
const int supp=200; // the max size of the brq base support
const int maxw=31; // the upper bound for exponents
int prime[supp], // brq base primes
wkd[supp], // and their exponents
pDim, // the actual brq base support size
roof[supp], // the sum of recommendations by other primes
qw[supp][maxw][supp], // ord_q(sd(p^w(p)))
mpw[supp][supp], // max (ord_q(sd(p^w(p))) : p < pDim)
vertex[supp], // the s.a. randomly orbiting vertex/
configuration
vRcmd[supp][supp], // vertex recomandation
vrf[supp], // vertex roof
iter; // the number of reduction iterations
int show_v()
{ int follow=0, v, i;
for(i=0;i<pDim;++i)
{ if(v=vertex[i])
{ if(follow) cout << " * "; follow=1;
cout<<prime[i];
if(v > 1) cout<<"^"<<vertex[i];
} }
cout << endl;
}
int research()
{ int p, q, sd, sdd, sdw, w, i, j; // sd -- the sum of divisors
for (i=0; i<pDim; ++i) roof[i]=0;
for (i=0; i<pDim; ++i)
{ p = prime[i];
sd=1; // process p^0
for (j=0; j<pDim; ++j)
{ mpw[i][j] = qw[i][0][j] = 0; } // done
for (w=1; w<=wkd[i]; ++w) // process higher powers p^w
{ (sd *= p)++; // the sum of divisors of p^w
sdd = sd; // extract divisors q^v|sd(p^v); q \in Q
for (j=0; j<pDim; ++j)
{ q = prime[j];
sdw=0;
while (!(sdd % q))
{ ++sdw;
sdd /= q;
}
qw[i][w][j] = sdw;
(sdw > mpw[i][j]) && (mpw[i][j] = sdw);
} }
for (j=0; j < pDim; ++j) roof[j] += mpw[i][j];
} }
// function rm0() is executed only once, at the beginning,
// and before the main loop (THE loop) over the temperature
int rm0(int argc) // remove each prime[i] with exponent wkd[i] \<
0
{ int del=0, i;
for(i=0; i<pDim; ++i)
{ if(wkd[i]<= 0) ++del;
else
{ prime[i-del] = prime[i];
wkd[i-del] = wkd[i];
if(argc!=2) vertex[i-del] = vertex[i];
} }
pDim -= del;
return del;
}
// function reduce() is executed only once, at the beginning,
// and before the main loop (THE loop) over the temperature
int reduce(int argc)
{ int del=1, // the nof primes deleted from the base
TWR=0, // true/false flag
rf, // auxiliary (temporary) roof parameter
i, v;
iter=0;
while (!TWR)
{ TWR=1; del=0;
for (i=0; i < pDim; ++i)
{ if (!(rf=roof[i])) ++del;
else
{ prime[i-del] = prime[i];
if (wkd[i] > rf)
{ TWR = 0;
wkd[i-del] = rf;
}
else wkd[i-del] = wkd[i];
if (argc != 2)
{ v = vertex[i-del] = vertex[i];
if(v > wkd[i-del]) vertex[i-del]=wkd[i];
}
} }
if (del)
{ TWR=0;
pDim -= del;
del = 0;
}
++iter;
TWR || research();
} }
int research_v() // research vertex from scratch,just once, before THE
loop
{ int i, j, r, v;
for(i=0;i<pDim;++i) vrf[i]=0;
for (i=0; i < pDim; ++i)
{ v = vertex[i];
for (j=0;j<pDim;++j)
{ vRcmd[i][j] = r = qw[i][v][j];
vrf[j] += r;
} } }
int selectv() // select and research the initial vertex
{ int i;
for(i=0;i<pDim;++i) vertex[i] = wkd[i];
research_v();
}
int penalty()
{ int pen=0, d, i;
for(i=0;i<pDim;++i)
if((d = vertex[i] - vrf[i]) > 0) ++pen; // pen += d;
if(!pen) cout<<endl<<"Baroque: ";
return pen;
}
int move(int* pi) // returns new exponent of the rnd prime[*pi]
{ int i, v, r;
i = *pi = ((r=random()) % pDim);
if(v=vertex[i])
return ((v==wkd[i]) ? --v : v + (r&2) - 1);
else return wkd[i];
} // to do: ADD multiplicative moves!!!
// Then don't re-use r but call random()
again
int new_v()
{ int i, j, v, w, q;
v = move(&i); // new exponent
for(j=0; j<pDim; ++j)
{ w = vertex[i]; // old exponent
q = qw[i][v][j]; // new recomendation
vrf[j] += q - qw[i][w][j];
vRcmd[i][j] = q;
}
vertex[i] = v;
}
int findbar()
{
}
int main(int argc, char **argv)
{ clock_t start;
double duration;
const int nofBars = 50;
int k, pen, lastPen, minPen, i=0;
if(argc > 1) srandom(argv[1][0]);
while ((i<supp) && (cin>>prime[i]))
{ cin>>wkd[i];
(wkd[i] < maxw) || (wkd[i] = maxw-1);
if(argc != 2)
{ cin>>vertex[i];
if (vertex[i] > wkd[i])
{ cout<< "WRONG input -- wkd < vertex";
cout<< "or provide argv with argc=2\n\n";
exit(1);
} }
++i;
} // read the brq base (primes and exponents)
////////////////////////////////////////////////////////
start = clock(); // the true start of the program
////////////////////////////////////////////////////////
pDim = i; // the initial dim of the brq base (i.e. the nof primes)
rm0(argc); // remove each prime[i] with exponent wkd[i] \<
0
research();
reduce(argc);
if(argc==2) selectv(); // select & research the initial vertex
else research_v(); // just research the initial vertex
pen = penalty();
show_v();
cout << " penalty = " << pen << endl<<endl;
minPen = 99999999; // reset minPenalty
// while(1) findbar(); // an inifinite loop :-)
//
// TEST
int kb, ar, printbd=2;
if(argc > 2) printbd = argv[2][0] - '0';
if(argc>1)
{ ar = argv[1][0];
kb = 200*ar*ar*ar;
}
else kb=4000000;
for(k=0; k < kb; ++k)
{ new_v();
pen = penalty();
if((pen <= printbd)||(pen < minPen))
{ show_v();
minPen=pen;
cout << k << ": penalty = " << pen << endl<<endl;
} }
// END of TEST
////////////////////////////////////////////
duration = difftime(clock(), start)/CLK_TCK;
////////////////////////////////////////////
cout << "\n\t\t" << duration << " seconds\n\n";
}