Ĺadny brzuch
Oprocz spoja robie zadanka na specialnej testerce dla uczniow mojej szkoly... jedno z zadan brzmi:
NWPR (1e 05/06 nr 9)
Pytamy o najdłuższy wspólny podciąg niemalejący dwóch ciagów.
Napisz program, który dla podanych dwóch ciągów liczb naturalnych obliczy długość ich najdłuższego wspólnego podciągu niemalejącego.
Wejście
W pierwszej linii wejścia znajduje się liczba naturalna 1 <= n <= 600 oznaczająca długości obu ciągów. W każdej z dwóch następnych linii znajduje się opis jednego z ciągów w postaci n liczb naturalnych nie większych od 1 000 000, oddzielonych spacjami - kolejnych wyrazów rozważanego ciągu.
Wyjście
Wyjście powinno zawierać dokładnie jedną liczbę naturalną - długość najdłuższego wspólnego podciągu niemalejącego podanych dwóch ciągów.
Przykład
Dla danych wejściowych 6
4 5 1 7 1 9
1 1 5 1 9 8
poprawną odpowiedzią jest 3
Niby proste, kilka sekund szukania na goglach i juz mam algorytm, nastepnia minuta to implementacja i gotowe... Tylko ze dla przykladowych danych moj progs wyswietla 4... i uwazam ze slusznie to robi, poniewaz ten podciag zeczywiscie ma dlugosc 4, bo jest on taki: 1 1 5 9 (jest on przeciez niemalejacy). Wiec dlaczego taki nie moze byc (dodam ze jezeli powiedzialem cos glupiego to moze byc to troche usprawiedliwione gdyz jeszcze nie bralismy ciagow)?
w ciągu jest istotna kolejność, więc
a = 1 1 5 9
nie jest podciągiem ciągu
x = 4 5 1 7 1 9
ale jest podciągiem ciągu np.
y = 1 4 1 7 5 9
mimo że x i y zawierają takie same elementy
(podciąg powstaje przez pominięcie dowolnej ilości elementów ciągu, bez ingerencji w kolejność pozostałych)
To w takim razie jakim cudem moze ten ciag miec dlugosc 3? Tzn moglby miec gdyby nie bylo napisane "niemalejacy"... bo wtedy mamy 5 1 9 i wtedy jest to rzeczywiscie najdluzszy wspolny podciag... ale po dodaniu niemalejacy zostaje nam opcja 5 9...
zapewniam Cię, że może
» Kliknij aby pokazać/ukryć spoiler... «
Oto mój problem:
Napisz program, który wylosuje 100 liczb całkowitych i wypełni nimi tablicę. Liczby mają być wylosowane z zakresu od 2 do 20000. Następnie program wyświetli najdłuższy podciąg rosnący w tablicy.
Proszę o Pomoc.
Napisz program, który wylosuje 100 liczb całkowitych i wypełni nimi tablicę. Liczby mają być wylosowane z zakresu od 2 do 20000. Następnie program wyświetli najdłuższy podciąg rosnący w tablicy.
A co to ma wspólnego z tym tematem?
I z czym konkretnie nie możesz sobie poradzić? Ban na Google?
zanotowane.pl doc.pisz.pl pdf.pisz.pl zsf.htw.pl
NWPR (1e 05/06 nr 9)
Pytamy o najdłuższy wspólny podciąg niemalejący dwóch ciagów.
Napisz program, który dla podanych dwóch ciągów liczb naturalnych obliczy długość ich najdłuższego wspólnego podciągu niemalejącego.
Wejście
W pierwszej linii wejścia znajduje się liczba naturalna 1 <= n <= 600 oznaczająca długości obu ciągów. W każdej z dwóch następnych linii znajduje się opis jednego z ciągów w postaci n liczb naturalnych nie większych od 1 000 000, oddzielonych spacjami - kolejnych wyrazów rozważanego ciągu.
Wyjście
Wyjście powinno zawierać dokładnie jedną liczbę naturalną - długość najdłuższego wspólnego podciągu niemalejącego podanych dwóch ciągów.
Przykład
Dla danych wejściowych 6
4 5 1 7 1 9
1 1 5 1 9 8
poprawną odpowiedzią jest 3
Niby proste, kilka sekund szukania na goglach i juz mam algorytm, nastepnia minuta to implementacja i gotowe... Tylko ze dla przykladowych danych moj progs wyswietla 4... i uwazam ze slusznie to robi, poniewaz ten podciag zeczywiscie ma dlugosc 4, bo jest on taki: 1 1 5 9 (jest on przeciez niemalejacy). Wiec dlaczego taki nie moze byc (dodam ze jezeli powiedzialem cos glupiego to moze byc to troche usprawiedliwione gdyz jeszcze nie bralismy ciagow)?
w ciągu jest istotna kolejność, więc
a = 1 1 5 9
nie jest podciągiem ciągu
x = 4 5 1 7 1 9
ale jest podciągiem ciągu np.
y = 1 4 1 7 5 9
mimo że x i y zawierają takie same elementy
(podciąg powstaje przez pominięcie dowolnej ilości elementów ciągu, bez ingerencji w kolejność pozostałych)
To w takim razie jakim cudem moze ten ciag miec dlugosc 3? Tzn moglby miec gdyby nie bylo napisane "niemalejacy"... bo wtedy mamy 5 1 9 i wtedy jest to rzeczywiscie najdluzszy wspolny podciag... ale po dodaniu niemalejacy zostaje nam opcja 5 9...
zapewniam Cię, że może
» Kliknij aby pokazać/ukryć spoiler... «
Oto mój problem:
Napisz program, który wylosuje 100 liczb całkowitych i wypełni nimi tablicę. Liczby mają być wylosowane z zakresu od 2 do 20000. Następnie program wyświetli najdłuższy podciąg rosnący w tablicy.
Proszę o Pomoc.
Napisz program, który wylosuje 100 liczb całkowitych i wypełni nimi tablicę. Liczby mają być wylosowane z zakresu od 2 do 20000. Następnie program wyświetli najdłuższy podciąg rosnący w tablicy.
A co to ma wspólnego z tym tematem?
I z czym konkretnie nie możesz sobie poradzić? Ban na Google?