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.

3
Optymalna strategia dla abstrakcyjnej gry
W wywiadzie otrzymałem następujący problem (którego już nie udało mi się rozwiązać, nie próbując oszukać mojej przeszłości): Gra rozpoczyna się od dodatniej liczby całkowitej . (Np. ) Liczba ta jest konwertowana na reprezentację binarną, a jest liczbą bitów ustawioną na . (Np. , )A 0 = 1234 N 1 A …
2
Czy ten szczególny przypadek problemu z planowaniem można rozwiązać w czasie liniowym?
Alice, studentka, ma dużo pracy domowej w ciągu najbliższych tygodni. Każda praca domowa zabiera ją dokładnie jednego dnia. Każda pozycja ma również termin i negatywny wpływ na jej oceny (zakładamy liczbę rzeczywistą, punkty bonusowe za przyjęcie założenia porównywalności), jeśli nie dotrzyma terminu. Napisz funkcję, która podając listę (termin, wpływ na …
1
Edytuj odległość listy za pomocą unikalnych elementów
Odległość edycji Levenshtein-Distance między listami jest dobrze zbadanym problemem. Ale nie mogę znaleźć wiele możliwych ulepszeń, jeśli wiadomo, że żaden element nie występuje więcej niż raz na każdej liście . Załóżmy również, że elementy są porównywalne / sortowalne (ale listy do porównania nie są sortowane na początek). O(min(m,n)s)O(min(m,n)s)O(\min(m,n)s)O(min(s,m,n)s)O(min(s,m,n)s)O(\min(s,m,n)s)sss Bardziej formalnie, …
9
Czym dokładnie jest algorytm?
Wiem, że może to zabrzmieć trochę po wyjęciu z pudełka, w rzeczywistości zawsze myślałem w środku, ale ostatnio myślałem, być może dlatego, że informatyka zapewnia dużą swobodę, o sposobach opracowywania programów innych niż te nauczane na uniwersytecie. Rozważ funkcję silni. Zazwyczaj definiujemy tę funkcję jak int fact(int n) { int …
12 algorithms 
3
Multicore SAT Solver
Próbuję rozwiązać problem SAT z 25k klauzul 5k zmiennych. Ponieważ działa od godziny (precosat), a potem chciałbym rozwiązać większe, szukam wielordzeniowego SAT-Solvera. Ponieważ wydaje się, że jest wiele rozwiązań SAT, jestem całkiem zagubiony. Czy ktoś mógłby wskazać mi najlepszy dla mojej sprawy? Byłbym również szczęśliwy, gdyby ktoś mógł podać mi …
2
Algorytm liniowego oznaczania czasu dla drzewa?
Mam drzewo bezkierunkowe, którego wierzchołki chcę opisać. Węzły liści powinny być oznaczone jako jeden. Następnie załóżmy, że liście zostały usunięte. W drzewie, które pozostaje, liście powinny być oznaczone jako dwa. Proces ten trwa w oczywisty sposób, dopóki wszystkie wierzchołki nie będą miały etykiety. Powodem tego jest to, że chcę przechowywać …
12 algorithms  trees 
3
Znajdowanie elementu, który występuje najczęściej w bardzo dużym pliku
Słyszałem to pytanie podczas wywiadu i miałem nadzieję uzyskać opinie na temat dobrych odpowiedzi: masz duży plik 10+ GB i chcesz dowiedzieć się, który element występuje najczęściej, co jest dobrym sposobem zrobić to? Iterowanie i śledzenie mapy prawdopodobnie nie jest dobrym pomysłem, ponieważ zużywasz dużo pamięci, a śledzenie pojawiających się …
2
Układanie ortogonalnego wielokąta za pomocą kwadratów
Biorąc pod uwagę ortogonalny wielokąt (wielokąt, którego boki są równoległe do osi), chcę znaleźć najmniejszy zestaw kwadratów wewnętrznie rozłącznych, których zjednoczenie jest równe wielobokowi. Znalazłem kilka odniesień do nieco innych problemów, takich jak: Pokrycie prostopadłego wielokąta kwadratami - podobnie jak w moim problemie, ale zakrywające kwadraty mogą się pokrywać. Ten …
4
Porównywanie liczb wymiernych
Biorąc pod uwagę a , b , c , d∈ N.za,b,do,re∈N.a,b,c,d \in \mathbb N i ,b , d∉ { 0 }b,re∉{0}b,d \notin \{0\} zab&lt; cre⟺d&lt; c bzab&lt;dore⟺zare&lt;dob \begin{eqnarray*} \frac a b < \frac c d &\iff& ad < cb \end{eqnarray*} Moje pytania to: Biorąc pod uwagęa , b , c …
2
Rekonstrukcja wykresów z rozkładu stopni
Biorąc pod uwagę rozkład stopni, jak szybko możemy zbudować wykres zgodny z danym rozkładem stopni? Szkic łącza lub algorytmu byłby dobry. Algorytm powinien zgłaszać „brak”, ponieważ nie można zbudować żadnego wykresu i dowolnego przykładu, jeśli można zbudować wiele wykresów.
1
O algorytmie redukcji Codda
Algorytm Codda konwertuje wyrażenie w krotkowym rachunku relacyjnym na relacyjną algebrę. Czy istnieje standardowa implementacja algorytmu? Czy ten algorytm jest używany gdziekolwiek? (Wydaje się, że branża potrzebuje tylko SQL i wariantów, nie jestem pewien co do teoretyków baz danych w środowisku akademickim). Jaka jest złożoność redukcji? Zostało to opublikowane w …
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.