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
a>=0
, ya<b
hay siempre varias soluciones?1,4
y2,3
daría5
, 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.Respuestas:
Casco ,
191816141315 bytesGracias Zgarb por guardar 1 byte.
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(+).).(++)
, dondemapad2
se 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)fuente
JavaScript (Node.js) ,
92 90 89 91 8382 bytes-3 bytes-1 byte gracias a ThePirateBay-8-9 bytes gracias a Neil.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 cona,b
: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,b
existe una solución satisfactoriaa+b < n
:si
n
es parFIB(0,n/2,3) = n
si
n
es extrañoFIB(1,(n-1)/2,3) = n
Prueba
Casos donde
n < 5
se pueden verificar exhaustivamente.Supongamos que tenemos dos soluciones mínimas para
n >= 5
,a0,b0
ya1,b1
cona0 + b0 = a1 + b1
ya0 != a1
.Entonces existe
k0,k1
tal queFIB(a0,b0,k0) = FIB(a1,b1,k1) = n
.Caso 1:
k0 = k1
WLOG asume
b0 < b1
(y por lo tantoa0 > a1
)Sea
DIFF(k)
la diferencia entre las secuencias similares a Fibonnaci que comienzan cona1,b1
ya0,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) = 0
es cuándok = 2
, por lo que la única opción parak0 = k1
es2
.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 parak >= 0
, tampoco es decreciente.Esto nos da
a2 >= b1 > a0
yb2 >= 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,
DIFF
tiene 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) = 0
esk = 1
, por lo que la única opciónk0
es1
.FIB(a0,b0,1) = n
b0 = n
Esto contradice el Lema 2.
fuente
b
lugar de minimizara+b
, y así su solución daf(27) = [3,7]
pero la solución óptima esf(27)=[0,9]
. Después de revertir los cambios de última hora, tenemos 83 bytes.b-~a
lugar dea+b+1
.a2 >= a1 + b1
no es correcto cuandok1-k0=1
. En su lugar, puede usara2 >= b1 > a0
yb2 >= a1+b1 = a0+b0
, y luego el resto sigue.Haskell ,
76 7274 bytesEDITAR:
/
lugar dediv
, aunque esto requiere usar un tipo de número fraccionario.Enum
rangos al agregar-1
.f
toma un valor deDouble
oRational
type y devuelve una tupla de lo mismo.Double
debería ser suficiente para todos los valores que no son lo suficientemente grandes como para causar errores de redondeo, mientrasRational
que en teoría es ilimitado.Pruébalo en línea! (con los ajustes del encabezado de H.PWiz a las entradas / salidas
Rational
en formato entero)Cómo funciona
?
es un operador anidado localmente en el ámbito def
.a?b
avanza recursivamente a través de la secuencia similar a Fibonacci comenzando cona,b
hastab>=n
, y regresaTrue
si llega a golpearn
exactamente.s
itera a través de todos los números desde1
arriba, representando la suma dea
yb
.a
itera a través de los números de0
as/2-1
. (Sis
es impar, el final del rango se redondea).a?(s-a)
prueba si la secuencia comienza cona,s-a
hitsn
. Si es así, la comprensión de la lista incluye la tupla(a,s-a)
. (Es decir,b=s-a
aunque era demasiado corto para que valiera la pena nombrarlo).!!0
selecciona el primer elemento (hit) en la comprensión.fuente
APL (Dyalog) ,
7571645953484443 bytes2 bytes guardados gracias a @ Adám
12 bytes guardados gracias a @ngn
Pruébalo en línea!
Usos
⎕IO←0
.¿Cómo? Esto se había vuelto realmente loco.
k←⎕
- asignar entrada ak
⍳2⍴1+k←⎕
- Producto cartesiano de la gama0
parak
consigo mismo|-\¨
- reste cada elemento del par derecho de la izquierda y obtenga valores absolutosa←,⍉
- transponer, aplanar y asignar aa
o←a/⍨</¨a
- mantenga solo pares donde el elemento izquierdo sea más pequeño que el derecho, y asigne ao
o
ahora contiene una lista de todos los paresa < b
, ordenados por su media aritmética+\∘⌽⍣{k≤⊃⍺}¨o
- para cada paro
, aplique fibonacci (invierta el par y el cumsum) hastak
que se alcance un plazo mayork∊¨
- luego decida sik
es este último término (lo que significa que está contenido en la secuencia)o/⍨
- y mantener pares eno
donde se aplica la verificación anterior⊃
- Devuelve el primer resultado.fuente
Python 2 ,
127109107 bytes-2 bytes gracias a ovs (cambiando
and
a*
)Pruébalo en línea!
¿Algún punto extra para
n,a,s-a
?Explicación:
g
, que verifica si sea, b
expande como una secuencia de Fibonaccix
. También verifica esoa <= b
, uno de los criterios de la pregunta. (Esto permitiría casos dondea == b
, pero en tal caso0, a
ya se habrían descubierto y devuelto).a<=b<x
realiza dos tareas prácticas a la vez: verificara <= b
y esob < x
.b < x
los rendimientosTrue
, 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 ...b < x
rindeFalse
, entonces hemos llegado al punto en el que debemos verificar sib==x
. Si es así, esto regresaráTrue
, lo que significa que el par iniciala, b
eventualmente alcanzaráx
. De lo contrario, sib > x
el par no es válido.f
, que encuentra la solución para un valor dadon
. Intenta recursivamente nuevos pares inicialesa, b
, hasta queg(n, a, b)
rindeTrue
. Esta solución luego se devuelve.s
(inicialmente 1) ya
(inicialmente 0). En cada iteración,a
se incrementa ya, s-a
se usa como el primer par. Sin embargo, cuandoa
golpeas
, se restablece a 0 ys
se incrementa. Esto significa que los pares se cuentan en el siguiente patrón: Obviamente, esto contiene algunos pares no válidos, sin embargo, estos se eliminan instantáneamente cuando se pasan ag
(ver el primer punto).a
ys
se encuentran de tal manerag(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.fuente
R ,
183 bytes160 bytesPruébalo en línea!
Gracias a Giuseppe por jugar golf en 23 bytes
Explicación del código
fuente
Mathematica, 117 bytes
Pruébalo en línea!
fuente
Jalea , 19 bytes
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.fuente
Ḣ
x
, parezca más reciente. Six
se encontraran en el tercer índice para múltiples, entonces funciona0,x
y, por lo tanto, también funcionaría en1,(x-1)/2
(x
impar) o2,x/2-1
(x
par), conx
lo 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áx
encontrado en un índice posterior . Como tal, podemos hacerṫ-Sṭµ¡i³¶ḶŒcÇÐṀ
guardar cuatro bytes.ṫ-Sṭµ¡i³¶‘ḶŒcÇÐṀ
GolfScript -
8877 bytes¡No busqué varias soluciones, gracias a cartón_box!
Explicación
fuente
Lotes,
160158 bytesfuente
3 7
en entrada27
. La solución correcta es0 9
.