Pole-počet proměnných – Pascal – Fórum – Programujte.com

Dobrý,

 Mám problém snažím se řešit matematickou olympiádu P. Je tam úkol který +- zní :"Máme max 500 planet mezi kterými je max 10000 jednostranných teleportů. Z důvodu jednostrannosti jsem "vytvořil" algoritmus na kontrolu takový, že jsem chtěl udělat pole obsahující všechny možné varianty pojmenované z "pětistovkové" soustavy (1.20=20;2.20=520; atd.) a takových možností je 250 000 a při každém kontrolovaném teleportu se jedna proměnná z těch 250 000 vynuluje a potom přijde podmínka že se nerovná 0 atd. Prakticky pro menší počty možností nemá algoritmus chybu. Můj problém je, že mi Turbo Pascal 7 nežere "var kontrola: array[1..250000] of integer" píše to, že byl překročen ordinální typ. Dá se to nějak obejít? Napadlo mě udělat několik polí pro kontrolu třeba po 50000, ale to bude zase problém při práci. Poraďte prosím. PS: napadl mě ještě jeden algoritmus na kontrolu ale při zběžném propočtu mi přišel časově náročnější.

#1 Kalgys
Že je příliš mnoho variací mi to píše i při 15k

da se to obejit... musis najit pojem Dynamicke pole...

(samozrejme to predpoklada 32b pascal... se 16bitovyho TP7 se mozna na tak velky pole nedostanes ani tak)

Jakékoli pole, ať už statické nebo dynamické, bere překladač jako jednu proměnnou. Limit velikosti proměnné v real módu, ve kterém TP pracuje, je cca 64 KB (u dynamických proměnných je to přesně 65528 B, u statických tuším plných 65536). Statických globálních proměnných může být v jednom modulu (programu nebo jednotce) celkem max. taky jenom 64 KB, ale dá se to obejít rozdělením do několika jednotek. Při dynamické alokaci na hromadě (New nebo Getmem) je dostupných teoreticky 640 KB (samozřejmě po max. 64 KB blocích), ale v praxi to bývá míň - např. u mě většinou tak 300..400 KB podle toho, kolik mám zrovna rezidentních ovladačů, kolik místa zabere vlastní program a jeho statické proměnné, jestli běží TP a jestli kompiluju na disk nebo do paměti a tak. Bacha, že těch 250000 integerů zabere skoro půl mega paměti.

Vidím tři možnosti:

1) Jak říká KIIV: přejít na plně 32bitový překladač, kde máš paměti hafo a bez 64 KB limitu (např. Freepascal nebo Delphi).

2) Rozdělit si to do několika polí. Integer zabere 2 B, takže jich do jednoho pole nacpeš max. 32768. Na obsluhu si potom můžeš napsat funkce, třeba "ulož číslo" a "načti číslo", kterým předáš jenom index a hodnotu a už se nestaráš o to, jak to konkrétně provedou a do kterého pole budou sahat (tj. transparentnost - zvenku se to chová jako jedno obrovské pole). Teoreticky, kdyby nestačila paměť, si můžeš data ukládat do souboru, ale bude to samozřejmě pomalejší.

3) Vymyslet jiný algoritmus. Osobně bych asi zvolil tenhle způsob, ale neznám celé zadání.

Mimochodem, co vlastně se všemi těmi teleporty máte dělat? :-)

No 1.) můžeš si to najít na stránkách matematické olympiády a tam kategorie P příklad P-I-I nebo

2.) ti to přibližně popíšu; takže :Máš n planet (1<=n<=500), které jsou rozděleny do tří typů ( 0-> nepřežiješ ani minutu; 1-> chvíli přežiješ a můžeš využít teleportu; 2-> můžeš žít až do smrti (to všude :D) a podmínky tě nezabijí)

dále máš m  (0<=m<=10000) jednostranných teleportů; planety pojmenuješ jako 1,2,3,...,n a jako výstup vstupu má být

" n m

typ[1] typ[2] ... typ[n]

port[nějaká_počáteční_planeta].odkud port[nějaká_koncová_planeta].kam

port[nějaká_jiná_počáteční_planeta].odkud port[nějaká_koncová_jiná_planeta].kam

atd."

potom máš udělat program, který se "podívá" na planetu 1 a podívá se na její typ jestli je 0 tak ji přejde;

else podívá se na teleporty z ní pokud je ta planeta typ 2 a všechny planety na které se dá i několika teleporty z ní dostat jsou také typ 2 tak ji nazveš bezpečnou a třetí možností je když se dá na planetě zůstat (je typ 2) nebo se z ní dá nějak na typ 2 dojít tak je snesitelná 

a výstup je "bezpecna: planeta[neco] dalsi planety

snesitelna: ty snesitelne"

a to je tak vse problém mám jenom s tím polem

PS: jako další možnost kontrolního algoritmu jsem přemýšlel přibližně o tomto; vemu teleport[1].odkud and teleport[1].kam a porovnám je se všemi následujícími a ty z následujících co jsou stejné změním tento krok budu opakovat dokud nebude teleport[1] jedinečný a pak pro teleport[2] atd. ale to mi na p

řešením mého problému tedy bude stáhnout si lepší "editor"?

Je to tohle? http://mo.mff.cuni.cz/…adani-1.html Jestli jo, tak na to TP bohatě postačí, jenom prostě nebudeš moct natvrdo udělat tu matici "každý s každým".

Na 500 planet bohatě postačí množina ve formě pole 500 booleanů. Kdybys použil bitové pole (pro inspiraci viz např. http://mircosoft.mzf.cz/…ad/NFSUP.PAS ), zvětší se kapacita na osminásobek, čili až 524224 planet v jednom 64kilobytovém poli.

Všechny teleporty se s rezervou vejdou do jednoho pole: 10000 teleportů * (2 B na výchozí planetu + 2 B na cílovou) = 40000 B, což je míň než 64 KB, takže pohoda. Těch 200000 už by bylo horších, tam už by se musely použít čtyřbytové longinty a 4*2*200000 = 1.6 MB a tolik paměti v TP dohromady nedáš. Ale dalo by se to řešit opakovaným načítáním ze souboru, i když by to bylo o dost pomalejší - o rychlost nejde, ne?

Zbytek bych řešil cyklickým prohledáváním a postupným přesouváním planet, u kterých už si jsem jistý, do výstupních množin, ale to už nechám na tobě, abych ti to náhodou nějakým omylem nevyhrál :-).

jako na výhru si šance určitě nedávám, ale přece jen jsem s programováním trochu dál než ostatní tak mě to donutila udělat; a poky jak to myslíš s těma 500 booleanama máš přece 500 planet a ne 500 teleportu teleportu máš až 10000 na to 500 ano ne nepostačí 

Přátelé stáhl jsem Free Pascal IDE (a taky půl lahve vodky  ) a problém s rozsahem pole je vyřešen ( asi) ale teď mi to kompilátor bere v pohodě, ale když ten program, který obsahuje proceduru kontrola1, která mi přiřadí pro těch 250 000 proměnných jejich hodnoty tak mi to problikne a skončí to a hodí mi to "EXITED WITH EXITCODE = 201" co s tím pro menší rozsah generovaných proměnných ( array[1..250000] of integer ), ale definuju jich třeba "jen" 25 000 tak to fachá dobře

PS: pro 

procedure kontrola1;

var d:integer;
begin
  d:=1;
  repeat
   kont[d]:=d;
   d:=d+1;
  until(d=32767);
end;

mi to funguje

Reakce na #8:

Taky že ne, v booleanových polích by byly jenom samotné planety. Hlavní myšlenka je o tom, že bys neměl jedno pole planet, kde by u každé byl uložen její typ a případně ještě informace o teleportech, ale oddělená pole pro jednotlivé typy planet (a ničeho jiného), takže pak u každého čísla bude akorát informace, jestli v tomhle poli je nebo ne. Plus potom samostatný seznam teleportů. Ten by vypadal třeba jako array [0..10000] of record start,cil:integer end nebo tak nějak.

U planet bys měl výhodu okamžitého přístupu (kouknutí na daný index v poli je záležitost jedné instrukce). Seznam teleportů budeš muset nějakým způsobem prohledávat, abys našel ty, které vycházejí z planety, kterou zrovna zkoumáš. Bude výhodné předem si ho setřídit podle výchozí planety a pak hledat třeba půlením intervalu. Případně si ještě udělat pomocný seznam indexů prvních teleportů od každého čísla, takže se vyhledávání zjednoduší a zrychlí. To už je ale pro začátek celkem podružná záležitost.

Reakce na #9:

Tady ti pomůže jedině manuál k FP, kde ten kód snad bude popsaný :-).

Sry asi jsem blbej, ale pořád nechápu ty typy planet nemáš předem určené ty mají být náhodné třeba nemusí být ani jedna typu 2

Jasně, to se dozvíš až jak je budeš načítat. Pole si nadeklaruj pro 500 a pak do nich ty planety házej, jak budou chodit. Je jedno, že pole nebudou plná.

Edit, P.S. k tvému P.S.: Proč to dělat takhle složitě, když existuje cyklus For? Jo, a jestli ta chyba byla překročený rozsah proměnné, tak to je tím, že maximum pro integer je 32767. Na cokoli většího potřebuješ longint.

#12 Mircosoft
Díky všem už mi to šlape stáhl jsem free pascal místo velké části integeru jsem dal longinty a je to v pohodě