Twoim zadaniem tutaj będzie zaimplementowanie funkcji 1, która tworzy permutację na dodatnich liczbach całkowitych (bijection z dodatnich liczb całkowitych na siebie). Oznacza to, że każda dodatnia liczba całkowita powinna pojawić się dokładnie raz w permutacji. Złap to twoja funkcja powinna mieć większe prawdopodobieństwo wyprowadzenia liczby nieparzystej niż liczba parzysta.
Teraz może się to wydawać dziwne lub niemożliwe. Z pewnością jest tyle samo liczb nieparzystych, co liczb parzystych? I chociaż ta intuicja jest poprawna dla zbiorów skończonych, tak naprawdę nie obowiązuje dla zbiorów nieskończonych. Na przykład weź następującą permutację:
1 3 2 5 7 4 9 11 6 13 15 8 17 19 10 21 23 12 25 27 14 29 31 16 33 35 18 37 39 20 41 43 22 45 47 24 49 51 26 53 55 ...
Jeśli weźmiesz podsekcję sekwencji o rozmiarze większym niż , będziesz mieć co najmniej tyle nieparzystych liczb, co liczb parzystych, więc wydaje się, że prawdopodobieństwo dowolnego nieparzystego wyrażenia jest większe niż bycie parzystym. Zauważysz również, że każda liczba nieparzysta lub parzysta ostatecznie pojawi się w sekwencji i może pojawić się tylko raz. Zatem sekwencja jest prawdziwą permutacją.
Definicja prawdopodobieństwa
Aby uniknąć zamieszania lub dwuznaczności, zamierzam jasno wyjaśnić, co oznacza prawdopodobieństwo w tym pytaniu.
Powiedzmy, że mamy funkcję . Prawdopodobieństwo, że liczba będzie nieparzysta, zostanie zdefiniowane jako granica stosunku nieparzystych elementów zbioru do wielkości zbioru gdy zmierza w kierunku nieskończoności.
Na przykład wyżej wspomniana funkcja miałaby prawdopodobieństwo nieparzystości .
To jest golf golfowy, więc odpowiedzi będą liczone w bajtach, przy czym mniej bajtów będzie lepszych.
Dodatkowe wyzwania
Oto kilka zabawnych pomysłów do zabawy i być może próby wdrożenia. Są one dla zabawy i nie wpływają w żaden sposób na zdobywanie punktów. Niektóre z nich nie są nawet prawidłowymi rozwiązaniami tego wyzwania, a odpowiedź, która obejmuje tylko rozwiązania problemów 2 lub 3, nie jest prawidłową odpowiedzią i może zostać usunięta .
Napisz permutację z dziwnym prawdopodobieństwem . (to jest możliwe)
Napisz permutację, która ma więcej nieparzystych liczb niż parzystych w dla dowolnego ale ma nieparzyste prawdopodobieństwo .
Napisz permutację, która nie ma zdefiniowanego prawdopodobieństwa (czyli nie ma limitu).
1: Tutaj funkcja oznacza program lub funkcję. To tylko fragment kodu, który pobiera dane wejściowe i generuje dane wyjściowe.
Łuska ,
1110 bajtów-1 bajt dzięki Leo i nieco innej funkcji
Ma to dziwne prawdopodobieństwo
1
Wypróbuj online!
Indeksuje sekwencję:
Wyjaśnienie
źródło
Haskell,
353432 bajtówImplementuje przykładową sekwencję
[1,3,2,5,7,4,9,11,6,13,15,8,17,19,10,21,...]
.Wypróbuj online!
Dla odniesienia: stara wersja, 34 bajty (-1 bajt dzięki @xnor):
Wypróbuj online!
źródło
(!!)$do ...
Łuska , 8 bajtów
Wypróbuj online!
To implementuje przykładową sekwencję (
1,3,2,5,7,4...
).Wyjaśnienie
źródło
Wszyscy wykonują Wyzwanie 1, więc zróbmy pozostałe dwa.
Perl 6 , 26 bajtów - wyzwanie 2
Wypróbuj online!
Po prostu
1 3 2 5 4 7 6...
w parzystej liczbie przypadków zawsze są 2 liczby nieparzyste niż parzyste. W liczbie nieparzystej 1 więcej. Ma to jednak wyraźnie limit(n+2)/(2n+2) -> ½
.Perl 6 , 70 bajtów - Wyzwanie 3
Wypróbuj online!
Trzeba przyznać, że gra w golfa jest straszna. Indeksuje sekwencję, która zawiera 2⁰ liczb nieparzystych, następnie 2¹ parzystych, następnie 2² nieparzystych, następnie 2³ parzystych i tak dalej.
Prawdopodobieństwo po n takich „blokach”, jeśli n jest nieparzyste, wynosi (2⁰ + 2² + 2⁴ + ... + 2ⁿ⁻¹) / (2ⁿ-1). Suma w liczniku jest równa ⅓ (4 ½ (n + 1) - 1) = ⅓ (2 n + 1 - 1). Prawdopodobieństwo po nieparzystej liczbie bloków wynosi ⅔ (w limicie).
Jeśli dodamy jeszcze jeden blok (i uzyskamy parzystą liczbę n + 1), nie dodamy jednak żadnych liczb nieparzystych (licznik pozostaje taki sam), ale teraz jest (2 n + 1 - 1) liczb w sumie . Nawiasy są anulowane i otrzymujemy prawdopodobieństwo ⅓ (w limicie).
Najwyraźniej ma to mieć 2 różne punkty skupienia ⅓ i ⅔, aby upewnić się, że limit nie istnieje, ale tak naprawdę to nie dowodzi. Moja próba zrobienia solidnego, rygorystycznego dowodu znajduje się w tej odpowiedzi Math.SE: https://math.stackexchange.com/a/2416990/174637 . Mile widziane błędy.
Perl 6 , 39 bajtów - podstawowe wyzwanie.
Wypróbuj online!
Chociaż zamieściłem tę odpowiedź z powodu wyzwań 2 i 3, które stanowiły przyjemną małą łamigłówkę mathy, istnieje ścisły wymóg, aby wszystkie odpowiedzi zawierały rozwiązanie podstawowego wyzwania. Oto jest.
To jest przykładowa sekwencja.
źródło
Brain-Flak , 120 bajtów
Wypróbuj online!
Wykonuje następującą funkcję:
Ta funkcja generuje sekwencję
Funkcja ma dziwne prawdopodobieństwo
1
źródło
R, 82 bajty (dodatkowe wyzwanie 1)
Wypróbuj online!
Jeśli wejście jest idealnym kwadratem, podaje liczbę parzystą. W przeciwnym razie podaje liczbę nieparzystą. Idealne kwadraty mają naturalną gęstość 0, co oznacza, że ta sekwencja daje liczby nieparzyste z prawdopodobieństwem 1.
źródło
C (gcc) , 29 bajtów
Wypróbuj online!
Co czwarta liczba to nawet:
Dodatkowe wyzwanie 1, 52 bajty
Wypróbuj online!
Zwraca 2 * (x + 1), jeśli n jest równe 2 x, a kolejne liczby nieparzyste w przeciwnym razie:
źródło
Brain-Flak ,
140138136 bajtówWypróbuj online!
Wyjaśnienie
Pełni tę funkcję podobną do tej sugerowanej w pytaniu.
Działa głównie w oparciu o fragment, który zrobiłem, aby rzucić stos dla stosów rozmiaru 3.
Ustawiliśmy dwa stosy, jeden z wartościami akumulatorów (dwa parzyste nieparzyste) i jeden z liczbami
4 4 2
. W każdej iteracji rzucamy obydwoma stosami i dodajemy górę lewego stosu do góry prawego stosu.To zwiększy każdą nieparzystą liczbę o 4, a jedną parzystą liczbę o 2. Gdy przechodzimy przez pętlę, otrzymujemy wzór 2 nieparzystych 1 parzystych, z każdą trafioną dodatnią liczbą całkowitą. Tak więc po prostu zapętlamy
n
czasy,n
będąc wejściowymi. Ma to asymptotyczne prawdopodobieństwo 2/3 .źródło
Galaretka , 10 bajtów
Prawdopodobieństwo szans wynosi 2/3 .
Wypróbuj online!
Jak to działa
źródło
C, 80 bajtów
Implementacja przykładowej permutacji z pytania.
Wypróbuj online!
źródło
Partia, 36 bajtów
Realizuje sekwencję podaną w pytaniu.
źródło
JavaScript, 23 bajty
Wyjście: 1, 3, 5, 2, 7, 9, 11, 4, 13, 15, 17, 6, 19, 21, 23, 8 ...
Wyzwanie 2:
Wyjście: 1, 3, 2, 5, 4, 7, 6, 9, 8, 11, 10, 13, 12, 15, 14
źródło
n=>n%4?1.5*n|1:n/2
jest o 5 bajtów krótszy.CJam (21 bajtów)
Demo online pokazujące pierwsze 32 wyniki. To anonimowy blok (funkcja).
Jest to również rozwiązanie dla wyzwania 1: liczby odwzorowane na liczby parzyste są potęgami 2, więc gęstość liczb parzystych na pierwszych n wyjściach wynosi lg (n) / n, który dąży do zera.
Sekcja
źródło
Perl 40 bajtów
źródło
Brain-Flueue , 88 bajtów
Wypróbuj online!
Wyjaśnienie
To implementuje tę samą funkcję, co moja ostatnia odpowiedź, ale używa modelu FIFO firmy Brain-Flueue, aby skrócić niektóre rogi. Oto kilka pierwszych warunków, które generuje.
Pierwsza część kodu to tylko trochę instalacji, kładziemy
0,-1,-3
na pierwszym stosie i2,4,4
na drugim stosie.2,4,4
Zostaną wykorzystane do przechodzenia parzystych i nieparzystych numerów tak jak ja w moim Brain-Flak odpowiedź.Następnie zapętlamy n razy, za każdym razem dodając górę lewego stosu do prawego stosu. Ponieważ Brain-Flueue używa kolejek zamiast stosów, wartości naturalnie rzutują się, gdy ich dotykamy, zapobiegając potrzebie dodatkowego kodu.
źródło
-lflueue
Argument.Python 2 ,
4610455 bajtówWypróbuj online!
Źle odczytałem pytanie, teraz poprawnie zaimplementowałem funkcję, której można użyć do wygenerowania sekwencji zamiast takiej, która generuje sekwencję. Wyłączone również
0
z zestawu możliwych wyników.Prawdopodobieństwo znalezienia nieparzystej dodatniej liczby całkowitej jest teraz zbieżne z
1
.źródło
0
.Galaretka , 9 bajtów
Wypróbuj online!
Implementuje
1, 3, 2, 5, 7, 4, 9, 11, 6, ...
(prawdopodobieństwo 2/3).źródło
05AB1E , 11 bajtów
Wypróbuj online!
źródło
Pyth , 9 bajtów
Wypróbuj tutaj! lub Przetestuj więcej za jednym razem!
Możesz użyć tego kodu, aby sprawdzić stosunek liczb nieparzystych do pewnego punktu. Zastąp
10000
żądany limit (nie ustawiaj go znacznie wyżej, ponieważ to błędy pamięci).Wypróbuj tutaj .
Powyższe daje z grubsza 0,667 . Rzeczywiste prawdopodobieństwo wystąpienia nieparzystych zdarzeń wynosi 2/3 . To podejście stanowi równoważne wdrożenie odpowiedzi Dennisa .
Wyjaśnienie
źródło
Java 8, 20 bajtów
Odpowiedź C na port @nwellnhof .
Niektóre rzeczy, które sam próbowałem, skończyły się bajtami dłuższymi lub nieco niepoprawnymi.
Implementuje:
1,3,5,2,7,9,11,4,13,15,17,6,19,21,23,8,25,27,29,10,31,33,35,12,37,...
z prawdopodobieństwem
3/4
.Wypróbuj tutaj.
źródło
Lua,
6753 bajtówWyjaśnienie nadchodzi, kiedy skończę grać w golfa :)Ten program pobiera jako dane wejściowe liczbę całkowitą za pomocą argumentów wiersza poleceń i wypisuje n-ty element przykładowej sekwencji na STDOUT
Objaśnienia
Liczby parzyste w tej sekwencji są zarówno
n
liczbą parzystą, jak in
wielokrotnością liczby 3, dlatego wzórn%3*2
jest wystarczający do ich wygenerowania.W przypadku liczb nieparzystych jest to trochę trudniejsze. W oparciu o fakt, że możemy je znaleźć w zależności od prądu
n
, mamy następującą tabelę:Nazwijmy wartość
target-n
i
, którą widzimy za każdym razemn%3==2
,i
jest zwiększana. Oto nasza formuła:Liczby nieparzyste są oparte
n
na których dodajemyi
.Wartość
i
przyrostów w tym samym tempie, co podział euklidesowy o 3, z przesunięciem.math.floor(n/3)
daje nam tempo przyrostu in%3-1
daje nam przesunięcie, dzięki czemu dzieje się takn%3==2
zamiastn%3==0
.źródło
...and (n/...
).and n/3*2or
działa równie dobrze