[Algorytmika] Zliczanie podzbiorów tablicy o tej samej sumie

gmore
Użytkownik
Użytkownik
Posty: 8
Rejestracja: 6 paź 2017, o 21:36
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 2 razy

[Algorytmika] Zliczanie podzbiorów tablicy o tej samej sumie

Post autor: gmore »

zadanie polega na napisaniu takiej funkcji, która przy danym \(\displaystyle{ x}\) i tablicy \(\displaystyle{ A[n]}\). Znajdzie liczbę podzbiorów \(\displaystyle{ J \subset \left\{ 0,...,n-1\right\}}\) takich, że \(\displaystyle{ \sum_{j \in J}^{} A[j] =x}\).
Mój kod jest następujący:

Kod: Zaznacz cały


int pot(int tab[], int i, int suma,int x){
		int cz=0; //liczy ilość podzbiorów lokalnie
	if (suma - tab[i]==x) cz++;
	for(int j=0;j<i;j++){
		
	cz = cz+	pot(tab,j,suma-tab[i],x);
		
		
	}
	return cz;
}

int podzbiory( int tab[], int x, int n){
	int suma = suma(tab);
	int czy =0;//liczy ilość podzbiorów
	
	for(int j=0;j<n;j++){
		
	czy = czy+	pot(tab,j,suma,x);
		
		
	}
	
	
	
	
}


Czyli rekurencyjnie sprawdzamy - bierzemy najpierw sumę wszystkich wyrazów tablicy. Sprawdzamy i później po kolei odejmujemy któryś element i rekurencyjnie. No i teraz pytania jaką to coś ma złożoność (jestem pewien prawie na 100% że to jest 2^n, bo równanie na złożoność to mniej więcej \(\displaystyle{ T(n) = T(n-1)+...+T(2)+1}\)), czy da się szybciej?


I jeszcze pytanie o drugie zadanie:
Mamy dwie tablice \(\displaystyle{ A[n],B[n]}\) liczb całkowitych o tej własności, że \(\displaystyle{ A[i+2] -A[i+1] > A[i+1] - A}\) oraz \(\displaystyle{ B[i+2] -B[i+1] < B[i+1] - B}\) (dla dowolnych i oczywiście). Mamy podać liczbę indeksów \(\displaystyle{ k}\) takich, że \(\displaystyle{ A[k] = B [k]}\). Kompletnie nie mam pomysłu, jak przyspieszyć taki prymitywny algorytm \(\displaystyle{ O(n)}\)- jakieś wskazówki?
Afish
Moderator
Moderator
Posty: 2828
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 356 razy

Re: [Algorytmika] Zliczanie podzbiorów tablicy o tej samej s

Post autor: Afish »

1. To jest odrobinę ogólniejsze

Kod: Zaznacz cały

https://en.wikipedia.org/wiki/Subset_sum_problem
, więc nie liczyłbym na złożoność niższą niż wykładnicza.
2. Na oko pójdzie wyszukiwaniem binarnym.
gmore
Użytkownik
Użytkownik
Posty: 8
Rejestracja: 6 paź 2017, o 21:36
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 2 razy

Re: [Algorytmika] Zliczanie podzbiorów tablicy o tej samej s

Post autor: gmore »

Afish, dzięki za odpowiedź.
Na oko pójdzie wyszukiwaniem binarnym.
Dlaczego? To sugeruje, że może istnieć tylko jeden taki indeks, a to przecież nie prawda.
Afish
Moderator
Moderator
Posty: 2828
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 356 razy

Re: [Algorytmika] Zliczanie podzbiorów tablicy o tej samej s

Post autor: Afish »

gmore pisze:To sugeruje, że może istnieć tylko jeden taki indeks, a to przecież nie prawda.
Zgadza się, to nie jest prawda, ale to nie oznacza, że nie da się wyszukać binarnie.

Podpowiedź:
Ukryta treść:    
gmore
Użytkownik
Użytkownik
Posty: 8
Rejestracja: 6 paź 2017, o 21:36
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 2 razy

Re: [Algorytmika] Zliczanie podzbiorów tablicy o tej samej s

Post autor: gmore »

O ile się nie mylę, mogą być co najwyżej dwa takie indeksy
No racja . No to moja propozycja jest taka. Ciąg A najpierw maleje na jakimś przedziale, a potem rośnie (jeden z przedziałów może być zdegenerowany). Analogicznie ciąg B najpierw rośnie na jakimś przedziale, a potem już tylko maleje (też jeden z przedziałów może być zdegenerowany). Wyszukanie punktu zmiany monotoniczności w przypadku każdego z ciągów to jest jakieś \(\displaystyle{ O(ln(n))}\). Znajdujemy te przedziały monotoniczności - jest jasne, że jeśli mają dwa punkty wspólne, to każdy leży w osobnych przedziałach. To znaczy może być tak, że A wszędzie rośnie i ma dwa punkty wspólne z B, ale w przypadku B już jeden z tych punktów będzie siedział w przedziale rosnącym, a drugi malejącym. Więc możemy szukać punktów wspólnych na przecięciach tych przedziałów (binarnie) - będziemy musieli sprawdzić maksymalnie cztery takie segmenty (np tam gdzie A rosnie, a B maleje, tam gdzie oba rosną itp) - ogółem wyjdzie suma kilku operacji \(\displaystyle{ O(ln(n))}\) czyli \(\displaystyle{ O(ln(n))}\). O to chodzi?

Edit: nie no jednak nie wiem jak szukać wspólnego indeksu w posortowanych rosnąco tablicach szybciej niż w \(\displaystyle{ O(n)}\)
Afish
Moderator
Moderator
Posty: 2828
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 356 razy

Re: [Algorytmika] Zliczanie podzbiorów tablicy o tej samej s

Post autor: Afish »

Powiem tak: nie mam dowodu, że moje rozumowanie jest poprawne, ale tak długo machałem rękami, że aż sam siebie przekonałem.
gmore pisze:Ciąg A najpierw maleje na jakimś przedziale, a potem rośnie (jeden z przedziałów może być zdegenerowany). Analogicznie ciąg B najpierw rośnie na jakimś przedziale, a potem już tylko maleje (też jeden z przedziałów może być zdegenerowany).
Koncepcyjnie poprawnie, do tego dochodzi jeszcze potencjalny przedział (właściwie dwa indeksy) równych wartości.
gmore pisze:Wyszukanie punktu zmiany monotoniczności w przypadku każdego z ciągów to jest jakieś \(\displaystyle{ O(ln(n))}\).
Tak, do tego potrzebujesz lekko zmodyfikowanego wyszukiwania ternarnego ekstremum funkcji unimodalnej — to skomplikowanie brzmi, ale jest bardzo podobne do wyszukiwania binarnego. Modyfikacja polega na uwzględnieniu faktu, że ekstremum może wystąpić dwukrotnie
gmore pisze:Znajdujemy te przedziały monotoniczności - jest jasne, że jeśli mają dwa punkty wspólne, to każdy leży w osobnych przedziałach. To znaczy może być tak, że A wszędzie rośnie i ma dwa punkty wspólne z B, ale w przypadku B już jeden z tych punktów będzie siedział w przedziale rosnącym, a drugi malejącym. Więc możemy szukać punktów wspólnych na przecięciach tych przedziałów (binarnie) - będziemy musieli sprawdzić maksymalnie cztery takie segmenty (np tam gdzie A rosnie, a B maleje, tam gdzie oba rosną itp) - ogółem wyjdzie suma kilku operacji \(\displaystyle{ O(ln(n))}\) czyli \(\displaystyle{ O(ln(n))}\). O to chodzi?
Koncepcyjnie tak, robi się trochę przypadków, ale da się je ogarnąć ifologią.
gmore pisze:Edit: nie no jednak nie wiem jak szukać wspólnego indeksu w posortowanych rosnąco tablicach szybciej niż w \(\displaystyle{ O(n)}\)
Podejrzewam, że rysunek pomoże, zwróć uwagę, że jedne wartości będą rosły coraz szybciej, a drugie coraz wolniej. Najpierw uciąglijmy funkcję. Przede wszystkim sprawdzasz, czy punkt przecięcia w ogóle istnieje, czyli sprawdzasz wartości na końcach przedziału.

Jeżeli \(\displaystyle{ A_0 > B_0}\) i \(\displaystyle{ A_n < B_n}\), to funkcje musiały się przeciąć dokładnie raz, więc możesz spróbować wyszukać ten indeks binarnie.

Jeżeli zaś \(\displaystyle{ A_0 > B_0 \wedge A_n > B_n}\) oraz A rośnie coraz szybciej, a B coraz wolniej (w przeciwnym wypadku przecięcia nie ma), to chcesz znaleźć indeks, w którym funkcje zamienią się miejscami (czyli A jest pod B). Kluczowe jest dla Ciebie użycie nie tylko wartości w punkcie, ale także otoczenie. Bierzesz indeks środkowy, obliczasz styczne w punkcie i patrzysz, po której stronie się przetną, a następnie w tę stronę przesuwasz indeks i kontynuujesz wyszukiwanie binarne. Tutaj oczywiście masz wartości dyskretne, więc nie liczysz stycznej per se, tylko różnicę wartości w indeksie i w indeksie o jeden mniejszym, a potem na tej podstawie wnioskujesz. Jak już znajdziesz indeks „zamiany miejsc” (o ile takowy istnieje), to masz dwa przedziały z pojedynczym przecięciem każdy.

Sumarycznie wyjdzie pewnie jakieś osiem przypadków, z których część chyba nie zachodzi, do tego trochę ifów wartości na krańcach przedziałów i powinno pójść w czasie logarytmicznym.
ODPOWIEDZ