Diberikan input integer positif N , output dua angka non-negatif, a dan b , di mana a <b , dengan nilai rata-rata serendah mungkin yang akan menghasilkan angka N yang menjadi bagian dari urutan relasi berulang:

f(0) = a
f(1) = b
f(n) = f(n-2)+f(n-1)

Dalam hal ada lebih dari satu solusi di mana rata-rata a dan b minimal, maka Anda harus mengeluarkan satu dengan yang terendah b .

Anda dapat menganggap N berada dalam kisaran bilangan bulat representatif dalam bahasa / sistem Anda.

Uji kasus

N = 1
a = 0, b = 1

N = 15
a = 0, b = 3

N = 21
a = 0, b = 1

N = 27
a = 0, b = 9   <- Tricky test case. [3, 7] is not optimal and [4, 3] is not valid

N = 100
a = 4, b = 10

N = 101
a = 1, b = 12

N = 102
a = 0, b = 3

N = 1000
a = 2, b = 10

Sekam , 19 18 16 14 13 15 byte

Terima kasih Zgarb untuk menghemat 1 byte.

ḟö£⁰ƒẊ++ÖΣṖ2Θḣ⁰

Cobalah online!

Penjelasan:

Penafian: Saya benar-benar tidak mengerti ȯƒẊ++bagian dari kode.

Sunting: Tampaknya menerjemahkan ke Haskell fix.(mapad2(+).).(++), di mana mapad2ada fungsi untuk semua pasangan yang berdekatan dalam daftar. (Meskipun, mengenal Sekam, dalam konteks program ini bisa berarti sesuatu yang lain)

            Θḣ⁰    Create the list [0..input]
          Ṗ2       Generate all possible sublists of length 2
        ÖΣ         Sort them on their sums
ḟ                  Find the first element that satisfies the following predicate.
    ƒẊ++             Given [a,b], magically generate the infinite Fibonacci-like
                     sequence from [a,b] without [a,b] at the start.
 ö£⁰                 Is the input in that list (given that it is in sorted order)?

JavaScript (Node.js) , 92 90 89 91 83 82 byte

-3 byte -1 byte berkat ThePirateBay

-8 -9 byte terima kasih kepada Neil.

f=(n,a=1,b=0,c=(a,b)=>b<n?c(a+b,a):b>n)=>c(a,b)?b+2<a?f(n,a-1,b+1):f(n,b-~a):[b,a]

Cobalah online!

Catatan: solusi ini bergantung pada kenyataan bahwa tidak pernah ada beberapa solusi minimal.

Bukti bahwa tidak pernah ada banyak solusi:

Membiarkan FIB(a,b,k)menjadi urutan Fibonacci seperti dimulai dengan a,b:

FIB(a,b,0) = a
FIB(a,b,1) = b
FIB(a,b,k) = FIB(a,b,k-1) + FIB(a,b,k-2)

Lemma 1

Perbedaan antara urutan Fibonacci adalah Fibonacci itu sendiri, yaitu FIB(a1,b1,k) - FIB(a0,b0,k) = FIB(a1-a0,b1-b0,k). Buktinya diserahkan kepada pembaca.

Lemma 2

Sebab n >= 5, a,bada solusi yang memuaskan a+b < n:

jika ngenap,FIB(0,n/2,3) = n

jika naneh,FIB(1,(n-1)/2,3) = n

Bukti

Kasus-kasus dimana n < 5dapat diperiksa secara mendalam.

Misalkan kita memiliki dua solusi minimal untuk n >= 5, a0,b0dan a1,b1dengan a0 + b0 = a1 + b1dan a0 != a1.

Lalu ada yang k0,k1seperti itu FIB(a0,b0,k0) = FIB(a1,b1,k1) = n.

• Kasus 1: k0 = k1

  WLOG menganggap b0 < b1(dan karenanya a0 > a1)

  Membiarkan DIFF(k)menjadi perbedaan antara urutan seperti Fibonnaci dimulai dengan a1,b1dan a0,b0:

  DIFF(k) = FIB(a1,b1,k) - FIB(a0,b0,k) = FIB(a1-a0,b1-b0,k) (Lemma 1)

  DIFF(0) = a1 - a0 < 0

  DIFF(1) = b1 - b0 > 0

  DIFF(2) = (a1+b1) - (a0+b0) = 0

  DIFF(3) = DIFF(1) + DIFF(2) = DIFF(1) > 0

  DIFF(4) = DIFF(2) + DIFF(3) = DIFF(3) > 0

  Setelah urutan seperti Fibonnaci memiliki 2 istilah positif, semua istilah berikutnya positif.

  Jadi, satu-satunya waktu DIFF(k) = 0adalah kapan k = 2, jadi satu-satunya pilihan k0 = k1adalah 2.

  Karena itu n = FIB(a0,b0,2) = a0 + b0 = a1 + b1

  Minimal dari solusi ini bertentangan dengan Lemma 2.

• Kasus 2 k0 != k1::

  WLOG berasumsi k0 < k1.

  Kita punya FIB(a1,b1,k1) = n

  Membiarkan a2 = FIB(a1,b1,k1-k0)

  Membiarkan b2 = FIB(a1,b1,k1-k0+1)

  Kemudian FIB(a2,b2,k0) = FIB(a1,b1,k1) = FIB(a0,b0,k0)(berolahraga untuk pembaca)

  Karena FIB(a1,b1,k)tidak negatif untuk k >= 0, itu juga tidak menurun.

  Ini memberi kita a2 >= b1 > a0dan b2 >= a1+b1 = a0+b0.

  Kalau begitu biarkan DIFF(k) = FIB(a2,b2,k) - FIB(a0,b0,k) = FIB(a2-a0,b2-b0,k)(Lemma 1)

  DIFF(0) = a2 - a0 > 0

  DIFF(1) = b2 - b0 >= (a0 + b0) - b0 = a0 >= 0

  DIFF(2) = DIFF(0) + DIFF(1) >= DIFF(0) > 0

  DIFF(3) = DIFF(1) + DIFF(2) >= DIFF(2) > 0

  Sekali lagi, DIFFmemiliki 2 istilah positif dan oleh karena itu semua istilah berikutnya adalah positif.

  Jadi, satu-satunya waktu ketika itu mungkin DIFF(k) = 0adalah k = 1, jadi satu-satunya pilihan k0adalah 1.

  FIB(a0,b0,1) = n

  b0 = n

  Ini bertentangan dengan Lemma 2.

Haskell , 76 72 74 byte

EDIT:

• -4 byte: @ H.PWiz menyarankan untuk menggunakan /alih-alih div, meskipun ini membutuhkan penggunaan tipe angka pecahan.
• +2 byte: Memperbaiki bug dengan Enumrentang dengan menambahkan -1.

fmengambil nilai Doubleatau Rationaltipe dan mengembalikan tupel yang sama. Doubleharus mencukupi untuk semua nilai yang tidak cukup besar untuk menyebabkan kesalahan pembulatan, sementara Rationalsecara teoritis tidak terbatas.

f n|let a?b=b==n||b<n&&b?(a+b)=[(a,s-a)|s<-[1..],a<-[0..s/2-1],a?(s-a)]!!0

Cobalah online! (dengan penyesuaian header H.PWiz untuk input / output Rationaldalam format integer)

Bagaimana itu bekerja

• ?adalah operator yang bersarang secara lokal dalam lingkup f. a?blangkah-langkah rekursif melalui urutan Fibonacci mulai dari a,bsampai b>=n, kembali Truejika itu ntepat.
• Dalam pemahaman daftar:
  • siterates melalui semua angka dari 1atas, mewakili jumlah adan b.
  • aiterates melalui angka dari 0ke s/2-1. (Jika sganjil, ujung rentang ditangkap.)
  • a?(s-a)menguji apakah urutan dimulai dengan a,s-aklik n. Jika demikian, pemahaman daftar termasuk tuple (a,s-a). (Artinya b=s-a, meskipun terlalu pendek untuk diberi nama.)
  • !!0 memilih elemen pertama (klik) dalam pemahaman.

APL (Dyalog) , 75 71 64 59 53 48 44 43 byte

2 byte disimpan berkat @ Adám

12 byte disimpan berkat @ngn

⊃o/⍨k∊¨+\∘⌽⍣{k≤⊃⍺}¨o←a/⍨</¨a←,⍉|-\¨⍳2⍴1+k←⎕

Cobalah online!

Penggunaan ⎕IO←0.

Bagaimana? Ini benar-benar gila.

k←⎕ - tetapkan input ke k

⍳2⍴1+k←⎕- Produk Cartesian dari kisaran 0untuk kdengan sendirinya

|-\¨ - kurangi setiap elemen pasangan kanan dari kiri, dan dapatkan nilai absolut

a←,⍉ - transpos, ratakan dan tetapkan ke a

o←a/⍨</¨a - pertahankan hanya pasangan di mana elemen kiri lebih kecil dari kanan, dan tetapkan o

osekarang berisi daftar semua pasangan dengan a < b, diperintahkan oleh rata-rata aritematis mereka

+\∘⌽⍣{k≤⊃⍺}¨o- untuk setiap pasangan dalam o, terapkan fibonacci (membalikkan pasangan dan cumsum) sampai katau jangka waktu yang lebih tinggi tercapai

k∊¨- lalu tentukan apakah kini istilah terakhir (artinya terkandung dalam urutan)

o/⍨- dan simpan pasangan di otempat pemeriksaan sebelumnya berlaku

⊃ - kembalikan hasil pertama.

Python 2 , 127 109 107 byte

-2 byte berkat ovs (berubah andmenjadi *)

g=lambda x,a,b:a<=b<x and g(x,b,a+b)or b==x
f=lambda n,s=1,a=0:g(n,a,s-a)*(a,s-a)or f(n,s+(a==s),a%s+(a<s))

Cobalah online!

Ada poin bonus untuk n,a,s-a?

Penjelasan:

• Baris pertama menyatakan lambda rekursif g, yang memverifikasi apakaha, b diperluas sebagai urutan Fibonacci akan mencapai x. Ini juga memeriksa itu a <= b, salah satu kriteria pertanyaan. (Ini akan memungkinkan kasus di mana a == b, tetapi dalam kasus seperti 0, aitu sudah ditemukan dan dikembalikan).
  • Ketidaksetaraan dirantai a<=b<xmelakukan dua tugas praktis sekaligus: memverifikasi a <= b, dan itu b < x.
  • Jika b < x hasil True, fungsi menyebut dirinya lagi dengan dua angka berikutnya dalam urutan Fibonacci: b, a+b. Ini berarti fungsinya akan terus mengerjakan ketentuan baru sampai ...
  • Jika b < xhasil False, maka kita telah mencapai titik di mana kita perlu memeriksa apakah b==x. Jika demikian, ini akan kembali True, menandakan bahwa pasangan awala, b pada akhirnya akan mencapai x. Kalau tidak, jika b > x, pasangan tidak valid.
• Baris kedua menyatakan lambda rekursif lain f, yang menemukan solusi untuk nilai yang diberikan n. Secara rekursif mencoba pasangan awal baru,a, b ,, hingga g(n, a, b)hasil True. Solusi ini kemudian dikembalikan.
  • Fungsi secara rekursif menghitung pasangan Fibonacci awal menggunakan dua variabel, s(awalnya 1) dan a(awalnya 0). Pada setiap iterasi, abertambah, dana, s-a digunakan sebagai pasangan pertama. Namun, ketika aklik s, itu disetel kembali ke 0, dan sbertambah. Ini berarti pasangan dihitung dalam pola berikut:

    s = 1 (0, 1) (1, 0)
    s = 2 (0, 2) (1, 1) (2, 0)
    s = 3 (0, 3) (1, 2), (2, 1), (3, 0)
    

    Jelas, ini mengandung beberapa pasangan yang tidak valid, namun ini dihilangkan secara instan ketika diteruskan ke g(lihat poin pertama).
  • Ketika nilai adan sditemukan sedemikian rupa g(n, a, s-a) == True, maka nilai ini dikembalikan. Karena solusi yang mungkin dihitung dalam urutan 'ukuran' (diurutkan berdasarkan rata-rata, kemudian nilai minimum), solusi pertama yang ditemukan akan selalu menjadi yang terkecil, sesuai dengan permintaan tantangan.

R , 183 byte 160 byte

n=scan();e=expand.grid(n:0,n:0);e=e[e[,2]>e[,1],];r=e[mapply(h<-function(n,a,b,r=a+b)switch(sign(n-r)+2,F,T,h(n,b,r)),n,e[,1],e[,2]),];r[which.min(rowSums(r)),]

Cobalah online!

Terima kasih kepada Giuseppe untuk bermain golf 23 byte

Penjelasan kode

n=scan()                        #STDIO input
e=expand.grid(n:0,n:0)          #full outer join of integer vector n to 0
e=e[e[,2]>e[,1],]               #filter so b > a
r=e[mapply(
  h<-function(n,a,b,r=a+b)switch(sign(n-r)+2,F,T,h(n,b,r)),
                                #create a named recursive function mid-call 
                                #(requires using <- vs = to denote local variable creation 
                                #rather than argument assignment
  n,e[,1],e[,2]),]              #map n, a and b to h() which returns a logical
                                #which is used to filter the possibilities
r[which.min(rowSums(r)),]       #calculate sum for each possibility, 
                                #get index of the minimum and return
                                #because each possibility has 2 values, the mean and 
                                #sum will sort identically.

Mathematica, 117 byte

If[#==1,{0,1},#&@@SortBy[(S=Select)[S[Range[0,s=#]~Tuples~2,Less@@#&],!FreeQ[LinearRecurrence[{1,1},#,s],s]&],Mean]]&

Cobalah online!

Jelly , 19 byte

ṫ-Sṭµ¡³e
0rŒcÇÐfSÐṂ

Cobalah online!

-1 byte berkat buktinya oleh cardboard_box . Dalam kasus ini terbukti salah, Anda dapat menambahkan UṂṚke akhir baris kedua untuk total 22 byte.

GolfScript - 88 77 byte

~:N[,{1+:a,{[.;a]}/}/][{[.~{.N<}{.@+}while\;N=]}/]{)1=\;},{(\;~+}$(\;);~~' '\

Saya tidak memeriksa beberapa solusi, terima kasih ke cardboard_box!

Penjelasan

~:N                           # Reads input
[,{1+:a,{[.;a]}/}/]           # Creates an array of pairs [a b]
[{[.~{.N<}{.@+}while\;N=]}/]  # Compute solutions
{)1=\;},         # Pairs that are not solutions are discarded
{(\;~+}$         # Sorts by mean
(\;);~~' '\      # Formats output

Batch, 160 158 byte

@set/aa=b=0
:g
@if %a% geq %b% set/ab-=~a,a=0
@set/ac=a,d=b
:l
@if %c% lss %1 set/ad+=c,c=d-c&goto l
@if %c% gtr %1 set/aa+=1,b-=1&goto g
@echo %a% %b%