Kezdőoldal » Számítástechnika » Programozás » Házi feladat segítségre lenne...

Házi feladat segítségre lenne szükségem?

Figyelt kérdés

Sziasztok ez a feladat:

[link]


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.



2020. okt. 22. 21:00
1 2 3
 1/22 anonim ***** válasza:
0%
Na ez már érdekesebb feladat, nem olyan unalmas, mint amiket sokszor szoktak adni. Mivel már nem emlékszem matematikai dolgokra, én nyers erővel mennék neki a feladatnak. Azaz eltárolok egy int változót, amibe beírom, mennyi eddig a maximuma (kezdőérték 0). Ezután egy (vagy dupla) for ciklussal végigmennék a mátrixon, és elhelyezném az adott helyre a hangszórót, ha az a mező épp 0. (Ha 1, akkor skippeljük ezt, vagyis continue utasítás). Mivel csak négy irány van, nem nehéz manuálisan megnézni a négy irányt, és az összegüket összehasonlítjuk a max változóval (ami az eddigi legnagyobb cellamennyiséget jelenti). Ha nagyobb, eltároljuk, ha nem nagyobb, rakjuk a következő cellába a hangszórót.
2020. okt. 22. 21:37
Hasznos számodra ez a válasz?
 2/22 anonim ***** válasza:
0%
Annyit hozzáírnék még a válaszomhoz, hogy ez nagyon nem optimális algoritmus, mert O(n*n)-es komplexitású. Szóval tényleg érdemes összefüggést keresni, amivel O(n) vagy O(n*log(n)) lehetne, már az is nagy nyeremény volna. Az n négyzet elég lassú tud lenni, a te esetedben az n=1000nél már egymillió kört menne a ciklus.
2020. okt. 22. 21:47
Hasznos számodra ez a válasz?
 3/22 anonim ***** válasza:

#2 O(n^3) az algoritmusod.

Negyzetes pedig boven eleg ehhez, par ms alatt lefut.

2020. okt. 22. 21:57
Hasznos számodra ez a válasz?
 4/22 A kérdező kommentje:

"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?

2020. okt. 22. 22:16
 5/22 anonim ***** válasza:
0%
Úgy juthatnánk vele helyes megoldáshoz, hogy kihagyjuk azokat a cellákat, amik biztosan nem hoznak maximumértéket.
2020. okt. 22. 22:21
Hasznos számodra ez a válasz?
 6/22 A kérdező kommentje:
De honnan tudjuk hogy biztosan nem hoznak maximum értéket ha nem is láttuk őket?
2020. okt. 22. 22:24
 7/22 anonim ***** válasza:

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.

2020. okt. 23. 11:29
Hasznos számodra ez a válasz?
 8/22 A kérdező kommentje:

"Az konnyen belathato, hogy negyzetesnel nincs jobb megoldas"


Én is így gondolom de az 5-ös miről beszél akkor?

2020. okt. 23. 12:05
 9/22 anonim ***** válasza:
Van egy valaszolo, aki ilyen jellegu kerdesekhez mindig baromsagokat irkal, aztan eltunik. Lehet o az.
2020. okt. 23. 17:09
Hasznos számodra ez a válasz?
 10/22 curiousgeorge09 ***** válasza:

Sziasztok!

Ha még aktuális, itt egy lehetséges C# implementáció, hogy O(n^2) időben megoldjuk a feladatot:

[link]

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!

2020. okt. 28. 08:57
Hasznos számodra ez a válasz?
1 2 3

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

A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!