Anonymní profil Shaolin – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu

Anonymní profil Shaolin – Programujte.comAnonymní profil Shaolin – Programujte.com

 

Příspěvky odeslané z IP adresy 82.142.106.–

Shaolin
C / C++ › Ukládání potomků jedné nadtř…
25. 2. 2009   #95976

Tak už jsem to vyřešil. V tom for cyklu je třeba obdélníky vytvářet dynamicky. Takže teď to volám takto: seznam.vloz(new Obdelnik(1, 2, 3, 4); diky

Shaolin
C / C++ › [Algoritmus - rebus] Kruhový…
8. 1. 2009   #93981

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

Shaolin
C / C++ › [Algoritmus - rebus] Kruhový…
5. 1. 2009   #93626

To je pravda, takhle to nepůjde.

Shaolin
C / C++ › [Algoritmus - rebus] Kruhový…
5. 1. 2009   #93608

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.

Anonymní uživatel
C / C++ › [Algoritmus - rebus] Kruhový…
5. 1. 2009   #93585

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.

 

 

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