Informatyka UJ forum

Spectro

[link widoczny dla zalogowanych]

Klasyk z Cormena.

Rogal

Może i klasyk z Cormena, ale podane jest tam tylko rozwiązanie korzystające z O(mn) pamięci i wzmianka, że liniowe owszem istnieje, ale to już czytelnik rozkmini sobie sam :D

hansu

No z tymze to rozkminianie samemu nalezy do takich raczej prostych i intuicyjnych (tzn jak znasz O(mn) to bez problemu przerobisz na liniowe)

wuodi

jesli jestes hansem :)

Rogal

@hansu: No wiesz, jakby to powiedzieć... Jak mi czegoś nie podadzą na tacy to muszę myśleć... a myślenie jest trudne i boli.

hansu

wuodi

dobra to moze zamiast piedol jakies pomysly na zrobienie tego zadania

ostoj

a gdzies jest wymog ze musi byc liniowka? bo w tresci zadania tego nie widze

hansu

Wszystko bedzie powiedziane na cwiczeniach, cierpliwosci, panowie ;)

@Ostoj: Moze nigdzie nie jest napisane, ale w zadaniu A z ASD1 tez nie bylo napisane jaka ma byc, a i tak wszyscy wiedzieli ;)

Madras

Rogal

@Ostoj: To przeczytaj treść zadania jeszcze raz :D

A pamięciowo faktycznie jest O(mn).

Skrobocik

wuodi

bardzo pomocne a nie mozna uzywac do czytania cin i do pisania cout ??

pawell

to chyba za wolne bedzie;] przynajmniej tak slyszalem....

Rogal

@Skrobocik: A ja po Potyczkach Algorytmicznych nie mam zaufania do takiej metody, z tego względu, że %s zczytuje ciąg znaków jako stringa, czyli dostawia na końcu tablicy dodatkowy znak (bodajże o kodzie 0). A to ma z koleji tą prostą konsekwencję, że jeśli masz tablicę char o rozmiarze 1000 i zczytasz do niej 1000 znaków to znak końca linii się w tej tablicy nie zmieści i zostanie zapisany w pamięci tuż za nią. Może się zdarzyć, że akurat nie będzie tam nic ważnego :D Ale może się też zdarzyć, że będzie tam jakaś kluczowa dla programu zmienna, która nagle nie wiadomo czemu zmienia swą wartość na 0 :D

Więc jeśli ktoś chce koniecznie tego używać to dla bezpieczeństwa radzę pamiętać o używaniu tablic o 1 większych niż wynika to z treścia zadania, co by znak końca również się w nich zmieścił :wink:

nathaniel

... albo wczytywac znaki do tablicy zaczynajac od indeksu t[0], czyli tak jak robi to kazdy szanujacy sie programista :)

Rogal

@Nathaniel: Nie no to jest akurat oczywiste :D Co nie zmienia faktu, że jak zrobisz tablicę na 1000 znaków (indeksy od 0 do 999), a zapiszesz do niej 1001 (1000 znaczących, które chcesz i wiesz że tam są + znak końca o którym możesz nie wiedzieć) to tablica się przepełni, a efekty tego mogą być zupełnie nieoczekiwane.

wuodi

macie jakies duze testy?
ja wczytac z pliku liczbe zestawow i kolejne stringi a potem wypisac wyniki do pliku ??

wuodi

czy ktos moglby mi looknac w kod i znalezc blad ktory powoduje u mnie ans ?? 8)

Rogal

Wyślij mi ten kod na prive'a

wuodi

wyslalem

Rogal

nie dostałem

Pandunia · Gość

[deleted]

hansu

O zesz, to nie ja to pisalem i nawet tego nie czytalem w zyciu :P. Ale juz poprawilem :) Cialo smasa bedzie wystawione w kostnicy jutro 16-20, pogrzeb w okolicach srody...

wuodi

heh juz dziala brak () spowodowal nieokreslone zachowania w niektorych przypadkach
u mnie bylo X[j]= Y[j] >= X[j+1] ? Y[j] : X[j+1];
a jak dodalem nawias X[j]=(Y[j] >= X[j+1] ? Y[j] : X[j+1]);
jest OK.
Dzieki Rogal