[LUGOS-PROG] Sortiranje mnozice stevil glede na non-tranzitivno relacijo

[igor]

> Ce sem te prav razumel imas le nekaj (sto) izjem.  Jaz bi v dodatni
> tabeli hranil indekse
> teh nekaj problematicnih clenov zaporedja.  Ne vem, ali sem kaj
> spregledal. 

Sorry, slabo sem premislil.  
Torej popravni izpit.

1. korak
Sortiraj stevila po velikosti, recimo temu navadna ureditev.
Stevila vecja od najvecje izjeme in manjsa od najmanjse izjeme
so ze optimalno urejena.  D.N. Dokazi.  - salim se

2. korak
Pusti neproblematicna stevila urejena po navadni ureditvi
ter ustavi problematicna stevila cim bolje.
Indekse problematicnih stevil hrani v tabeli,
tako da zlahka izracunas vse konflikte:
a) konflikte med problematicnimi stevili
b) konflikte zaradi prestavitve problematicnih stevil iz navadne
ureditve
(konflikte med problematicnimi in neproblematicnimi stevili)
Drugih konfliktov tu ni.

3. korak
Predpostavimo, da je problematicnih stevil le nekaj in da so v tabeli
dalec narazen.  Recimo 100., 180., 240. clen.  
Priredi vsakemu problematicnemu stevilu okolico - pol poti do soseda.
Tj. 180. clen naj ima okolico 140.-210. clen.
Problematicna stevila se v tem primeru niso prestavila dalec iz
navadne razporeditve.  Prestavi se stevila iz njegove okolice blizje
k njemu.  To ne spremeni konfliktov izven okolice, zato lahko
za ta del izpeljes zaprto formulo.

Ce je problemov le nekaj in so dalec narazen, je to ze optimalna
resitev.  Sicer pa poskusi se kaj.  Moja ideja z permutacijami je
najbrz od tu dalje prepocasna.  Tako da tole lahko uporabis kot
res dober zacetni priblizek.

Pa veliko uzitkov ob programiranju.  LP, igor



-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://liste2.lugos.si/pipermail/lugos-prog/attachments/20040323/46363849/attachment-0001.htm