Podciąg liczb od 1 do a

0

Jaki jest najszybszy sposób na zrobienie tego?

Na wejściu są:
Dwie liczby naturalne: a oraz b, następnie b liczb naturalnych w zakresie od 1 do a, czyli wejściowy ciąg. Mamy wypisać długość najkrótszego podciągu zawierającego wszystkie liczby naturalne od 1 do a.

Mam już pewien kod, ale jeżeli nie chciało się nikomu czytać mojego poprzedniego tematu, to nie będzie się chciało i teraz.

1

najkrótszy podciąg który zawiera wszystkie liczby od 1 do a to po prostu ciąg liczb od 1 do a. Prawdę mówiąc udowodniłem dzisiaj, że czytanie ze zrozumieniem nie jest moją mocną stroną jednak treści twojego zadania nie rozumiem.

0

Ale liczby mogą się powtarzać. Dla

3 6
1 2 1 1 3 1 

Poprawna odpowiedź to
4
Najkrótszy podciąg tutaj to
2 1 1 3
Zawiera wszystkie od 1 do a. Teraz lepiej wyjaśniłem?

1

Ja tego wciąż nie czaję, masz wejście:
a == 3
b == 6

w takim układzie masz znaleźć najkrótszy podciąg ciągu 1, 2, 3
z liczby 1, 2, 1, 1, 3, 1, dla mnie odpowiedź brzmi tak jak dla allocera bierzemy 1, potem 2, potem dwie jedynki opószczamy i bierzemy 3, i opószczamy 1.
Najlepiej podaj więcej przykładów, tak z 4, żeby można było załapać na jakiej zasadzie chcesz to zrobić.

0

Chodzi o to, że nie opuszczamy niczego. Mamy wypisać długość najkrótszego spójnego ciągu, która zawiera wszystkie liczby od 1 do a. Nie możemy niczego opuszczać. Nie przerazisz się, jak wrzucę kod na 83 linie?

1

Panie MJay jak najbardziej, musi pan wyjść w końcu z ciemnych jaskiń. ;)
Chodzi o to, że mamy pewien ciąg na wejściu i trzeba znaleźć jak najkrótszy podciąg spójny (bez przerw), w którym są wszystkie liczby z przedziału 1..a.

Przykład:
1 2 1 2 3 1 1
3 1 1 1 1 2 2
1 3 1 2 1 2 3

1

Czaję w SPACJA końcu ;] Można to rozwiązać dynamicznie, sprawdzając wartości poprzedników

0

Mógłbyś rozwinąć wypowiedź? Chyba wiem, o co Ci chodzi, ale nie jestem pewien. Wrzucę swój kod, może będzie Wam się chciało ogarniać :) Wyniki są zawsze dobre, chodzi o to, aby go przyspieszyć. Macie jakieś pomysły?

#include <stdio.h>
#include <string.h>
#define ui unsigned int
ui v[1000];
inline void READ(ui t[], ui L)
{
    for(ui i=0; i<L; i++)
        scanf("%u", &t[i]);
}
inline void ADD(ui t[], ui pointer)
{
    t[pointer-1]++;
}
inline void SUB(ui t[], ui pointer)
{
    t[pointer-1]--;
}
inline void CLEAR(ui t[], ui size)
{
    memset(t, 0, size*sizeof(unsigned int));
}
ui CHECQUE(ui t[], ui size)
{
    for(ui i=0; i<size; i++)
            if(t[i]<1)
                    return 0;
        return 1;
}
ui CHECQUE_ELEMENT(ui t[], ui element)
{
    if (t[element-1]>0) return 1;
    return 0;
}
ui SEARCHEND(ui t[], ui begining, ui end, ui v[], ui vend)
{
    for(ui i=begining; i<end; i++)
        {
            ADD(v, t[i]);
                if(CHECQUE(v, vend)) return i;
        }
        return 0;
}
ui SEARCHBEGIN(ui t[], ui begining, ui v[])
{
    ui temp=0;
    for(ui i=begining;;i++)
        {
            SUB(v, t[i]);
            temp=i;
            if (!CHECQUE_ELEMENT(v, t[i])) break;          
        }
        return temp;
}
ui M(ui a, ui b)
{
        if(b<a) a=b;
        return a;
}
int main() {
    ui n, L;
    scanf("%u%u", &n, &L);
    ui tab[L];
        CLEAR(v, n);
        READ(tab, L);
        ui min=16843009, begin=0, end=0;
        while(true)
        {
            end=SEARCHEND(tab, end, L, v, n);
                if (end==0) break;
                begin=SEARCHBEGIN(tab, begin, v);
                min=M(min, end-begin+1);
                if(min==n) break;
                begin++;
                end++;
        }
        printf("%u", min);
}
1

Ok. Powiedzmy, że mamy pierwszy przykład który podał T.

user image

Teraz sprawdzasz dla tych ciągów gdzie jest najdłuższy podciąg. Czyli sprawdzimy dla 3 z ukośną strzałką i wyjdzie nam podciąg 1, 2, 3
Ale sprawdzimy też dla 3 ze strzałką pionową i wychodzi 2, 3, 1. Sprawdzimy też dla ciągu z 2, 3, 1, 1, ale potem wywnioskujemy, że jest za długi, i nie nadaje się.

1

Twój program niestety u mnie się nie kompiluje. Mój program u mnie na kompie trwa 12ms.
Sprawdzane dla ciagów:
1212311 oraz
121131

#include <iostream>
#include <Windows.h>
#include <time.h>
using namespace std;

bool Koniec(const bool* tab, int zakres)
{
    for(int i = 0; i < zakres; ++i)
        if(tab[i] == false)
            return false;
    return true;
}

int Exist(int** tab, int zakres, int dlugoscCiagu)
{
    for(int i = 1; i <= zakres; ++i)
        if(tab[i][dlugoscCiagu] == dlugoscCiagu)
            return i;
    return zakres;
}

int main()
{
    cout << "Podaj liczbe zakonczajaca ciag: ";
    int DlugoscCiaguA;
    cin >> DlugoscCiaguA;

    bool* DoneA = new bool[DlugoscCiaguA];
    for(int i = 0; i < DlugoscCiaguA; ++i)
        DoneA[i] = false;

    cout << "Podaj ilosc liczb drugiego ciagu: ";
    int DlugoscCiaguB;
    cin >> DlugoscCiaguB;

    int* CiagB = new int[DlugoscCiaguB];
    for(int i = 0; i < DlugoscCiaguB; ++i)
    {
        cout << "Wprowadz " << i + 1 << "-ta wartosc Ciagu B: ";
        cin >> CiagB[i];
    }

    //Bajer ;]
    cout << "\nWspaniale, teraz wyszukuje najkrotszy podciag: \n";

    char wiatraczek[] = { '\\', '|', '/', '-' };
    for(int i = 0; i < 20; ++i)
    {
        Sleep(200);
        cout << wiatraczek[i % 4] << "\r";
    }
    //~Bajer ;]

    // Tworzenie tablicy dynamicznego sprawdzania ciagu:
    clock_t start = clock();
    int** tab = new int*[DlugoscCiaguB + 1];
    for(int i = 0; i <= DlugoscCiaguB; ++i)
        tab[i] = new int[DlugoscCiaguA + 1];

    //Wyzerowanie pierwszej kolumny i pierwszego wiersza
    for(int i = 0; i <= DlugoscCiaguB; ++i)
        tab[i][0] = 0;
    for(int i = 0; i <= DlugoscCiaguA; ++i)
        tab[0][i] = 0;

    for(int i = 1; i <= DlugoscCiaguB; ++i)
        for(int j = 1; j <= DlugoscCiaguA; ++j)
            if(CiagB[i - 1] == j)
                tab[i][j] = tab[i - 1][j - 1] + 1;
            else
                tab[i][j] = max(tab[i - 1][j], tab[i][j - 1]);

    //Wypisanie zawartosci tablicy dynamicznego sprawdzania ciagu
    for(int i = 0; i <= DlugoscCiaguB; ++i)
    {
        for(int j = 0; j <= DlugoscCiaguA; ++j)
            cout << tab[i][j] << " ";
        cout << endl;
    }
    cout << endl;

    //Wypisywanie najkrotszego ciagu
    int index = Exist(tab, DlugoscCiaguB, DlugoscCiaguA);
    if(index < DlugoscCiaguB)
    {
        int dlugosc;
        int minDlugosc = DlugoscCiaguB;
        int najkrotszyIndex;
        for(int i = index; i < DlugoscCiaguB ; ++i)
        {
            dlugosc = 0;
            for(int j = i - 1; j >= 0 ; --j)
            {
                ++dlugosc;
                DoneA[CiagB[j] - 1] = true;
                if(Koniec(DoneA, DlugoscCiaguA))
                    break;
            }
            if(dlugosc < minDlugosc)
            {
                for(int i = 0; i < DlugoscCiaguA; ++i)
                    DoneA[i] = false;
                minDlugosc = dlugosc;
                najkrotszyIndex = i - 1;
            }
        }

        cout << "Najkrotszy podciag, to: ";
        najkrotszyIndex = najkrotszyIndex - minDlugosc + 1;
        for(int i = 0; i < minDlugosc; ++i)
            cout << CiagB[najkrotszyIndex++];

        cout << endl;
    }
    else
        cout << "Nie ma takiego podciagu\n";
    //Usuwanie wszystkiego co mozliwe (nawet Windowsa)
    for(int i = 0; i <= DlugoscCiaguB; ++i)
        delete [] tab[i];
    delete [] tab;
    delete [] DoneA;
    delete [] CiagB;
    clock_t koniec = clock();

    cout << "Czas wykonania aplikacji (bez uwzgledniania Bajeru ;]) to: " << koniec - start << endl;
    system("pause");
    return 0;
}

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