Algorytm jest sekwencją dobrze zdefiniowanych kroków, które definiują abstrakcyjne rozwiązanie problemu. Użyj tego tagu, gdy Twój problem dotyczy projektowania i analizy algorytmów.
Binarnej sekwencji o długości nnn właśnie uporządkowaną sekwencję x1,…,xnx1,…,xnx_1,\ldots,x_n , tak że każdy xjxjx_j oznacza albo 000 lub 111 . Aby wygenerować wszystkie takie sekwencje binarne, można użyć oczywistej struktury drzewa binarnego w następujący sposób: katalog główny jest „pusty”, ale każde lewe dziecko odpowiada dodaniu 000 do istniejącego łańcucha, a …
Wykres jest akordowy, jeśli nie indukował cykli o długości 4 lub większej. Drzewo klika T z G jest drzewem, w którym wierzchołki drzewa są maksymalne klik z G . Krawędź w T odpowiada minimalnemu separatorowi. Liczba odrębnych drzew kliki może być wykładnicza pod względem liczby wierzchołków na wykresie akordowym.solsolG444T.T.TsolsolGsolsolGT.T.T Zmniejszona …
Ostatnio natknąłem się na artykuł opisujący technikę parsowania wspomnianą w tytule. Niestety terminologia zastosowana we wspomnianym artykule jest nieco poza moim zrozumieniem, więc starałem się zrozumieć algorytm konstrukcji bardziej intuicyjnie. Wierzę, że mi się udało ( ta prezentacja była źródłem momentu ah-ha), ale doceniona zostanie weryfikacja poprawności przez kogoś, kto …
Jest to problem z sesji treningowej Polskiego Konkursu Programowania Uczelnianego 2012 . Chociaż mogłem znaleźć rozwiązania dla głównego konkursu, nie mogę nigdzie znaleźć rozwiązania tego problemu. Problem polega na tym: biorąc pod uwagę zbiór NNN wyraźnych liczb całkowitych dodatnich nie większych niż , znajdź rozmiar najmniejszego podzbioru, który nie ma …
Załóżmy, że mam ukierunkowany wykres z wagami krawędzi narysowanymi z zakresu [1,…,K][1,…,K][1,\dots, K] gdzie KKK jest stałe. Jeśli próbuję znaleźć najkrótszą ścieżkę za pomocą algorytmu Dijkstry , jak mogę zmodyfikować strukturę algorytmu / danych i poprawić złożoność czasu do O(|V|+|E|)O(|V|+|E|)O(|V|+|E|) ?
Mam problem, który można sprowadzić do problemu przydziału. (W poprzednim pytaniu dowiedziałem się, jak to zrobić.) Co oznacza, że mamy zestaw ZAZAA agentów i zestaw zadań, a także funkcję kosztu . Musimy znaleźć zadanie, aby całkowity koszt był minimalny.c ( i , j )T.T.Tc ( i , j )do(ja,jot)c(i,j) Algorytm …
Szukam szybkiego algorytmu dopasowywania ciągów typu k-mismatch. Biorąc pod uwagę ciąg wzorca P o długości m i ciąg tekstowy T o długości n, potrzebuję szybkiego algorytmu (czas liniowy), aby znaleźć wszystkie pozycje, w których P pasuje do podłańcucha T z co najwyżej k niedopasowań. Różni się to od problemu różnic …
W Wikipedii podano implementację oddolnego schematu programowania dynamicznego dla odległości edycji. Nie jest całkowicie zgodny z definicją; komórki wewnętrzne są obliczane w następujący sposób: if s[i] = t[j] then d[i, j] := d[i-1, j-1] // no operation required else d[i, j] := minimum ( d[i-1, j] + 1, // a …
\newcommand\ldotd{\mathinner{..}} Biorąc pod uwagę, że A[1..n]A[1..n]A[1\ldotd n] to liczby całkowite takie, że 0≤A[k]≤m0≤A[k]≤m0\le A[k]\le m dla wszystkich 1≤k≤n1≤k≤n1\le k\le n oraz występowanie każdego liczba z wyjątkiem określonej liczby w A[1..n]A[1..n]A[1\ldotd n] jest liczbą nieparzystą. Spróbuj znaleźć numer, którego wystąpienie jest liczbą parzystą. Istnieje algorytm Θ(nlogn)Θ(nlogn)\Theta(n\log n) : sortujemy A[1..n]A[1..n]A[1\ldotd n] …
Nie jestem pewien, czy to pytanie należy tutaj i przepraszam, jeśli nie. Chcę opracować programowy sposób, w jaki mogę probabilistycznie określić, czy dany ciąg „należy” do worka ciągów. Na przykład, jeśli mam torbę z 10 000 nazwami miast w USA, a następnie mam ciąg „Philadelphia”, chciałbym uzyskać ilościową miarę tego, …
Powszechnie wiadomo, że wielokąty monotoniczne odgrywają kluczową rolę w triangulacji wielokątów . Definicja: Wielokąt w płaszczyźnie jest nazywany monotonicznym w odniesieniu do linii prostej L , jeśli każda linia prostopadła do L przecina P najwyżej dwa razy.P.PPL.LLL.LLP.PP Biorąc pod uwagę linię i wielokąt P , czy istnieje skuteczny algorytm do …
Dla zabawy próbuję stworzyć przeglądarkę z ramką dla DCPU-16 . Rozumiem, jak to zrobić wszystko oprócz ukrywania linii ukrytych w ramce drucianej. Wszystkie pytania tutaj na SO zakładają, że masz dostęp do OpenGL, niestety nie mam dostępu do niczego takiego w przypadku DCPU-16 (ani żadnego rodzaju przyspieszenia sprzętowego). Znalazłem dość …
W wielu tekstach wyznacza się dolną granicę dla znalezienia tego najmniejszego elementu za pomocą argumentów wykorzystujących mediany. Jak mogę je znaleźć, używając argumentu przeciwnika?kkk Wikipedia twierdzi, że algorytm turnieju działa w , a n - k + ∑ n j = n + 2 - k ⌈ lgO ( n …
Rozważ model CSP, w którym zmiana wartości konkretnej zmiennej jest kosztowna. Czy jest jakaś praca, w której funkcja celu bierze również pod uwagę liczbę zmian wartości zmiennej podczas procesu wyszukiwania? Przykład: Zmienna kosztowna do zmiany może być pod kontrolą jakiegoś innego agenta i istnieje pewien narzut związany z zaangażowaniem tego …
Biorąc pod uwagę liczbę całkowitą nnn i zestaw trojaczków różnych liczb całkowitych S⊆{(i,j,k)∣1≤i,j,k≤n,i≠j,j≠k,i≠k},S⊆{(i,j,k)∣1≤i,j,k≤n,i≠j,j≠k,i≠k},S \subseteq \{(i, j, k) \mid 1\le i,j,k \le n, i \neq j, j \neq k, i \neq k\}, znajdź algorytm, który albo znajduje permutację ππ\pi zbioru {1,2,…,n}{1,2,…,n}\{1, 2, \dots, n\} taką, że (i,j,k)∈S⟹(π(j)<π(i)<π(k)) ∨ (π(i)<π(k)<π(j))(i,j,k)∈S⟹(π(j)<π(i)<π(k)) ∨ (π(i)<π(k)<π(j))(i,j,k) …
Używamy plików cookie i innych technologii śledzenia w celu poprawy komfortu przeglądania naszej witryny, aby wyświetlać spersonalizowane treści i ukierunkowane reklamy, analizować ruch w naszej witrynie, i zrozumieć, skąd pochodzą nasi goście.
Kontynuując, wyrażasz zgodę na korzystanie z plików cookie i innych technologii śledzenia oraz potwierdzasz, że masz co najmniej 16 lat lub zgodę rodzica lub opiekuna.