C# algoritmus pro počet inverzí – .NET – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu

C# algoritmus pro počet inverzí – .NET – Fórum – Programujte.comC# algoritmus pro počet inverzí – .NET – Fórum – Programujte.com

 

sh00ter0
Newbie
18. 3. 2011   #1
-
0
-

Zdravím,

dostal jsem za úkol stvořit program, kterej na vstupu dostane soubor s posloupností a vrátí kolik obsahuje inverzí.

Přesné zadání:

Je dána posloupnost celých čísel P1 ... PN. Čísla Pi a Pj jsou v inverzi, pokud i < j a zároveň Pi > Pj. 

Inverze je tedy porucha ve vzestupném uspořádání posloupnosti. Vašim úkolem je zjistit, kolik inverzí posloupnost obsahuje.

Vstupní posloupnost je uložena v textovém souboru cisla.in, kde na prvním řádku je číslo N
a na druhém řádku následuje N celých čísel v desítkovém zápisu oddělených mezerami.
Počet inverzí vypište na standardní výstup (v desítkovém zápisu).

Čísla mohou být i záporná a vejdou se do 32-bitového integeru.
Čisel v poslounosti je maximálně 100 000 a počet inverzí se také vejde do 32-bitového integeru.
Vstupní soubor se vejde do operační paměti (i několikrát).

Příklad:
cisla.in
5
4 5 3 1 2
std. výstup:
8


stvořil jsem 2 řešení
#1
http://pastebin.com/DUvRbDz1

#2
http://pastebin.com/641Ciahc
1. je na bázi merge sortu prakticky okopírovaný odsud
http://ksp.mff.cuni.cz/tasks/19/solution5.html#task5
2. je co mě napadlo jako první, při vkládání kontroluju kolik čísel dříve vložených je větších

Obě řešení na nějakých vstupech, které neznám, vrací údajně špatné výsledky.

Neměl by někdo nápad jak to vyřešit?

Díky.

Nahlásit jako SPAM
IP: 94.113.85.–
sh00ter0
Newbie
18. 3. 2011   #2
-
0
-

Tak nakonec vyřešeno, chyba u prvního řešení byla na řádku 58, 100 000 jsem si převed na byte :D druhé se nakonec (nečekaně) projevilo jako neefektivní.

Nahlásit jako SPAM
IP: 94.113.85.–
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, 16 hostů

 

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