Informatyka integers

2

Wydajny algorytm do „sumowania” zestawu sum

Biorąc pod uwagę zbiór wielu liczb naturalnych X, rozważ zestaw wszystkich możliwych sum: sums(X)={∑i∈Ai|A⊆X}sums(X)={∑i∈Ai|A⊆X}\textrm{sums}(X)= \left\{ \sum_{i \in A} i \,|\, A \subseteq X \right\} Na przykład podczas gdy .sumy ( { 1 , 1 } ) = { 0 , 1 , 2 }sums({1,5})={0,1,5,6}sums({1,5})={0,1,5,6}\textrm{sums}(\left\{1,5\right\}) = \left\{0, 1, 5, 6\right\}sums({1,1})={0,1,2}sums({1,1})={0,1,2}\textrm{sums}(\left\{1,1\right\}) = …

24 algorithms optimization combinatorics integers

3

Algorytm minimalizujący pole powierzchni, przy danej objętości

Rozważ następujące zadanie algorytmiczne: Dane wejściowe: dodatnia liczba całkowita wraz z podstawową faktoryzacją Znajdź: dodatnie liczby całkowite które minimalizują , z zastrzeżeniem ograniczenia, żennnx,y,zx,y,zx,y,zxy+yz+xzxy+yz+xzxy+yz+xzxyz=nxyz=nxyz=n Jaka jest złożoność tego problemu? Czy istnieje algorytm czasu wielomianowego? Czy to trudne NP? Ten problem zasadniczo pyta: ze wszystkich prostokątnych brył, których objętość wynosi i …

22 algorithms optimization integers

3

Jaki jest najskuteczniejszy sposób obliczenia silni modulo a prime?

Czy znasz jakiś algorytm, który skutecznie oblicza silnię po module? Na przykład chcę zaprogramować: for(i=0; i<5; i++) sum += factorial(p-i) % p; Ale pjest duża liczba (prime) stosowania bezpośrednio silnia (p≤108)(p≤108)(p \leq 10^ 8) . W Pythonie to zadanie jest naprawdę łatwe, ale naprawdę chcę wiedzieć, jak zoptymalizować.

20 algorithms efficiency integers

2

Reprezentowanie liczb ujemnych i zespolonych za pomocą rachunku Lambda

Większość samouczków na temat rachunku Lambda stanowi przykład, w którym dodatnie liczby całkowite i liczby boolowskie mogą być reprezentowane przez funkcje. Co z -1 i ja?

14 data-structures lambda-calculus integers real-numbers

3

Określ brakującą liczbę w strumieniu danych

Otrzymujemy strumień n−1n−1n-1 par różnych liczb ze zbioru {1,…,n}{1,…,n}\left\{1,\dots,n\right\} . Jak mogę ustalić brakującą liczbę za pomocą algorytmu, który odczytuje strumień raz i wykorzystuje pamięć tylko bitów?O(log2n)O(log2⁡n)O(\log_2 n)

14 algorithms integers online-algorithms

1

Bezpieczne podsumowanie przelewu

Załóżmy, że podano mi liczb całkowitych o stałej szerokości (tzn. Mieszczą się one w rejestrze szerokości ), tak że ich suma również mieści się w rejestrze szerokości .w a 1 , a 2 , … a n a 1 + a 2 + ⋯ + a n = S wnnnwwwa1,a2,…ana1,a2,…ana_1, …

13 algorithms arrays integers numerical-analysis

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< cre⟺d< c bzab<dore⟺zare<dob \begin{eqnarray*} \frac a b < \frac c d &\iff& ad < cb \end{eqnarray*} Moje pytania to: Biorąc pod uwagęa , b , c …

12 algorithms integers

3

Liczba multisetów, dzięki czemu każda liczba od 1 do może być jednoznacznie wyrażona jako suma niektórych elementów multisetu

Mój problem. Biorąc pod uwagę, , chcę policzyć ważny multisets . Multiset jest ważny, jeślin nnS SSSSS Suma elementów wynosi , iS SSnnn Każdy numer od do może być wyrażona jednoznacznie jako sumę niektórych elementów .1 11n nnS.SS Przykład. Na przykład, jeśli to są poprawne.n = 5 n=5n=5{ 1 , …

11 algorithms integers

4

Najbardziej wydajny algorytm do drukowania 1-100 przy użyciu danego generatora liczb losowych

Dostajemy generator liczb losowych, RandNum50który generuje losową liczbę całkowitą równomiernie w zakresie 1–50. Możemy używać tylko tego generatora liczb losowych do generowania i drukowania wszystkich liczb całkowitych od 1 do 100 w losowej kolejności. Każda liczba musi przyjść dokładnie raz, a prawdopodobieństwo wystąpienia dowolnej liczby w dowolnym miejscu musi być …

11 algorithms integers randomness random-number-generator

3

Jaka struktura danych skutecznie przechowuje zakresy liczb całkowitych?

Muszę przechowywać kolekcję liczb całkowitych z zakresu od 0 do 65535, aby móc szybko wykonać następujące czynności: Wstaw nową liczbę całkowitą Wstaw zakres ciągłych liczb całkowitych Usuń liczbę całkowitą Usuń wszystkie liczby całkowite poniżej liczby całkowitej Sprawdź, czy występuje liczba całkowita Moje dane mają tę właściwość, że często zawierają ciągi …

10 data-structures efficiency search-trees integers

2

Złożoność obliczeń

Jaka jest złożoność obliczeń ?nn2,n∈Nnn2,n∈Nn^{n^2},\;n \in \mathbb{N}

10 complexity-theory integers number-theory

5

Język wartości funkcji afinicznej

Napisz n¯n¯\bar n dla dziesiętnego rozszerzenia nnn (bez wiodącego 0). Niech aaa i bbb będą liczbami całkowitymi o a>0a>0a > 0 . Rozważmy język rozwinięć dziesiętnych wielokrotności plus stałej:aaa M={ax+b¯¯¯¯¯¯¯¯¯¯¯¯¯¯∣x∈N}M={ax+b¯∣x∈N}M = \{ \overline{a\,x+b} \mid x\in\mathbb{N} \} Czy MMM regularne? bez kontekstu? (Kontrast z językiem wykresu funkcji afinicznej ) Myślę, że …

10 formal-languages context-free regular-languages integers

1

Jakie istnieją algorytmy rozwiązywania układów liniowych z liczbami naturalnymi?

Patrzę na następujący problem: Biorąc pod uwagę wymiarowe wektory liczb naturalnych i niektóre wektory wejściowe , czy jest liniową kombinacją z współczynnikami liczb naturalnych?nnnv1,…,vmv1,…,vmv_1, \ldots, v_muuuuuuviviv_i tzn. czy są jakieś gdzie ?t1,…,tm∈Nt1,…,tm∈Nt_1, \ldots, t_m \in \mathbb{N}u=t1v1+⋯+tmvmu=t1v1+⋯+tmvmu = t_1 v_1 + \dots + t_m v_m Oczywiście rzeczywistą wersję tego problemu można …

9 algorithms reference-request linear-algebra integers knapsack-problems

Pytania otagowane jako integers