Los números iniciales más bajos en una secuencia similar a Fibonacci

22

Dada una entrada entera positiva N , genera los dos números no negativos, a y b , donde a <b , con el valor medio más bajo posible que dará como resultado que el número N sea ​​parte de la secuencia de relaciones recurrentes:

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

En caso de que haya más de una solución donde la media de a y b sean mínimas, entonces debe generar la que tenga la b más baja .

Puede suponer que N está dentro del rango representativo de enteros en su idioma / sistema.

Casos de prueba

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
Stewie Griffin
fuente
Si a>=0, y a<bhay siempre varias soluciones?
Jonathan Allan
No puedo garantizar que haya o no múltiples soluciones. Tanto 1,4y 2,3daría 5, y tienen la misma media. Supongo que es posible encontrar casos similares a ese, donde estos son los valores medios más bajos. Si puede mostrar / probar que no hay múltiples soluciones, entonces no necesita verificar esa condición.
Stewie Griffin
2
totalmente inspirado en codegolf.stackexchange.com/q/147200/67961
J42161217
3
La secuencia OEIS correspondiente para la media más baja posible, A249783 , tiene un gráfico de aspecto salvaje .
Peter Kagey el
1
@ ØrjanJohansen Agregué una prueba a mi respuesta de que no hay soluciones duplicadas (ya que mi respuesta dependía de ello).
cardboard_box

Respuestas:

8

Casco , 19 18 16 14 13 15 bytes

Gracias Zgarb por guardar 1 byte.

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

Pruébalo en línea!

Explicación:

Descargo de responsabilidad: realmente no entiendo la ȯƒẊ++sección del código.

Editar: Parece traducir al Haskell fix.(mapad2(+).).(++), donde mapad2se aplica la función a todos los pares adyacentes en una lista. (Aunque, conociendo a Husk, en el contexto de este programa podría significar algo más)

            Θḣ⁰    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)?
H.PWiz
fuente
Estoy seguro de que lo intenté ...
H.PWiz
8

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

-3 bytes -1 byte gracias a ThePirateBay

-8 -9 bytes gracias a 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]

Pruébalo en línea!

Nota: esta solución se basa en el hecho de que nunca hay múltiples soluciones mínimas.

Prueba de que nunca hay múltiples soluciones:

Sea FIB(a,b,k)la secuencia similar a Fibonacci que comienza con 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)

Lema 1

La diferencia entre secuencias similares a Fibonacci es en sí misma similar a Fibonacci, es decir FIB(a1,b1,k) - FIB(a0,b0,k) = FIB(a1-a0,b1-b0,k). La prueba se deja al lector.

Lema 2

Para n >= 5, a,bexiste una solución satisfactoria a+b < n:

si nes parFIB(0,n/2,3) = n

si nes extrañoFIB(1,(n-1)/2,3) = n

Prueba

Casos donde n < 5se pueden verificar exhaustivamente.

Supongamos que tenemos dos soluciones mínimas para n >= 5, a0,b0y a1,b1con a0 + b0 = a1 + b1y a0 != a1.

Entonces existe k0,k1tal que FIB(a0,b0,k0) = FIB(a1,b1,k1) = n.

  • Caso 1: k0 = k1

    WLOG asume b0 < b1(y por lo tanto a0 > a1)

    Sea DIFF(k)la diferencia entre las secuencias similares a Fibonnaci que comienzan con a1,b1y a0,b0:

    DIFF(k) = FIB(a1,b1,k) - FIB(a0,b0,k) = FIB(a1-a0,b1-b0,k) (Lema 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

    Una vez que una secuencia similar a Fibonnaci tiene 2 términos positivos, todos los términos posteriores son positivos.

    Por lo tanto, el único momento DIFF(k) = 0es cuándo k = 2, por lo que la única opción para k0 = k1es 2.

    Por lo tanto n = FIB(a0,b0,2) = a0 + b0 = a1 + b1

    La minimidad de estas soluciones contradice el Lema 2.

  • Caso 2 k0 != k1:

    WLOG asume k0 < k1.

    Tenemos FIB(a1,b1,k1) = n

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

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

    Luego FIB(a2,b2,k0) = FIB(a1,b1,k1) = FIB(a0,b0,k0)(ejercicio para el lector)

    Como FIB(a1,b1,k)no es negativo para k >= 0, tampoco es decreciente.

    Esto nos da a2 >= b1 > a0y b2 >= a1+b1 = a0+b0.

    Entonces deja DIFF(k) = FIB(a2,b2,k) - FIB(a0,b0,k) = FIB(a2-a0,b2-b0,k)(Lema 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

    Una vez más, DIFFtiene 2 términos positivos y, por lo tanto, todos los términos posteriores son positivos.

    Por lo tanto, el único momento en que es posible DIFF(k) = 0es k = 1, por lo que la única opción k0es 1.

    FIB(a0,b0,1) = n

    b0 = n

    Esto contradice el Lema 2.

caja de cartón
fuente
1
77 bytes
Neil
@Neil Eso minimiza en blugar de minimizar a+b, y así su solución da f(27) = [3,7]pero la solución óptima es f(27)=[0,9]. Después de revertir los cambios de última hora, tenemos 83 bytes.
caja de cartón
1
Creo que puede guardar otro byte utilizando en b-~alugar de a+b+1.
Neil
1
Hay un pequeño error en su segundo caso: a2 >= a1 + b1no es correcto cuando k1-k0=1. En su lugar, puede usar a2 >= b1 > a0y b2 >= a1+b1 = a0+b0, y luego el resto sigue.
Ørjan Johansen
8

Haskell , 76 72 74 bytes

EDITAR:

  • -4 bytes: @ H.PWiz sugirió usar en /lugar de div, aunque esto requiere usar un tipo de número fraccionario.
  • +2 bytes: se corrigió un error con Enumrangos al agregar -1.

ftoma un valor de Doubleo Rationaltype y devuelve una tupla de lo mismo. Doubledebería ser suficiente para todos los valores que no son lo suficientemente grandes como para causar errores de redondeo, mientras Rationalque en teoría es ilimitado.

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

Pruébalo en línea! (con los ajustes del encabezado de H.PWiz a las entradas / salidas Rationalen formato entero)

Cómo funciona

  • ?es un operador anidado localmente en el ámbito de f. a?bavanza recursivamente a través de la secuencia similar a Fibonacci comenzando con a,bhasta b>=n, y regresa Truesi llega a golpear nexactamente.
  • En la lista de comprensión:
    • sitera a través de todos los números desde 1arriba, representando la suma de ay b.
    • aitera a través de los números de 0a s/2-1. (Si ses impar, el final del rango se redondea).
    • a?(s-a)prueba si la secuencia comienza con a,s-ahits n. Si es así, la comprensión de la lista incluye la tupla (a,s-a). (Es decir, b=s-aaunque era demasiado corto para que valiera la pena nombrarlo).
    • !!0 selecciona el primer elemento (hit) en la comprensión.
Ørjan Johansen
fuente
8

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

2 bytes guardados gracias a @ Adám

12 bytes guardados gracias a @ngn

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

Pruébalo en línea!

Usos ⎕IO←0.

¿Cómo? Esto se había vuelto realmente loco.

k←⎕ - asignar entrada a k

⍳2⍴1+k←⎕- Producto cartesiano de la gama 0para kconsigo mismo

|-\¨ - reste cada elemento del par derecho de la izquierda y obtenga valores absolutos

a←,⍉ - transponer, aplanar y asignar a a

o←a/⍨</¨a - mantenga solo pares donde el elemento izquierdo sea más pequeño que el derecho, y asigne a o

oahora contiene una lista de todos los pares a < b, ordenados por su media aritmética

+\∘⌽⍣{k≤⊃⍺}¨o- para cada par o, aplique fibonacci (invierta el par y el cumsum) hasta kque se alcance un plazo mayor

k∊¨- luego decida si kes este último término (lo que significa que está contenido en la secuencia)

o/⍨- y mantener pares en odonde se aplica la verificación anterior

- Devuelve el primer resultado.

Uriel
fuente
5

Python 2 , 127 109 107 bytes

-2 bytes gracias a ovs (cambiando anda *)

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

Pruébalo en línea!

¿Algún punto extra para n,a,s-a?

Explicación:

  • La primera línea declara una lambda recursiva g, que verifica si se a, bexpande como una secuencia de Fibonacci x. También verifica eso a <= b, uno de los criterios de la pregunta. (Esto permitiría casos donde a == b, pero en tal caso 0, aya se habrían descubierto y devuelto).
    • La desigualdad encadenada a<=b<xrealiza dos tareas prácticas a la vez: verificar a <= by eso b < x.
    • Si b < xlos rendimientos True, la función se llama a sí mismo de nuevo con los dos números siguientes en la secuencia de Fibonacci: b, a+b. Esto significa que la función seguirá resolviendo nuevos términos hasta ...
    • Si b < xrinde False, entonces hemos llegado al punto en el que debemos verificar si b==x. Si es así, esto regresará True, lo que significa que el par inicial a, beventualmente alcanzará x. De lo contrario, si b > xel par no es válido.
  • La segunda línea declara otra lambda recursiva f, que encuentra la solución para un valor dado n. Intenta recursivamente nuevos pares iniciales a, b, hasta que g(n, a, b)rinde True. Esta solución luego se devuelve.
    • La función cuenta recursivamente pares iniciales de Fibonacci utilizando dos variables, s(inicialmente 1) y a(inicialmente 0). En cada iteración, ase incrementa y a, s-ase usa como el primer par. Sin embargo, cuando agolpea s, se restablece a 0 y sse incrementa. Esto significa que los pares se cuentan en el siguiente patrón:
      s = 1 (0, 1) (1, 0)
      s = 2 (0, 2) (1, 1) (2, 0)
      s = 3 (0, 3) (1, 2), (2, 1), (3, 0)
      
      Obviamente, esto contiene algunos pares no válidos, sin embargo, estos se eliminan instantáneamente cuando se pasan a g(ver el primer punto).
    • Cuando los valores ay sse encuentran de tal manera g(n, a, s-a) == True, se devuelve este valor. Como las posibles soluciones se cuentan en orden de 'tamaño' (ordenadas por la media, luego el valor mínimo), la primera solución encontrada siempre será la más pequeña, según lo requiera el desafío.
FlipTack
fuente
3

R , 183 bytes 160 bytes

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

Pruébalo en línea!

Gracias a Giuseppe por jugar golf en 23 bytes

Explicación del código

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.
marca
fuente
1
160 bytes : en general, debe guardar los bytes siempre que pueda, por lo que guardar 4 bytes eliminando los nombres agradables no solo es aceptable o recomendable, sino que, en cierto sentido, lo requiere el código de golf . Aun así, buena respuesta, +1.
Giuseppe
1

Mathematica, 117 bytes

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


Pruébalo en línea!

J42161217
fuente
1

Jalea , 19 bytes

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

Pruébalo en línea!

-1 byte gracias a la prueba de cartón_box . En caso de que sea refutado, puede agregar UṂṚal final de la segunda línea 22 bytes en total.

Erik el Outgolfer
fuente
... un incremento inicial debería resolver la observación de @ StewieGriffin.
Jonathan Allan
Tengo la sensación de que puedes dejar caer el
Jonathan Allan
1
Solo necesitamos encontrar la semilla que hace que la entrada x, parezca más reciente. Si x se encontraran en el tercer índice para múltiples, entonces funciona 0,xy, por lo tanto, también funcionaría en 1,(x-1)/2( ximpar) o 2,x/2-1( xpar), con xlo cual aparecería más adelante en el resultado, de modo que eso no sucederá. Para una colisión posterior, la media solo puede ser la misma si los terceros términos también son iguales, pero entonces uno debe tener una diferencia menor entre los términos iniciales (de lo contrario, serían los mismos) y, por lo tanto, se habrá xencontrado en un índice posterior . Como tal, podemos hacer ṫ-Sṭµ¡i³¶ḶŒcÇÐṀguardar cuatro bytes.
Jonathan Allan
... Uy, más el incremento:ṫ-Sṭµ¡i³¶‘ḶŒcÇÐṀ
Jonathan Allan
@StewieGriffin Ese caso de prueba no existía cuando respondí: p
Erik the Outgolfer
1

GolfScript - 88 77 bytes

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

¡No busqué varias soluciones, gracias a cartón_box!

Explicación

~: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
FedeWar
fuente
Pruébalo en línea!
Ørjan Johansen
0

Lotes, 160 158 bytes

@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%
Neil
fuente
Esto (también) da 3 7en entrada 27. La solución correcta es 0 9.
caja de cartón
@cardboard_box Todavía no veo dónde la pregunta requiere que ...
Neil
En la primera oración: "con el valor medio más bajo posible".
cartón_12 de
@cardboard_box Ah, lo siento, fue demasiado fácil pasarlo por alto.
Neil
1
@cardboard_box OK debería arreglarse ahora.
Neil