[solved] Neumím programovat 3

4.5.2009 20:23 | Přečteno: 2153× | Jiné | poslední úprava: 4.5.2009 23:10

Tak a je to tady zase.

Další úkol z C++ a další problémy. Zkoušel jsem to na vzorovém příkladu, výstup je identický s ukázkou, ale progtestu se to prostě nezdá a dá mi za ukázku 87% a o zbytku nemluvě. Chybu prostě nevidím a nevidím, ale třeba bude mít někdo lepší oči Zdroják a PDFko se zadáním v prvním komentáři. Moc moc děkuju.

Solved

Update 2

A kdyby chtěl někdo pomoct s úkolama na matiku (diferenciální rovnice/soustavy), budu jen rád, ve čt je chce a zatím nemám ani půlku... klidně toho dotyčného pak nechám dát mi přes držku        

Komentáře

[Jardík]

Přílohy:

• main.cpp (5440 bytů)
• zadani.pdf (473839 bytů)

Tu

[Jardík]

Aha, už něco vidím, tak moment

[Jardík]

Hmm, planý poplach, nevidím

[Jardík]

Ouvej, ach to binární půlení, ono mi to přistupuje za konec na konci v tom return, má tam být false

[Jardík]

Sakra, ještě tam je něco ...

[Jardík]

Hmm, půlení Snad takhle?

bool Mnozina::find(int x, size_t& result) const
{
	const int *p = _data;
	size_t size = _size;
	size_t index;
	
	while (size > 0)
	{
		index = size >> 1;
		
		if (p[index] == x)
		{
			result = (size_t)(p - _data) + index;
			return true;
		}
		else if (p[index] > x)
		{
			size = index;
		}
		else // p[index] < num
		{
			p += index + 1;
			size -= index + 1;
		}
	}
	
	result = (size_t)(p - _data);
	return false;
}

Ano !!! Progtest to sežral. Děkuji všem za rady, nakonec jsem to teda našel sám Příště si správně napsat to hledání...

[deda.jabko]

nechapu, proc se paples s vlastnim vyhledavanim (obzvlast, kdyz to neumis) a misto toho nepouzijes bsearch ze stdlib.

binarni vyhledavani je ukazkovym prikladem algoritmu typu divide et impera, takze pouziti rekurze je vic nez nasnade. z vyse uvedeneho kodu je opravdu radost lustit, co vlastne dela.

mimochodem, tvuj priserny zlozvyk zamenovat operace nasobeni a deleni s operacemi bitovych posunu byl povazovan za znamku spatneho programatora uz v sedesatych letech minuleho stoleti... a to tehdy byly jine pocitace...

[Ladicek]

Protože stdlib použít nesmí, nebo něco takového jsem v tom zadání viděl.

Vyhledávání půlením intervalu je úžasný algoritmus , ale rekurzivně ho nepíše snad nikdo.

[deda.jabko]

ale rekurzivně ho nepíše snad nikdo

to je hodne silne tvrzeni. ja treba jo a nejsem sam. imho je tak ten algoritmus citelnejsi a jednotliva volani jsou v tail-pozici, takze rychlost je plne srovnatelna s iterativni verzi. a hlavne.

[deda.jabko]

(sakra) a hlavne... v nekterych jazycich je psani iterativni verze hodne nepohodlne... ;-]

[Ladicek]

No jo, jasně. Když jsem psal interpret Lispu, taky jsem implementoval spojové seznamy rekurzivně

[Ladicek]

V Object Pascalu, dodávám. Tam myslím optimalizace tail callů není

[deda.jabko]

ja jsem ted zase implementoval operace nad setridenymi spojovymi seznamy iterativne... az me prekvapilo jaky je to priserny opruz ve srovnani s tim, kdyz se to dela rekurzivne.

jinak muzes nadhodit nejaky duvod proc nedelat binary search rekurzivne?

[Ladicek]

S TCO žádný, jenom jsem to fakt ještě nikde neviděl.

[Deleted [8409]]

Zkuste se někdy podívat třeba do knihovny Cairo, Pixman, do X serveru atd. (bitové operace)

[deda.jabko]

chapu, ze za urcitych okolnosti to muze mit opodstatneni, i.e., pokud se opravdu pracuje s bitovyma reprezentacema nebo pokud je opravdu potreba vykon... ale pouzivat a >> 1 misto (a / 2) v domaci uloze, aby se dosahlo naprosto nemeritelneho zrychleni, je spis asi ta znamka spatneho stylu... docela se divim, ze to vyucujicimu nevadi.

[kralyk z abclinuxu]

Jj. Nadruhou stranu to vypadá drsně, člověk tím ukáže, že má l33t hax0r skillz, yeah nigga...
V kombinaci se zásadním nepsaním komentářů je člověk potom naprostej uberhax0r king

[Jardík]

Minule mi někdo nadával, že co řádek, to komentář, a teď zase nadávaj, že tam žádnej neni

[deda.jabko]

dobry program nepotrebuje komentare, protoze z nej jde poznat co dela. coz u peti zanorenych if-u s kryptickymi podmikami jde docela stezi.

[mektige]

Komentáře nemají vysvětlovat co program dělá (tedy ne na stejné úrovni abstrakce jako kód, protože by měl být, jak píšeš, samovysvětlující), mají hlavně vysvětlovat proč a jak. Sebelepší prdukční kód potřebuje komentáře.

[mektige]

I kvůli výkonu je to diskutabilní, protože překladač je chytřejší než programátor (v případě Jardíka obzvlášť).

[Jardík]

Bitový posun je mnohem rychlejší a nepracuji se znaménkovým typem, takže ...

[deda.jabko]

Bitový posun je mnohem rychlejší a nepracuji se znaménkovým typem, takže ...

a muzes mi to tvrzeni nejak dolozit... a demonstrovat o kolik je to mnohem rychlejsi?

[Jardík]

# vstup rax, výstup rax
48 d1 e8                       shr rax #bitový posun vpravo o 1b
vs
48 c7 c3 02 00 00 00           mov rbx, 0x2
48 f7 f3                       div rbx

[Jardík]

ještě jsem zapomněl na vynulování rdx k tomu dělení ... další instrukce navíc

[Deleted [8409]]

Není to v debug módu? To je mi nezdá, že by překladač tak hloupě použil dělení, to je až na facku :)

[deda.jabko]

nevim, co ma jardik za prekladac, ale GCC tady toto optimalizuje uz v rezimu -O0.

[deda.jabko]

ja bych chtel, ale videt nejake realne srovnani casu na bud umelych nebo realnych programech.

[Ladicek]

Bitový posun napsaný programátorem je mnohem rychlejší než bitový posun vyrobený překladačem?

[Jardík]

Tak to asi ne, něco na tom bude ... co když někdo bude mít rozbitý kompilátor, který to na posun nepřevede

[Ladicek]

Tak se zboří svět! Viz též to PDFko o optimalizujících překladačích, které tu někdo odkazoval, velmi poučné.

[AltOS]

Vyborne. Dalsi orna puda pro KU.

Hodnotim Dobre.

[kotyz]

Ja mu dal spatny, aby nemel moc vysoky hodnoceni a nestouplo mu to do hlavy. Ale kdyby mel nulu, dal bych mu dobry, aby se mu nesplnilo to jeho vecny prani ...

Rikejte mi "Mistr Svinak"

[AltOS]

Ale kdyby mel nulu, dal bych mu dobry, aby se mu nesplnilo to jeho vecny prani ...

Sak ji tam taky mel, kdyz jsem klikal na "dobre".

[=^..^= AmigaPower®]

...tywoe, tu školu dělá Jardík, nebo abclinuxu?

[kotyz]

Vypada to ze to je 50:50, ale az budou tezsi tadani, bude to spis 80:20 (80 pro abc)

[AltOS]

No a co? Uz jenom to, ze se tu klucina jeden usatej snazi nakopnout nektere "linuxaky" spravnym smerem k pochopeni, co ze vlastne je user friendly, nebo to, ze si tu nechava vypracovavat domaci ukoly, zatimco si vesele vystaci odpovidat sam sobe v diskuzi pod jeho vlastnim blogem v jednom vlakne devetkrat, popr. last but not least pripravujic ornou pudu pro KU, IMHO stoji za to.

Mno, alespon nikdy nezustane osamocen jako "PeTovo tricko".

[saly]

No, hele, co takhle v zadání "Odevzdávaný soubor nesmí kromě implementace třídy Mnozina obsahovat nic jinéh, zejména ne funkci main" ... ?

[saly]

Aha, tak nic, nečetl jsem tu větu za tím ;)

[kotyz]

To my vime ze neumis, nemusis nam to porad opakovat, jednou to staci

[Ladicek]

Další úkol z C++ a další problémy.

Já nevím, co na tom jazyku lidi vidí…

[kralyk z abclinuxu]

ále kušuj ty tam v Indonésii... :p

[Deleted [8409]]

Jazyk pro vyvolené :-P

[kotyz]

Pro vyholene?

[Salamek]

Vyhulené ?

[Deleted [8409]]

I vyhulené, ale vše má meze ;)

[Jardík]

Já se omlouvám, ale na tamto "tajné" nějak nezbývá čas. Sice jsem kouknul na TODO, zjistil, že tabulátory byly nahrazeny mezerami, ale zatím ani ťuk A nechci to zkazit, jsem amatér, to vidíš ...

[Deleted [8409]]

To jo, změnit taby na mezery zvětšilo zdrojáky, takže jde vidět nějaká práce Popravdě na TODO není moc času, teď mě zajímá nejvíc zkusit použít vlákna na vykreslování, celkem zábava :)

PS: Jinak to tajné zní dobře :)

[kotyz]

Nebudes po nas (na me nekoukej, ja to umim jenom zkompilovat, ale nevim co to vlastne dela) za chvili chtit abysme ti ty ukoly rovnou psali ze bys je jenom odevzdaval?

[Jardík]

To né ... to bych přišel o radost se vztekat, když to nejde

[kotyz]

Ale zase by si tu skolu mozna dodelal ...

[ʚĭɞ 🍉]

Ty nemachruj...

[Jardík]

Ste jak malý Jardové ... jistě že školu nedodělám

[Jardík]

Malý Jardové, jako mladý .. mladí .. aha, malí.

[kralyk z abclinuxu]

Máš ten blog v podstatě jako formu samostudia
Vždyť ty si tu (téměř) všechny problémy vyřešíš sám...

[kotyz]

Ja nikdy nerikal ze ji dodelam nebo ze ji chci dodelat. Kdyz to klapne tak budu brzo prodavat pracky a televize a naka skola me muze bejt ukradena

[ʚĭɞ 🍉]

To raději školu než prodávat pračky.

[kotyz]

Me ta skola po tolika letech uz leze krkem ...

[=^..^= AmigaPower®]

...dneska bez školy nemůžeš prodávat ani ty pračky, ale nezoufej, možná to vyjde s lopatou.

[kotyz]

Ne, vysokou na to fakt nepotrebujes

[ʚĭɞ 🍉]

Co za to dostaneš? Pac a pusu? Vynadáno od zákazníka?

[kotyz]

Penize!

[ʚĭɞ 🍉]

Fakt? Nekecej!

[...............23]

...dneska bez školy nemůžeš prodávat ani ty pračky, ale nezoufej, možná to vyjde s lopatou.

Aj na to sú už dneska školy

[=^..^= AmigaPower®]

+1

[ʚĭɞ 🍉]

Bude i čtvrtý díl? Čtyřka je číslo smrti, smůly a podobně... ^_^