Suma de combinaciones con repetición.

8

Escriba el código más corto que pueda para resolver el siguiente problema:

Entrada:

Un entero X con 2 <= XyX <= 100

Salida:

Combinaciones totales de 2, 3 y 5 (se permite la repetición, el orden importa) cuya suma es igual a X.

Ejemplos:

Entrada: 8

Salida: 6porque las combinaciones válidas son:

3+5
5+3
2+2+2+2
2+3+3
3+2+3
3+3+2

Entrada: 11

Salida: 16porque las combinaciones válidas son

5+3+3
5+2+2+2
3+5+3
3+3+5
3+3+3+2
3+3+2+3
3+2+3+3
3+2+2+2+2
2+5+2+2
2+3+3+3
2+3+2+2+2
2+2+5+2
2+2+3+2+2
2+2+2+5
2+2+2+3+2
2+2+2+2+3

Entrada: 100

Salida: 1127972743581281porque las combinaciones válidas son ... muchas

La entrada y salida pueden ser de cualquier forma razonable. El conteo de bytes más bajo en cada idioma gana. Aplican reglas estándar de .

anta40
fuente
1
Bienvenido a PPCG! Desafortunadamente, aquí no respondemos preguntas generales de programación. Sin embargo, es posible que pueda obtener ayuda sobre Stack Overflow . Solo asegúrese de consultar su centro de ayuda antes de preguntar. :)
Erik the Outgolfer
1
¿Alguien puede reformular esto como un desafío? Porque esto sería divertido.
Urna mágica de pulpo
1
@Shaggy Ugghhh ... filtrar los desafíos con la palabra sumen ellos no fue una buena idea para tratar de resolver esa pregunta ...
Urna de pulpo mágico
2
Reescribí un poco tu pregunta para que se adaptara mejor a codegolf. También cambié el resultado para la entrada 11de 12a 16. Por supuesto, siéntete libre de arreglar esto si no
entendí
2
Esto es oeis.org/A079973
Ton Hospel

Respuestas:

9

Python 2 , 46 45 bytes

gracias a xnor por -1 byte

f=lambda n:n>0and f(n-2)+f(n-3)+f(n-5)or n==0

Pruébalo en línea!

ovs
fuente
Parece que and/orlas obras y ahorra un byte: f=lambda n:n>0and f(n-2)+f(n-3)+f(n-5)or n==0.
xnor
@xnor muchas gracias. Acabo de intentar que al revés
ovs
6

Oasis , 9 bytes

cd5e++VT1

Pruébalo en línea!

Explicación

        1    # a(0) = 1
       T     # a(1) = 0, a(2) = 1
      V      # a(3) = 1, a(4) = 1

             # a(n) = 
c    +       # a(n-2) +
 d  +        # a(n-3) +
  5e         # a(n-5)
Emigna
fuente
3

Pyth , 9 bytes

/sM{y*P30

Pruébalo aquí!

Pyth , 16 bytes

l{s.pMfqT@P30T./

Pruébalo aquí

¿Cómo?

  1. Genera los factores primos de 30 , a saber [2, 3, 5] , obtiene el conjunto de potencias repetidas N veces, elimina elementos duplicados, suma cada lista y cuenta las ocurrencias de N en eso.

  2. Para cada parición entera p , verifica si p es igual a p ∩ primefac (30) . Solo mantiene aquellos que satisfacen esta condición, y para cada partición k restante , obtiene la lista de permutaciones de k , aplana la lista resultante en 1 nivel, la deduplica y recupera la longitud.

Sr. Xcoder
fuente
3

Jalea , 11 bytes

5ÆRẋHŒPQḅ1ċ

Pruébalo en línea!

Cómo funciona

5ÆRẋHŒPQḅ1ċ -> Programa completo. Argumento: N, un número entero.
5ÆR -> Empuja todos los números primos entre 2 y 5, inclusive.
   ẋH -> Repita esta lista N / 2 veces.
     ŒP -> Generar el conjunto de potencia.
       Q -> Eliminar entradas duplicadas.
        ḅ1 -> Convertir cada uno de unario (es decir, sumar cada lista)
          ċ -> Cuente las ocurrencias de N en esta lista.
Sr. Xcoder
fuente
Acelere reemplazando ³con H(luego expirará a las 12 en lugar de a las 6)
Jonathan Allan
@ JonathanAllan Hecho, gracias.
Sr. Xcoder
2

Perl, 38 bytes

Incluye +1parap

perl -pE '$_=1x$_;/^(...?|.{5})+$(?{$\++})\1/}{' <<< 11; echo

Lo suficientemente interesante que tengo que usar \1para forzar el retroceso. Usualmente uso, ^pero el optimizador de expresiones regulares parece demasiado inteligente para eso y da resultados demasiado bajos. Probablemente tendré que comenzar a dar números de versión de Perl cuando use este truco ya que el optimizador puede cambiar en cada versión. Esto fue probado enperl 5.26.1

Esto 49es eficiente y realmente puede manejar X=100(pero se desborda X=1991)

perl -pe '$\=$F[@F]=$F[-2]+$F[-3]+$F[-5]for($F[5]=1)..$_}{' <<< 100;echo
Ton Hospel
fuente
2

R , 56 49 47 bytes

Enfoque recursivo de la respuesta de ovs . Giuseppe eliminó esos dos bytes finales para que sea 47.

f=pryr::f(+`if`(x<5,x!=1,f(x-2)+f(x-3)+f(x-5)))

Pruébalo en línea!

rturnbull
fuente
1
48 bytes
Giuseppe
@Giuseppe Muy buena mejora!
rturnbull
1
ah, no necesitas el 0(no lo consideré antes), ya que unario también +lo obligará numeric.
Giuseppe
1

MATL , 15 bytes

:"5Zq@Z^!XsG=vs

Muy ineficiente: la memoria requerida es exponencial.

Pruébalo en línea!

Cómo funciona

:"       % For each k in [1 2 ... n], where n is implicit input
  5Zq    %   Push primes up to 5, that is, [2 3 5]
  @      %   Push k
  Z^     %   Cartesian power. Gives a matrix where each row is a Cartesian k-tuple
  !Xs    %   Sum of each row
  G=     %   Compare with input, element-wise
  vs     %   Concatenate all stack contents vertically and sum
         % Implicit end. Implicit display
Luis Mendo
fuente
1

Ruby , 41 bytes

f=->n{n<5?n==1?0:1:[n-5,n-2,n-3].sum(&f)}

Pruébalo en línea!

Esta es una solución recursiva, el ser llamado recurcive: [n-5,n-2,n-3].sum(&f).

MegaTom
fuente
0

Pyth, 12 bytes

l{fqQsTy*P30

Esto es terriblemente ineficiente y alcanza el límite de memoria para entradas superiores a 5.

Pruébalo en línea

Explicación

l{fqQsTy*P30
         P30   Get the prime factors of 30 [2, 3, 5].
        *   Q  Repeat them (implicit) input times.
       y       Take the power set...
  fqQsT        ... and filter the ones whose sum is the input.
l{             Count unique lists.

fuente
0

Wolfram Language (Mathematica) , 43 bytes

Tr[Multinomial@@@{2,3,5}~FrobeniusSolve~#]&

Pruébalo en línea!

Explicación: FrobeniusSolvecalcula todas las soluciones de la suma desordenada 2a + 3b + 5c = n, luego Multinomialcalcula cuántas formas podemos ordenar esas sumas.

O podríamos copiar la solución de todos los demás para el mismo número de bytes:

f@1=0;f[0|2|3|4]=1;f@n_:=Tr[f/@(n-{2,3,5})]
No un arbol
fuente