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.

2
Gdzie jest błąd w tym najwyraźniej O (n lg n) algorytmie mnożenia?
Niedawny post na łamigłówce dotyczący znalezienia trzech równomiernie rozłożonych prowadzi mnie do pytania o przepełnienie stosu z najlepszą odpowiedzią, która twierdzi, że zrobię to w czasie O (n lg n). Interesujące jest to, że rozwiązanie polega na podniesieniu kwadratu do wielomianu, odnosząc się do artykułu opisującego, jak to zrobić w …
3
Obliczanie najdłuższego wspólnego podłańcucha dwóch łańcuchów przy użyciu tablic sufiksów
Po tym, jak nauczyłem się, jak budować tablicę sufiksów w złożoności , jestem zainteresowany odkrywaniem zastosowania tablic sufiksów. Jednym z nich jest znalezienie najdłuższego wspólnego podłańcucha między dwoma łańcuchami w czasie . W Internecie znalazłem następujący algorytm:O(N)O(N)O(N)O(N)O(N)O(N) połącz dwa ciągi AAA i BBB w jeden ciąg ABABAB obliczyć tablicę przyrostków …
1
Znajdź proste cykle na wykresie ukierunkowanym
Dla mnie ten problem wygląda bardzo interesująco. Już miał znaleźć prosty cykl (tj. Cykl, w którym nie ma powtarzalnych węzłów) na ukierunkowanym wykresie. Moje rozwiązanie wygląda następująco, tzn. Ten wykres jest problemem przypadku: Wiem, że na wykresie jest cykl, w którym można znaleźć „tylne krawędzie” w wyszukiwaniu z głębokością pierwszą …
6
Czy może istnieć idealny algorytm szachowy?
Aktualne algorytmy szachowe idą około 1 lub może 2 poziomy w dół drzewa możliwych ścieżek w zależności od ruchów gracza i ruchów przeciwnika. Powiedzmy, że mamy moc obliczeniową do opracowania algorytmu, który przewiduje wszystkie możliwe ruchy przeciwnika w grze w szachy. Algorytm, który ma wszystkie możliwe ścieżki, które przeciwnik może …
2
Dlaczego w twierdzeniu głównym występuje warunek regularności?
Czytałem Wstęp do algorytmów Cormena i in. i czytam twierdzenie Twierdzenia Mistrza zaczynające się na stronie 73 . W przypadku 3 istnieje również warunek regularności, który należy spełnić, aby zastosować twierdzenie: ... 3. Jeśli fa( n ) = Ω ( nlogba + ε)fa(n)=Ω(nlogb⁡za+ε)\qquad \displaystyle f(n) = \Omega(n^{\log_b a + \varepsilon}) …
4
Biorąc pod uwagę zestaw zestawów, znajdź najmniejsze zestawy zawierające co najmniej jeden element z każdego zestawu
Biorąc pod uwagę zestaw zestawów, chciałbym znaleźć zestaw takie, że każdy zbiór w zawiera co najmniej jeden element . Chciałbym również, aby zawierał jak najmniej elementów, jednocześnie spełniając to kryterium, chociaż może istnieć więcej niż jeden najmniejszy z tą właściwością (rozwiązanie niekoniecznie jest unikalne).S.S.\mathbf{S}M.M.MS.S.SS.S.\mathbf{S}M.M.MM.M.MM.M.M Jako konkretny przykład, załóżmy, że zestaw …
1
Wszyscy żołnierze powinni strzelać w tym samym czasie
Kiedy byłem studentem, widziałem problem w podręczniku do projektowania systemów cyfrowych / logiki, dotyczący N żołnierzy stojących w rzędzie i chcących strzelać w tym samym czasie. Trudniejszą wersją tego problemu było to, że żołnierze stoją w ogólnej sieci zamiast w rzędzie. Jestem pewien, że to klasyczny problem, ale nie pamiętam …
1
Znajdź najdłuższą ścieżkę od korzenia do liścia na drzewie
Mam drzewo (w sensie teorii grafów), takie jak następujący przykład: Jest to ukierunkowane drzewo z jednym węzłem początkowym (korzeń) i wieloma końcowymi węzłami (liście). Każda krawędź ma przypisaną długość. Moje pytanie brzmi: jak znaleźć najdłuższą ścieżkę, zaczynając od korzenia i kończąc na którymś z liści? Podejście brutalnej siły polega na …
2
Przecięcie okręgu z algorytmem linii przeciągnięcia
Niestety nadal nie jestem tak silny w zrozumieniu algorytmu linii przeciągania . Wszystkie artykuły i podręczniki na ten temat są już przeczytane, jednak ich zrozumienie jest wciąż bardzo odległe. Aby to wyjaśnić, próbuję rozwiązać jak najwięcej ćwiczeń. Ale naprawdę interesujące i ważne zadania wciąż stanowią dla mnie wyzwanie. Poniższe ćwiczenie …
3
Jak podejść do problemów związanych z dynamicznym wykresem
Zadałem to pytanie przy ogólnym przepełnieniu stosu i skierowano mnie tutaj. Świetnie będzie, jeśli ktoś będzie w stanie wyjaśnić, w jaki sposób ogólnie podejść do częściowych lub w pełni dynamicznych problemów graficznych. Na przykład: Znajdź najkrótszą ścieżkę między dwoma wierzchołkami na niekierowanym wykresie ważonym dla wystąpień, gdy krawędź jest usuwana …
3
Czy drzewo można przemierzać bez rekurencji, stosu lub kolejki, a jedynie garść wskazówek?
Pół dekady temu siedziałem w klasie struktur danych, w której profesor oferował dodatkowy kredyt, jeśli ktokolwiek mógł przemierzać drzewo bez użycia rekurencji, stosu, kolejki itp. (Lub innych podobnych struktur danych) i tylko kilka wskazówek. Wpadłem na to, co uważałem za oczywistą odpowiedź na to pytanie, które ostatecznie zostało zaakceptowane przez …
2
Sterta - Daj algorytmowi
Najprawdopodobniej pytanie to zostało zadane wcześniej. Pochodzi z problemu CLRS (2nd Ed) 6.5-8 - Podaj algorytm czasu O(nlgk)O(nlg⁡k)O(n \lg k) , aby połączyć kkk sortowanych list w jedną posortowaną listę, gdzie nnn jest całkowitą liczbą elementów na wszystkich listach wejściowych. (Wskazówka: użyj min-sterty do scalania -way.)kkk Ponieważ istnieje list posortowanych …
5
Jakie jest znaczenie ujemnych krawędzi masy na wykresie?
Robiłem ćwiczenia programowania dynamicznego i znalazłem algorytm Floyda-Warshalla. Najwyraźniej znajduje wszystkie pary najkrótszych ścieżek dla wykresu, który może mieć ujemne krawędzie wagi, ale nie ma ujemnych cykli. Zastanawiam się więc, jakie jest rzeczywiste znaczenie ujemnych krawędzi wagi? Przydałoby się proste angielskie wyjaśnienie.
2
Czy ten program zakończy się z każdą liczbą całkowitą?
W częściowym teście na przygotowanie GATE pojawiło się pytanie: f(n): if n is even: f(n) = n/2 else f(n) = f(f(n-1)) Odpowiedziałem: „Zakończy się dla wszystkich liczb całkowitych”, ponieważ nawet w przypadku niektórych liczb całkowitych ujemnych zakończy się jako Błąd przepełnienia stosu . Ale mój przyjaciel nie zgodził się z …
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.