[Algoritmus - rebus] Kruhový seznam – C / C++ – Fórum – Programujte.com

Bohužel tu není žádné téma v diskuzi Programování - algoritmy (nebo obecné). Myslím, že by se hodilo... Píšu sem, protože tu je nejživější diskuze.

Řeším zajímavý problém.
Mějme dán jednosměrně zřetězený spojový seznam s nijak neomezeným počtem
prvků, který je zakončen odkazem na některý z prvků tohoto seznamu.
Tímto zpětným odkazem, který může vést na zcela libovolný prvek (první, poslední,
libovolný vnitřní ... ), vzniká cyklická struktura.

Úkolem je najít algoritmus, který určí
celkový počet prvků (tj. délku) tohoto seznamu.
- algoritmus však může vedle samotného spojového seznamu použít jen
pomocné paměti konstantní velikosti.

Už to řeším docela dlouho a stále se nemůžu dobrat kvalitního řešení, které by řešilo všechny možné případy.

Znáte někdo tento problém a víte, jak ho vyřešit?

leda ten seznam pokaždý, než se přesunes na další prvek projet od začátku a zjistit, jestli tam kde zrovna jseš, neodkazuješ na nějaký předchozích prvků...

To KIIV : Jo to vypadá jako jediné, velmi neefektivní řešení ;-) Ale asi jediné... Napadly mne různé vychytávky, ale žádná nebyla dokonalá.

no složitost bude nejspíš někde kolem exponencialní ...
leda si ještě ukládat i předchůdce... a pokud by se předchůdce lišil od prvku ze kterého jdeš.. poznal bys, že už se to točí

Přiznám se, že nechápu, co jsi tím myslel (možná je už moc pozdě :-), můžeš to prosím malinko rozvést?

no, když bys ten seznam vytvářel, tak by sis v každym prvku pamatoval i ze kterého byl vytvořen...

tj.
1 null 2 ( aktuální, vytvořil, další prvek )
2 1 3
3 2 4
4 3 5
5 4 2 (tady odkaz na druhý prvek) tj 1 -> 2 -> 3 -> 4 -> 5 -> 2 ....

a ty bys jen kontroloval, zda prvek, ze kterého přicházíš, ten prvek na který vstupuješ vytvořil...
pokud ne, tak to musel vytvořit nejaký jiný a tím víš že je to kruh...
neco jako 1 následující je 2 a vytvořil ho 1 1==1 ok.-... takhle jedeš až k 5.. vytvořil to 4 a přicházíš taky ze 4...
ale další je 2--- přicházíš z 5ky ale vytvořena byla z 1 .. tím končíš počítání(bez tý dvojky samo)

Jo rozumím. Ale to nepůjde. Ten seznam už je vytvořený a nejde měnit jeho strukturu. Ale myslím, že už mám celkem šikovné řešení: S nějakou (ještě nevím přesně jakou) pravidelností budu vkládat do seznamu své vlastní zarážky. Zarážky budou mít mou vlastní strukturu, budou vzestupně číslované. Jelikož je seznam založen na odkazech na další prvky, tak to nebude problém. No a pak při procházení seznamu někdy narazím na mou vlastní zarážku. Pak vím, že už jsem v cyklu. Takže si poznamenám nějaké potřebné hodnoty a můžu začít procházet seznam od začátku a odstraňovat svoje zarážky (aby zůstal seznam po skončení algoritmu stejný jako na začátku). Pokud budu vkládat svůj prvek po každém desátém prvku v seznamu, tak mi stačí si poznamenat do pomocného konstantního pole těch 10 prvků v seznamu, na které musí odkazovat poslední prvek v seznamu a ty kontrolovat, než dojdu na konec.
To je základ. Možná by ten konec šel udělat ještě lépe, ale obecně by to mělo mít lepší časovou náročnost. Každopádně díky za rady, pomohlo mi to se držet určitého správného směru.

tak je to podobne jako ty zarazky... jen by se to ukladalo jinam :)

Shaolin napsal:
Bohužel tu není žádné téma v diskuzi Programování - algoritmy (nebo obecné). Myslím, že by se hodilo... Píšu sem, protože tu je nejživější diskuze.

Řeším zajímavý problém.
Mějme dán jednosměrně zřetězený spojový seznam s nijak neomezeným počtem
prvků, který je zakončen odkazem na některý z prvků tohoto seznamu.
Tímto zpětným odkazem, který může vést na zcela libovolný prvek (první, poslední,
libovolný vnitřní ... ), vzniká cyklická struktura.

Úkolem je najít algoritmus, který určí
celkový počet prvků (tj. délku) tohoto seznamu.
- algoritmus však může vedle samotného spojového seznamu použít jen
pomocné paměti konstantní velikosti.

Už to řeším docela dlouho a stále se nemůžu dobrat kvalitního řešení, které by řešilo všechny možné případy.

Znáte někdo tento problém a víte, jak ho vyřešit?

Anonymní uživatel napsal:
Jo rozumím. Ale to nepůjde. Ten seznam už je vytvořený a nejde měnit jeho strukturu. Ale myslím, že už mám celkem šikovné řešení: S nějakou (ještě nevím přesně jakou) pravidelností budu vkládat do seznamu své vlastní zarážky. Zarážky budou mít mou vlastní strukturu, budou vzestupně číslované. Jelikož je seznam založen na odkazech na další prvky, tak to nebude problém. No a pak při procházení seznamu někdy narazím na mou vlastní zarážku. Pak vím, že už jsem v cyklu. Takže si poznamenám nějaké potřebné hodnoty a můžu začít procházet seznam od začátku a odstraňovat svoje zarážky (aby zůstal seznam po skončení algoritmu stejný jako na začátku). Pokud budu vkládat svůj prvek po každém desátém prvku v seznamu, tak mi stačí si poznamenat do pomocného konstantního pole těch 10 prvků v seznamu, na které musí odkazovat poslední prvek v seznamu a ty kontrolovat, než dojdu na konec.
To je základ. Možná by ten konec šel udělat ještě lépe, ale obecně by to mělo mít lepší časovou náročnost. Každopádně díky za rady, pomohlo mi to se držet určitého správného směru.

Moc jsem to nečetl, ale napadá mě Pollardův rho algoritmus.

(Příklad toho, na co se hodí vysoká škola ;)


A ta sekce na algoritmy a programování obecně by se vážně hodila.

Díky za podrobný rozbor :-)
K 1 příspěvku: Všechna ta řešení nejsou použitelná, protože v zadání je uvedeno použít konstantní velikost pomocného pole. Jedině tedy vyhovuje řešení číslo 4. To je přesně to samé, které navrhl KIIV.
K 2 příspěvku: Jedná se o takový rébus. Je tedy nutné se odprostit od praktických řešení ;-) Přidávat prvky do seznamu je možné. Je ale nutné, aby seznam na konci algoritmu byl stejný jako na začátku.

Zjišťuju ale, že moje řešení možná také není správné, protože možná nevyhovuji zadání na konstantním pomocné pole. Počet pomocných zarážek bude totiž závislý na délce pole.

Vypadá to že jediné 100% řešení je to první od KIIV (tvůj bod 4). Připadá mi to ale dost neefektivní, tak se snažím vymyslet něco efektivnějšího. Možná kdyby se ty zarážky nevytvářely pravidelně ale třeba pomocí násobku dvou. Tedy první zarážka třeba 4 a další pak 8, 16, 32, 64, 128, 256 atd... U seznamu s milionem prvků bych se dostal na počet 20 zarážek, které se myslím dají chápat jako konstantní číslo (i pro delší seznamy). Myslím, že cokoli trochu zlepší tu složitost O(n^2) pomůže.

Nic proti, ale to je normální logaritmus a to za konstantní číslo nikdo nepovažuje...

To je pravda, takhle to nepůjde.

Předvedl bych tu svůj algoritmus, několikrát jsem ho kontroloval, celkem bez chyb. :-)
Jeho složitost je jestli se nemylim někde pod 2*n (provedl jsem EDIT), ale
Předpokládám že se dá dál optimalizovat použitím rovnic na konstantní rychlost, nechávám prostor "zadavateli", využívá dvourychlostních pointerů.
Místo popisu schematicky, funkční zdroják.

uses crt;

Type

 tsezuk=^tsez;

 tsez=record

   prvek:integer;

   uk:tsezuk;

 end;

Var

  Sez:array[1..100]of tsez;

  i,j,a,b:integer;

  cit,cit2:integer;

  s1,s2,sp:tsezuk;

Begin

  clrscr;

  for i:=1 to 99 do

   begin

     sez[i].prvek:=i;

     sez[i].uk:=@sez[i+1];

   end;

   sez[91].uk:=@sez[10];

   cit:=1;

   s1:=@sez[1];

   s2:=@sez[1];

  repeat

   s1:=s1^.uk;

   s2:=s2^.uk;

   s2:=s2^.uk;

   inc(cit);

  If s1^.prvek=s2^.prvek then break;

  until false;

 {NASLI JSME BOD STRETU}

  cit2:=0;

  repeat

   s1:=s1^.uk;

   s2:=s2^.uk;

   s2:=s2^.uk;

   inc(cit2);

  If s1^.prvek=s2^.prvek then break;

  until false;

 { ZJISTILI JSME VELIKOST SMYCKY!}

  i:=cit;

  j:=2*cit-1;

  a:=(j-i)div cit2;

  dec(a);

  b:=0;

  If a>0 then

  b:=cit2*a;

  s1:=@sez[1];

  for i:=1 to b do

   s1:=s1^.uk;

  cit:=1;

 {TIM NEJHLOUPEJSIM ZPUSOBEM SE PRESUNEME TESNE PRED SMYCKU A JELIKOZ ZNAME JEJI VELIKOST NEBUDE PROBLEM ZJISTIT JEJI START}

 {TOTEZ BY SLO NEJAKO PRES ROVNICE}

  while s1^.prvek<>s2^.prvek do

  begin

   s2:=s1;

   s1:=s1^.uk;

   for j:=1 to cit2+1 do s2:=s2^.uk;

   inc(cit);

  end;

 {VSE PRICTEME: SMYCKU+POMOCNE POSUVY}

  writeln(cit2+cit+b-1);

End.

Ahoj, heureka :-) To vypadá na ten správný algoritmus. Vyzkoušel jsem ho a vypadá to, že opravdu funguje. Někdo mi už předtím radil, abych zkusil použít dva různě rychlé pointery. Bylo to ale bez bližších podrobností a když jsem to zkoušel, tak mi to nijak nevycházelo. Gratuluju :-)

..mno ted jeste vyresit sve vlastni zadrhele :D

EDIT> jeste drobnost napadlo me bezrovnicove zrychleni pri sikovnem puleni posledni hledane casti pred smyckou. Klasicky jsme max. 1 delku smycky pred tozn. pricteme celou cast, jsme za? pricteme polovic - nejsme? zpet ... atd.

a ten konec ma vypadat hospodarneji takhle:
cit:=1;
s2:=s1;
for j:=1 to cit2 do s2:=s2^.uk;
while s1^.prvek<>s2^.prvek do
begin
s2:=s2^.uk;
s1:=s1^.uk;
inc(cit);
end;

Shaolin: Napsal jsi do zadání paměť konstantní velikosti, tak jsem to chápal jinak. Každopádně řešení od o-loxe vypadá jako nejlepší :-)

Jinak už jsem zjistil, že se jedná o využití algoritmu želvy a zajíce. Viz: http://en.wikipedia.org/wiki/Floyd%27s_cycle-finding_algorithm#Tortoise_and_hare

Hlavně že to píšu o x příspěvků výš :)

zdravim mam jeden sw ktery podle alogoritmu a zadanich cisel spocita adalsi cislo a potrebuju najit ten algoritmus.

je to napriklad cislo
vstupni cislo vypocitane cislo podle niakeho algo
356406026581289 183446241425705
183446241425705 749978045358374
749978045358374 909268725573188
909268725573188 339123253520206
339123253520206 334160184123923
334160184123923 960999798388027
960999798388027 970694399860788
970694399860788 720634397769492
720634397769492 287705703529598
287705703529598 053558454924221
053558454924221 046890538400522
046890538400522 684749373562696
684749373562696 116230595331085
116230595331085 053877375823062
053877375823062 446732398247766
446732398247766 068222579985117
068222579985117 612660639566034
612660639566034 763429023358828
763429023358828 425990166183787

jinak ak by sa na to chcel niekto pozret mam aj ten sw kde to je vidiet ako to pocita naskakuju cisilka atd.
len temu nechapem.

klidne sa ozvete financna odmena.

datamobil@datamobil.sk

ak by existoval niaky sw ktory bi hladal alebo pocital algoritmy myslim takim sposobom ze tam zadam cisilka a on mi najde vsetky mozne variacie a cim viac cisel zadam tamk nakoniec vyselektuje tu spravnu variaciu na algoritmus.

v principu takovy algoritmus najit nelze, protoze pro kazdy konecny pocet znamych hodnot existuje nekonecne mnoho funkci takove vlastnosti. z toho jak ty cisla vypadaji bych ale tipnul ze se jedna o nejake bitove operace. kazdopadne zkouset to je o stesti, na prvni pohled v tom nic znameho nevidim.