Pytania otagowane jako algorithms

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.

1
Obsługa struktur danych dla lokalnego wyszukiwania SAT
WalkSAT i GSAT są dobrze znanymi i prostymi lokalnymi algorytmami wyszukiwania służącymi do rozwiązania logicznego problemu satysfakcji. Pseudokod algorytmu GSAT jest kopiowany z pytania Implementacja algorytmu GSAT - Jak wybrać literał, który ma być odwrócony? i przedstawione poniżej. procedure GSAT(A,Max_Tries,Max_Flips) A: is a CNF formula for i:=1 to Max_Tries do …
2
Jak opracować algorytm do rozmieszczania (skalowalnych) okien na ekranie tak, aby zajmował jak najwięcej miejsca?
Chciałbym napisać prosty program, który akceptuje zestaw okien (szerokość + wysokość) oraz rozdzielczość ekranu i wyświetla układ tych okien na ekranie, aby okna zajmowały najwięcej miejsca. Dlatego można zmienić rozmiar okna, zachowując output size >= initial sizei proporcje. Tak więc dla okna chciałbym, aby algorytm zwrócił krotkę .( x , …
1
Implementacja algorytmu GSAT - Jak wybrać literał do przerzucenia?
Algorytm GSAT jest w większości prosty: dostajesz formułę w spójnej normalnej formie i przerzucasz literały klauzul, aż znajdziesz rozwiązanie, które spełnia formułę lub nie osiągniesz limitu max_tries / max_flips i nie znajdziesz rozwiązania. Implementuję następujący algorytm: procedure GSAT(A,Max_Tries,Max_Flips) A: is a CNF formula for i:=1 to Max_Tries do S <- …
5
Skuteczna kompresja nieoznakowanych drzew
Rozważ nieoznakowane, ukorzenione drzewa binarne. Możemy skompresować takich drzew: gdy istnieją wskaźniki do poddrzew i T ' z T = T ' (ustne = jak równość strukturalne), możemy zapisać (wlog) T i zastąpić wszystkie wskaźniki do T ' z wskazówki dla T . Zobacz odpowiedź uli na przykład.T.TTT.′T′T'T.= T′T=T′T = …
1
Optymalny algorytm do znalezienia obwodu rzadkiego wykresu?
Zastanawiam się, jak znaleźć obwód rzadkiego nieukierunkowanego wykresu. Przez rzadki mam na myśli . Przez optymalne rozumiem najmniejszą złożoność czasową.| mi| =O ( | V|)|mi|=O(|V.|)|E|=O(|V|) Myślałem o pewnej modyfikacji algorytmu Tarjana dla niekierowanych grafów, ale nie znalazłem dobrych wyników. Właściwie pomyślałem, że jeśli uda mi się znaleźć 2 połączone elementy …
12
Struktura danych lub algorytm do szybkiego znajdowania różnic między łańcuchami
Mam tablicę 100 000 ciągów o długości . Chcę porównać każdy ciąg z każdym innym, aby zobaczyć, czy dwa ciągi różnią się o 1 znak. W tej chwili, gdy dodam każdy ciąg do tablicy, sprawdzam go względem każdego łańcucha już w tablicy, który ma złożoność czasową .kkkn(n−1)2kn(n−1)2k\frac{n(n-1)}{2} k Czy istnieje …
1
Złożoność znalezienia współczynnika dwumianowego równego liczbie
Załóżmy, że otrzymujesz liczbę mmm (używając O(logm)O(log⁡m)O(\log m) bitów w kodowaniu binarnym). Jak szybko można znaleźć (lub stwierdzić, że takie nie istnieje) ?n,k∈N,1&lt;k≤n2:(nk)=mn,k∈N,1&lt;k≤n2:(nk)=mn,k\in \mathbb N, 1<k\leq\frac{n}{2}:{n \choose k}=m Na przykład, biorąc pod uwagę wejście , można wyprowadzić .m=8436285m=8436285m=8436285n=27,k=10n=27,k=10n=27, k=10 Naiwny algorytm dla problemu przekroczyłby wszystkie możliwe wartości dla i szukałby …
3
Deterministyczny algorytm czasu liniowego do sprawdzania, czy jedna tablica jest posortowaną wersją drugiej
Rozważ następujący problem: Dane wejściowe: dwie tablice i o długości , gdzie jest posortowane.B n BAAABBBnnnBBB Pytanie: czy i zawierają te same elementy (z ich wielokrotnością)?B.AAABBB Jaki jest najszybszy algorytm deterministyczny dla tego problemu? Czy można to rozwiązać szybciej niż ich sortowanie? Czy ten problem można rozwiązać w deterministycznym czasie …
2
Sortuj tablicę 5 liczb całkowitych z maksymalnie 7 porównaniami
Jak mogę posortować listę 5 liczb całkowitych tak, że w najgorszym przypadku potrzeba 7 porównań? Nie obchodzi mnie, ile innych operacji zostanie wykonanych. Nie wiem nic szczególnego o liczbach całkowitych. Wypróbowałem kilka różnych metod dzielenia i podbijania, które obniżają mnie do 8 porównań, takich jak stosowanie podejścia scalesort lub łączenie …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.