Házi feladat segítségre lenne szükségem?
Sziasztok ez a feladat:
Miképpen kellene ezt megoldani? Próbálom magamtól megírni a kódot úgyhogy nem kész megoldást kérek hanem ötletekre lennék kíváncsi inkább. Nem tudom milyen algoritmust kéne használnom.
#2 O(n^3) az algoritmusod.
Negyzetes pedig boven eleg ehhez, par ms alatt lefut.
"Szóval tényleg érdemes összefüggést keresni, amivel O(n) vagy O(n*log(n)) lehetne"
Ha n*n-nél jobb az nem azt jelenti hogy nem is nézünk meg minden cellát? Úgy hogy juthatnánk helyes megoldáshoz?
Ha nem erdekli a tanart a futasido, akkor az elso valaszolo O(n^3) megoldasa is jo lehet akar.
Ha igen, akkor O(n^2) megoldashoz azon gondolkozz el, hogy adott poziciohoz hogyan tudod megkapni konstans idoben a hangos cellak szamat.
Az konnyen belathato, hogy negyzetesnel nincs jobb megoldas.
"Az konnyen belathato, hogy negyzetesnel nincs jobb megoldas"
Én is így gondolom de az 5-ös miről beszél akkor?
Sziasztok!
Ha még aktuális, itt egy lehetséges C# implementáció, hogy O(n^2) időben megoldjuk a feladatot:
Nem veszi figyelembe azt az esetet, ha a mátrix minden mezőjében 1-es áll, azt hiszem, nem is az a lényeg...
Más: nem jagged array-t, hanem 2D tömböt használtam, de ez ugyebár könnyen átírható.
Szép napot mindenkinek!
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!