Tentang Representasi Zeckendorf / Nomor Fibonacci Dasar

Ini adalah sistem angka yang menggunakan angka Fibonacci sebagai basisnya. Angka-angka terdiri dari 0 dan 1 dan masing-masing 1 berarti angka tersebut berisi angka Fibonacci yang sesuai, dan 0 berarti tidak.

Sebagai contoh, mari kita konversi semua bilangan asli <= 10 ke basis Fibonacci.

• 1 akan menjadi 1, karena itu adalah jumlah dari 1, yang merupakan angka Fibonacci,

• 2 akan menjadi 10, karena itu adalah jumlah dari 2, yang merupakan angka Fibonacci, dan itu tidak perlu 1, karena kami telah mencapai jumlah yang diinginkan.

• 3 akan menjadi 100, karena itu adalah jumlah dari 3, yang merupakan angka Fibonacci dan tidak perlu 2 atau 1 karena kita sudah mencapai jumlah yang diinginkan.

• 4 akan menjadi 101, karena itu adalah jumlah [3,1], yang keduanya adalah angka Fibonacci.
• 5 akan menjadi 1000, karena itu adalah jumlah dari 5, yang merupakan angka Fibonacci, dan kita tidak memerlukan angka lainnya.
• 6 akan menjadi 1001, karena itu adalah jumlah angka Fibonacci 5 dan 1.
• 7 akan menjadi 1010, karena itu adalah jumlah angka Fibonacci 5 dan 2.
• 8 akan menjadi 10.000, karena itu adalah angka Fibonacci.
• 9 akan menjadi 10001, karena itu adalah jumlah angka Fibonacci 8 dan 1.
• 10 akan menjadi 10010, karena itu adalah jumlah angka-angka Fibonacci 8 dan 2.

Mari kita konversi angka Fibonacci Basis acak, 10101001010 ke desimal: Pertama kita menulis angka Fibonacci yang sesuai. Kemudian kami menghitung jumlah angka di bawah 1.

 1   0   1   0   1   0   0   1   0   1   0
 144 89  55  34  21  13  8   5   3   2   1  -> 144+55+21+5+2 = 227.

Baca lebih lanjut tentang angka Fibonacci Dasar: tautan , ini juga memiliki alat yang mengubah bilangan bulat reguler ke Fibonacci dasar. Anda bisa bereksperimen dengannya.

Sekarang Pertanyaannya:

Tugas Anda adalah mengambil nomor di Representasi Zeckendorf, dan menampilkan nilai desimalnya.

Input adalah string yang hanya berisi 0 dan 1 (walaupun Anda dapat mengambil input dengan cara apa pun yang Anda inginkan).

Keluarkan satu angka dalam desimal.

Test case: (dalam format input-> output)

 1001 -> 6
 100101000 -> 73
 1000000000 -> 89
 1001000000100100010 -> 8432
 1010000010001000100001010000 -> 723452

Ini adalah kode-golf, jadi jawaban tersingkat dalam byte menang.

Catatan: Input tidak akan berisi 0 terkemuka atau 1 berturut-turut.

Taksi , 1987 1927 byte

-60 byte karena kesadaran bahwa linebreak adalah opsional.

Go to Post Office:w 1 l 1 r 1 l.Pickup a passenger going to Chop Suey.Go to Chop Suey:n 1 r 1 l 4 r 1 l.[B]Switch to plan C if no one is waiting.Pickup a passenger going to Cyclone.Go to Cyclone:n 1 l 3 l.Pickup a passenger going to Narrow Path Park.Pickup a passenger going to Sunny Skies Park.Go to Zoom Zoom:n.Go to Sunny Skies Park:w 2 l.Go to Narrow Path Park:n 1 r 1 r 1 l 1 r.Go to Chop Suey:e 1 r 1 l 1 r.Switch to plan B.[C]1 is waiting at Starchild Numerology.1 is waiting at Starchild Numerology.Go to Starchild Numerology:n 1 l 3 l 3 l 2 r.Pickup a passenger going to Addition Alley.Pickup a passenger going to Cyclone.Go to Cyclone:w 1 r 4 l.[D]Pickup a passenger going to Addition Alley.Pickup a passenger going to Cyclone.Go to Addition Alley:n 2 r 1 r.Go to Cyclone:n 1 l 1 l.Pickup a passenger going to Multiplication Station.Go to Zoom Zoom:n.Go to Narrow Path Park:w 1 l 1 l 1 r.Switch to plan E if no one is waiting.Pickup a passenger going to The Babelfishery.Go to The Babelfishery:e 1 r.Pickup a passenger going to Multiplication Station.Go to Multiplication Station:n 1 r 2 l.Pickup a passenger going to Joyless Park.Go to Joyless Park:n 2 l 1 r 1 r.Go to Addition Alley:w 1 r 2 l 1 l.Pickup a passenger going to Cyclone.Go to Cyclone:n 1 l 1 l.Pickup a passenger going to Addition Alley.Switch to plan D.[E]Go to Addition Alley:w 1 l 1 r 1 l.Pickup a passenger going to Riverview Bridge.Go to Riverview Bridge:n 1 r.Go to Joyless Park:e 1 r 2 l.Pickup a passenger going to Addition Alley.[F]Switch to plan G if no one is waiting.Pickup a passenger going to Addition Alley.Go to Fueler Up:w 1 l.Go to Addition Alley:n 3 l 1 l.Pickup a passenger going to Addition Alley.Go to Joyless Park:n 1 r 1 r 2 l.Switch to plan F.[G]Go to Addition Alley:w 1 r 2 l 1 l.Pickup a passenger going to The Babelfishery.Go to The Babelfishery:n 1 r 1 r.Pickup a passenger going to Post Office.Go to Post Office:n 1 l 1 r.

Cobalah online!

Karena saya tidak kembali ke Garasi Taksi pada akhirnya, bos saya memecat saya, sehingga keluar dengan kesalahan.

Perl 6 , 28 23 byte

{[+] (1,2,*+*...*)Z*$_}

Cobalah online!

Codeblock anonim yang mengambil daftar 1s dan 0s di LSB memesan dan mengembalikan nomor.

Penjelasan:

{                     }   # Anonymous codeblock
 [+]                      # The sum of
     (1,2,*+*...*)        # The infinite Fibonacci sequence starting from 1,2
                  Z*      # Zip multiplied by
                    $_    # The input list in LSB form

Jelly , 5 byte

T‘ÆḞS

Tautan monadik yang menerima daftar dalam bentuk Little-endian (yaitu dari LSB di kiri ke MSB di kanan).

Cobalah online!

Bahasa Wolfram (Mathematica) , 35 32 29 28 byte

Fibonacci[Range@Tr[#!]+1].#&

Cobalah online!

Haskell , 38 byte

f=1:scanl(+)2f
sum.zipWith(*)f.reverse

Cobalah online!

Mengambil input sebagai daftar 1s dan 0s.

Penjelasan

f=1:scanl(+)2f

Membuat daftar angka Fibonacci tanpa yang pertama, dalam variabel f.

sum.zipWith(*)f.reverse

Mengambil daftar input reversedan mengalikan setiap entri dengan entri yang sesuai f, lalu sumhasilnya.

Haskell , 30 byte

f=1:scanl(+)2f
sum.zipWith(*)f

Cobalah online!

Jika kita mengambil input dengan bit paling signifikan terlebih dahulu, kita tidak perlu reversesehingga kita bisa menghemat 8 byte.

Python 2 , 43 byte

a=b=0
for x in input():b+=a+x;a=b-a
print b

Cobalah online!

Mengambil input sebagai daftar. Pembaruan adalah versi yang lebih pendek a,b=b+x,a+b+x, yang seperti pembaruan Fibonacci a,b=b,a+bjika Anda abaikan x.

Python 2 , 45 byte

f=lambda n,a=1,b=1:n and n%10*b+f(n/10,b,a+b)

Cobalah online!

Mengambil input sebagai angka desimal.

Pyth, 13 byte

Sebagian besar (8 byte) ini hanya menghasilkan angka Fibonacci.

s*V_m=+Z|~YZ1

Cobalah dengan test suite ini!

Penjelasan:

s*V_m=+Z|~YZ1QQ     Autofill variables
    m=+Z|~YZ1Q      Generate the first length(input) Fibonacci numbers as follows:
       Z             Start with Z=0
         ~YZ         And Y=[] (update it to Y=Z, return old Y)
        |   1        if Y is [], then replace with 1
      +              Sum Z and Y
     =               Replace Z with sum
    m                Repeat process
             Q       once for each element of the input
   _                Reverse the order of the Fibonacci numbers
 *V                 Vectorize multiplication
s                   Sum

Brain-Flak , 110 , 102 , 96 , 94 , 78 , 74 byte

([[]]<>((()))){({}()<([({})]({}({})))>)}{}{}({<>{<{}><>({})(<>)}{}<><{}>})

Cobalah online!

J , ₂₄ 14 byte

#.~2+&%&1~#-#\

Cobalah online!

Menurunkan versi 24-byte yang menggunakan basis campuran untuk Fibonacci.

Bagaimana itu bekerja

#.~2+&%&1~#-#\  Example input: y=1 0 0 1 0
          #-#\  Length minus 1-based indices; 4 3 2 1 0
   2     ~      Starting from 2, run the following (4,3,2,1,0) times:
    +&%&1         Given y, compute 1 + 1 / y
                The result is 13/8 8/5 5/3 3/2 2
#.~             Mixed base conversion of y into base above; 2+8=10

J , 21 byte

1#.|.*[:+/@(!~#-])\#\

Cobalah online!

Versi olahan dari solusi 25-byte Galen Ivanov .

Menggunakan jumlah diagonal dari segitiga Pascal, yang setara dengan jumlah koefisien binomial:

$F_n = \sum\limits_{i=0}^{n} {}_{n-i}C_{i}$

Bagaimana itu bekerja

1#.|.*[:+/@(!~#-])\#\
                       Example input: 1 0 0 1 0
                   #\  Generate 1-based index; 1 2 3 4 5
      [:          \    For each prefix of above... (ex. 1 2 3)
              #-]        Subtract each element from the length (ex. 2 1 0)
           (!~   )       Compute binomial coefficient (ex. 3C0 + 2C1 + 1C2)
        +/@              Sum
                       The result is Fibonacci numbers; 1 2 3 5 8
   |.*                 Multiply with mirrored self; 0 2 0 0 8
1#.                    Sum; 10

J , 24 byte

3 :'y#.~|.(1+%)^:(<#y)2'

Cobalah online!

Kata kerja eksplisit monadik. Menghasilkan basis campuran yang mewakili basis Fibonacci, dan kemudian dimasukkan ke dalam konversi basis #..

Bagaimana itu bekerja

y#.~|.(1+%)^:(<#y)2  Explicit verb, input: y = Fibonacci digit array, n = length of y
      (1+%)          x -> 1 + 1/x
           ^:(<#y)2  Apply the above 0..n-1 times to 2
                     The result looks like 2/1, 3/2, 5/3, 8/5, 13/8, ...
    |.               Reverse
                     Now, if it is fed into #. on the left, the digit values become
                     ...(8/5 * 5/3 * 3/2 * 2/1), (5/3 * 3/2 * 2/1), (3/2 * 2/1), 2/1, 1
                     which is ... 8 5 3 2 1 (Yes, it's Fibonacci.)
y#.~                 Convert y to a number using Fibonacci base

Alternatif

J , 27 byte

}.@(+#{.3#{.)^:(<:@#)@(,&0)

Cobalah online!

Ide:

 1  0  0  1  0  1
-1 +1 +1
------------------
    1  1  1  0  1
   -1 +1 +1
------------------
       2  2  0  1
      -2 +2 +2
------------------
          4  2  1
         -4 +4 +4
------------------
             6  5
            -6 +6 +6 <- Add an imaginary digit that has value 1
---------------------
               11  6
              -11+11
---------------------
                  17 <- the answer

J , 30 byte

0.5<.@+(%:5)%~(-:>:%:5)#.,&0 0

Cobalah online!

Yang ini paling membutuhkan upaya untuk membangun. Menggunakan ekspresi bentuk tertutup dengan trik pembulatan. Dalam ekspresi, nilai 0 dan 1 masing-masing adalah 0 dan 1, jadi angka sebenarnya harus dimulai dengan 2.

0.5<.@+(%:5)%~(-:>:%:5)#.,&0 0  Tacit verb.
                         ,&0 0  Add two zeroes at the end
              (-:>:%:5)#.       Convert to a number using base phi (golden ratio)
       (%:5)%~                  Divide by sqrt(5)
0.5<.@+                         Round to nearest integer

Sementara kesalahan ( ((1-sqrt(5))/2)^nistilah) dapat meningkat, tidak pernah melebihi 0,5, jadi trik pembulatan bekerja hingga tak terbatas. Secara matematis:

$\max(|error|) = \frac{1}{\sqrt{5}} \sum\limits_{1}^{\infty} (\frac{1-\sqrt{5}}{2})^{2n} = \frac{1}{\sqrt{5}} \sum\limits_{0}^{\infty} (\frac{1-\sqrt{5}}{2})^{n} = \frac{\sqrt{5}-1}{2\sqrt{5}} < \frac{1}{2}$

MathGolf , 8 6 byte

{î)f*+

Cobalah online!

Penjelasan

{        Start block (foreach in this case)
 î)      Push loop index (1-based) and increment by 1
   f     Get fibonacci number of that index
    *    Multiply with the array value (0 or 1)
     +   Add top two elements of stack. This implicitly pops the loop index the first iteration, which makes the addition become 0+a, where a is the top of the stack.

Disimpan 1 byte berkat JoKing, dan satu byte lagi berkat pemesanan LSB.

05AB1E , 11 9 8 byte

vyiNÌÅfO

Cobalah online!

Penjelasan:

v             : For each character in input string (implicit) in LSB order
  yi          : If the current character is truthy (1)
    NÌ        : Add 2 to the current index
       ÅfO    : Add the fibonacci of this number to the stack

• -2 byte : Terima kasih kepada @KevinCruijssen karena menunjukkan cara-cara kecil untuk mempersingkat kode ini!
• -1 byte : Terima kasih kepada @JonathanAllan karena telah menunjukkan pesanan LSB untuk input!

Python 3 , 63 byte

a=b=n=1
for i in input()[::-1]:n+=b*int(i);a,b=b,a+b
print(n-1)

Cobalah online!

Mengambil input melalui STDIN sebagai string.

Merah , 142, 126 106 byte

func[a][b: copy[1 1]reverse a s: 0 n: 1
until[s: b/1 * a/:n + s insert b b/1 + b/2(n: n + 1)> length? a]s]

Cobalah online!

Ruby , 39 byte

->n{a,b=0,1;n.digits.sum{|x|x*b=a+a=b}}

Cobalah online!

Stax , 6 byte

çéC◘0â

Jalankan dan debug itu

:1F^|5+           #Full program, unpacked, implicit input as array    
:1                #Get indicies of truthy
  F               #Use rest of program to loop through elements
   ^              #Increment current element
    |5+           #Get n-th fib and Add

Cukup lurus ke depan. Pemesanan LSB.

Brain-Flak , 40 byte

([]){{}([({}<>{})]({}{}))<>([])}<>({}{})

Cobalah online!

C (gcc) , 63 byte

Mengambil input sebagai array 1's dan 0' s, bersama dengan panjang array. Solusi ini adalah loop mundur yang agak lurus ke depan.

f(_,l,a,b,t)int*_;{a=b=1;for(t=0;l--;b=(a+=b)-b)t+=a*_[l];_=t;}

Cobalah online!

Prolog (SWI) , 74 byte

\D-->[X,Y],{D is 2*X+Y};[D];a,\D.
a,[A],[B]-->[X,Y,Z],{A is X+Y,B is X+Z}.

Cobalah online!

Mengambil input sebagai daftar bilangan bulat 1 dan 0 dengan bit paling signifikan terlebih dahulu.

Retina 0.8.2 , 23 byte

0?
;
+`1;(1*);
;1$1;1
1

Cobalah online! Tautan termasuk kasus uji lebih cepat. Penjelasan:

0?
;

Masukkan pemisah di mana-mana dan hapus angka nol apa pun. Misalnya, 1001menjadi ;1;;;1;.

+`1;(1*);
;1$1;1

Ganti masing 1- masing dengan yang berulang 1di masing-masing dua tempat berikutnya, karena jumlah nilainya sama dengan nilai aslinya 1. 1Karena itu bermigrasi dan mengakumulasikan hingga mencapai dua tempat terakhir, yang (karena pemisah yang baru ditambahkan) sekarang keduanya memiliki nilai 1.

1

Hitung 1s.

Japt -x, 9 byte

Ë*MgUÊa´E

Cobalah

JavaScript (Node.js) , 41 byte

Port jawaban xnor . Mengambil input sebagai literal BigInt.

f=(n,a=1n,b=a)=>n&&n%10n*b+f(n/10n,b,a+b)

Cobalah online!

JavaScript (ES6), 44 byte

Mengambil input sebagai array karakter, dalam urutan LSB-pertama.

s=>s.map(k=>t+=k*(z=x,x=y,y+=z),x=t=0,y=1)|t

Cobalah online!

Sebenarnya , 8 byte

;r⌐@░♂FΣ

Cobalah online!

Input diambil sebagai daftar bit dalam urutan pertama LSB.

Penjelasan:

;r⌐@░♂FΣ
;r        range(0, len(input))
  ⌐       add 2 to every element in range (range(2, len(input)+2))
   @░     filter: take values in range that correspond to 1s in input
     ♂F   Fibonacci number at index of each element in list (Actually uses the F(0)=F(1)=1 definition, which is why we needed to add 2 earlier)
       Σ  sum

Powershell, 68 byte

param($s)$b=1
$s[$s.Length..0]|%{$a,$b=$b,($a+$b)
$x+=($_-48)*$b}
$x

Skrip uji:

$f = {
param($s)$b=1
$s[$s.Length..0]|%{$a,$b=$b,($a+$b)
$x+=($_-48)*$b}
$x
}

@(
    ,("1001", 6)
    ,("100101000", 73)
    ,("1000000000", 89)
    ,("1001000000100100010", 8432)
    ,("1010000010001000100001010000", 723452)
) | % {
    $s,$e = $_
    $r = &$f $s
    "$($r-eq$e): $r"
}

Keluaran:

True: 6
True: 73
True: 89
True: 8432
True: 723452

Java (OpenJDK 8) , 65 byte

Cukup kecil untuk jawaban Java saya senang dengan itu. Mengambil input sebagai array int pertama yang dipesan LSB.

d->{int s=0,f=1,h=1;for(int i:d){s+=i>0?f:0;f=h+(h=f);}return s;}

Cobalah online!

Tidak disatukan

d->{                        // Lambda function that takes array of ints
    int s=0,f=1,h=1;        // Initialise sum and fibonacci vars
    for(int i:d){           // Loop through each input integer
        s+=i>0?f:0;         // If it's 1 add current fibonacci number to sum
        f=h+(h=f);          // Increase fibonacci number 
    }return s;              // return sum
}

Z80Golf , 34 byte

00000000: dde1 f1b7 2819 fe30 2812 4504 aff5 3cf5  ....(..0(.E...<.
00000010: d1f1 82d5 f510 f9c1 f17c 8067 2c18 e3dd  .........|.g,...
00000020: e5c9                                     ..

Contoh dengan input 1001-Coba online!

Contoh dengan input 100101000-Coba online!

Majelis:

zeck:		; input=push on stack in MSB order (eg top is LSB) output=reg h
pop ix		; save return addr in ix
f:
pop af		; get next digit
or a
jr z, return	; if current digit==0, return
cp 0x30
jr z, skip	; if current digit=='0' (e.g. not '1'), skip loop
ld b, l		; find fib of counter
fib:
	inc b	; 1-indexing for func to work
	xor a	; set a to 0 (1st fibo num)
	push af
	inc a	; set a to 1 (2nd fibo num)
	push af
	fib_loop:
		pop de
		pop af
		add d
		push de
		push af
		djnz fib_loop
pop bc		; get the fibo num just calculated
pop af		; pop just to reset stack frame
ld a, h
add b		; add current fibo number to sum
ld h, a
skip:
inc l		; increment counter reg
jr f		; repeat loop
return:
push ix		; push the return addr to ret to it
ret