Teoria i przykłady do tego działu są właśnie opracowywane. Struktura działu jest już gotowa — poniżej znajdziesz dostępne zadania, a nauczyciel może dodać kolejne z panelu.
W pliku tekstowym pary.txt znajduje się 500 par słów złożonych z liter alfabetu angielskiego *a, b, ...*, z. Każda para słów jest zapisana w osobnym wierszu. Słowa w wierszu są oddzielone pojedynczym odstępem, a długość każdego z nich nie przekracza 50 znaków. Pierwszych pięć wierszy pliku pary.txt zawiera następujące pary słów: bcba babb abaa ccc bcb abbba bca cdd aadc ddcdccaba Napisz program (lub kilka programów), który(-e) znajdzie(-a) i da(dzą) odpowiedzi do podanych zadań. Odpowiedzi do poszczególnych zadań zapisz w pliku wyniki3.txt. Każdą odpowiedź poprzedź numerem oznaczającym zadanie. Do dyspozycji masz plik pary_przyklad.txt, który zawiera 500 par słów. Odpowiedzi dla tego pliku podano w treściach zadań. Możesz sprawdzać na nim działanie swojego programu. Niech f(s) oznacza sumę kodów ASCII znaków występujących w słowie s. Podaj parę słów s1,s2 występujących w jednym wierszu pliku pary.txt, dla których wartość ∣f(s1)−f(s2)∣ (wartość bezwzględna różnicy sum kodów ASCII) jest największa, oraz podaj tę wartość. Jest tylko jedna taka para słów w pliku. Przykład: Dla pary słów *oko i pies*, mamy następujące wartości f(oko)=111+107+111=329 f(pies)=112+105+101+115=433 oraz ∣f(oko)−f(pies)∣=104. Dla pliku pary_przyklad.txt poprawną odpowiedzią jest eddcd eedcddcceeecedcc 1403 Uwaga: Pamiętaj, że Twój program musi ostatecznie działać na pliku pary.txt. Do oceny oddajesz plik wyniki3.txt i kody źródłowe programów; brak kodów jest równoznaczny z brakiem rozwiązania.
Odpowiedź do samodzielnego porównania z pełnym rozwiązaniem; bez automatycznej oceny.
Wskazówka
Użyj ord() i porównaj bezwzględną różnicę sum kodów.
Rozwiązanie krok po kroku
1Wczytujemy 500 par z pary.txt.
2Dla każdego słowa sumujemy ord(znak).
3Obliczamy wartość bezwzględną różnicy i zapamiętujemy parę z największą wartością.
W pliku tekstowym pary.txt znajduje się 500 par słów złożonych z liter alfabetu angielskiego *a, b, ...*, z. Każda para słów jest zapisana w osobnym wierszu. Słowa w wierszu są oddzielone pojedynczym odstępem, a długość każdego z nich nie przekracza 50 znaków. Pierwszych pięć wierszy pliku pary.txt zawiera następujące pary słów: bcba babb abaa ccc bcb abbba bca cdd aadc ddcdccaba Napisz program (lub kilka programów), który(-e) znajdzie(-a) i da(dzą) odpowiedzi do podanych zadań. Odpowiedzi do poszczególnych zadań zapisz w pliku wyniki3.txt. Każdą odpowiedź poprzedź numerem oznaczającym zadanie. Do dyspozycji masz plik pary_przyklad.txt, który zawiera 500 par słów. Odpowiedzi dla tego pliku podano w treściach zadań. Możesz sprawdzać na nim działanie swojego programu. Wspólną liczbę wystąpień litery x w słowach s1,s2 oznaczymy przez W(x,s1,s2) i definiujemy jako W(x,s1,s2)=minimum(d(x,s1),d(x,s2)) gdzie d(x,s) oznacza liczbę wystąpień litery x w słowie s. Podaj parę słów występujących w jednym wierszu w pliku pary.txt, dla której suma wspólnych wystąpień wszystkich liter jest największa, oraz podaj tę sumę. Jest jedna taka para. Przykład: Dla poniższej pary słów wpisano wspólną liczbę wystąpień wszystkich liter (wyniki wpisano w kolejności alfabetycznej): adabbcddeaadabbbccdc→a: 2, b: 2, c: 1, d: 2, e: 0 Suma wspólnych wystąpień wszystkich liter dla pary z tego przykładu wynosi: 2+2+1+2=7. Dla pliku pary_przyklad.txt poprawną odpowiedzią jest ccccdcedddddecdeccdcdddecc 10 Uwaga: Pamiętaj, że Twój program musi ostatecznie działać na pliku pary.txt. Do oceny oddajesz plik wyniki3.txt i kody źródłowe programów; brak kodów jest równoznaczny z brakiem rozwiązania.
Odpowiedź do samodzielnego porównania z pełnym rozwiązaniem; bez automatycznej oceny.
Wskazówka
Zlicz litery w obu słowach i sumuj minima liczników.
Rozwiązanie krok po kroku
1Dla każdego słowa tworzymy liczniki 26 liter.
2Dla każdej litery dodajemy minimum jej dwóch liczników.
3Porównujemy sumy i wybieramy jedyną parę z największą sumą.
W pliku tekstowym pary.txt znajduje się 500 par słów złożonych z liter alfabetu angielskiego *a, b, ...*, z. Każda para słów jest zapisana w osobnym wierszu. Słowa w wierszu są oddzielone pojedynczym odstępem, a długość każdego z nich nie przekracza 50 znaków. Pierwszych pięć wierszy pliku pary.txt zawiera następujące pary słów: bcba babb abaa ccc bcb abbba bca cdd aadc ddcdccaba Napisz program (lub kilka programów), który(-e) znajdzie(-a) i da(dzą) odpowiedzi do podanych zadań. Odpowiedzi do poszczególnych zadań zapisz w pliku wyniki3.txt. Każdą odpowiedź poprzedź numerem oznaczającym zadanie. Do dyspozycji masz plik pary_przyklad.txt, który zawiera 500 par słów. Odpowiedzi dla tego pliku podano w treściach zadań. Możesz sprawdzać na nim działanie swojego programu. *Prefiksosufiksem* pary słów s1, s2 nazywamy słowo, które jest początkiem s1 (czyli s1 zaczyna się tym słowem) oraz końcem s2 (czyli s2 kończy się tym słowem) lub początkiem s2 oraz końcem s1. Podaj wszystkie pary słów z pliku pary.txt, dla których najdłuższy prefiksosufiks ma co najmniej 5 liter. Dla każdej podanej w odpowiedzi pary słów podaj długość najdłuższego prefiksosufiksu tej pary. Przykłady: Dla pary aabbbcacaacaab mamy następujące prefiksosufiksy: * aab – początek pierwszego słowa i koniec drugiego * ca – początek drugiego słowa i koniec pierwszego. Najdłuższy prefiksosufiks ma długość 3, zatem para tych słów nie spełnia wymaganych warunków. Dla pary abbaabaabaabaabba mamy następujące prefiksosufiksy: * a – początek pierwszego słowa i koniec drugiego * abba – początek pierwszego słowa i koniec drugiego * baa – początek drugiego słowa i koniec pierwszego * baabaa – początek drugiego słowa i koniec pierwszego. Najdłuższy prefiksosufiks ma długość 6, zatem para spełnia warunki wymagane w zadaniu. Dla pliku pary_przyklad.txt poprawną odpowiedzią jest ececdddeeddddeedd 6 (najdłuższy prefiksosufiks ma długość 6) Uwaga: Pamiętaj, że Twój program musi ostatecznie działać na pliku pary.txt. Do oceny oddajesz plik wyniki3.txt i kody źródłowe programów; brak kodów jest równoznaczny z brakiem rozwiązania.
Odpowiedź do samodzielnego porównania z pełnym rozwiązaniem; bez automatycznej oceny.
Wskazówka
Sprawdź oba kierunki: początek pierwszego i koniec drugiego oraz odwrotnie.
Rozwiązanie krok po kroku
1Dla każdej pary badamy długości od min(len(s1),len(s2)) do 1.
2Sprawdzamy s1[:k]==s2[-k:] lub s2[:k]==s1[-k:].
3Pierwsza pasująca długość jest największa; wypisujemy parę, jeśli wynosi co najmniej 5.
W korporacji pracuje *n* osób, które na potrzeby zadania ponumerujemy liczbami 1, 2, ..., *n*. Pracownik numer 1 jest prezesem korporacji, a każdy z pozostałych pracowników ma dokładnie jednego bezpośredniego przełożonego. Numer bezpośredniego przełożonego pracownika *x* jest zawsze mniejszy od numeru tego pracownika. Prezes korporacji nie ma żadnego przełożonego. Przełożonym pracownika jest jego bezpośredni przełożony i każdy przełożony tego bezpośredniego przełożonego. Jeśli *x* jest (bezpośrednim) przełożonym *y*, to powiemy, że *y* jest (bezpośrednim) podwładnym *x*. Prezes jest przełożonym każdego pracownika. Dany jest plik korpo.txt zawierający *n* = 50 000 liczb, który opisuje strukturę korporacji. W pierwszym wierszu jest liczba 0 oznaczająca brak przełożonego dla prezesa korporacji, który ma numer 1. W *i*-tym (2 ≤ *i* ≤ 50 000) wierszu pliku jest numer pracownika, który jest bezpośrednim przełożonym pracownika *i*. Przykład 2. Zapis w pliku dla przykładowej korporacji (Rysunek 1) miałby postać: 0 1 2 1 2 2 3 4 Napisz program(-y), który(-e) znajdzie(-ą) i da(dzą) odpowiedzi do podanych zadań. Odpowiedzi zapisz w pliku wyniki4.txt, a każdą z nich poprzedź numerem odpowiedniego zadania. Do Twojej dyspozycji jest również plik korpo_przyklad.txt, w identycznym formacie, w którym bezpośrednim przełożonym pracowników 2 i 3 jest pracownik 1, a wszystkich innych – pracownik 3. Odpowiedzi dla danych z tego pliku są podane pod treściami zadań. Uwaga: Pamiętaj, że Twój program musi ostatecznie działać dla pliku korpo.txt. Na podstawie danych zapisanych w pliku korpo.txt podaj, ilu pracowników nie jest przełożonym żadnego pracownika. Dla danych z pliku korpo_przyklad.txt poprawna odpowiedź to: 49 998 Do oceny oddajesz plik wyniki4.txt oraz kody źródłowe programów; brak kodów jest równoznaczny z brakiem rozwiązania.
Odpowiedź do samodzielnego porównania z pełnym rozwiązaniem; bez automatycznej oceny.
Wskazówka
Policz pracowników, których numer nie występuje jako przełożony.
Rozwiązanie krok po kroku
1Wczytujemy korpo.txt i tworzymy liczniki bezpośrednich podwładnych.
2Pomijamy zero w pierwszym wierszu.
3Zliczamy pracowników, których licznik pozostał równy zero.
W korporacji pracuje *n* osób, które na potrzeby zadania ponumerujemy liczbami 1, 2, ..., *n*. Pracownik numer 1 jest prezesem korporacji, a każdy z pozostałych pracowników ma dokładnie jednego bezpośredniego przełożonego. Numer bezpośredniego przełożonego pracownika *x* jest zawsze mniejszy od numeru tego pracownika. Prezes korporacji nie ma żadnego przełożonego. Przełożonym pracownika jest jego bezpośredni przełożony i każdy przełożony tego bezpośredniego przełożonego. Jeśli *x* jest (bezpośrednim) przełożonym *y*, to powiemy, że *y* jest (bezpośrednim) podwładnym *x*. Prezes jest przełożonym każdego pracownika. Dany jest plik korpo.txt zawierający *n* = 50 000 liczb, który opisuje strukturę korporacji. W pierwszym wierszu jest liczba 0 oznaczająca brak przełożonego dla prezesa korporacji, który ma numer 1. W *i*-tym (2 ≤ *i* ≤ 50 000) wierszu pliku jest numer pracownika, który jest bezpośrednim przełożonym pracownika *i*. Przykład 2. Zapis w pliku dla przykładowej korporacji (Rysunek 1) miałby postać: 0 1 2 1 2 2 3 4 Napisz program(-y), który(-e) znajdzie(-ą) i da(dzą) odpowiedzi do podanych zadań. Odpowiedzi zapisz w pliku wyniki4.txt, a każdą z nich poprzedź numerem odpowiedniego zadania. Do Twojej dyspozycji jest również plik korpo_przyklad.txt, w identycznym formacie, w którym bezpośrednim przełożonym pracowników 2 i 3 jest pracownik 1, a wszystkich innych – pracownik 3. Odpowiedzi dla danych z tego pliku są podane pod treściami zadań. Uwaga: Pamiętaj, że Twój program musi ostatecznie działać dla pliku korpo.txt. Podaj, który pracownik spośród zapisanych w pliku korpo.txt ma najwięcej bezpośrednich podwładnych. Podaj numer tego pracownika oraz liczbę jego bezpośrednich podwładnych. Dla danych z pliku korpo_przyklad.txt poprawna odpowiedź to: 3 49 997 (pracownik numer 3 ma 49 997 bezpośrednich podwładnych). Do oceny oddajesz plik wyniki4.txt oraz kody źródłowe programów; brak kodów jest równoznaczny z brakiem rozwiązania.
Odpowiedź do samodzielnego porównania z pełnym rozwiązaniem; bez automatycznej oceny.
Wskazówka
Znajdź największy licznik bezpośrednich podwładnych.
Rozwiązanie krok po kroku
1Dla każdej osoby od 2 do 50000 zwiększamy licznik jej przełożonego.
2Wybieramy największy licznik i numer osoby, do której należy.
W korporacji pracuje *n* osób, które na potrzeby zadania ponumerujemy liczbami 1, 2, ..., *n*. Pracownik numer 1 jest prezesem korporacji, a każdy z pozostałych pracowników ma dokładnie jednego bezpośredniego przełożonego. Numer bezpośredniego przełożonego pracownika *x* jest zawsze mniejszy od numeru tego pracownika. Prezes korporacji nie ma żadnego przełożonego. Przełożonym pracownika jest jego bezpośredni przełożony i każdy przełożony tego bezpośredniego przełożonego. Jeśli *x* jest (bezpośrednim) przełożonym *y*, to powiemy, że *y* jest (bezpośrednim) podwładnym *x*. Prezes jest przełożonym każdego pracownika. Dany jest plik korpo.txt zawierający *n* = 50 000 liczb, który opisuje strukturę korporacji. W pierwszym wierszu jest liczba 0 oznaczająca brak przełożonego dla prezesa korporacji, który ma numer 1. W *i*-tym (2 ≤ *i* ≤ 50 000) wierszu pliku jest numer pracownika, który jest bezpośrednim przełożonym pracownika *i*. Przykład 2. Zapis w pliku dla przykładowej korporacji (Rysunek 1) miałby postać: 0 1 2 1 2 2 3 4 Napisz program(-y), który(-e) znajdzie(-ą) i da(dzą) odpowiedzi do podanych zadań. Odpowiedzi zapisz w pliku wyniki4.txt, a każdą z nich poprzedź numerem odpowiedniego zadania. Do Twojej dyspozycji jest również plik korpo_przyklad.txt, w identycznym formacie, w którym bezpośrednim przełożonym pracowników 2 i 3 jest pracownik 1, a wszystkich innych – pracownik 3. Odpowiedzi dla danych z tego pliku są podane pod treściami zadań. Uwaga: Pamiętaj, że Twój program musi ostatecznie działać dla pliku korpo.txt. Policz, ilu najwięcej przełożonych ma jeden pracownik. Podaj tę liczbę oraz podaj, ilu pracowników ma taką liczbę przełożonych. Dla danych z pliku korpo_przyklad.txt poprawna odpowiedź to: 2 49 997 (największa liczba przełożonych: 2, liczba pracowników, którzy mają 2 przełożonych: 49 997). Do oceny oddajesz plik wyniki4.txt oraz kody źródłowe programów; brak kodów jest równoznaczny z brakiem rozwiązania.
Odpowiedź do samodzielnego porównania z pełnym rozwiązaniem; bez automatycznej oceny.
Wskazówka
Numer przełożonego jest mniejszy: obliczaj głębokości w kolejności numerów.
Rozwiązanie krok po kroku
1Prezes ma głębokość 0.
2Dla każdej kolejnej osoby: głębokość[i]=głębokość[przełożony[i]]+1.
3Znajdujemy największą głębokość i liczbę jej wystąpień.