beatagmys@o2.pl pgmys@o2.pl

Informatyka rozszerzona

  1. Informatyka rozszerzona
  2. Klasa II

Szukamy różnych podciągów


Cele ogólne
Uczeń:
  • planuje kolejne kroki rozwiązywania problemu, z uwzględnieniem podstawowych etapów myślenia komputacyjnego (określenie problemu, definicja modeli i pojęć, znalezienie rozwiązania, zaprogramowanie i testowanie rozwiązania) (I.1),
  • porównuje działanie różnych algorytmów dla wybranego problemu, analizuje algorytmy na podstawie ich gotowych implementacji (I.4),
  • sprawdza poprawność działania algorytmów dla przykładowych danych (I.5),
  • projektuje i programuje rozwiązania problemów z różnych dziedzin, stosuje przy tym: instrukcje wejścia/wyjścia, wyrażenia arytmetyczne i logiczne, instrukcje warunkowe, instrukcje iteracyjne, funkcje z parametrami i bez parametrów, testuje poprawność programów dla różnych danych; w szczególności programuje algorytmy z punktu 1.2 (II.1),
  • w zależności od problemu rozwiązuje go, stosując metodę wstępującą lub zstępującą (RI.1),
  • objaśnia dobrany algorytm, uzasadnia poprawność rozwiązania na wybranych przykładach danych i ocenia jego efektywność (RI.3),
  • ilustruje i wyjaśnia rolę pojęć, obiektów i operacji matematycznych w projektowaniu rozwiązań problemów informatycznych i z innych dziedzin, posługuje się pojęciem logarytmu (RI.4),
  • dyskutuje na temat roli myślenia komputacyjnego i jego metod, takich jak: abstrakcja, reprezentacja danych, dekompozycja problemu, redukcja, myślenie rekurencyjne, podejście heurystyczne w rozwiązywaniu problemów z różnych dziedzin (RI.8),
  • stosuje zasady programowania strukturalnego i obiektowego w rozwiązywaniu problemów (RII.2),
  • sprawnie posługuje się zintegrowanym środowiskiem programistycznym przy pisaniu, uruchamianiu i testowaniu programów (RII.3),
  • wykorzystuje znane sobie algorytmy przy rozwiązywaniu i programowaniu rozwiązań następujących problemów: znajdowania w ciągu podciągów o różnorodnych własnościach, np. najdłuższego spójnego podciągu niemalejącego, spójnego podciągu o największej sumie (RI+II.2c).
  • definiuje pojęcia: podciąg, podciąg spójny, podciąg niemalejący, liczba trójkątna.
    •  
  • wyjaśnia, na czym polega poszukiwanie podciągów w ciągu
  • znajduje w ciągu podciąg o maksymalnej sumie elementów.
  • analizuje złożoność czasową algorytmów znajdowania maksymalnej sumy podciągu.
  • ocenia, czy dany podciąg jest podciągiem spójnym.
  • tworzy i wywołuje w języku C++ funkcje szukające podciągu o maksymalnej sumie elementów
  • Przydatne narzędzia/oprogramowanie
  • komputer z zainstalowanym środowiskiem Code::Blocks http://www.codeblocks.org/downloads/binaries
  • Kodowaniew online:
    • Zapoznaj się tekstem w podręczniku strony od 182 do 189 ze szczególnym uwzględnieniem Podsumowania.

    Najdłuższy spójny podciąg niemalejący 

                Specyfikacja
            Dane A[0 .. n-1] - tablica n liczb całkowitych
            Wynik: maks_dl  - długość najdłuższego spójnego podciągu niemalejącego w tablicy A (A jest niepuste)

            Algorytm w postaci pseudokodu

            maks_dl = 1;
            akt-dl = 1; 

            dla i = 1 ... n-1 wykonuj
                jeśli  A[i] >= A[i-1] to
                    akt_dl = akt_dl + 1
                    jeśli akt-dl > maks_dl to maks_dl = akt-dl
                w przeciwnym przypadku akt-dl = 1


    Maksymalna suma podciągu spójnego - sposób 1 

                    Przykład: 23, -49, 6, 23, 24, -42, 40, 4, -48, 39
	
	
                Specyfikacja
                Dane A[0 .. n-1] - tablica n liczb całkowitych z co najmniej jedną liczbą nieujemną
                Wynik: maks_suma  - maksymalna suma elementó podciągu spójnego w tablicy A

                Algorytm w postaci pseudokodu

                maks_suma = 0
                dla i = 0 ... n-1 wykonuj
                    dla j = 1 ... n-1 wykonuj
                        akt_suma = 0
                        dla k = i ... j wykonuj
                            akt_suma  = akt_suma +A[k]
                        jeśli akt_suma > maks_suma to
                            maks_suma = akt_suma


    Maksymalna suma podciągu spójnego - sposób 2 

                    maks_suma = 0
                dla i = 0 ... n-1 wykonuj
	                akt_suma = 0
		            dla j = 1 ... n-1 wykonuj
			            akt_suma = akt_suma + A[j]				
			            jeśli akt_suma > maks_suma to
			            maks_suma = akt_suma

    Maksymalna suma podciągu spójnego - sposób 3

                    maks_suma = 0
                akt_suma = 0
                dla i = 0 ... n-1 wykonuj
	                jeśli akt_suma +A[i] > 0 to 
		                akt_suma = akt_suma + A[i]
		                jeśli akt_suma > maks_suma to
			                maks_suma = akt_suma
	                    w po zostałych przypadkach 
		                    akt_suma = 0




    Porównanie algorytmów znajdowania masymalnej sumy podciagu






    Ćwiczenie 1



    Napisz program losujący 20 liczb losowych z przedziału od -10 do +10




    Ćwiczenie 2



    Napisz program wypisujący najdłuższy spójny podciąg niemalejący. Wykorzystaj program/funkcję losującą liczby z ćwiczenia 1



    Ćwiczenie 3


    Napisz program wypisujący podciąg spójny o maksymalnej sumie



    Zadania



    1. Napisz program wypisujący najdłuższy spójny podciąg malejący ciągu n liczb całkowitych.
    2. Napisz program, który wypisze najdłuższy spójny podciąg rosnący ciągu n liczb całkowitych, a w przypadku występowania więcej niż jednego najdłuższego podciągu wypisze ostatni znaleziony.
    3. Napisz program, który wypisze najdłuższy spójny podciąg rosnący ciągu n liczb całkowitych, a w przypadku występowania więcej niż jednego najdłuższego podciągu wypisze wszystkie.
    4. Napisz program wypisujący najdłuższy podciąg spójny złożony z liczb całkowitych dodatnich ciągu n liczb całkowitych. Wykorzystaj w nim funkcję losującą tablicę tak, aby występowały w niej zarówno liczby dodatnie, jak i ujemne.
    5. Napisz program znajdujący maksymalną sumę podciągu spójnego ciągu n liczb całkowitych, w którym mogą wystąpić same liczby ujemne. Program napisz tak, żeby przejrzał tablicę co najwyżej dwa razy.
    6. Napisz program wyznaczający w ciągu n liczb całkowitych liczbę podciągów spójnych o podanej (wczytanej) sumie. Program napisz tak, aby wykonywał jak najmniej operacji.
    7. Napisz program wypisujący z ciągu n liczb całkowitych wszystkie podciągi spójne o podanej (wczytanej) sumie. Program napisz tak, aby wykonywał jak najmniej operacji.




    Test wiedzy



    |
    		    Pytanie 1.



    Podsumowanie



  • Podciąg to wybrane wyrazy ciągu zachowujące kolejność występowania.
  • Podciąg spójny to taki podciąg, którego wyrazy w ciągu wyjściowym występują obok siebie.
  • Podciąg niemalejący to taki podciąg, w którym każdy kolejny element jest większy lub równy poprzedniemu.
  • Żeby znaleźć spójny podciąg niemalejący, wystarczy raz przejrzeć elementy ciągu.
  • Algorytmy znajdowania maksymalnej sumy podciągu analizujące wszystkie możliwe sumy podciągów mają złożoność czasową O(n3) lub O(n2).
  • Istnieje algorytm liniowy O(n), który znajduje maksymalną sumę podciągu spójnego.
  • Nie analizuje on wszystkich podciągów. Kiedy suma aktualnie badanego podciągu nie jest dodatnia, rozpoczyna badanie kolejnego podciągu od następnego elementu.
  • Jeśli funkcja ma zwrócić więcej niż jedną wartość typu prostego, warto zastosować przekazanie parametru przez referencję.

    • Najdłuższy spójny podciąg ciągu binarnego

    https://pl.spoj.com/problems/AL_03_02/



    Zadanie 2 - Najdłuższy podciąg różnowartościowy

    https://pl.spoj.com/problems/FR_02_17/



    Zadanie 3 - Długość najdłuższego wspólnego podciągu (podsłowa)

    https://pl.spoj.com/problems/LENLCS/



    Zadanie 4 - Sok jabłkowy

    https://pl.spoj.com/problems/FR_10_09/



    Zadanie 5 - Ciąg arytmetyczny

    https://pl.spoj.com/problems/AL_20_02/





    Zadania
  • W kolejnych wierszach pliku cyfry.txt znajduje się 1000 liczb naturalnych, mniejszych niż 109 (jeden miliard), po jednej liczbie w każdym wierszu.
    Napisz program, który Wypisz wszystkie liczby z pliku p18a.txt, których cyfry tworzą ciąg rosnący.
    Przykład:
    Cyfry liczby 123579 tworzą ciąg rosnący, ponieważ 1<2<3<5<7<9.
    Cyfry liczby 1232 nie tworzą ciągu rosnącego, ponieważ ostatnia cyfra (2) nie jest większa od przedostatniej (3).
    Cyfry liczby 34556 nie tworzą ciągu rosnącego, ponieważ cyfra trzecia (5) i cyfra czwarta (5) są sobie równe.

    • Zadanie - najlepsze sumy


    treść zadania
    dane do zadania
    Odpowiedzi:
    Przykładowe rozwiązania oraz komentarze do wybranych ćwiczeń i zadań
  • Wkrótce