Poprawa programu ciagi

0

Siemka wie ktoś może jak zrobić, żeby program szukał najdłuższego ciagu

#include <bits/stdc++.h>
#include <iostream>
#include <string>

using namespace std;

// Gdy znaleziono najdlusza sume, metoda drukuje wynik
// Jesli nie znaleziono zadnego pasujacego ukladu liczb, metoda drukuje informacje o braku wyniku
void znajdz_najdluzszy_podciag(int tablica[], int dlugosc, int suma) {
    // Zmienne pomocnicze
    int aktualna_suma, i, j;

    for (i = 0; i < dlugosc; i++) {
        // Ustawiamy aktualny element jako aktualna suma
        aktualna_suma = tablica[i];

        // Mamy jeden wybrany element z naszej tablicy
        // I przeszukujemy reszte tablicy do konca w poszukiwaniu najdluzszej sekwencji elementow
        // Pasujacych do sumy
        for (j = i + 1; j <= dlugosc; j++) {
            // Jesli aktualna suma jest rowna oczekiwanej, znalezlismy wynik
            if (aktualna_suma == suma) {
                int dlugosc_najdluzszego = j - i;
                // Drukujemy wynik na konsoli
                cout << "Najdluzszy podciag to [";
                for (int k = i; k <= j - 1; k++) {
                    if (k != i) cout << ", ";
                    cout << tablica[k];
                }
                cout << "] o dlugosci " << dlugosc_najdluzszego;

                // Zapisujemy do pliku
                ofstream plik("wyniki.txt");
                plik << "Najdluzszy podciag to [";
                for (int k = i; k <= j - 1; k++) {
                    if (k != i) plik << ", ";
                    plik << tablica[k];
                }
                plik << "] o dlugosci " << dlugosc_najdluzszego;
                plik.close();

                // Konczymy dzialanie funkcji
                return;
            }
            // Jesli aktualna suma przekroczyla oczekiwana lub wyszlismy poza dlugosc tablicy, to przerywamy petle
            if (aktualna_suma > suma || j == dlugosc) break;
            // W przeciwnym razie dodajemy do aktualnej sumy aktualny element
            // I robimy kolejny obrot petli by znow sprawdzic aktualna sume
            aktualna_suma = aktualna_suma + tablica[j];
        }
    }

    cout << "Nie znaleziono pasujacych liczb";
}


int main() {
    // Wczytujemy dane z pliku
    // Wczytujemy dane linia po linii
    // Dlatego mamy 2 elementy:
    // Pierwszy to pierwsza linijka z pliku czyli "A[] = [...]"
    // Drugi to druga linijka z pliku czyli "Suma = ..."
    // Wszystko jest stringiem w tym momencie
    string aktualna_linia;
    string linie[2];
    int index = 0;
    ifstream plik("dane.txt");
    while (getline(plik, aktualna_linia))
    {
        linie[index] = aktualna_linia;
        index++;
    }
    plik.close();

    // Bierzemy pierwsza linie i wyciagamy z niej sama tablice liczb aby miec ja w formacie "x,y,z"
    // Wywalamy zatem "A[] = " oraz nawiasy kwadratowe
    // Zostana nam jeszcze przecinki pomiedzy liczbami, ktore usuniemy pozniej
    string tablica_z_pliku = linie[0].substr(linie[0].find(" = ") + 4, linie[0].length() - 8);

    // Bierzemy druga linie i wyciagamy wartosc sumy
    // Wywalamy "Suma = "
    string suma_z_pliku = linie[1].substr(linie[1].find(" = ") + 3);

    // Wywalamy wszystkie przecinki i to co zostanie zamieniamy na liczby
    vector<int> wektor;
    stringstream tablica_jako_array(tablica_z_pliku);
    for (int i; tablica_jako_array >> i;) {
        wektor.push_back(i);
        if (tablica_jako_array.peek() == ',') {
            tablica_jako_array.ignore();
        }
    }
    int tablica[wektor.size()];
    for (std::size_t i = 0; i < wektor.size(); i++) {
        tablica[i] = wektor[i];
    }

    // Ustalamy dlugosc tablicy (ile elementow)
    int dlugosc = wektor.size();

    // Zmieniamy sume ze stringa na liczbe
    int suma;
    stringstream suma_jako_liczba(suma_z_pliku);
    suma_jako_liczba >> suma;

    // Wywolujemy funkcje szukajaca
    znajdz_najdluzszy_podciag(tablica, dlugosc, suma);
    return 0;
}
1

Pseudokod, O(n^2):

function longest_subseq_sum(xs, s):  # xs - list, s - given sum
    if empty(xs): 
        return NULL
    limit = length(xs)
    sequence = []
    maximum = 0
    for i = 0 to limit - 1:
        j = i
        tmp_sum = 0
        tmp_seq = []
        while j < limit and tmp_sum <= s:
            tmp_sum += xs[j]
            tmp_seq.append(xs[j])
            j += 1
            if tmp_sum == s:
                if len(tmp_seq) >= maximum:
                    maximum = len(tmp_seq)
                    sequence = tmp_seq  # copy must be assigned here
    return sequence
0

Najdłuższego podciagu czy najdłuższego podzbioru?
Co ma do tego przekazywana suma?

1 użytkowników online, w tym zalogowanych: 0, gości: 1