Berechnen Sie den Fibonomialkoeffizienten

11

Hintergrund

Die Fibonacci-Sequenz ist definiert als

f(1) = 1
f(2) = 1
f(n) = f(n-1) + f(n-2)

Das Fibonorial ist ähnlich wie die Fakultät das Produkt der ersten n Fibonacci-Zahlen.

g(n) = f(1) * f(2) * ... * f(n-1) * f(n)

Der Fibonomialkoeffizient, ähnlich dem Binomialkoeffizienten, ist definiert als

a(n, 0) = 1
a(n, k) = g(n) / ( g(n-k) * g(k) )
        = f(n) * f(n-1) * ... * f(n-k+1) / ( f(1) * f(2) * ... * f(k) )

Aufgabe

Ihr Ziel ist es, eine Funktion oder ein Programm zur Berechnung des Fibonomialkoeffizienten bei zwei nicht negativen ganzen Zahlen n und k mit kn zu erstellen .

Testfälle

a(0, 0) = 1
a(1, 1) = 1
a(2, 0) = 1
a(3, 2) = 2
a(8, 3) = 1092
a(11, 5) = 1514513
a(22, 7) = 7158243695757340957617
a(25, 3) = 49845401197200
a(50, 2) = 97905340104793732225
a(100, 1) = 354224848179261915075

Regeln

  • Dies ist also gewinnt der kürzeste Code.
  • Builtins sind erlaubt.

verbunden

Meilen
quelle
Bei Bedarf finden Sie hier eine Webseite, auf der die ersten 1335Werte in der Sequenz Fibonomial Coefficient aufgeführt sind.
R. Kap
Fehlt dem a(50, 2)Testfall eine Führung 9?
Joe
@ SirBidenXVII Oh ja, du hast recht, ich habe eine Ziffer verpasst.
Meilen

Antworten:

1

Gelee , 16 Bytes

0+⁸С1ḊP
;_/Ç€:/

Probieren Sie es online aus!

Dank an Dennis für den Fibonacci-Orial-Helfer-Link.

;_/Ç€:/     Main chain,  argument: [n,r]
 _/         Find n-r
;           Attach it to original: [n,r,n-r]
   ǀ       Apply helper link to each element, yielding [g(n),g(r),g(n-r)]
     :/     Reduce by integer division, yielding g(n)//g(r)//g(n-r)

0+⁸С1ḊP    Helper link, argument: n
0+⁸С1ḊP    Somehow return the n-th Fibonacci-orial.
Undichte Nonne
quelle
4

Haskell, 46 Bytes

l=0:scanl(+)1l;a%0=1;a%b=(a-1)%(b-1)*l!!a/l!!b

Ausgänge schweben. Erzeugt die unendliche Fibonacci-Liste. Dann erfolgt die Binomialrekusion, Multiplikation und Division durch Elemente aus der Fibonacci-Liste.

xnor
quelle
4

Python 67 Bytes

f=lambda n,a=1,b=1:n<1or a*f(n-1,b,a+b)
lambda n,k:f(n)/f(k)/f(n-k)

Rufen Sie mit an a(n,k). Verwendet die fibonorische Antwort von @Dennis (ist das erlaubt?) Und ansonsten eine einfache Implementierung der Frage.

Das Ö
quelle
Alle Benutzerinhalte sind unter CC-BY-SA lizenziert. Solange Sie eine Zuordnung vornehmen, können Sie Code aus anderen Antworten wiederverwenden. Sie können Ihr zweites Lambda auf kürzen lambda n,k:f(n)/f(k)/f(n-k); eine Benennung ist nicht erforderlich.
Dennis
3

Haskell, 77 57 55 52 50 Bytes

Die erste Zeile stammt ursprünglich aus der Fibonacci-Funktions- oder Sequenz- Challenge und wurde von @Anon geschrieben.

Die zweite Zeile wurde in der Fibonacci-orial Challenge von @ChristianSievers hinzugefügt.

Jetzt habe ich die dritte Zeile hinzugefügt. Wie weit werden diese Herausforderungen noch gehen? =)

f=1:scanl(+)1f
g=(scanl(*)1f!!)
n#k=g n/g(n-k)/g k

Danke für 5 Bytes @xnor!

fehlerhaft
quelle
Kannst du /lieber als div?
xnor
Hm ja, aber das würde in Gleitkommazahlen enden.
Fehler
Oh, das ist eigentlich nicht unzulässig, danke =)
Fehler
Sie können vermutlich zweimal teilen, um Parens zu vermeiden.
xnor
1
Jetzt, wo wir das haben, könnte das nächste die fibonomische Transformation sein ;-)
Christian Sievers
3

C, 206 Bytes:

#include <inttypes.h>
uint64_t F(x){return x<1 ? 0:x==1 ? 1:F(x-1)+F(x-2);}uint64_t G(H,B){uint64_t P=1;for(B=3;B<=H;B++)P*=F(B);return P;}main(U,Y){scanf("%d %d",&U,&Y);printf("%llu\n",G(U)/(G(U-Y)*G(Y)));}

Fordert bei der Ausführung 2 durch Leerzeichen getrennte Ganzzahlen als Eingabe an. Der #includePräprozessor ist erforderlich , da er ohne ihn uint_64kein gültiger Typ ist. Die einzige andere Möglichkeit, diese Funktion für relativ große Ausgaben zu verwenden, besteht darin, unsigned long longRückgabetypen sowohl für die Funktionen F(Fibonacci) als auch für die GFunktionen (Fibonorial) zu verwenden, was viel länger als nur ist einschließlich der <inttypes.h>und unter Verwendung von 3 uint64_tTypdeklarationen. Aber auch bei , daß, stoppt sie korrekt an Eingabewerten arbeitet 14 1(bestätigt durch Verwendung von dieser , die Listen , die die ersten 1325Werte in der Fibonomial Koeffizientenfolge), wahrscheinlich weil die Fibonacci und / oder Fibnorial Darstellung von Zahlen 15und vor Überlauf der 64-Bit - ganzzahliger Typ verwendet.

C Es online! (Ideone)

R. Kap
quelle
Es ist wahrscheinlich seit dem Fibonorial von 15 Überläufenuint_64
Meilen
3

Cheddar , 75 64 Bytes

a->b->(g->g((a-b+1)|>a)/g(1|>b))(n->n.map(Math.fib).reduce((*)))

Verwendung

cheddar> var f = a->b->(g->g((a-b+1)|>a)/g(1|>b))(n->n.map(Math.fib).reduce((*)))
cheddar> f(11)(5)
1514513
Undichte Nonne
quelle
2

MATL , 25 23 Bytes

1ti2-:"yy+]vtPi:)w5M)/p

Probieren Sie es online aus!

Erläuterung

1t      % Push 1 twice
i2-:    % Take input n. Generate vector [1 2 ... n-2]
"       % Repeat n-2 times
  yy    %   Push the top two elements again
  +     %   Add them
]       % End
v       % Concatenate into column vector of first n Fibonacci numbers
tP      % Duplicate and reverse
i:      % Take input k. Generate vector [1 2 ... k]
)       % Apply index to get last k Fibonacci numbers
w       % Swap to move vector of first n Fibonacci numbers to top
5M      % Push [1 2 ... k] again
)       % Apply index to get first k Fibonacci numbers
/       % Divide element-wise
p       % Product of vector. Implicitly display
Luis Mendo
quelle
2

R, 120 Bytes

Etwas mehr Golf ist wahrscheinlich möglich, daher sind Kommentare natürlich willkommen!
Ich habe meine Antwort auf die Fibonacci- Frage am Anfang des Codes verwendet:

A=function(n,k){p=(1+sqrt(5))/2;f=function(N){x=1;for(n in 1:N){x=prod(x,(p^n-(-1/p)^n)/sqrt(5))};x};f(n)/(f(k)*f(n-k))}

Ungolfed:

A=function(n,k){
p=(1+sqrt(5))/2
    f=function(N){
        x=1
        for(n in 1:N){
           x=prod(x,(p^n-(-1/p)^n)/sqrt(5))
                     }
        x
        }

f(n)/(f(k)*f(n-k))
}
Frédéric
quelle
2

Java: 304 260 257

Ich habe einige Bytes gespart, indem ich die Memoisierungsfunktion ein wenig komprimiert und f(n)vollständig entfernt und durch direkten Array-Zugriff ersetzt habe.

BigInteger[]c;BigInteger a(int n,int k){m(n);return g(n).divide(g(n-k)).divide(g(k));}BigInteger g(int n){return n<3?BigInteger.ONE:g(n-1).multiply(c[n-1]);}void m(int n){c=new BigInteger[n];for(int i=0;i<n;++i)c[i]=(i<2)?BigInteger.ONE:c[i-2].add(c[i-1]);}

Leider BigIntegerist wegen Überläufen erforderlich und ich musste Memoization hinzufügen. Selbst bei einer Generation 6 i7 dauerte es viel zu lange, um mit großen Eingaben zu arbeiten.

Ungolfed, mit Boilerplate classund mainCode:

import java.math.BigInteger;

public class ComputeTheFibonomialCoefficient {

  public static void main(final String[] args) {
    // @formatter:off
    String[][] testData = new String[][] {
      { "0", "0", "1" },
      { "1", "1", "1" },
      { "2", "0", "1" },
      { "3", "2", "2" },
      { "8", "3", "1092" },
      { "11", "5", "1514513" },
      { "22", "7", "7158243695757340957617" },
      { "25", "3", "49845401197200" },
      { "50", "2", "97905340104793732225" },
      { "100", "1", "354224848179261915075" }
    };
    // @formatter:on

    for (String[] data : testData) {
      System.out.println("a(" + data[0] + ", " + data[1] + ")");
      System.out.println("  Expected -> " + data[2]);
      System.out.print("    Actual -> ");
      System.out.println(new ComputeTheFibonomialCoefficient().a(
          Integer.parseInt(data[0]), Integer.parseInt(data[1])));
      System.out.println();
    }
  }

  // Begin golf

  BigInteger[] c;

  BigInteger a(int n, int k) {
    m(n);
    return g(n).divide(g(n - k)).divide(g(k));
  }

  BigInteger g(int n) {
    return n < 3 ? BigInteger.ONE : g(n - 1).multiply(c[n - 1]);
  }

  void m(int n) {
    c = new BigInteger[n];
    for (int i = 0; i < n; ++i)
      c[i] = (i < 2) ? BigInteger.ONE : c[i - 2].add(c[i - 1]);
  }
  // End golf
}

Programmausgabe:

a(0, 0)
  Expected -> 1
    Actual -> 1

a(1, 1)
  Expected -> 1
    Actual -> 1

a(2, 0)
  Expected -> 1
    Actual -> 1

a(3, 2)
  Expected -> 2
    Actual -> 2

a(8, 3)
  Expected -> 1092
    Actual -> 1092

a(11, 5)
  Expected -> 1514513
    Actual -> 1514513

a(22, 7)
  Expected -> 7158243695757340957617
    Actual -> 7158243695757340957617

a(25, 3)
  Expected -> 49845401197200
    Actual -> 49845401197200

a(50, 2)
  Expected -> 97905340104793732225
    Actual -> 97905340104793732225

a(100, 1)
  Expected -> 354224848179261915075
    Actual -> 354224848179261915075

quelle
1

JavaScript (ES6), 70 Byte

a=n=>n<2?1:a(--n)+a(--n);b=n=>n?a(--n)*b(n):1;c=n=>k=>b(n)/b(n-k)/b(k)

Rufen Sie mit c(n)(k), ziemlich einfach.

Nur ASCII
quelle
1

Gleichstrom, 67 Bytes

?skdsn[si1d[sadlarla+zli>b*]sbzli>b*]dsgxsplnlk-lgxsqlklgxlprlqr*/f

Die Eingabe erfolgt als durch Leerzeichen getrennte Dezimalkonstanten in einer einzelnen Zeile.

Dies verwendet meine Antwort auf die /Fibon(acci-)?orial/Frage, bei der im letzten Schritt alle Zahlen auf dem Stapel multipliziert werden und die anderen Zahlen an anderer Stelle gespeichert werden müssen, während die anderen Fibonorials berechnet werden.

?       # Take input from stdin
skdsn   # Store second number in register `k'; store a copy of first number in register `n'
[si1d[sadlarla+zli>b*]sbzli>b*] # Compute Fibonorial of top-of-stack, multiplying
                                #   until stack depth is 1
dsgx    # Store a copy of this function as g and execute it: g(n)
sp      # Store g(n) in register `p'
lnlk-   # Compute n-k
lgx     # Compute g(n-k)
sq      # Store g(n-k) in register `q'
lk lgx  # Compute g(k)
        # Top ---Down--->
lp      #  g(n)    g(k)
r       #  g(k)    g(n)
lq      #  g(n-k)  g(k)    g(n)
r       #  g(k)    g(n-k)  g(n)
*       # (g(k)g(n-k))     g(n)
/       #  g(n)/(g(k)g(n-k))
f       # Dump stack to stdout
Joe
quelle
1

Julia, 53 Bytes

!x=[([1 1;1 0]^n)[2]for n=1:x]|>prod;n\k=!n/!(n-k)/!k

Dank an @Lynn für seine Fibonorial-Antwort .

Mama Fun Roll
quelle
1

Axiom 108 Bytes

b(n,k)==(n<=k or k<1=>1;reduce(*,[fibonacci(i) for i in (n-k+1)..n])/reduce(*,[fibonacci(i) for i in 1..k]))

ein Test

(34) -> b(0,0),b(1,1),b(2,0),b(3,2),b(8,3),b(11,5),b(22,7)
   Compiling function b with type (NonNegativeInteger,
      NonNegativeInteger) -> Fraction Integer
   Compiling function b with type (PositiveInteger,PositiveInteger) ->
      Fraction Integer
   Compiling function b with type (PositiveInteger,NonNegativeInteger)
       -> Fraction Integer

   (34)  [1,1,1,2,1092,1514513,7158243695757340957617]
                                                 Type: Tuple Fraction Integer
(35) -> b(25,3),b(50,2),b(100,1)

   (35)  [49845401197200,97905340104793732225,354224848179261915075]

Typ: Tuple Fraction Integer

RosLuP
quelle
1

Mathematica, 30 Bytes

(f=Fibonorial)@#/f[#-#2]/f@#2&
Alephalpha
quelle