Liczby katalońskie

36

Te numery Kataloński ( OEIS ) to sekwencja liczb naturalnych, często występujących w kombinatoryki.

N-ta liczba katalońska to liczba słów Dyck (zrównoważone ciągi nawiasów lub nawiasów, takie jak [[][]]; formalnie zdefiniowane jako ciąg znaków przy użyciu dwóch znaków a i b tak, że dowolny ciąg znaków rozpoczynający się od początku ma liczbę znaków większą lub równą liczbie znaków b, a cały łańcuch ma taką samą liczbę znaków aib) o długości 2n. N-ta liczba katalońska (dla n> = 0) jest również wyraźnie zdefiniowana jako:

Począwszy od n = 0, pierwsze 20 liczb katalońskich to:

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190...

Wyzwanie

Napisz pełny program lub funkcję, która przyjmuje nieujemną liczbę całkowitą n przez STDIN lub akceptowalną alternatywę i wyprowadza ntą liczbę katalońską. Twój program musi działać co najmniej dla wejść 0–19.

I / O

Wkład

Twój program musi pobierać dane wejściowe z STDIN, argumenty funkcji lub dowolne z dopuszczalnych alternatyw dla tego meta postu. Wprowadzoną liczbę można odczytać jako jej standardową reprezentację dziesiętną, jedność lub bajty.

  • Jeśli (i tylko jeśli) twój język nie może pobierać danych wejściowych ze STDIN lub jakiejkolwiek akceptowalnej alternatywy, może pobierać dane wejściowe ze zmiennej zakodowanej na stałe lub odpowiedniego odpowiednika w programie.

Wydajność

Twój program musi wypisać n-ty kataloński numer do STDOUT, wyniku funkcji lub dowolnej z dopuszczalnych alternatyw dla tego meta-postu. Możesz wypisać liczbę katalońską w jej standardowej reprezentacji dziesiętnej, jedności lub bajtach.

Wynik powinien składać się z odpowiedniej liczby katalońskiej, po której opcjonalnie może następować jedna lub więcej nowych linii. Żadne inne dane wyjściowe nie mogą być generowane, z wyjątkiem stałych wyników tłumacza języka, których nie można stłumić (takich jak powitanie, kody kolorów ANSI lub wcięcia).


Tu nie chodzi o znalezienie najkrótszego języka. Chodzi o znalezienie najkrótszego programu w każdym języku. Dlatego nie przyjmuję odpowiedzi.

W tym wyzwaniu języki nowsze niż wyzwanie są dopuszczalne, o ile mają implementację. Dozwolone jest (a nawet zachęcane) samodzielne pisanie tego tłumacza dla wcześniej niewdrożonego języka. Poza tym należy przestrzegać wszystkich standardowych zasad gry w . Zgłoszenia w większości języków będą oceniane w bajtach w odpowiednim wcześniej istniejącym kodowaniu (zwykle UTF-8). Należy również pamiętać, że wbudowane metody obliczania n-tej liczby katalońskiej są dozwolone.

Katalog

Fragment kodu na dole tego postu generuje katalog na podstawie odpowiedzi a) jako listy najkrótszych rozwiązań według języka oraz b) jako ogólnej tabeli wyników.

Aby upewnić się, że twoja odpowiedź się pojawi, zacznij od nagłówka, korzystając z następującego szablonu Markdown:

## Language Name, N bytes

gdzie Njest rozmiar twojego zgłoszenia. Jeśli poprawić swój wynik, to może zachować stare porachunki w nagłówku, uderzając je przez. Na przykład:

## Ruby, <s>104</s> <s>101</s> 96 bytes

Jeśli chcesz umieścić w nagłówku wiele liczb (np. Ponieważ twój wynik to suma dwóch plików lub chcesz osobno wymienić kary za flagi tłumacza), upewnij się, że rzeczywisty wynik jest ostatnią liczbą w nagłówku:

## Perl, 43 + 2 (-p flag) = 45 bytes

Możesz także ustawić nazwę języka jako link, który pojawi się we fragmencie:

## [><>](http://esolangs.org/wiki/Fish), 121 bytes

spaghetto
źródło
Czy możemy wydrukować / zwrócić liczbę zmiennoprzecinkową zamiast liczby całkowitej?
Alex A.,
@AlexA. To jest do przyjęcia.
spaghetto
Czy powinna istnieć tag oeis ?
Vi.
1
@Vi. Jakiś czas temu odbyła się na ten temat meta dyskusja i zgodziliśmy się, że oeis jest niepotrzebny
spaghetto
@Vi. Oto post z meta: meta.codegolf.stackexchange.com/a/5546/8478 . Jeśli chodzi o pewne rozumowanie, wyzwania w stylu OEIS można znaleźć całkiem niezawodnie, jeśli chodzi o sekwencję i jedną z teorii liczb lub teorii liczb . To, czy dana sekwencja rzeczywiście znajduje się w OEIS, jest całkowicie nieistotne dla wyzwania.
Martin Ender,

Odpowiedzi:

26

C, 78 52 39 34 33 bajtów

Jeszcze więcej magii C (dzięki xsot):

c(n){return!n?:(4+6./~n)*c(n-1);}

?: jest rozszerzeniem GNU .


Tym razem rozszerzając ponowny cykl poniżej (dzięki xnor i Thomas Kwa):

jeszcze jedna rekurencja

c(n){return n?(4+6./~n)*c(n-1):1;}

-(n+1)jest zastąpiony przez ~n, co jest równoważne uzupełnieniu dwóch i pozwala zaoszczędzić 4 bajty.


Ponownie jako funkcja, ale tym razem wykorzystując następującą powtarzalność:

powtarzać się

c(n){return n?2.*(2*n++-1)/n*c(n-2):1;}

c(n)wchodzi w nieskończoną rekurencję jako negatywną n, chociaż nie ma to znaczenia dla tego wyzwania.


Ponieważ wywoływanie funkcji wydaje się akceptowalną alternatywą dla konsoli I / O:

c(n){double c=1,k=2;while(k<=n)c*=1+n/k++;return c;}

c(n)bierze inti zwraca an int.


Oryginalny wpis:

main(n){scanf("%d",&n);double c=1,k=2;while(k<=n)c*=1+n/k++;printf("%.0f",c);}

Zamiast bezpośrednio obliczać definicję, formuła jest przepisywana jako:

przepisać

Formuła zakłada n >= 2, ale kod stanowi n = 0i n = 1zbyt.

W bałaganie C powyżej ni kpełnią tę samą rolę, co w formule, jednocześnie ckumulując produkt. Wszystkie obliczenia są wykonywane przy użyciu liczb zmiennoprzecinkowych double, co prawie zawsze jest złym pomysłem, ale w tym przypadku wyniki są poprawne do co najmniej n = 19, więc jest w porządku.

float zaoszczędziłby 1 bajt, niestety nie jest wystarczająco precyzyjny.

Stefano Sanfilippo
źródło
Nie mogę tego teraz przetestować, ale myślę, że można to jeszcze skrócić:c(n){return!n?:(4+6./~n)*c(n-1);}
xsot
Dzięki @xsot, nie wiedziałem ?:! Najwyraźniej jest to rozszerzenie GNU C, ale myślę, że nadal się kwalifikuje.
Stefano Sanfilippo,
23

Galaretka , 4 bajty

Ḥc÷‘

Wypróbuj online!

Jak to działa

Ḥc÷‘    Left argument: z

Ḥ       Compute 2z.
 c      Hook; apply combinations to 2z and z.
  ÷‘    Divide the result by z+1.
Dennis
źródło
1
Co oznacza „haczyk”? Jak rozumieć cget 2zi zjego argumenty?
xnor
@ xnor Hak oznacza funkcje oceniane jak f (x, g (x)). Gdy występuje funkcja dynamiczna, a po niej następna funkcja dynamiczna, parser ocenia pierwszą jako hak.
lirtosiast
5
@Dennis Czy to naprawdę 4 bajty? W przypadku znaków spoza ASCII mothereff.in/byte-counter mówi 9 bajtów
Luis Mendo
@LuisMendo to prawdopodobnie inne kodowanie
undergroundmonorail
3
@LuisMendo Jelly używa własnego, niestandardowego domyślnego kodowania, w którym każdy znak jest pojedynczym bajtem. W przypadku UTF-8 kod źródłowy ma rzeczywiście 9 bajtów.
Dennis,
11

CJam, 12 bajtów

ri_2,*e!,\)/

Wypróbuj online.

Poza wejściem 11 musisz powiedzieć maszynie wirtualnej Java, aby zużywała więcej pamięci. I tak naprawdę nie zalecałbym wychodzenia daleko poza 11. Teoretycznie działa to na dowolne N, ponieważ CJam używa liczb całkowitych o dowolnej precyzji.

Wyjaśnienie

CJam nie ma wbudowanego współczynnika dwumianowego, a obliczenie ich z trzech silni zajmuje dużo bajtów ... więc będziemy musieli zrobić coś lepszego. :)

ri  e# Read input and convert it to integer N.
_   e# Duplicate.
2,  e# Push [0 1].
*   e# Repeat this N times, giving [0 1 0 1 ... 0 1] with N zeros and N ones.
e!  e# Compute the _distinct_ permutations of this array.
,   e# Get the number of permutations - the binomial. There happen to be 2n-over-n of
    e# of them. (Since 2n-over-n is the number of ways to choose n elements out of 2n, and
    e# and here we're choosing n positions in a 2n-element array to place the zeros in.)
\   e# Swap with N.
)/  e# Increment and divide the binomial coefficient by N+1.
Martin Ender
źródło
To jest naprawdę fajne. +1
spaghetto
To jest sprytne. Próbowałem z obliczeniem silni. Zajmuje to tylko dwa ze zwykłych trzech, ponieważ dwa z nich są takie same. Nadal używał 17 bajtów ( ri_2*m!1$m!_*/\)/) w mojej implementacji. Jedyną dobrą rzeczą jest to, że jest znacznie szybsza. :)
Reto Koradi,
11

Mathematica, 16 13 bajtów

CatalanNumber

Wbudowane, amirite fellas: /

Wersja niewbudowana (21 bajtów):

Binomial[2#,#]/(#+1)&

Wersja bez dwumianowa (25 bajtów):

Product[(#+k)/k,{k,2,#}]&
spaghetto
źródło
10

TI-BASIC, 11 bajtów

(2Ans) nCr Ans/(Ans+1

O dziwo, nCr ma wyższy priorytet niż mnożenie.

lirtosiast
źródło
10

Python 3, 33 bajty

f=lambda n:0**n or(4+6/~n)*f(n-1)

Korzysta z nawrotu

f(0) = 1
f(n) = (4-6/(n+1)) * f(n-1)

Podstawowy przypadek 0 jest obsługiwany jako 0**n or, który zatrzymuje się jako 1kiedy, n==0a w przeciwnym razie ocenia wyrażenie rekurencyjne po prawej stronie. Bitowy operator ~n==-n-1skraca mianownik i oszczędza na parenach.

Python 3 jest używany do podziału zmiennoprzecinkowego. Python 2 mógłby zrobić to samo z jeszcze jednym bajtem do napisania 6..

xnor
źródło
Dlaczego nie n<1zamiast 0**n?
feersum,
@feersum Zwraca Truena n==0zamiast 1. Oczywiście, True == 1ale True is not 1i drukuje inaczej. Spodziewałbym się, że to nie będzie dozwolone. Czy wiesz, czy mamy w tej sprawie orzeczenie?
xnor
Uważam, że jest w porządku. isinstance(True, int) is Truepo wszystkim.
feersum,
2
Myślę, że nadal jest niepewny w ogólnym przypadku i więcej tutaj, gdzie wyzwanie określa wynik jako liczbę lub jego reprezentację. Ale do @ quartata
xnor
7

J, 8 bajtów

>:%~]!+:

To jest pociąg monadyczny; wykorzystuje formułę (2x nCr x) / (x + 1). Wypróbuj tutaj .

lirtosiast
źródło
7

pl, 4 bajty

☼ç▲÷

Wypróbuj online.

Wyjaśnienie

W pl, funkcje usuwają argumenty ze stosu i wypychają wynik z powrotem na stos. Zwykle, gdy na stosie nie ma wystarczającej liczby argumentów, funkcja po prostu nie działa. Jednak dzieje się coś wyjątkowego, gdy ilość argumentów na stosie jest jednoznaczna z rodzajem funkcji - zmienna wejściowa _jest dodawana do listy argumentów:

☼ç▲÷

☼      double: takes _ as the argument since there is nothing on the stack
 ç     combinations: since there is only one item on the stack (and arity is 2), it adds _ to the argument list (combinations(2_,_))
  ▲    increment last used var (_)
   ÷   divide: adds _ to the argument list again

W efekcie jest to pseudokod:

divide(combinations(double(_),_),_+1);
spaghetto
źródło
6

Sesos , 94 86 68 bajtów

8 bajtów poprzez zmianę silnidera z wersji 1 na wersję 2.

18 bajtów, obliczając n!(n+1)!w jednym kroku. W dużej mierze inspirowany algorytmem testowania pierwotności Dennisa .

Hexdump:

0000000: 16f8de a59f17 a0ebba 7f4cd3 e05f3f cf0fd0 a0ebde  ..........L.._?......
0000015: b1c1bb 76fe18 8cc1bb 76fe1c e0fbda 390fda bde3d8  ...v.....v.....9.....
000002a: 000fbe af9d1b b47bc7 cfc11c b47bc7 cff1fa e07bda  .......{.....{.....{.
000003f: 39e83e cf07                                       9.>..

Wypróbuj online!

Korzysta ze wzoru a(n) = (2n)! / (n!(n+1)!).

  • Współczynnik: wersja 1 (w miejscu, stała pamięć), wersja 2 (w miejscu, pamięć liniowa)
  • Mnożnik: tutaj (w miejscu, stała pamięć)
  • Dzielnik: tutaj (nie zatrzymuje się, jeśli nie jest podzielny)

Monter

set numin
set numout
get
jmp,sub 1,fwd 1,add 1,fwd 2,add 2,rwd 3,jnz
fwd 1,add 1
jmp
  jmp,sub 1,rwd 1,add 1,rwd 1,add 1,rwd 1,add 1,fwd 3,jnz
  rwd 1,sub 1,rwd 1,sub 1,rwd 1
  jmp,sub 1,fwd 3,add 1,rwd 3,jnz
  fwd 1
jnz
fwd 3
jmp
  jmp
    sub 1,rwd 1
    jmp,sub 1,rwd 1,add 1,rwd 1,add 1,fwd 2,jnz
    rwd 2
    jmp,sub 1,fwd 2,add 1,rwd 2,jnz
    fwd 3
  jnz
  rwd 1
  jmp,sub 1,jnz
  rwd 1
  jmp,sub 1,fwd 2,add 1,rwd 2,jnz
  fwd 3
jnz 
fwd 1
jmp
  jmp,sub 1,fwd 1,add 1,fwd 1,add 1,rwd 2,jnz
  fwd 1,sub 1,fwd 1
  jmp,sub 1,rwd 2,add 1,fwd 2,jnz
  rwd 1
jnz
rwd 2
jmp
  jmp
    sub 1,fwd 1
    jmp,sub 1,fwd 1,add 1,fwd 1,add 1,rwd 2,jnz
    fwd 2
    jmp,sub 1,rwd 2,add 1,fwd 2,jnz
    rwd 3
  jnz
  fwd 1
  jmp,sub 1,jnz
  fwd 1
  jmp,sub 1,rwd 2,add 1,fwd 2,jnz
  rwd 3
jnz 
fwd 1
jmp
  fwd 1,add 1,rwd 3
  jmp,sub 1,fwd 1,add 1,fwd 1,sub 1,rwd 2,jnz
  fwd 1
  jmp,sub 1,rwd 1,add 1,fwd 1,jnz
  fwd 1
jnz
fwd 1
put

Odpowiednik Brainfuck

Ten skrypt Retina jest używany do generowania ekwiwalentu pieprzenia mózgu. Zauważ, że akceptuje tylko jedną cyfrę jako argument polecenia i nie sprawdza, czy polecenie jest w komentarzach.

[->+>>++<<<]>+
[[-<+<+<+>>>]<-<-<[->>>+<<<]>]>>>
[[-<[-<+<+>>]<<[->>+<<]>>>]<[-]<[->>+<<]>>>]>
[[->+>+<<]>->[-<<+>>]<]<<
[[->[->+>+<<]>>[-<<+>>]<<<]>[-]>[-<<+>>]<<<]>
[>+<<<[->+>-<<]>[-<+>]>]>
Leaky Nun
źródło
5

Pyth, 8

/.cyQQhQ

Wypróbuj online lub uruchom pakiet testowy

Wyjaśnienie

/.cyQQhQ   ## implicit: Q = eval(input())
/     hQ   ## integer division by (Q + 1)
 .c        ## nCr
   yQ      ## use Q * 2 as n
     Q     ## use Q as r
FryAmTheEggman
źródło
5

Poważnie, 9 bajtów

,;;u)τ╣E\

Hex Dump:

2c3b3b7529e7b9455c

Wypróbuj online

Wyjaśnienie:

,                   Read in evaluated input n
 ;;                 Duplicate it twice
   u)               Increment n and rotate it to bottom of stack
     τ╣             Double n, then push 2n-th row of Pascal's triangle
       E            Look-up nth element of the row, and so push 2nCn
        \           Divide it by the n+1 below it.
kwintopia
źródło
Możesz zapisać bajt, wykorzystując fakt, że rzędy trójkąta Pascala są symetryczne, więc mediana 2ntrzeciego rzędu to C(2n,n). Zatem: ,;u@τ╣║/dla 8 bajtów.
Mego
Co? Czy 2nCn nie jest maksimum w 2 rzędzie?
kwintopia,
Tak, i to także mediana. Oba i Mdziałałyby.
Mego
@Mego Martwię się o twoją medianę, jeśli coś może być zarówno medianą, jak i maksimum w przypadku, gdy lista nie jest taka sama. Jeśli masz na myśli „na środku listy”, możesz wybrać dla niego inną nazwę ...
kwintopia
Tak, to środek listy. W przypadku list posortowanych jest to typowa mediana statystyczna, ale w przypadku list nieposortowanych jest to tylko środek (lub średnio 2 środkowe elementy)
Mego
4

JavaScript (ES6), 24 bajty

Na podstawie odpowiedzi w języku Python .

c=x=>x?(4+6/~x)*c(x-1):1

Jak to działa

c=x=>x?(4+6/~x)*c(x-1):1
c=x=>                     // Define a function c that takes a parameter x and returns:
     x?               :1  //  If x == 0, 1.
       (4+6/~x)           //  Otherwise, (4 + (6 / (-x - 1)))
               *c(x-1)    //  times the previous item in the sequence.

Myślę, że jest to najkrótszy możliwy, ale sugestie są mile widziane!

ETHprodukcje
źródło
4

Julia, 23 bajty

n->binomial(2n,n)/(n+1)

Jest to anonimowa funkcja, która przyjmuje liczbę całkowitą i zwraca liczbę zmiennoprzecinkową. Wykorzystuje podstawową formułę dwumianową. Aby to nazwać, nadaj mu nazwę, np f=n->....

Alex A.
źródło
4

Matlab, 35 25 bajtów

@(n)nchoosek(2*n,n)/(n+1)

Oktawa, 23 bajty

@(n)nchoosek(2*n,n++)/n
costrom
źródło
2
Możesz użyć @(n)zamiast funkcji, funkcje anonimowe są w porządku.
FryAmTheEggman,
Widziałem tutaj kilka odpowiedzi, które miały dostęp do zmiennych obszaru roboczego (co sugeruje, że zostały już ustawione przez użytkownika w innym miejscu). Skrypty w MATLAB / Octave mogą również pojawiać się jako proste fragmenty. Na razie
zmieniłem
1
Możesz zrzucić jeszcze 2 bajty, zwiększając n:@(n)nchoosek(2*n,n++)/n
zlewka
@beaker dzięki za wskazówkę! działa jednak tylko w Octave, nie w Matlabie, więc podzieliłem go
koszt z
@costrom To ciekawe. Chyba .../++nteż nie działa. : /
zlewka
4

𝔼𝕊𝕄𝕚𝕟, 3 znaki / 6 bajtów

Мƅï

Try it here (Firefox only).

Wbudowane ftw! Cieszę się, że wcześnie zaimplementowałem math.js.

Rozwiązanie premiowe, 12 znaków / 19 bajtów

Мơ 2*ï,ï)/⧺ï

Try it here (Firefox only).

Ay! 19 bajt!

Ocenia na pseudo-ES6 jako:

nchoosek(2*input,input)/(input+1)
Mama Fun Roll
źródło
3

Haskell, 27 bajtów

g 0=1
g n=(4-6/(n+1))*g(n-1)

Recursywna formuła. Musi być sposób na oszczędzanie na parens ...

Bezpośrednie pobranie produktu było o 2 bajty dłuższe:

g n=product[4-6/i|i<-[2..n+1]]
xnor
źródło
Gdzie twój kod odczytuje ze standardowego wejścia lub pisze na standardowe wyjście?
user2845840,
2
@ user2845840 Funkcje są jedną z dopuszczalnych alternatyw powiązanych z opisem w specyfikacji.
xnor
g(n-1)=> g$n-1zapisuje jeden bajt. Edycja: tak naprawdę to nie działa, ponieważ wtedy formuła jest interpretowana jako (...*g) (n-1).
Przywróć Monikę
3

Dyalog APL, 9 bajtów

+∘1÷⍨⊢!+⍨

To jest pociąg monadyczny; wykorzystuje formułę (2x nCr x) / (x + 1). Wypróbuj online tutaj .

lirtosiast
źródło
3

C, 122 121 119 108 bajtów

main(j,v)char**v;{long long p=1,i,n=atoi(v[1]);for(j=0,i=n+1;i<2*n;p=(p*++i)/++j);p=n?p/n:p;printf("%d",p);}

Użyłem gcc (GCC) 3.4.4 (cygming special, gdc 0.12, używając dmd 0.125) do kompilacji w środowisku Windows cygwin. Dane wejściowe pojawiają się w wierszu poleceń. Jest podobny do rozwiązania Python Sherlock9, ale pętle są łączone w jedną, aby uniknąć przepełnienia i uzyskać wynik do 20. liczby katalońskiej (n = 19).

cleblanc
źródło
1
Możesz usunąć spację po przecinku w maindefinicji, aby zapisać bajt.
Alex A.,
Fajnie,
zredaguję
Możesz zapisać 2 dodatkowe bajty za pomocą char**vzamiast char *v[]. (Poprzednia przestrzeń *nie jest potrzebna, a typy są równoważne.)
Mat
Rzeczywiście, to działa świetnie. Dzięki Mat
cleblanc
To skraca niektóre elementy ze strony ze wskazówkami . Zauważ jednak, że dla Ideone ustaliłem na stałe wartość n.
FryAmTheEggman,
3

Javagony , 223 bajty

public class C{public static int f(int a,int b){try{int z=1/(b-a);}catch(Exception e){return 1;}return a*f(a+1,b);}public static void main(String[]s){int m=Integer.parseInt(s[0])+1;System.out.println(f(m,2*m-1)/f(1,m)/m);}}

W pełni rozbudowany:

public class C {
    public static int f(int a,int b){
        try {
            int z=1/(b-a);
        } catch (Exception e){
            return 1;
        }
        return a*f(a+1,b);
    }
    public static void main(String[] s){
        int m=Integer.parseInt(s[0])+1;
        System.out.println(f(m,2*m-1)/f(1,m)/m);
    }
}
wada
źródło
Zgłoszenie do Esolangs nie ma znaczenia - dopóki używasz tłumacza wykonanego przed zawodami, wszystko jest dobre i ważne.
Addison Crump,
I tak nie wygra ^^
flawr
To java, więc tak.
Rɪᴋᴇʀ
1
@Riker Cóż, jest gorzej niż Java.
Jakob,
2

Japt, 16 bajtów

Nawet Mathematica jest krótsza. :-/

U*2ª1 o àU l /°U

Wypróbuj online!

Bez golfa i wyjaśnienia

U*2ª 1 o àU l /° U
U*2||1 o àU l /++U

         // Implicit: U = input number
U*2||1   // Take U*2. If it is zero, take 1.
o àU     // Generate a range of this length, and calculate all combinations of length U.
l /++U   // Take the length of the result and divide by (U+1).
         // Implicit: output result

Alternatywna wersja, oparta na rekurencyjnej formule:

C=_?(4+6/~Z *C$(Z-1):1};$C(U
ETHprodukcje
źródło
2

Vitsy , 13 bajtów

VV2*FVF/V1+F/
V              Capture the input as a final global variable.
 V             Push it back.
  2*           Multiply it by 2
    F          Factorial.
     VF        Factorial of the input.
       /       Divide the second to top by the first.
        V1+    1+input
           F   Factorial.
            /  Divide.

Jest to funkcja w Vitsy . Jak zrobić program, który to robi, pytasz? Łączy N. do:

Wypróbuj online!

Addison Crump
źródło
2

Droga Mleczna 1.5.14 , 14 bajtów

':2K;*Ny;1+/A!

Wyjaśnienie

'               # read input from the command line
 :              # duplicate the TOS
  2      1      # push integer to the stack
   K            # push a Pythonic range(0, TOS) as a list
    ;   ;       # swap the TOS and the STOS
     *          # multiply the TOS and STOS
      N         # push a list of the permutations of the TOS (for lists)
       y        # push the length of the TOS
          +     # add the STOS to the TOS
           /    # divide the TOS by the STOS
            A   # push the integer representation of the TOS
             !  # output the TOS

lub, alternatywnie, znacznie bardziej wydajna wersja:


Droga Mleczna 1.5.14 , 22 bajty

'1%{;K£1+k1-6;/4+*}A!

Wyjaśnienie

'                      # read input from the command line
 1     1  1 6  4       # push integer to the stack
  %{  £           }    # for loop
    ;        ;         # swap the TOS and the STOS
     K                 # push a Pythonic range(0, TOS) as a list
        +       +      # add the TOS and STOS
         k             # push the negative absolute value of the TOS
           -           # subtract the STOS from the TOS
              /        # divide the TOS by the STOS
                 *     # multiply the TOS and the STOS
                   A   # push the integer representation of the TOS
                    !  # output the TOS

Stosowanie

python3 milkyway.py <path-to-code> -i <input-integer>
Zach Gates
źródło
2

Clojure / ClojureScript, 53 bajty

(defn c[x](if(= 0 x)1(*(c(dec x))(- 4(/ 6(inc x))))))

Clojure może być dość frustrujący podczas gry w golfa. Jest bardzo krwisty, a jednocześnie bardzo czytelny, ale niektóre z bardziej subtelnych cech są naprawdę pełne. (inc x)jest bardziej idiomatyczny (+ x 1)i „wydaje się” bardziej zwięzły, ale tak naprawdę nie zapisuje postaci. A pisanie łańcuchów operacji jest przyjemniejsze (->> x inc (/ 6) (- 4)), ale w rzeczywistości jest dłuższe niż robienie tego w brzydki sposób.

MattPutnam
źródło
2

Prolog, 42 bajty

Korzystanie z rekurencji jest prawie zawsze sposobem na skorzystanie z Prologu.

Kod:

0*1.
N*X:-M is N-1,M*Y,X is(4-6/(N+1))*Y.

Przykład:

19*X.
X = 1767263190.0

Wypróbuj online tutaj

Emigna
źródło
Czy redefiniujesz * tutaj symbol?
Paŭlo Ebermann,
@ PaŭloEbermann nie do końca. Definiuję nowy predykat dyadyczny o nazwie *. Nadal mogę używać zwykłego arytmetycznego. W powyższym programie M * Y jest moim zdefiniowanym predykatem, podczas gdy (4-6 / (N + 1)) * Y jest regularnym mnożeniem.
Emigna,
Jest nieco krótszy niż napisanie go jako p (X, Y): - co jest dobre dla golfa kodowego.
Emigna,
2

Oktawa, 22 bajty

@(n)prod(4-6./(2:n+1))
alephalpha
źródło
2

Cejlon, 60 bajtów

Integer c(Integer n)=>(1:n).fold(1)((p,i)=>p*(n+i)/i)/(n+1);

Działa to do C 30 , ponieważ liczby całkowite Cejlona są oznaczone liczbami 64-bitowymi (C 31 ma przepełnienie, zostanie obliczone jako -4050872099593203).

Nie wiem, czy Ceylon ma jakieś wbudowane wyższe funkcje matematyczne, ale zaimportowanie odpowiedniego pakietu prawdopodobnie byłoby dłuższe niż zwykłe obliczenie tego na piechotę.

// Catalan number C_n
//
// Question:  http://codegolf.stackexchange.com/q/66127/2338
// My answer: http://codegolf.stackexchange.com/a/66425/2338

Integer c(Integer n) =>
        // sequence of length n, starting at 1.
        (1:n)
        // starting with 1, for each element i, multiply the result
        // of the previous step by (n+i) and then divide it by i.
    .fold(1)((p, i) => p * (n + i) / i)
        // divide the result by n+1.
        / (n + 1);
Paŭlo Ebermann
źródło
2

R, 35 28 16 bajtów

numbers::catalan

Edycja: użyj wbudowanego pakietu liczb.

mnel
źródło
2

MATL , 8 bajtów

2*GXnGQ/

Wypróbuj online!

Wyjaśnienie

2*     % take number n as input and multiply by 2
G      % push input again
Xn     % compute "2*n choose n"
G      % push input again
Q      % add 1
/      % divide
Luis Mendo
źródło
2

05AB1E , 6 bajtów

Dxcr>/

Wyjaśnienie:

Code:     Stack:               Explanation:

Dxcr>/

D         [n, n]               # Duplicate of the stack. Since it's empty, input is used.
 x        [n, n, 2n]           # Pops a, pushes a, a * 2
  c       [n, n nCr 2n]        # Pops a,b pushes a nCr b
   r      [n nCr 2n, n]        # Reverses the stack
    >     [n nCr 2n, n + 1]    # Increment on the last item
     /    [(n nCr 2n)/(n + 1)] # Divides the last two items
                               # Implicit, nothing has printed, so we print the last item
Adnan
źródło
2

R, 28 bajtów

Nie używa pakietu, więc nieco dłużej niż poprzednia odpowiedź

choose(2*(n=scan()),n)/(n+1)
Frédéric
źródło