Solutions to exercises and problems from "Introduction to Algorithms", Second Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (in Polish)
Przepisać na rozwiązanie prostsze. Należy zrobić kopię X' oryginalnego ciągu X, posortować X', a następnie wywołać LCS-Length(X,X'). Napisać uzasadnienie, że algorytm jest poprawny. Załóżmy, że W jest LCS ciągów X i X'. Jest on oczywiście podciągiem X i jest niemalejący, bo jest podciągiem ciągu niemalejącego X'. Załóżmy nie-wprost, że NNP ciągu X jest ciąg W' dłuższy od W. Ale W' jest też podciągiem X i jednocześnie jest niemalejący o wyrazach z X, czyli musi stanowić też podciąg X'. Czyli W' jest LCS ciągów X i X', co jest sprzeczne z założeniem.
Jeśli będzie potrzeba używać nazwy procedury, to zmienić ją na LMIS-Length-By-Sorting.
Do wypisania znalezionego rozwiązania można użyć Print-LCS. W implementacji trzeba pamiętać, że oryginalna wersja działała dla znaków, a dla liczb trzeba stosować jakiś separator w funkcji print.
Przepisać na rozwiązanie prostsze. Należy zrobić kopię X' oryginalnego ciągu X, posortować X', a następnie wywołać LCS-Length(X,X'). Napisać uzasadnienie, że algorytm jest poprawny. Załóżmy, że W jest LCS ciągów X i X'. Jest on oczywiście podciągiem X i jest niemalejący, bo jest podciągiem ciągu niemalejącego X'. Załóżmy nie-wprost, że NNP ciągu X jest ciąg W' dłuższy od W. Ale W' jest też podciągiem X i jednocześnie jest niemalejący o wyrazach z X, czyli musi stanowić też podciąg X'. Czyli W' jest LCS ciągów X i X', co jest sprzeczne z założeniem.
Jeśli będzie potrzeba używać nazwy procedury, to zmienić ją na LMIS-Length-By-Sorting.
Do wypisania znalezionego rozwiązania można użyć Print-LCS. W implementacji trzeba pamiętać, że oryginalna wersja działała dla znaków, a dla liczb trzeba stosować jakiś separator w funkcji print.