Forum Informatyka UJ forum Strona Główna Informatyka UJ forum
Rocznik 2005 - czyli najlepsze forum w sieci
 
 FAQFAQ   SzukajSzukaj   UżytkownicyUżytkownicy   GrupyGrupy   GalerieGalerie   RejestracjaRejestracja 
 ProfilProfil   Zaloguj się, by sprawdzić wiadomościZaloguj się, by sprawdzić wiadomości   ZalogujZaloguj 

Zadanie A - Największy wspólny podciąg
Idź do strony 1, 2  Następny
 
Napisz nowy temat   Odpowiedz do tematu    Forum Informatyka UJ forum Strona Główna -> Archiwum / 1 rok / 2 i 3 semestr - Algorytmy i Struktury Danych
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Spectro
Mistrz grilla



Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów

Skąd: Kurdwanów

PostWysłany: Śro 22:39, 04 Paź 2006    Temat postu: Zadanie A - Największy wspólny podciąg

[link widoczny dla zalogowanych]

Klasyk z Cormena.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Rogal
Zjeb z kaszanką



Dołączył: 13 Mar 2006
Posty: 1745
Przeczytał: 0 tematów

Skąd: koło podbiegunowe

PostWysłany: Czw 8:49, 05 Paź 2006    Temat postu:

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
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
hansu
Nieomylny Admin



Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów

Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?

PostWysłany: Czw 12:29, 05 Paź 2006    Temat postu:

No z tymze to rozkminianie samemu nalezy do takich raczej prostych i intuicyjnych (tzn jak znasz O(mn) to bez problemu przerobisz na liniowe)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
wuodi
pijak



Dołączył: 10 Lis 2005
Posty: 140
Przeczytał: 0 tematów


PostWysłany: Czw 16:23, 05 Paź 2006    Temat postu:

jesli jestes hansem :)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Rogal
Zjeb z kaszanką



Dołączył: 13 Mar 2006
Posty: 1745
Przeczytał: 0 tematów

Skąd: koło podbiegunowe

PostWysłany: Czw 17:08, 05 Paź 2006    Temat postu:

@hansu: No wiesz, jakby to powiedzieć... Jak mi czegoś nie podadzą na tacy to muszę myśleć... a myślenie jest trudne i boli.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
hansu
Nieomylny Admin



Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów

Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?

PostWysłany: Czw 20:12, 05 Paź 2006    Temat postu:

wuodi napisał:
jesli jestes hansem :)

jestem, a co? :P

Rogal napisał:
@hansu:(...)


Aghhhhrrr!!! W tym przedszkolu rozrozniamy literki ;)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
wuodi
pijak



Dołączył: 10 Lis 2005
Posty: 140
Przeczytał: 0 tematów


PostWysłany: Czw 23:32, 05 Paź 2006    Temat postu:

dobra to moze zamiast piedol jakies pomysly na zrobienie tego zadania
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
ostoj
Przewijak Tasmy



Dołączył: 08 Lis 2005
Posty: 883
Przeczytał: 0 tematów

Skąd: Tychy

PostWysłany: Czw 23:35, 05 Paź 2006    Temat postu:

a gdzies jest wymog ze musi byc liniowka? bo w tresci zadania tego nie widze
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
hansu
Nieomylny Admin



Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów

Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?

PostWysłany: Pią 0:45, 06 Paź 2006    Temat postu:

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 ;)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Madras
Omylny Admin



Dołączył: 09 Lis 2005
Posty: 2021
Przeczytał: 0 tematów

Skąd: Z Pokoju :]

PostWysłany: Pią 8:48, 06 Paź 2006    Temat postu:

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

Bo pamięciowo tablica 30kx30k nie przejdzie. Natomiast złożoność czasowa tego programu powinna być równa O(n^2).
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Rogal
Zjeb z kaszanką



Dołączył: 13 Mar 2006
Posty: 1745
Przeczytał: 0 tematów

Skąd: koło podbiegunowe

PostWysłany: Pią 14:41, 06 Paź 2006    Temat postu:

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

A pamięciowo faktycznie jest O(mn).
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Skrobocik
[SKROBORANGA]



Dołączył: 29 Lis 2005
Posty: 2958
Przeczytał: 0 tematów

Skąd: Skarżysko , Kraków

PostWysłany: Sob 10:36, 07 Paź 2006    Temat postu:

Rogal w topicu o zadaniu B napisał:
Słyszałem, że wiele osób ma problemy z wejściem / wyjściem w C++. Aby nieco pomóc zamieszczam funkcję read() mojego autorstwa :D
Kod:
int read(char *tab) {
    int res=0;
    char c;
    do {
        scanf("%c",&c);
    } while(!(c>='0'&&c<='9') && !(c>='a'&&c<='z') && !(c>='A'&&c<='Z'));
    do {
        tab[res++] = c;
        scanf("%c",&c); 
    } while((c>='0'&&c<='9') || (c>='a'&&c<='z') || (c>='A'&&c<='Z'));
    return res;
}

Funkcja pobiera jako parametr tablicę char, zwraca ilość zczytanych znaków.


Do tego zadania polecam troszkę łatwiejsze implementacyjnie wczytywanie ;)
Najpierw zainkludować header do łańcuchów znaków:
Kod:
#include <string.h>

Potem w głównej pętli wczytującej daje się tylko:
Kod:
scanf( "%s %s" , pierwszyCiag , drugiCiag );

i bezproblemowo wczyta te dwa stringi ;)
Jeśli potrzebujemy ich długości, to wystarczy:
Kod:
int dlugoscPierwszego = strlen( pierwszyCiag );


Miło, lekko i przyjemnie ;)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
wuodi
pijak



Dołączył: 10 Lis 2005
Posty: 140
Przeczytał: 0 tematów


PostWysłany: Sob 11:48, 07 Paź 2006    Temat postu:

bardzo pomocne a nie mozna uzywac do czytania cin i do pisania cout ??
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
pawell
alkoholik



Dołączył: 19 Gru 2005
Posty: 498
Przeczytał: 0 tematów


PostWysłany: Sob 11:51, 07 Paź 2006    Temat postu:

to chyba za wolne bedzie;] przynajmniej tak slyszalem....
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Rogal
Zjeb z kaszanką



Dołączył: 13 Mar 2006
Posty: 1745
Przeczytał: 0 tematów

Skąd: koło podbiegunowe

PostWysłany: Sob 12:03, 07 Paź 2006    Temat postu:

@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:
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
nathaniel
pijak



Dołączył: 25 Paź 2005
Posty: 229
Przeczytał: 0 tematów

Skąd: Bielsko-Biała

PostWysłany: Sob 17:51, 07 Paź 2006    Temat postu:

... albo wczytywac znaki do tablicy zaczynajac od indeksu t[0], czyli tak jak robi to kazdy szanujacy sie programista :)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Rogal
Zjeb z kaszanką



Dołączył: 13 Mar 2006
Posty: 1745
Przeczytał: 0 tematów

Skąd: koło podbiegunowe

PostWysłany: Sob 19:45, 07 Paź 2006    Temat postu:

@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.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
wuodi
pijak



Dołączył: 10 Lis 2005
Posty: 140
Przeczytał: 0 tematów


PostWysłany: Sob 20:32, 07 Paź 2006    Temat postu:

macie jakies duze testy?
ja wczytac z pliku liczbe zestawow i kolejne stringi a potem wypisac wyniki do pliku ??
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
wuodi
pijak



Dołączył: 10 Lis 2005
Posty: 140
Przeczytał: 0 tematów


PostWysłany: Nie 0:52, 08 Paź 2006    Temat postu:

czy ktos moglby mi looknac w kod i znalezc blad ktory powoduje u mnie ans ?? 8)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Rogal
Zjeb z kaszanką



Dołączył: 13 Mar 2006
Posty: 1745
Przeczytał: 0 tematów

Skąd: koło podbiegunowe

PostWysłany: Nie 9:19, 08 Paź 2006    Temat postu:

Wyślij mi ten kod na prive'a
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
wuodi
pijak



Dołączył: 10 Lis 2005
Posty: 140
Przeczytał: 0 tematów


PostWysłany: Nie 10:58, 08 Paź 2006    Temat postu:

wyslalem
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Rogal
Zjeb z kaszanką



Dołączył: 13 Mar 2006
Posty: 1745
Przeczytał: 0 tematów

Skąd: koło podbiegunowe

PostWysłany: Nie 12:49, 08 Paź 2006    Temat postu:

nie dostałem
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Pandunia
Gość






PostWysłany: Nie 13:16, 08 Paź 2006    Temat postu:

[deleted]

Ostatnio zmieniony przez Pandunia dnia Pią 6:29, 10 Lis 2006, w całości zmieniany 1 raz
Powrót do góry
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
hansu
Nieomylny Admin



Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów

Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?

PostWysłany: Nie 14:10, 08 Paź 2006    Temat postu:

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...
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
wuodi
pijak



Dołączył: 10 Lis 2005
Posty: 140
Przeczytał: 0 tematów


PostWysłany: Nie 14:37, 08 Paź 2006    Temat postu:

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
Powrót do góry
Zobacz profil autora
Wyświetl posty z ostatnich:   
Napisz nowy temat   Odpowiedz do tematu    Forum Informatyka UJ forum Strona Główna -> Archiwum / 1 rok / 2 i 3 semestr - Algorytmy i Struktury Danych Wszystkie czasy w strefie EET (Europa)
Idź do strony 1, 2  Następny
Strona 1 z 2

 
Skocz do:  
Nie możesz pisać nowych tematów
Nie możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach

fora.pl - załóż własne forum dyskusyjne za darmo
Powered by phpBB © 2001, 2005 phpBB Group
Regulamin