Suchen Sie die Anzahl der x-stelligen Zahlen, deren Ziffernprodukt N ist

8

Bestimmen Sie bei zwei Zahlen N und x die Anzahl der x-stelligen Zahlen, deren Ziffernprodukt N ist

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

Sample Input:
8 3
Sample Output:
10
fR0DDY
quelle
kürzeste Codelänge oder kürzeste Laufzeit? Scheint für diese eine, kürzeste Laufzeit mit Codelänge? <1000 (sagen wir) ein sinnvolleres Ziel zu sein.
smci
Ich verstehe nicht: 2 Ziffern x und N, x = 8, N = 3 bedeutet 8 Ziffern, wobei das Produkt 3 ist. Da 3 eine Primzahl ist, kann es nur 3111 ... 1, 1311 ... 1, 113 sein ... - 8 Möglichkeiten. Was vermisse ich?
Benutzer unbekannt
@userunknown Es ist umgekehrt: drei Ziffern, bei denen das Produkt acht ist. (222, 811, 181, 118 und sechs Möglichkeiten, 1,2,4 zu arrangieren, glaube ich.)
Breadbox
@breadbox: Ich habe das inzwischen erkannt, aber die Beschreibung sollte korrigiert werden. Wenn ich zwei Zahlen N und x gebe, sollte nicht behauptet werden, dass ich zwei Zahlen x und N bekomme (was auch die Reihenfolge in der Überschrift ist).
Benutzer unbekannt

Antworten:

3

Python 208 Zeichen

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
quelle
3

Golfscript 42 31

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

Eingabe: Erwartet die Zahlen Nund xals Befehlszeilenargumente (durch Leerzeichen getrennt).

Das Programm kann hier getestet werden .

Cristian Lupascu
quelle
Ich habe getestet und eine Code took longer than 5 seconds to run, so it was aborted.mit umgekehrten Parametern bekommen. :)
Benutzer unbekannt
@userunknown Du hast recht. Der Code ist sehr ineffizient, wenn er xüber 4 hinausgeht. Wenn ich ihn beispielsweise auf meinem Computer mit den Parametern ausführe, 3 5erhalte ich das Ergebnis nach mehr als 30 Sekunden. Also für 3 8ich denke, es könnte Stunden sein ...
Cristian Lupascu
Ich habe mir dieses Golfscript-Ding nie angesehen. Ist es fast immer so langsam?
Benutzer unbekannt
@userunknown Golfscript hat nicht die Geschwindigkeit und ist bekanntermaßen etwas langsam. In diesem Fall ist jedoch der Algorithmus sehr ineffizient. Aber der Code ist kurz :)
Cristian Lupascu
1
@userunknown, GolfScript wird in Ruby interpretiert. Außerdem sind alle Werte unveränderlich, sodass viel kopiert werden muss. Es ist in der Regel nicht schnell und kann der asymptotischen Laufzeit von Algorithmen, die normalerweise im RAM-Modell analysiert werden, häufig eine oder zwei Potenzen von n hinzufügen.
Peter Taylor
2

Brachylog (2), 13 Bytes, Herausforderung nach Sprachdaten

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

Probieren Sie es online aus!

Erläuterung

{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}

Ein netter Golf-Trick, der hier verwendet wird, ist, dass er sich im Gegensatz zu fast allen Metapredikaten überhaupt nicht um den tatsächlichen Wert von kümmert .(der normalerweise verwendet wird, um eine Ausgabe für die Metapredikate zu erstellen). kann als solche .wie jede andere Variable verwendet werden (Speichern eines Bytes, da es implizit vorher angezeigt wird }). Da es hier nirgendwo implizite Beschriftungen gibt, musste ich eine explizite Beschriftung hinzufügen , um etwas zu zählen.


quelle
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

ungolfed, debugfriendly version:

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
}

Aufruf mit Debugging-Ausgabe:

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
Benutzer unbekannt
quelle
Ich habe es auf simplyscala.com getestet und es ist sehr schnell. +1 für Leistung.
Cristian Lupascu
0

Python (arbeitet noch daran) 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
quelle
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);}

Diese C # -Methode gibt die Anzahl der xeinstelligen Zahlen zurück, deren Ziffernprodukt ist n. Es erfordert, dass Namespaces Systemund System.Linqim aktuellen Kontext importiert werden.

Online-Version: http://ideone.com/0krup

Cristian Lupascu
quelle
0

Haskell 117 Zeichen

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
quelle
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
quelle
0

J, 40 Bytes

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

Generiert alle x-stelligen Zahlen, konvertiert jede in Basis 10, findet dann das Produkt jeder Zahl und testet, ob jede Zahl gleich der linken Seite ist, und ermittelt dann die Summe jedes Booleschen Werts.

Undichte Nonne
quelle
0

Jelly , 12 Bytes, Herausforderung nach Sprachdaten

,’⁵*r/ḊDP€ċƓ

Probieren Sie es online aus!

Nimmt x als Befehlszeilenargument und N als Standardeingabe.

Erläuterung

,’⁵*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

Der schwierige Teil besteht darin, die Liste der Zahlen mit x Ziffern zu generieren . die niedrigste solche Zahl ist 10 x –1 , die höchste ist 10 x –1. Der Bereich wird hier erzeugt , indem zuerst das Paar ( x , x −1) erzeugt wird, dann 10 zur Potenz von beiden genommen wird und dann der Bereich zwischen ihnen erzeugt wird. Der Bereich umfasst standardmäßig beide Endpunkte. Nur für den Fall, dass N zufällig 0 ist, müssen wir das obere Ende des Bereichs (der zuerst kommt, weil es ein "Rückwärts" -Bereich ist) mit entfernen .


quelle