[Algoritmus - rebus] Kruhový seznam – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Shaolin
~ Anonymní uživatel
11 příspěvků
4. 1. 2009   #1
-
0
-

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?

Nahlásit jako SPAM
IP: 85.207.245.–
Reklama
Reklama
KIIV+42
God of flame
4. 1. 2009   #2
-
0
-

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ů...

Nahlásit jako SPAM
IP: 80.250.27.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Shaolin
~ Anonymní uživatel
11 příspěvků
4. 1. 2009   #3
-
0
-

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

Nahlásit jako SPAM
IP: 85.207.245.–
KIIV+42
God of flame
5. 1. 2009   #4
-
0
-

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čí

Nahlásit jako SPAM
IP: 80.250.27.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Shaolin
~ Anonymní uživatel
11 příspěvků
5. 1. 2009   #5
-
0
-

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?

Nahlásit jako SPAM
IP: 85.207.245.–
KIIV+42
God of flame
5. 1. 2009   #6
-
0
-

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)

Nahlásit jako SPAM
IP: 80.188.94.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Anonymní uživatel
~ Anonymní uživatel
0 příspěvků
5. 1. 2009   #7
-
0
-

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.

Nahlásit jako SPAM
IP: 82.142.106.–
KIIV+42
God of flame
5. 1. 2009   #8
-
0
-

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

Nahlásit jako SPAM
IP: 80.188.94.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Architekt0
Super člen
5. 1. 2009   #9
-
0
-

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?



Teoretická univerzální řešení:

1. Udělat kopii seznamu, jehož prvky obsahují hodnotu pointerů na prvky původního seznamu. Při průchodu a počítání prvků nastavovat jejich hodnotu na nulovou. Poslední prvek bude odkazovat na prvek obsahující nulovou hodnotu.

2. Stejně jako 1., jen jako hodnoty použít hashe jednotlivých prvků.

3. Pokud jsou prvky seznamu malé, udělat rovnou kopii seznamu a zopakovat postup jako v 1.

4. Pokud je té pomocné paměti k dispozici fakt málo (kdy? proč?). Nezbývá než projít a porovnat předchozí prvky seznamu, zdali prvek neodkazuje na některý z nich.

Praktická řešení:

5. Pokud náhodou mají ty prvky seznamu nějaký identifikátor, jehož hodnota roste s každým novým prvkem (něco jako pořadové číslo), a seznam je vytvořen pěkně postupně, lze porovnat pouze tyto identifikátory (když je identifikátor následujícího prvku menší než aktuálního, vracíme se ve smyčce). Pozor, při přeházení prvků seznamu to nebude fungovat.

6. Podobně jako identifikátor prvku ve 5. může posloužit ID objektu v garbage collectoru, pokud tedy byl ten seznam vytvořen postupně a garbage collector přiděluje objektům identifikátory postupně. Pozor, při přeházení prvků seznamu to nebude fungovat.

7. A teoreticky by šly porovnat adresy prvků v paměti (aktuální a odkazovaný). Ale to už je třeba mít hodně věcí pod kontrolou, aby tam ten seznam byl uložen postupně.


Víc mě teď nenapadá :-)

Ve vyšších programovacích jazycích je všeobecně nejvhodnější 1. (případně 2.) řešení. Nějaké větší omezení na pomocnou paměť, do které by se nevešel ten hashovaný seznam, by tam nemělo hrozit (leda by to byla umělě a zbytečně vytvořená překážka).

V nižších jazycích, kde se hraje na každý bit paměti a kde nějaká omezení mají smysl, je nejlepší 7. (případně 5.) protože když už je málo paměti, tak je pravděpodobně i málo výkonu procesoru, tedy 4. řešení nehrozí. Takže se to musí naprogramovat co nejefektivněji po všech stránkách, včetně implementace toho seznamu, aby to 7. řešení fungovalo.

Nahlásit jako SPAM
IP: 62.209.204.–
Python + Django + PostgeSQL = spokojený vývojář :-)
Architekt0
Super člen
5. 1. 2009   #10
-
0
-

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.



To vůbec není dobré řešení. Pokud máš počítat délku seznamu, rozhodně ho přitom nemůžeš měnit. Nemůžeš počítat s tím, že s tím seznamem budeš pracovat jen ty. V době kdy bude prováděn ten tvůj algoritmus může dojít k nějaké události/přerušení, kdy s tím seznamem bude pracovajit jiný program a tvé změny (ty zarážky) způsobí chyby. A kdyby si měl jistotu, že v době vykonávání tvého algoritmu se s tím seznamem nebude nic dít, stejně to nedělej, protože takovou jistotu nikdy mít nebudeš :-)

Nahlásit jako SPAM
IP: 62.209.204.–
Python + Django + PostgeSQL = spokojený vývojář :-)
Quiark0
Věrný člen
5. 1. 2009   #11
-
0
-

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.

Nahlásit jako SPAM
IP: 193.86.140.–
Shaolin
~ Anonymní uživatel
11 příspěvků
5. 1. 2009   #12
-
0
-

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.

Nahlásit jako SPAM
IP: 82.142.106.–
Quiark0
Věrný člen
5. 1. 2009   #13
-
0
-

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

Nahlásit jako SPAM
IP: 193.86.140.–
Shaolin
~ Anonymní uživatel
11 příspěvků
5. 1. 2009   #14
-
0
-

To je pravda, takhle to nepůjde.

Nahlásit jako SPAM
IP: 82.142.106.–
o-lox0
Super člen
5. 1. 2009   #15
-
0
-

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.

Nahlásit jako SPAM
IP: 85.71.152.–
Shaolin
~ Anonymní uživatel
11 příspěvků
6. 1. 2009   #16
-
0
-

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 :-)

Nahlásit jako SPAM
IP: 85.207.245.–
o-lox0
Super člen
6. 1. 2009   #17
-
0
-

..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;

Nahlásit jako SPAM
IP: 85.71.152.–
Architekt0
Super člen
7. 1. 2009   #18
-
0
-

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ší :-)

Nahlásit jako SPAM
IP: 213.192.22.–
Python + Django + PostgeSQL = spokojený vývojář :-)
Shaolin
~ Anonymní uživatel
11 příspěvků
8. 1. 2009   #19
-
0
-

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

Nahlásit jako SPAM
IP: 82.142.106.–
Quiark0
Věrný člen
3. 2. 2009   #20
-
0
-

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

Nahlásit jako SPAM
IP: 147.251.55.–
Pit
~ Anonymní uživatel
1 příspěvek
24. 4. 2009   #21
-
0
-

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.

Nahlásit jako SPAM
IP: 91.127.153.–
tmi0
Věrný člen
7. 5. 2009   #22
-
0
-

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.

Nahlásit jako SPAM
IP: 195.113.21.–
ksp.mff.cuni.cz -- doporučuje 5 z 0 přetečených bufferů!
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 82 hostů

Podobná vlákna

Kruhový seznam — založil Redby

Kruhovy zoznam — založil tom

Algoritmus — založil LuckaH

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý