Strefa wyzwań

Już wiesz

Na czym polega programowanie dynamiczne.
Jak rozpoznać i wyodrębnić w ciągu różne podciągi spełniające określone warunki (np. niemalejące, o największej sumie).

Teraz czas sprawdzić swoją wiedzę i umiejętności w praktyce. Zastosuj poznane metody krok po kroku, aby samodzielnie znaleźć podciągi o wymaganych własnościach w nowych przykładach.

R12AGRLSLCNM8

Ćwiczenie 1

R1MTD61RKN6NB

Ćwiczenie 2

RAA3LLZ9CS54S

Ćwiczenie 3

R61989AAD5RH4

Ćwiczenie 4

Zadanie 1. Giełda bajtocka

Ania jest analitykiem giełdowym. W ostatnim miesiącu zbierała dane dotyczące wzrostów i spadków wartości wskaźnika na lokalnej giełdzie w Bajtocji. W celach statystycznych zamierza sprawdzić, jaki najlepszy możliwy wynik giełda osiągnęła w ciągu następujących po sobie dni. By to zrobić, musi znaleźć w całym badanym okresie ciąg następujących po sobie dni, w których suma wyników była największa. Ania bierze pod uwagę to, że wśród dni może być taki, w którym wartość wskaźnika była ujemna oraz to, że na giełdzie może mieć miejsce bessa, czyli wszystkie wskaźniki będą ujemne. W takiej sytuacji program powinien wypisać jednoelementowy podciąg składający się z największej liczby ujemnej.

Dane zapisane są w pliku giełda.txt. Plik składa się ze $100$ wierszy. Każdy wiersz zawiera liczbę rzeczywistą oznaczającą wzrost lub spadek wartości wskaźnika giełdy w danym dniu miesiąca:

RnhKGi6W9wU54

Przycisk do pobrania pliku TXT z treścią zadania.

Plik TXT o rozmiarze 602.00 B w języku polskim

Napisz program, który dla danych z pliku giełda.txt znajdzie spójny podciąg o maksymalnej sumie, a jego sumę zaokrągloną do dwóch miejsc po przecinku zapisze w pliku wyniki.txt.

Ważne!

Poprzez spójny podciąg o maksymalnej sumie rozumiemy taki podciąg, który jest złożony z elementów kolejno następujących po sobie w ciągu bazowym, a którego zsumowane elementy dają największy możliwy wynik.

Przykład 1

Spójny podciąg o maksymalnej sumie wcale nie musi być podciągiem, który składa się ze wszystkich elementów danego ciągu.

Dla przykładowej tablicy dane:

dane[0..9] = {2.51, -1.3, 5.23, -7.1, -2.4, 
	3.1, -1, 2.5, 1.5, 0.4}

Suma wszystkich elementów wynosi 3.44. Jednak już na pierwszy rzut oka możemy stwierdzić, że spójnym podciągiem o większej sumie byłby podciąg jednoelementowy 5.23.

Tymczasem suma maksymalnego spójnego podciągu{3.1, -1, 2.5, 1.5, 0.4} wynosi 6.5.

Do oceny oddajesz:

Dane:

plik wyniki.txt z odpowiedzią (liczbą rzeczywistą będącą sumą maksymalnego spójnego podciągu liczb z pliku giełda.txt zaokrągloną do dwóch miejsc po przecinku)
plik(i) z komputerową realizacją zadania (kodem programu)

Ważne!

Poniżej masz możliwość wpisania kodu swojego rozwiązania i przetestowania go dla przykładowych danych (bez użycia plików). W razie problemów, możesz skorzystać z przykładowego rozwiązania umieszczonego pod przyciskiem Pokaż rozwiązanie. Na końcu materiału znajdziesz odpowiedź dla danych umieszczonych w pliku gielda.txt. Zadbaj o prawidłowe wczytanie danych z pliku tekstowego.

Ćwiczenie 5

RBSSsSnZGN2BM

Przykładowe rozwiązanie zadania:

dane = [
	13.60, -6.04, -19.26, -2.29, 6.33, 
	7.60, 12.49, -8.18, 3.03, 2.34, 
	-13.36, -0.15, -8.67, -16.02, 8.53, 
	-13.93, -4.14, -3.33, -9.54, 17.79
]

max_suma = dane[0]
obecna_suma = dane[0]

for i in range(1, len(dane)):
    if obecna_suma + dane[i] < dane[i]:
        obecna_suma = dane[i]
    else:
        obecna_suma += dane[i]
        
    if obecna_suma > max_suma:
        max_suma = obecna_suma

print(round(max_suma, 2))

Odpowiedź do zadania:

wyniki.txt

R14lLeGmOx6TH

Przycisk do pobrania pliku TXT z wynikiem zadania.

Plik TXT o rozmiarze 5.00 B w języku polskim

Misja matura

Zadanie 1. Giełda bajtocka

Odpowiedź do zadania: