Encuentre el número de números de x dígitos cuyo producto de dígitos es N

8

Dados dos números N yx, encuentre el número de números de x dígitos cuyo producto de dígitos es N

limits: N(<10^6) and x(<12)

Sample Input:
8 3
Sample Output:
10
fR0DDY
fuente
longitud de código más corta o tiempo de ejecución más corto? Parece que este, el tiempo de ejecución más corto con longitud de código <1000 (por ejemplo) sería un objetivo más significativo.
smci
No entiendo: 2 dígitos x y N, x = 8, N = 3 significa 8 dígitos donde el producto es 3. Como 3 es primo, solo puede ser 3111 ... 1, 1311 ... 1, 113 ... - 8 posibilidades. ¿Qué me estoy perdiendo?
usuario desconocido
@userunknown Es al revés: tres dígitos donde el producto es ocho. (222, 811, 181, 118 y seis formas de organizar 1,2,4, creo.)
breadbox
@breadbox: Mientras tanto, reconocí eso, pero la descripción debería ser reparada. Si doy dos números N y x, no se debe afirmar que me dan dos números x y N (que es el orden en el título también).
usuario desconocido

Respuestas:

3

Python 208 caracteres

def dec(num, num_dig):
    if num_dig==0:
        return int(num==1)
    else:
        return sum(dec(num/i, num_dig-1) for i in range(1,10) if num/i*i==num)

if __name__ == "__main__":    
    print dec(8,3)
Wok
fuente
3

Golfscript 42 31

~10\?.10/\,>{10base{*}*1$=},,\;

Entrada: Espera los números Ny xcomo argumentos de línea de comando (separados por espacio).

El programa se puede probar aquí .

Cristian Lupascu
fuente
Probé y obtuve un Code took longer than 5 seconds to run, so it was aborted.con los parámetros invertidos. :)
usuario desconocido
@userunknown Tienes razón. El código es muy ineficiente cuando xva por encima de 4. Por ejemplo, si lo ejecuto en mi máquina con los parámetros 3 5obtengo el resultado después de más de 30 segundos. Así 3 8que supongo que podrían ser horas ...
Cristian Lupascu
Nunca miré en esta cosa Golfscript. ¿Casi siempre es tan lento?
usuario desconocido
El propósito de @userunknown Golfscript no es la velocidad y se sabe que es un poco lento. Sin embargo, en este caso, es el algoritmo el que es muy ineficiente. Pero el código es corto :)
Cristian Lupascu
1
@userunknown, GolfScript se interpreta en Ruby. Además, todos los valores son inmutables, por lo que hay muchas copias involucradas. No tiende a ser rápido, y a menudo puede agregar una potencia o dos de n al tiempo de ejecución asintótico de los algoritmos que generalmente se analizan en el modelo de RAM.
Peter Taylor
2

Brachylog (2), 13 bytes, desafío de fechas posteriores al idioma

{h.&t~lℕẹ≜×}ᶜ

Pruébalo en línea!

Explicación

{h.&t~lℕẹ≜×}ᶜ
{          }ᶜ   Count the number of
         ≜      values at this point
   &t           formed via taking the last element of the input,
       ℕ        generating an integer
     ~l         of that length,
        ẹ       and splitting it into digits
          ×     such that the product of those digits
 h.             is the first element of {the input}

Un buen truco de golf utilizado aquí es que, a diferencia de casi todos los metapredicados, no le importa en absoluto el valor real de .(que normalmente se usa para construir una salida para los metapredicados); como tal, .se puede usar como cualquier otra variable (guardar un byte porque aparece implícitamente antes }). No hay labelisations implícitos en cualquier lugar aquí, así que he tenido que añadir un labelisation explícita usando para dar algo para contar.


fuente
1

Scala 107:

def f(N:Int,x:Int,s:Int=1):Int=if(s==N&&x==0)1 else
if(s>N||x==0)0 else
((1 to 9).map(i=>f(N,x-1,s*i))).sum

Versión no depurada y amigable:

def findProduct (N: Int, sofar: Int, togo:Int, collected:String=""):Int={
  if (sofar == N && togo == 0) {
    println (collected)
    1
  } else
  if (sofar > N || togo == 0) 0 else 
  (1 to 9).map (x=> findProduct (N, sofar*x, togo-1, collected + " " + x)).sum
}

Invocación con salida de depuración:

scala> findProduct (3, 1, 8)
 1 1 1 1 1 1 1 3
 1 1 1 1 1 1 3 1
 1 1 1 1 1 3 1 1
 1 1 1 1 3 1 1 1
 1 1 1 3 1 1 1 1
 1 1 3 1 1 1 1 1
 1 3 1 1 1 1 1 1
 3 1 1 1 1 1 1 1
res175: Int = 8

scala> findProduct (8, 1, 3)
 1 1 8
 1 2 4
 1 4 2
 1 8 1
 2 1 4
 2 2 2
 2 4 1
 4 1 2
 4 2 1
 8 1 1
res176: Int = 10
usuario desconocido
fuente
Lo probé en simplyscala.com y es realmente rápido. +1 por rendimiento.
Cristian Lupascu
0

Python (todavía trabajando en ello) 164

from itertools import *
N,x=map(int,raw_input().split())
print len([c for c in product([d for d in range(1,10)if N%d==0],repeat=x) if reduce(lambda x,y:x*y,c)==N])
st0le
fuente
0

C # 128

int Z(int n,int x){var i=(int)Math.Pow(10,x-1);return Enumerable.Range(i,i*9).Count(j=>(j+"").Aggregate(1,(a,c)=>a*(c-48))==n);}

Este método C # devuelve el número de xnúmeros de dígitos cuyo producto de dígitos es n. Requiere que los espacios de nombres Systemy System.Linqse importen en el contexto actual.

Versión en línea: http://ideone.com/0krup

Cristian Lupascu
fuente
0

Haskell 117 caracteres

import Data.Char
main = print $ f 3 8
f n t = length[x|x<-[10^(n-1)..(10^n-1)],foldr(*)1(map digitToInt $ show x)==t]
Romain
fuente
0

K, 49

{+/x=*/'"I"$''${x@&~x in y}.!:'"i"$10 xexp y,y-1}

.

k){+/x=*/'"I"$''${x@&~x in y}.!:'"i"$10 xexp y,y-1}[8;3]
10
tmartin
fuente
0

J, 40 bytes

[:+/[=[:*/"1(10#~])#:(10^<:@])}.[:i.10^]

Genera todos los xnúmeros de dígitos, convierte cada uno en base 10, luego encuentra el producto de cada número y prueba si cada número es igual al lado izquierdo, y luego encuentra la suma de cada booleano.

Monja permeable
fuente
0

Jelly , 12 bytes, desafío de fechas posteriores al idioma

,’⁵*r/ḊDP€ċƓ

Pruébalo en línea!

Toma x como argumento de línea de comando y N en la entrada estándar.

Explicación

,’⁵*r/ḊDP€ċƓ
,             On {the input} and
 ’            {the input} minus 1
  ⁵*          take 10 to the power of each of those numbers
    r/        then form a range between them
      Ḋ       without its first element;
       D      treat each element as a list of digits,
        P€    take the product of each of those digit lists,
          ċ   then count the number of times
           Ɠ  the value from standard input appears

La parte difícil es generar la lista de números con x dígitos; el número más bajo es 10 x −1 , el más alto es 10 x −1. El rango aquí se genera al generar primero el par ( x , x −1), luego tomar 10 a la potencia de ambos y luego generar el rango entre ellos. El rango incluye ambos puntos finales por defecto; solo en caso de que N sea ​​0, necesitamos eliminar el extremo superior del rango (que viene primero porque es un rango "hacia atrás") usando .


fuente