Milyen algoritmussal lehetne az alábbi feladatot megoldani?

"Figyelni kell arra, hogy a benet hossza 200 000 karakter, ez esetben is 0.3mp alatt kell lefutnia a programnak. Gyorsnak kell lennie, itt inkább ezen van a hangsúly."

Számomra pedig ez az érthetetlen. Ha "O" (ordó)-val adja meg a "futásidőt" akkor oké, de a 0.3mp programnyelv és hardver ismeretének hiányában értelmezhetetlen. (Sőt, még úgy is, mert ha mellette videót konvertál a proci, akkor garantálom, hogy a futásidő megnő, mivel várakozni fog. :D) Elég fura feladat ez szerintem is.

#2: Online versenyeken szokott ilyen megkötés lenni, ahol a saját szerverükön fut a kód, hogy mennyi az időlimit. Az sem teljesen egzakt, de ott legalább van értelme. De simán csak annyit kijelenteni, hogy ennyi meg annyi idő alatt fusson le, az értelmetlen. Mi van, ha nálam lefut, az iskolai gépen meg nem? Vagy fordítva: ad a kedves tanerő egy működő megoldást, én előveszem a 486-osomat, lefuttatom rajta, és lám-lám, könnyen lehet, hogy piszkosul túllépi az időlimitet.

De oké, értem, hogy ez akart az ösztönző rész lenni, hogy ne olyan algoritmussal dolgozz, ami 2 napig fut. :) Volt nekem ebből afférom főiskolán. :D A feladatot megoldottam, viszont a tanár által beírt adatokkal több, mint egy órán át dolgozott. Nem fogadta el jónak, mivel túl lassú. (Én meg az érvelését nem fogadtam el, de ez már másik történet, akkoriban kevésbé voltam diplomatikus emberke.)

Viszont maga a feladat sem érthető. (Vagy csak én vagyok túl dekoncentrált így influenzásan, kialvatlanul?)

"egy DNS szekvencia mutációt okozhat, ha valamely benne szereplő karakter darabszáma legalább a DNS szekvencia hosszának a fele" - Ez egy egyszerű megszámolás tétel lenne. Annyi nehezítéssel, hogy 4 számlálód van, mindegyik bázisra (karakterre) egy. Végiglépkedsz az elemeken, ha "A", akkor annak a számlálóját növeled, ha "T", akkor azét, stb. Ha bármelyik számláló (igaz, egynél több nem lehet egyszerre) a bemeneti karakterlánc hosszának legalább fele, akkor mutálódhat a DNS, különben nem. (Egyébként érdekelne, hogy ennek tényleg van-e biológiai alapja, vagy csak egy random elmeszülemény?)

"Készíts programot, ami kiszámítja a vizsgált DNS szekvenciának a leghosszabb összefüggő mutáns részsorozatát!" - Ennek viszont abszolút nincs semmi értelme. Mi az, hogy mutáns részsorozat? Sehol nincs ez definiálva.

Ne értetlenkedjetek már. Kicsit értelmetlenül van megfogalmazva, de rá lehet jönni mit kér a feladat. Biztos nem is lehetetlen.

Engem inkább az érdekelne, hogy a kérdező milyen algoritmussal oldotta meg, ha már attól eltérő megoldásokat kér.

#5 Most nem kötözködésképp, de most te is csak a hasadra csaptál ugye? "Nincs olyan algoritmus, ami ilyen gyorsan lefut 200 000 karakter esetén..."

Gondolom ő ismeri a konkrét hardvert, de amúgy nem lehetetlen.

Viszont itt felmerült bennem akkor, hogy az algoritmust tekintve nem csak pszeudokód szintjén kell(ene) gondolkodni, hanem konkrét programnyelvet figyelembe véve, több szálon futó algoritmust kellene alkotni.

Nem ertem olyan emberek miert valaszolgatnak, akik ertelmezni sem kepesek egy ilyen egyszeru feladatot.

#5-on meg fel is rohogtem :)

Kerdezo, en igy csinalnam:

Nevezzuk a bemeneti stringet S-nek. Vegig megyek S-en, osszeszamolom melyik karakterbol hany db van, ezek maximumat nevezzuk M-nek.

A megoldas min(M * 2, length(S)).

O(n) time, O(1) space.