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.
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.
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?
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ć.
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?
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
Czaję w SPACJA końcu ;] Można to rozwiązać dynamicznie, sprawdzając wartości poprzedników
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);
}
Ok. Powiedzmy, że mamy pierwszy przykład który podał T.
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ę.
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;
}
Dzięki wielkie, trochę lepiej już ogarniam, tyle tylko, że wyniki są złe.
3 6
1 2 3 1 2 3
wywala odpowiedź
2
I gdybyś mógł bez <windows.h>, bo pracuję pod linuksem :)
Mógłbyś napisać, co Ci wywala kompilator? Poprawię.
HAHA!!!
Zrobione!
Dodałem dwie linijki i mam ponad 3x lepszy czas! Dzięki za wszelką pomoc, wpadłem na to dzięki Twojemu <windows.h> :D
#include <stdio.h>
#include <string.h>
#define ui unsigned int
inline void READ(ui t[], ui L)
{
for(ui i=0; i<L; i++)
scanf("%u", &t[i]);
}
inline void PRINT(ui t[], ui L)
{
printf("DRUKOWANIE: ");
for(ui i=0; i<L; i++)
printf("%u ", t[i]);
printf("\n");
}
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++)
{
if(!CHECQUE_ELEMENT(v, t[i]))
{
ADD(v, t[i]);
if(CHECQUE(v, vend)) return i;
}
else
ADD(v, t[i]);
}
return 0;
}
ui SEARCHBEGIN(ui t[], ui begining, ui end, ui v[], ui vend)
{
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 v[n], tab[L];
CLEAR(v, n);
READ(tab, L);
ui min=16843009, begin=0, end=0;
while(begin!=L-n-1)
{
end=SEARCHEND(tab, end, L, v, n);
if (end==0) break;
begin=SEARCHBEGIN(tab, begin, L, v, n);
min=M(min, end-begin+1);
if(min==n) break;
begin++;
end++;
}
printf("%u", min);
}
Szkoda, że nie mogę Ci wstawić setki plusów :) Tyle godzin nad tym siedziałem!
No ja też właśnie poprawiłem mój kod ;] usuwając windows.h musiałem się pozbyć fajnego bajeru z wiatraczkiem ;]
Ale moja metoda ma jeden minus tak jak się teraz zastanowie. Sprawdzanie dynamiczne moim sposobem musi być zagwarantowane, że 1 pojawi się przed 2 i 2 przed 3 w całym ciągu. Tak więc nie jest to jednak dobry sposób.
#include <iostream>
#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];
}
// 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 && dlugosc >= 3)
{
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;
}