Angka Fibonacci Negatif

28

Anda mungkin semua tahu urutan fibonacci:

fibonacci(n)=fibonacci(n-1)+fibonacci(n-2)
fibonacci(0)=0
fibonacci(1)=1

Tugas Anda sesederhana mungkin:

  • Mengingat bilangan bulat Nmenghitungfibonacci(n)

tapi di sini adalah twist:

  • Juga lakukan negatif N

Tunggu. Apa?

fibonacci(1)=fibonacci(0)+fibonacci(-1)

begitu

fibonacci(-1)=1

dan

fibonacci(-2)=fibonacci(0)-fibonacci(1)=-1

dan seterusnya...

  • Ini adalah sehingga program terpendek dalam byte menang.
  • Anda dapat mengirimkan fungsi atau program penuh
  • N ada di [-100.100]

Testcase di CSV:

-9;-8;-7;-6;-5;-4;-3;-2;-1;0;1;2;3;4;5;6;7;8
34;-21;13;-8;5;-3;2;-1;1;0;1;1;2;3;5;8;13;21

Petunjuk:

n <0 dan n & 1 == 0:

fibonacci(n)=fibonacci(abs(n))*-1

Roman Gräf
sumber
Tidak. Milik saya ingin Anda mendukung angka negatif juga.
Roman Gräf
7
Saya pikir ini bukan penipuan. Dari jawaban di halaman pertama dari tantangan Fibonacci yang ada, hanya 1 yang dapat menangani negatif, dan sisanya perlu diubah secara signifikan untuk mundur juga.
xnor
Menambahkan beberapa. Jangan ragu untuk menambahkan lebih banyak. @Flip
Roman Gräf
1
Baca posting meta ini tentang memformat kasus uji: coba hindari tabel mewah
FlipTack
dan dengan CSV maksudmu SSV (nilai-nilai yang dipisahkan titik koma)?
NH.

Jawaban:

22

Mathematica, 9 byte

Fibonacci

Ya, fungsi bawaan ini mendukung angka negatif.

alephalpha
sumber
2
Ini hampir kata demi kata jawaban yang akan saya posting: D
Greg Martin
17

Oktaf, 20 byte

 @(n)([1,1;1,0]^n)(2)

Cobalah online!

Penjelasan

Ini memanfaatkan fakta bahwa deret fibonacci f(n)dapat ditulis sebagai (ini harus menjadi notasi vektor matriks):

Secara rekursif:

[f(n+1)]  = [1  1] * [f(n)  ]
[f(n)  ]    [1  0]   [f(n-1)]

Secara eksplisit:

[f(n+1)]  = [1  1] ^n * [1]
[f(n)  ]    [1  0]      [0]

Ini berarti bahwa entri kanan atas dari matriks ini dengan kekuatan nadalah nilai yang f(n)kami cari. Jelas kita juga bisa membalikkan matriks ini karena memiliki peringkat penuh, dan hubungannya masih menggambarkan relasi perulangan yang sama. Itu berarti ini juga berfungsi untuk input negatif.

cacat
sumber
1
(Bagaimana) Apakah ini juga berfungsi untuk input negatif?
Roman Gräf
ya, penjelasan akan datang ...
flawr
adalah ans(-6)dimaksudkan untuk menjadi positif?
FlipTack
@ Lipatan Maaf, mungkin karena pergeseran indeks. Saya menggunakan 1-based, sedangkan pertanyaan menggunakan 0-based, saya memperbaikinya sekarang.
flawr
13

Maksima, 3 byte

 fib

mendukung angka positif dan negatif.

Cobalah (tempel) di CESGA - Maxima on line

rahnema1
sumber
Bisakah Anda menambahkan tautan ke bahasa itu?
Pavel
Tentu saja menambahkan tautan ke kalkulator online!
rahnema1
Juga bekerja di WolframAlpha
Thunda
11

Python, 43 byte

g=5**.5/2+.5
lambda n:(g**n-(1-g)**n)/5**.5

Formula langsung dengan rasio emas g. Dengan ffungsi di atas:

for n in range(-10,11):print f(n) 

-55.0
34.0
-21.0
13.0
-8.0
5.0
-3.0
2.0
-1.0
1.0
0.0
1.0
1.0
2.0
3.0
5.0
8.0
13.0
21.0
34.0
55.0

Alt panjang yang sama, hanya alias akar kuadrat dari 5:

a=5**.5
lambda n:((a+1)**n-(1-a)**n)/a/2**n

Saya tidak melihat cara untuk membuat fungsi rekursif yang dapat bersaing dengan ini. Upaya dengan golf ringan selama 57 byte:

f=lambda n:n<0and(-1)**n*f(-n)or n>1and f(n-1)+f(n-2)or n

Sebagai perbandingan, metode berulang (60 byte dalam Python 2):

n=input()
a,b=0,1;exec"a,b=b,a+b;"*n+"a,b=b-a,a;"*-n
print a

Atau, untuk 58 byte:

n=input()
a,b=0,1;exec"a,b=b,a+cmp(n,0)*b;"*abs(n)
print a
Tidak
sumber
10

JavaScript (ES6), 42 byte

f=n=>n<2?n<0?f(n+2)-f(n+1):n:f(n-2)+f(n-1)

Uji

Arnauld
sumber
Saya sangat suka fungsi Anda. Saya punya saran di sini, tetapi saya mengabaikan sebuah -, jadi itu tidak akan berhasil ...
Luke
5

MATL , 11 9 byte

Saya senang dengan [3,2], yang pasti bisa golf, jika ada yang tahu cara tolong beri tahu saya =) (Ini juga akan bekerja dengan [1,3].) Terima kasih @LuisMendo untuk -2 byte =)

IHhBiY^2)

Ini menggunakan pendekatan yang sama dengan penjawab Octave . Tetapi untuk menghasilkan matriks

[1,1]
[1,0]

kita hanya mengonversi angka 3dan 2dari desimal ke biner (yaitu 11dan 10).

Cobalah online!

cacat
sumber
5

JavaScript (ES7) 37 byte

Menggunakan Formula Binet .

n=>((1+(a=5**.5))**n-(1-a)**n)/a/2**n

Output ini nth Fibonacci nomor + - 0.0000000000000005.

Luke
sumber
**membutuhkan ES7.
Neil
Oh, pikir itu bagian dari ES6, tapi kau benar. Mengubahnya. Saya juga menggunakan versi lain dari Formula Binet untuk menghemat 1B.
Luke
Sekarang saya berpikir tentang hal itu, hanya menggunakan 1-palih-alih -1/pseharusnya bekerja untuk penghematan yang sama.
Neil
3

Jolf, 2 byte

mL

Coba di sini!

The fibonacci builtin, diimplementasikan menggunakan phirumus.

Conor O'Brien
sumber
Uncaught SyntaxError: Token yang tidak terduga | di Function baru (<anonymous>) di p (math.min.js: 27) di Object (math.min.js: 27) di typed (eval at p (math.min.js: 27), <anonymous>: 36:14) di Object.n [sebagai pabrik] (math.min.js: 45) di t (math.min.js: 27) di f (math.min.js: 27) di Object.get [sebagai median ] (math.min.js: 27) di clone (rawgit.com/ConorOBrien-Foxx/Jolf/master/src/jolf.js:902) di rawgit.com/ConorOBrien-Foxx/Jolf/master/src/jolf. js: 2128 (Google Chrome Terbaru, versi 55.0.2883.87m)
Ismael Miguel
@IsmaelMiguel Ini seharusnya hanya berfungsi pada firefox
Conor O'Brien
Saya tidak tahu, itu tidak ada di mana saja
Ismael Miguel
2

Haskell, 51 byte

s=0:scanl(+)1s;f z|even z,z<0= -f(-z);f z=s!!abs z
Roman Czyborra
sumber
1
Beberapa tes dalam penjaga dapat dikombinasikan dengan ,bukannya &&: even z,z<0.
nimi
1

PowerShell , 112 Bytes

function f($n){$o=('-','+')[$n-lt0];&(({$a,$b=(2,1|%{f("$n$o$_"|iex)});"$a- $o$b"|iex},{$n*$n})[$n-in(-1..1)])}

Panggilan Demo:

-9..9 | %{"{0,2}`t=> {1,3}" -f $_,(f($_))} 

Output dari Demo:

-9  =>  34
-8  => -21
-7  =>  13
-6  =>  -8
-5  =>   5
-4  =>  -3
-3  =>   2
-2  =>  -1
-1  =>   1
 0  =>   0
 1  =>   1
 2  =>   1
 3  =>   2
 4  =>   3
 5  =>   5
 6  =>   8
 7  =>  13
 8  =>  21
 9  =>  34
JohnLBevan
sumber
1

Lithp , 88 byte

#N::((if(< N 2)((if(< N 0)((-(f(+ N 2))(f(+ N 1))))((+ N))))((+(f(- N 2))(f(- N 1))))))

Pandanganku pada semua tanda kurung itu .

Cobalah online!

Tidak terlalu kecil kok. Saat ini ada bug penguraian yang mengharuskan seseorang untuk menggunakan (get N)atau (+ N)bukan hanya N. Saya memilih yang lebih kecil. Namun saya tidak berpikir ada sesuatu yang bisa dilakukan lebih jauh untuk golf ini.

Andrakis
sumber