Hitung Koefisien Fibonomial

11

Latar Belakang

Urutan Fibonacci didefinisikan sebagai

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

Fibonorial, mirip dengan faktorial, adalah produk dari angka Fibonacci n pertama .

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

Koefisien Fibonomial, mirip dengan koefisien binomial didefinisikan sebagai

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) )

Tugas

Tujuan Anda adalah membuat fungsi atau program untuk menghitung koefisien Fibonomial yang diberikan dua bilangan bulat non-negatif n dan k dengan kn .

Uji Kasus

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

Aturan

  • Ini adalah sehingga kode terpendek menang.
  • Dibangun secara bawaan.

Terkait

mil
sumber
Jika diperlukan, berikut adalah halaman web yang mencantumkan nilai pertama 1335dalam urutan Koefisien Fibonomial.
R. Kap
Apakah kotak a(50, 2)uji tidak ada yang memimpin 9?
Joe
@ SirBidenXVII Oh ya, Anda benar saya melewatkan satu digit.
mil

Jawaban:

1

Jelly , 16 byte

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

Cobalah online!

Kredit ke Dennis untuk tautan pembantu Fibonacci-orial.

;_/Ç€:/     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.
Biarawati Bocor
sumber
4

Haskell, 46 byte

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

Output mengapung. Menghasilkan daftar Fibonacci yang tak terbatas. Kemudian, apakah resusi binomial, mengalikan dan membaginya dengan elemen-elemen dari daftar Fibonacci.

Tidak
sumber
4

Python 67 byte

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)

Panggilan menggunakan a(n,k). Menggunakan jawaban fibdenorial @Dennis (apakah itu diizinkan?), Dan implementasi langsung dari pertanyaan sebaliknya.

Theo
sumber
Semua konten pengguna dilisensikan di bawah CC-BY-SA, sehingga selama Anda memberikan atribusi, Anda dapat menggunakan kembali kode dari jawaban lain. Anda dapat mempersingkat lambda kedua menjadi lambda n,k:f(n)/f(k)/f(n-k); tidak perlu menyebutkan nama.
Dennis
3

Haskell, 77 57 55 52 50 byte

Baris pertama awalnya berasal dari fungsi Fibonacci atau tantangan urutan dan ditulis oleh @Anon.

Baris kedua ditambahkan dalam tantangan Fibonacci-orial oleh @ChristianSievers .

Sekarang saya menambahkan baris ketiga. Seberapa jauh tantangan itu pergi? =)

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

Terima kasih untuk 5 byte @ xnor!

cacat
sumber
Dapat Anda lakukan /daripada div?
xnor
Hm ya, tapi itu akan berakhir dengan angka floating point.
flawr
Oh, itu sebenarnya tidak dianulir, terima kasih =)
flawr
Anda mungkin dapat membagi dua kali untuk menghindari orangtua.
xnor
1
Sekarang kita sudah memiliki ini, hal berikutnya adalah transformasi fibonomial ;-)
Christian Sievers
3

C, 206 byte:

#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)));}

Setelah eksekusi, minta 2 integer yang dipisahkan spasi sebagai input. The #includepreprocessor yang diperlukan , karena tanpa itu, uint_64bukan jenis yang valid, dan satu-satunya cara lain untuk membuat karya ini untuk output yang cukup besar menggunakan unsigned long longtipe kembali untuk kedua F(Fibonacci) dan Gfungsi (Fibonorial), yang jauh lebih lama daripada hanya termasuk <inttypes.h>dan menggunakan uint64_tdeklarasi 3 tipe. Namun, bahkan dengan itu, ia berhenti bekerja dengan benar pada nilai input 14 1(dikonfirmasi dengan menggunakan ini , yang mencantumkan nilai pertama 1325dalam urutan Koefisien Fibonomial), kemungkinan besar karena Fibonacci dan / atau representasi angka Fibnorial 15dan di atas melimpah 64-bit tipe integer yang digunakan.

C Online! (Ideone)

R. Kap
sumber
Mungkin sejak Fibonorial of 15 meluapuint_64
mil
3

Cheddar , 75 64 byte

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

Pemakaian

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
Biarawati Bocor
sumber
2

MATL , 25 23 byte

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

Cobalah online!

Penjelasan

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
sumber
2

R, 120 byte

Beberapa golf mungkin saja bisa dilakukan, jadi komentar tentu saja disambut!
Saya menggunakan jawaban saya untuk pertanyaan Fibonacci-orial di awal kode:

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))}

Tidak Disatukan:

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
sumber
2

Jawa: 304 260 257

Saya menyimpan beberapa byte dengan memadatkan fungsi memoisasi sedikit dan menghapus f(n)seluruhnya, menggantinya dengan akses array langsung.

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]);}

Sayangnya, BigIntegerdiperlukan karena meluap dan saya harus menambahkan memoisasi. Bahkan pada generasi 6 i7, itu mengambil jalan terlalu lama untuk menjalankan dengan input yang besar.

Tidak disatukan, dengan pelat classdan mainkode:

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
}

Output program:

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

sumber
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)

Panggilan menggunakan c(n)(k), cukup mudah.

Khusus ASCII
sumber
1

dc, 67 byte

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

Input diambil sebagai konstanta desimal pembatas-ruang pada satu baris.

Ini menggunakan jawaban saya untuk /Fibon(acci-)?orial/pertanyaan, yang mengalikan semua angka pada tumpukan pada langkah terakhir, yang membutuhkan angka-angka lain untuk disimpan di tempat lain sementara Fibonorial lainnya dihitung.

?       # 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
sumber
1

Julia, 53 byte

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

Kredit ke @Lynn untuk jawaban Fibonorialnya .

Mama Fun Roll
sumber
1

Aksioma 108 byte

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]))

beberapa tes

(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]

Jenis: Integer Pecahan Tuple

RosLuP
sumber
1

Mathematica, 30 byte

(f=Fibonorial)@#/f[#-#2]/f@#2&
alephalpha
sumber