Sprawdź się

Zadanie 3. 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)

Praca domowa

Przedstaw rozwiązanie zadania, pisząc program w języku C++, Java lub Python. Zadbaj o prawidłowe wczytanie danych z pliku tekstowego. Rozwiązanie zadania znajduje się pod sekcją ćwiczeń.

Pokaż ćwiczenia:

Język C++

Ćwiczenie 1

RCRmhIk3lA0sP

Przykładowe rozwiązanie zadania:

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 2. kratka include otwórz nawias ostrokątny iomanip zamknij nawias ostrokątny. Linia 4. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 5. double dane otwórz nawias kwadratowy 20 zamknij nawias kwadratowy znak równości otwórz nawias klamrowy. Linia 6. 13 kropka 60 przecinek minus 6 kropka 04 przecinek minus 19 kropka 26 przecinek minus 2 kropka 29 przecinek 6 kropka 33 przecinek. Linia 7. 7 kropka 60 przecinek 12 kropka 49 przecinek minus 8 kropka 18 przecinek 3 kropka 03 przecinek 2 kropka 34 przecinek. Linia 8. minus 13 kropka 36 przecinek minus 0 kropka 15 przecinek minus 8 kropka 67 przecinek minus 16 kropka 02 przecinek 8 kropka 53 przecinek. Linia 9. minus 13 kropka 93 przecinek minus 4 kropka 14 przecinek minus 3 kropka 33 przecinek minus 9 kropka 54 przecinek 17 kropka 79. Linia 10. zamknij nawias klamrowy średnik. Linia 11. int n znak równości sizeof otwórz nawias okrągły dane zamknij nawias okrągły prawy ukośnik sizeof otwórz nawias okrągły dane otwórz nawias kwadratowy 0 zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 13. double max podkreślnik suma znak równości dane otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 14. double obecna podkreślnik suma znak równości dane otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 16. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 17. if otwórz nawias okrągły obecna podkreślnik suma plus dane otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny dane otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły. Linia 18. obecna podkreślnik suma znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 19. else. Linia 20. obecna podkreślnik suma plus znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 22. if otwórz nawias okrągły max podkreślnik suma otwórz nawias ostrokątny obecna podkreślnik suma zamknij nawias okrągły. Linia 23. max podkreślnik suma znak równości obecna podkreślnik suma średnik. Linia 24. zamknij nawias klamrowy. Linia 26. std dwukropek dwukropek cout otwórz nawias ostrokątny otwórz nawias ostrokątny std dwukropek dwukropek fixed otwórz nawias ostrokątny otwórz nawias ostrokątny std dwukropek dwukropek setprecision otwórz nawias okrągły 2 zamknij nawias okrągły otwórz nawias ostrokątny otwórz nawias ostrokątny max podkreślnik suma średnik. Linia 28. return 0 średnik. Linia 29. zamknij nawias klamrowy.

#include <iostream>
#include <iomanip>

int main() {
    double dane[20] = {
		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
	};
    int n = sizeof(dane) / sizeof(dane[0]);

    double max_suma = dane[0];
    double obecna_suma = dane[0];

    for(int i = 1; i < n; i++){
        if (obecna_suma + dane[i] < dane[i])
            obecna_suma = dane[i];
        else
            obecna_suma += dane[i];
            
        if (max_suma < obecna_suma)
            max_suma = obecna_suma;
    }

    std::cout << std::fixed << std::setprecision(2) << max_suma;

    return 0;
}

Java

Ćwiczenie 2

R4CEPNoMaWFAL

Przykładowe rozwiązanie:

Linia 1. public class Main otwórz nawias klamrowy. Linia 3. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 4. double dane otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy. Linia 5. 13 kropka 60 przecinek minus 6 kropka 04 przecinek minus 19 kropka 26 przecinek minus 2 kropka 29 przecinek 6 kropka 33 przecinek. Linia 6. 7 kropka 60 przecinek 12 kropka 49 przecinek minus 8 kropka 18 przecinek 3 kropka 03 przecinek 2 kropka 34 przecinek. Linia 7. minus 13 kropka 36 przecinek minus 0 kropka 15 przecinek minus 8 kropka 67 przecinek minus 16 kropka 02 przecinek 8 kropka 53 przecinek. Linia 8. minus 13 kropka 93 przecinek minus 4 kropka 14 przecinek minus 3 kropka 33 przecinek minus 9 kropka 54 przecinek 17 kropka 79. Linia 9. zamknij nawias klamrowy średnik. Linia 11. double max podkreślnik suma znak równości dane otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 12. double obecna podkreślnik suma znak równości dane otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 14. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny dane kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 15. if otwórz nawias okrągły obecna podkreślnik suma plus dane otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny dane otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 16. obecna podkreślnik suma znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 17. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 18. obecna podkreślnik suma plus znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 19. zamknij nawias klamrowy. Linia 21. if otwórz nawias okrągły obecna podkreślnik suma zamknij nawias ostrokątny max podkreślnik suma zamknij nawias okrągły otwórz nawias klamrowy. Linia 22. max podkreślnik suma znak równości obecna podkreślnik suma średnik. Linia 23. zamknij nawias klamrowy. Linia 24. zamknij nawias klamrowy. Linia 26. System kropka out kropka printf otwórz nawias okrągły cudzysłów procent kropka 2f cudzysłów przecinek max podkreślnik suma zamknij nawias okrągły średnik. Linia 27. zamknij nawias klamrowy. Linia 28. zamknij nawias klamrowy.

public class Main{

	public static void main(String[] args){
		double 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
		};

        double max_suma = dane[0];
        double obecna_suma = dane[0];

        for(int i = 1; i < dane.length; i++){
            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;
            }
        }

        System.out.printf("%.2f", max_suma);
    }
}

Python

Ćwiczenie 3

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

Prezentacja multimedialna

Dla nauczyciela

Zadanie 3. Giełda bajtocka

Odpowiedź do zadania: