abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
eParkomat, startup z ČR, postoupil mezi finalisty evropského akcelerátoru ChallengeUp!
Robot na pivo mu otevřel dveře k opravdovému byznysu
Internet věcí: Propojený svět? Už se to blíží...
3.12. 16:24 | Nová verze

Byla vydána Mageia 5.1. Jedná se o první opravné vydání verze 5, jež vyšla v červnu loňského roku (zprávička). Uživatelům verze 5 nepřináší opravné vydání nic nového, samozřejmě pokud pravidelně aktualizují. Vydání obsahuje všechny aktualizace za posledního téměř půldruhého roku. Mageia 5.1 obsahuje LibreOffice 4.4.7, Linux 4.4.32, KDE4 4.14.5 nebo GNOME 3.14.3.

Ladislav Hagara | Komentářů: 4
3.12. 13:42 | Pozvánky

V Praze probíhá konference Internet a Technologie 16.2, volné pokračování jarní konference sdružení CZ.NIC. Konferenci lze sledovat online na YouTube. K dispozici je také archiv předchozích konferencí.

Ladislav Hagara | Komentářů: 0
2.12. 22:44 | Komunita

Joinup informuje, že Mnichov používá open source groupware Kolab. V srpnu byl dokončen dvouletý přechod na toto řešení. V provozu je asi 60 000 poštovních schránek. Nejenom Kolabu se věnoval Georg Greve ve své přednášce Open Source: the future for the European institutions (SlideShare) na konferenci DIGITEC 2016, jež proběhla v úterý 29. listopadu v Bruselu. Videozáznam přednášek z hlavního sálu je ke zhlédnutí na Livestreamu.

Ladislav Hagara | Komentářů: 22
2.12. 15:30 | Zajímavý projekt

Společnost Jolla oznámila v příspěvku Case study: Sailfish Watch na svém blogu, že naportovala Sailfish OS na chytré hodinky. Využila a inspirovala se otevřeným operačním systémem pro chytré hodinky AsteroidOS. Použita je knihovna libhybris. Ukázka ovládání hodinek na YouTube.

Ladislav Hagara | Komentářů: 8
2.12. 14:15 | Nová verze

Byla vydána verze 7.1.0 skriptovacího jazyka PHP používaného zejména k vývoji dynamických webových stránek. Jedná se o první stabilní verzi nejnovější větvě 7.1. Přehled novinek v dokumentaci. Podrobnosti v ChangeLogu. K dispozici je také příručka pro přechod z PHP 7.0.x na PHP 7.1.x.

Ladislav Hagara | Komentářů: 3
2.12. 12:55 | Nová verze

Google Chrome 55 byl prohlášen za stabilní. Nejnovější stabilní verze 55.0.2883.75 tohoto webového prohlížeče přináší řadu oprav a vylepšení (YouTube). Opraveno bylo také 36 bezpečnostních chyb. Mariusz Mlynski si například vydělal 22 500 dolarů za 3 nahlášené chyby (Universal XSS in Blink).

Ladislav Hagara | Komentářů: 4
2.12. 11:55 | Pozvánky

Máte rádi svobodný software a hardware nebo se o nich chcete něco dozvědět? Přijďte na 135. sraz spolku OpenAlt, který se bude konat ve čtvrtek 8. prosince od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Sraz bude tentokrát tématický. Bude retro! K vidění budou přístroje jako Psion 5mx nebo Palm Z22. Ze svobodného hardwaru pak Openmoko nebo čtečka WikiReader. Přijďte se i vy pochlubit svými legendami, nebo alespoň na pivo. Moderní hardware má vstup samozřejmě také povolen.

xkucf03 | Komentářů: 1
2.12. 00:10 | Nová verze

Byla vydána verze 3.2 svobodného systému pro detekci a prevenci průniků a monitorování bezpečnosti počítačových sítí Suricata. Z novinek lze zmínit například podporu protokolů DNP3 a CIP/ENIP, vylepšenou podporu TLS a samozřejmě také aktualizovanou dokumentaci.

Ladislav Hagara | Komentářů: 0
1.12. 21:00 | Nová verze

Byla vydána beta verze Linux Mintu 18.1 s kódovým jménem Serena. Na blogu Linux Mintu jsou hned dvě oznámení. První o vydání Linux Mintu s prostředím MATE a druhé o vydání Linux Mintu s prostředím Cinnamon. Stejným způsobem jsou rozděleny také poznámky k vydání (MATE, Cinnamon) a přehled novinek s náhledy (MATE, Cinnamon). Linux Mint 18.1 bude podporován až do roku 2021.

Ladislav Hagara | Komentářů: 0
1.12. 16:42 | Nová verze

Byl vydán Devuan Jessie 1.0 Beta 2. Jedná se o druhou beta verzi forku Debianu bez systemd představeného v listopadu 2014 (zprávička). První beta verze byla vydána v dubnu letošního roku (zprávička). Jedna z posledních přednášek věnovaných Devuanu proběhla v listopadu na konferenci FSCONS 2016 (YouTube, pdf).

Ladislav Hagara | Komentářů: 2
Kolik máte dat ve svém domovském adresáři na svém primárním osobním počítači?
 (32%)
 (24%)
 (29%)
 (7%)
 (5%)
 (3%)
Celkem 771 hlasů
 Komentářů: 50, poslední 29.11. 15:50
Rozcestník
Reklama

Dotaz: C++ jednoduchý program nezvládá velké vstupy

11.11.2014 23:33 Lukáš Červený
C++ jednoduchý program nezvládá velké vstupy
Přečteno: 362×
Příloha:
Zdravím, předem se přiznávám, že se jedná o program do soutěže, nicméně funguje správně, ale neporadí si s většími vstupy. Zadání je takové:
Kevin je právě na horách a lyžuje. Stojí na vrcholu sjezdovky před svou poslední jízdou, za chvíli půjde na chatu opékat párky. Sjezdovku už dobře zná, každé místo projel snad stokrát a pamatuje si, jak se mu které líbí. Všechna jsou podle toho ohodnocená celými čísly.
    1
   2 3
  4 1 1
 2 5 0 2
Kevin by tedy chtěl, aby součet ohodnocení míst, přes která při poslední jízdě projede, byl co největší.

Na travních lyžích se dá jezdit z kopce a přitom zatáčet doleva nebo doprava. Z každé pozice na svahu se tak dá dostat na nejvýše dvě další pozice ležící pod ní.

Tvar vstupu: Pro jednoduchost bude kopec zadán po řádcích. Na prvním řádku bude číslo N udávající výšku kopce. Na dalších N řádcích bude vždy na i-tém řádku i celých čísel udávajících ohodnocení míst na kopci na i-té hladině od vrcholu, čísla budou oddělena mezerami.

Jízda doleva je v našem zápisu svahu ekvivalentní sestupu na další řádek a jízda doprava sestupu na další řádek a posunutí o pozici doprava.

Tvar výstupu: Na výstup vypište jedno celé číslo udávající maximální součet ohodnocení poslední Kevinovy jízdy z prvního řádku na libovolné místo na spodním řádku.
Program posílám v příloze. Problém je, že si poradí s kopcem vysokým 10 řádků, ale s kopcem vysokým 40 řádků už ne. A to by měl zvládnout i vstup 1000 řádků. Vstupy zapíše do pole správně, ale vrátí výsledek 0. Chyba tak musí být v rekurzivní funkci Všem předem děkuji za tipy.

Řešení dotazu:


Odpovědi

kozzi avatar 12.11.2014 00:40 kozzi | skóre: 55 | blog: vse_o_vsem | Pacman (Bratrušov)
Rozbalit Rozbalit vše Re: C++ jednoduchý program nezvládá velké vstupy

Mam pocit ze i bez kouknuti na program si dovolim tvrdit ze sis sam odpovedels v posledni, teda vlastne predposledni vete.

Linux je jako mušketýři "jeden za všechny, všichni za jednoho"
kozzi avatar 12.11.2014 00:43 kozzi | skóre: 55 | blog: vse_o_vsem | Pacman (Bratrušov)
Rozbalit Rozbalit vše Re: C++ jednoduchý program nezvládá velké vstupy

Tim samozrejme myslim tu rekurzi. Pokud chces aby to zvladalo vetsi vstupy tak urcite nepouzivej rekurzi.

Linux je jako mušketýři "jeden za všechny, všichni za jednoho"
12.11.2014 09:45 Kit | skóre: 36 | Brno
Rozbalit Rozbalit vše Re: C++ jednoduchý program nezvládá velké vstupy
Rekurze sama za to nemůže.
Komentáře označují místa, kde programátor udělal chybu nebo něco nedodělal.
kozzi avatar 12.11.2014 09:58 kozzi | skóre: 55 | blog: vse_o_vsem | Pacman (Bratrušov)
Rozbalit Rozbalit vše Re: C++ jednoduchý program nezvládá velké vstupy

JJ to je mozne, jak jsem psal kod jsem nestudoval, ale jen jsme vychazel s predpokladu ze rekurze je sice velmi dobre citelna, ale casto to neni idealni reseni.

Linux je jako mušketýři "jeden za všechny, všichni za jednoho"
12.11.2014 10:56 Kit | skóre: 36 | Brno
Rozbalit Rozbalit vše Re: C++ jednoduchý program nezvládá velké vstupy
Existuje pár algoritmů, u kterých je rekurze nepoužitelná - např. výpočet Fibonacciho posloupnosti. U některých je nevhodná, např. u výpočtu faktoriálu. Obecně však není méně efektivní než iterace v kombinaci se zásobníkem.
Komentáře označují místa, kde programátor udělal chybu nebo něco nedodělal.
Josef Kufner avatar 12.11.2014 11:10 Josef Kufner | skóre: 66
Rozbalit Rozbalit vše Re: C++ jednoduchý program nezvládá velké vstupy
Většinou ale rekurze znamená nějakou režii navíc s voláním funkce. Najde se však hodně případů, kdy to nevadí (není to zas tak moc) a výsledný kód je mnohem jednodušší než bez ní.
Hello world ! Segmentation fault (core dumped)
kozzi avatar 12.11.2014 11:56 kozzi | skóre: 55 | blog: vse_o_vsem | Pacman (Bratrušov)
Rozbalit Rozbalit vše Re: C++ jednoduchý program nezvládá velké vstupy

Tak on je problem ze rekurze se i hure optimalizuje s pohledu kompilatoru(optimalizatoru), dalsi problem s rekurzi je ze vyuziva zasobnik, ktery ma vetsinou nejak omezenou velikost. Samozrejme citelnost je velmi dulezita, takze pokud rekurze dostacuje tak bych ji zvolil taky. Bohuzel si nevzpominam na moc pripadu, kde bych rekurzi vyuzil, teda krom pripadu, kde jsme potreboval nazorne ukazat nejakej algoritmus.

Linux je jako mušketýři "jeden za všechny, všichni za jednoho"
12.11.2014 20:29 Kit | skóre: 36 | Brno
Rozbalit Rozbalit vše Re: C++ jednoduchý program nezvládá velké vstupy
Traverzování adresářovým stromem se typicky dělává rekurzí.
Komentáře označují místa, kde programátor udělal chybu nebo něco nedodělal.
12.11.2014 21:15 Šangala | skóre: 56 | blog: Dutá Vrba - Wally
Rozbalit Rozbalit vše Re: C++ jednoduchý program nezvládá velké vstupy
Dělá, protože se počítá s konečnou velikostí, ale kapacity disků a možnosti FS tomu už taky někdy slušně zatápí.
To, že trpíš stihomamem, ještě neznamená, že po tobě nejdou. ⰞⰏⰉⰓⰀⰜⰉ ⰗⰞⰅⰜⰘ ⰈⰅⰏⰉ ⰒⰑⰎⰉⰁⰕⰅ ⰏⰉ ⰒⰓⰄⰅⰎ ·:⁖⁘⁙†
Martin Tůma avatar 12.11.2014 00:47 Martin Tůma | skóre: 38 | blog: RTFM | Praha
Rozbalit Rozbalit vše Re: C++ jednoduchý program nezvládá velké vstupy

Moc jsem ten program nezkoumal, ale při výšce kopce > 31 ti přeteče ten výpočt mocniny, takže bych to tipoval na problém tady. K tomu 2 poznámky - počítat mocninu dvou násobenim je šílenost, podívej se na bitové posuvy.

A za druhé - i kdyby si měl tu proměnnou 64bit a mohl alokovat tolik paměti pro to pole (což je samozřejmě nesmysl), tak stejně končíš u výšky 64... Tzn takto to opravdu řešit principielně nelze.

Každý má právo na můj názor!
12.11.2014 09:48 Kit | skóre: 36 | Brno
Rozbalit Rozbalit vše Re: C++ jednoduchý program nezvládá velké vstupy
počítat mocninu dvou násobenim je šílenost, podívej se na bitové posuvy.
Slušný optimalizátor v překladači z násobení dvěma udělá bitový posun tak jak tak. Násobení dvěma je čitelnější pro programátora.
Komentáře označují místa, kde programátor udělal chybu nebo něco nedodělal.
Josef Kufner avatar 12.11.2014 11:14 Josef Kufner | skóre: 66
Rozbalit Rozbalit vše Re: C++ jednoduchý program nezvládá velké vstupy
Akorát, že ten bitový posun lze udělat o více než jeden bit najednou. Takže místo cyklu s násobením, který tam má:
    for(int i = 0; i < exponent; i++)
    {
        vysledek *= 2;
    }
Lze napsat jen toto:
vysledek <<= exponent;
Hello world ! Segmentation fault (core dumped)
kozzi avatar 12.11.2014 11:49 kozzi | skóre: 55 | blog: vse_o_vsem | Pacman (Bratrušov)
Rozbalit Rozbalit vše Re: C++ jednoduchý program nezvládá velké vstupy

Coz moderni optimalizator dokaze taky :), ale kazdopadne tady uz bych nemluvil o tom ze to je citelnejsi a nebo ze se na to da zcela spolehnout.

Linux je jako mušketýři "jeden za všechny, všichni za jednoho"
12.11.2014 12:01 Kit | skóre: 36 | Brno
Rozbalit Rozbalit vše Re: C++ jednoduchý program nezvládá velké vstupy
Ten zdroják jsem nezkoumal, druhý zápis je jistě přehlednější. Předpokládal jsem spíš posun o jeden bit a použití Hornerova schématu, u kterého by to vyšlo nastejno.
Komentáře označují místa, kde programátor udělal chybu nebo něco nedodělal.
kozzi avatar 12.11.2014 01:04 kozzi | skóre: 55 | blog: vse_o_vsem | Pacman (Bratrušov)
Rozbalit Rozbalit vše Re: C++ jednoduchý program nezvládá velké vstupy

Pokud muzu neco doporucit, tak asi toto: cti to radek po radku, hodnotu po hodnote. Vzdy si pamatuj predchozi radek a ten pricitej k tomu dalsimu co ctes tak jak je treba dle zadani a u posledniho radku vyber maximum.

dnes jsem unavenej zitra poslu pseudo kod

Linux je jako mušketýři "jeden za všechny, všichni za jednoho"
Řešení 1× (karl82)
Martin Tůma avatar 12.11.2014 01:25 Martin Tůma | skóre: 38 | blog: RTFM | Praha
Rozbalit Rozbalit vše Re: C++ jednoduchý program nezvládá velké vstupy

Pseudokód je třeba na wikipedii - jde o obyčejný BFS.

Každý má právo na můj názor!
kozzi avatar 12.11.2014 02:23 kozzi | skóre: 55 | blog: vse_o_vsem | Pacman (Bratrušov)
Rozbalit Rozbalit vše Re: C++ jednoduchý program nezvládá velké vstupy

Tak nakonec misto pseudo jsem to napsal v jazyku D. Jsem uz unaveny takze nerucim zcela za spravnost:

import std.stdio;
import std.algorithm;
import std.conv;

enum MAX_ROW_COUNT = 1000;
enum BUF_SIZE = 65535;

void main(string[] args)
{
	int[MAX_ROW_COUNT] row;
	char[] buf = new char[BUF_SIZE];
	auto f = File("test.txt");
	size_t len, rowCount;
	while((len = f.readln(buf)) != 0) {
		int lastVal = row[0];
		char[] rowData = buf[0 .. len];
		size_t index = 0;
		foreach (val; rowData.splitter(' ').map!(a=>parse!int(a))) {
			int tmp = row[index];
			row[index] = lastVal + val;
			lastVal = tmp;
			++index;
		}
		++rowCount;
	}
	writeln(minCount!("a > b")(row[0 .. rowCount])[0]); // seems wierd but minCount return maximum :)
}
Linux je jako mušketýři "jeden za všechny, všichni za jednoho"
kozzi avatar 12.11.2014 09:40 kozzi | skóre: 55 | blog: vse_o_vsem | Pacman (Bratrušov)
Rozbalit Rozbalit vše Re: C++ jednoduchý program nezvládá velké vstupy
Samozrejme je to spatne, toto by melo byt lepsi
import std.stdio;
import std.algorithm;
import std.conv;

enum MAX_ROW_COUNT = 1000;
enum BUF_SIZE = 65535;

void main(string[] args)
{
	int[MAX_ROW_COUNT] row;
	char[] buf = new char[BUF_SIZE];
	auto f = File("test.txt");
	size_t len, rowCount;
	int[2] lastVal;
	while((len = f.readln(buf)) != 0) {
		char[] rowData = buf[0 .. len];
		size_t index = 0;
		foreach (val; rowData.splitter(' ').map!(a=>parse!int(a))) {
			lastVal[index%2] = row[index];
			row[index] = max(lastVal[0] + val, lastVal[1] + val);
			++index;
		}
		++rowCount;
	}
	writeln(reduce!("max(a,b)")(row[0 .. rowCount]));
}
Linux je jako mušketýři "jeden za všechny, všichni za jednoho"
12.11.2014 17:25 Lukáš Červený
Rozbalit Rozbalit vše Re: C++ jednoduchý program nezvládá velké vstupy

Děkuji všem za rady. Jsem ještě začátečník, a abych pravdu řekl, tak jsem z Vašich odpovědí pořád nepochopil, proč mi program nefunguje :) Kód, který napsal Kozzi nemůžu použít, protože pracuji v c++ a ani mu pořádně nerozumím, abych ho přepsal.

12.11.2014 17:33 Radek Isa | skóre: 11
Rozbalit Rozbalit vše Re: C++ jednoduchý program nezvládá velké vstupy
Tak prinejmensim by jsi si mel neco nastudovat neco o umele inteligenci aspon zakladni algoritmy BFS nebo DFS. Ja osobne bych pro tento problem pouzil DFS, abych nemusel ukladat tolik uzlu v pameti.
Josef Kufner avatar 12.11.2014 17:38 Josef Kufner | skóre: 66
Rozbalit Rozbalit vše Re: C++ jednoduchý program nezvládá velké vstupy
DFS se na to nehodí, neboť dostáváš uzly po "vrstvách". Naopak s dobře udělaným BFS, nebo spíš lehkou modifikací Dijkstry to bude nejefektivnější. Stačí načítat řádek po řádku, sčítat hodnoty a brát vždy maximum z dvou možných hodnot na předchozím řádku. Výška stromu je předem známa díky odsazení vrcholu, takže si lze potřebné pole alokovat předem.
Hello world ! Segmentation fault (core dumped)
12.11.2014 17:48 Radek Isa | skóre: 11
Rozbalit Rozbalit vše Re: C++ jednoduchý program nezvládá velké vstupy
aha ja si neprecetl cele zadani.. to staci mit tolik jaka je viska stromu a pamatovat si maximu.. (+2) pro uzly pro ktere se bude zrovna vybirat maximu..
12.11.2014 18:27 Lukáš Červený
Rozbalit Rozbalit vše Re: C++ jednoduchý program nezvládá velké vstupy
Příloha:
brát vždy maximum z dvou možných hodnot na předchozím řádku
Toto nechápu. Vždyť na posledním řádku můžu dostat hodnotu, která bude větší, než všechny ostatní součty, tzn. že bude největší právě tato cesta. Těmto algoritmům nerozumím, ale ten svůj jsem přepracoval, takže hodnoty neukládá do pole. Nyní dělá toto: Prochází cesty úplně vlevo a sčítá. Až dojde na konec rozhodne, zda je součet větší, než zatím největší nalezení, případně ho zapíše. Následně se vrátí o vrstvu výš a vezme cestu vpravo, atd. atd. Pokud můžu mít dotaz, tak pořád nemůžu pochopit, proč mám číst vstup po řádcích. Původně jsem takový systém měl. Přečetl řádek, sečetl všechny kombinace, a ty zapsal do pole. Nakonec našel v poli největší hodnotu. Ten jsem ale přepracoval, protože se mi zdál zbytečně složitý. Díky za trpělivost a případné odpovědi :) V příloze posílám zdrojový kód.
Tarmaq avatar 12.11.2014 18:41 Tarmaq | skóre: 39
Rozbalit Rozbalit vše Re: C++ jednoduchý program nezvládá velké vstupy
Vzdy te zajima maximum, ke kteremu se dalo dojit na predchozim radku. Mozna to ukazu na dodanem prikladu:
    1
   2 3
  4 1 1
 2 5 0 2
Po zpracovani 1. radku [1]
Po zpracovani 2. radku [3, 4] = [2+1, 3+1]
Po zpracovani 3. radku [7, 5, 5] = [4+3, 1+4, 1+4]
Po zpracovani 4. radku [9, 12, 5, 7] = [2+7, 5+7, 0+5, 2+5]
Don't panic!
12.11.2014 18:46 Lukáš Červený
Rozbalit Rozbalit vše Re: C++ jednoduchý program nezvládá velké vstupy
Jé, už mi to docvaklo :) Díky moc.
kozzi avatar 12.11.2014 21:43 kozzi | skóre: 55 | blog: vse_o_vsem | Pacman (Bratrušov)
Rozbalit Rozbalit vše Re: C++ jednoduchý program nezvládá velké vstupy

JJ presne, to je vice mene to co dela muj kod, teda on alokuje zbytecne protoze nevyuiva informace o tom kolik realne radku tam bude.

Linux je jako mušketýři "jeden za všechny, všichni za jednoho"
12.11.2014 20:13 Šangala | skóre: 56 | blog: Dutá Vrba - Wally
Rozbalit Rozbalit vše Re: C++ jednoduchý program nezvládá velké vstupy

Mocnina dvojky je mocná

              2^40    = 1 099 511 627 776 * sizeof(int) = 4TiB RAM pro druhé pole
maximum int = 2^31 -1 =     2 147 483 647 * sizeof(int) = 8GiB RAM pro druhé pole
   ALE narveš tam jen třicetjedničku (to je daň za nulu :-)):
                            1 073 741 824 * sizeof(int) = 4GiB RAM pro druhé pole
¡31 je max! - na 64bit systému (omezení int) na 32 bit s PAE je to 29 bez PAE 29 nebo 28 (omezení systému) - zjednodušeně
¿Máš 4TiB paměti pro 40?

Zadej si 32 je docela pravděpodobné, že ti to vyhodí std::bad_alloc, bo fce mocninaDvojky() vrátí -2147483648 a to jaksi alokovat nelze.

Co se děje pokud tam zadáš vyšší číslo a mocnina se přetočí na nějaké kladné číslo, tak se mi nechce domýšlet co se tam vlastně děje - každopádně „kraviny“.
To, že trpíš stihomamem, ještě neznamená, že po tobě nejdou. ⰞⰏⰉⰓⰀⰜⰉ ⰗⰞⰅⰜⰘ ⰈⰅⰏⰉ ⰒⰑⰎⰉⰁⰕⰅ ⰏⰉ ⰒⰓⰄⰅⰎ ·:⁖⁘⁙†
12.11.2014 20:46 Lukáš Červený
Rozbalit Rozbalit vše Re: C++ jednoduchý program nezvládá velké vstupy
Díky za odpověď :) Když jsem si to pořádně rozmyslel, tak mi došlo, že je to hloupost :)

Založit nové vláknoNahoru

Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

ISSN 1214-1267   www.czech-server.cz
© 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.