Matematyka.pl

Zrób to prościej i szybciej Masz tablice A, B i C. Przygotowujesz sobie trzy wskaźniki i, j, k i ustawiasz na 1. I teraz: Jeśli A = B[j] = C[k], to znalazłeś dobry element. Jeśli te trzy liczby nie są wszystkie równe, to zwiększasz o 1 wskaźnik najmniejszej - ona się już na pewno nie przyda. Powtarz...

Żeby policzyć złożoność średnią algorytmu, musisz wiedzieć, jak losowane są liczby do tablic. Dlatego nazywa się "średnia" - musi być średnią po czymś

A swoją drogą, pojęcie złożoności optymistycznej jest nieco dziwne, nigdy nie spotkałem się, żeby ktoś liczył to na poważnie.

Nie, dalej jest "różnicy bezw." Nie ma czegoś takiego jak "różnica bezwzględna".
Ale jeśli chodzi po prostu o maksymalną różnicę to tak, wystarczy odjąć pierwszy od ostatniego.

"maksymalną bezwzględną wartość różnicy" czy "maksymalną różnicę wartości bezwzględnych"?

Skąd masz informację, że nie znaleziono? Każdą funkcję rekurencyjną można zamienić na iterację, choćby z użyciem stosu.

Zadanie I-4. Mam nadzieję, że dobrze. Oznaczmy sobie f(x) = x^{x-1} \mod k . Musimy znaleźć takie k , dla których f(1), \ldots, f(k) są różne, czyli f musi być bijekcją na zbiorze \{1,\ldots,k-1\} . Załóżmy od razu, że k > 3 - liczby 2 i 3 spełniają warunek zadania. Przede wszystkim widać, że k jest...

Można zupełnie inaczej do tego podejść. Weźmy najmniejszy dodatni mianownik q , dla którego istnieje takie p , że \sqrt{2} = \frac{p}{q} . Zauważmy przy tym, że ponieważ \sqrt{2}<2 , mamy p<2q . Ale wtedy p^2 = 2q^2 , a stąd wynika, że \frac{p}{q} = \frac{2q-p}{p-q} . Czyli istnieje ułamek, który te...

Chyba tak źle nie jest Dla ustalonych b, c, d istnieje dokładnie jedno a takie, żeby suma się zgadzała. Rozwiązań jest zatem nieskończenie wiele. Jeśli ograniczymy się do liczb nieujemnych, to b, c, d muszą być nie za duże - liczba rozwiązań to jakaś taka nieprzyjemna suma, ale też nic odkrywczego.

Oj, odróżniam jedno od drugiego, spokojnie. Faktycznie, świetny pomysł, aczkolwiek można go uciąć już po stwierdzeniu "grupa ma rząd 2, więc jest przemienna, czyli ciąg możemy permutować jak chcemy..." Oraz nie unikniemy argumentowania, że działanie na klasach abstrakcji jest dobrze zdefin...

Eee, mnie uczono, że grupa powinna mieć jakieś działanie

Jak ktoś słusznie zauwazył w 3 mogą być redukcje za zapis. Jedną z metod poprawnego zapisu prezentowanego tu kilkakrotnie pomysłu jest naturalne przyporządkowanie każdemu ciągowi liczby w systemie dziesiętnym i zauważenie, że wykonanie opisanej tu wielokrotnie operacji zamiany cyfr zmniejsza tę lic...

Można to zapisać dużo prościej - udowodnimy, że dowolna liczba \(\displaystyle{ a}\) jest wartością funkcji \(\displaystyle{ f}\).
Skoro \(\displaystyle{ g}\) jest surjekcją, to w szczególności przyjmuje wartość \(\displaystyle{ a+1}\) dla pewnego \(\displaystyle{ x}\). Stąd \(\displaystyle{ g(x) = a+1}\), czyli \(\displaystyle{ f(f(x)-1)+1 = a+1}\), a zatem \(\displaystyle{ f(f(x)-1) = a}\). Czyli dla \(\displaystyle{ y = f(x)-1}\) mamy \(\displaystyle{ f(y)=a}\).

Prawie. Jeśli zbiór \(\displaystyle{ X}\) miał \(\displaystyle{ 2^{n-1}}\) podzbiorów parzystych i nieparzystych, to \(\displaystyle{ X \cup \{a\}}\) będzie miał dalej te podzbiory, a oprócz tego "nowe" parzyste, i "nowe" nieparzyste, znowu po tyle samo.

Załóżmy, że każdy zbiór n-elementowy ma \(\displaystyle{ 2^{n-1}}\) podzbiorów parzystych i tyle samo nieparzystych. Jeśli teraz dorzucimy do niego jeden element, to ile i jakich pojawi się nowych podzbiorów?

W pierwszym połącz podzbiory w pary: zbiór zawierający \(\displaystyle{ a}\) z nie zawierającym.
W drugim ładnie działa indukcja matematyczna.