Einführung

Ihr Ziel ist es, die kleinste Anzahl zu finden, die Sie addieren oder multiplizieren müssen, um den Eingabewert zu erhalten. Dies ist A005245 .

Eingang

Eine positive ganze Zahl N .

Ausgabe

Die kleinste Anzahl von Einsen, die addiert / multipliziert werden müssen, um N zu erhalten .

Sample Input

7

Beispielausgabe

6

Erläuterung

( 1+ 1+ 1) * ( 1+ 1) + 1= 7

Da dies 6Einsen erfordert , ist die Ausgabe6

Testfälle

 1  1
 2  2
 3  3
 5  5
10  7
20  9
50 12

Da dies eine Code-Golf- Herausforderung ist, gewinnt die niedrigste Anzahl von Bytes.

Python 2 , 74-70 Bytes

f=lambda n:min([n]+[f(j)+min(n%j*n+f(n/j),f(n-j))for j in range(2,n)])

Probieren Sie es online!

Alternative Version, 59 Bytes (nicht überprüft)

f=lambda n:min([n]+[f(j)+f(n/j)+f(n%j)for j in range(2,n)])

Dies funktioniert mindestens bis zu n = 1.000.000 , aber ich muss noch beweisen, dass es für alle positiven n funktioniert .

Probieren Sie es online!

Gelee , 16 bis 14 Bytes

Danke Dennis, dass du 2 Bytes gespart hast!

ÆḌḊ,Ṗ߀€+U$FṂo

Probieren Sie es online!

Logik Erklärung

Gegeben eine Nummer n :

• Wenn 1ja, lautet die Antwort 1. Andernfalls:

Die Darstellung ist entweder a + boder a × b, wo aundb sind Ausdrücke.

Berücksichtigen Sie alle möglichen Werte von aund b:

• Wenn die Darstellung ist a + b, dann aund bsind in Reichweite [1 .. n-1].
• Wenn die Darstellung ist a × b, aund bsind richtige Teiler von ngrößer als 1.

In beiden Fällen wird die Liste [[<proper divisors of n larger than 1>], [1, 2, ..., n-1]]berechnet ( ÆḌḊ,Ṗ), der aktuelle Link wird über jede Zahl ߀€abgebildet, die richtigen Paare werden addiert ( +U$) und der Mindestwert wird ermittelt ( FṂo).

Code Erklärung

ÆḌḊ,Ṗ߀€+U$FṂo   Main link. Assume n = 10.
ÆḌ       Proper divisors. [1,2,5]
  Ḋ      Ḋequeue, remove the first element. [2,5]
   ,Ṗ    Pair with Ṗop. Auto convert n = 10 to range 
         [1,2,3,4,5,6,7,8,9,10] and remove the last element
         10, get [1,2,3,4,5,6,7,8,9].

߀€      Apply this link over each element.
   +U$   Add with the Upend of itself.

FṂ       Flatten and get the Ṃinimum element.
  o      Logical or with n.
         If the list is empty, minimum returns 0 (falsy), so logical or
         convert it to n.

JavaScript (ES6), 108 96 Bytes

f=n=>n<6?n:Math.min(...[...Array(n-2)].map((_,i)=>Math.min(f(++i)+f(n-i),n%++i/0||f(i)+f(n/i))))

Sehr ineffizient; Array(n>>1)beschleunigt es leicht auf Kosten eines Bytes. Erklärung: n%++iIst inicht Null, wenn kein Faktor ist, n%++i/0ist es also Infinity(und daher wahr und auch definitiv nicht minimal), wenn ies kein Faktor ist, aber NaN(und daher falsch), wenn ies ein Faktor ist. Bearbeiten: 12 Bytes mit Inspiration von @ edc65 gespeichert.

Pari / GP , 66 Bytes

Ein Port von Dennis 'Python-Antwort :

f(n)=vecmin(concat(n,[f(j)+min(n%j*j+f(n\j),f(n-j))|j<-[2..n-1]]))

Probieren Sie es online!

Pari / GP , 72 Bytes

Länger, aber effizienter:

f(n)=if(n<6,n,vecmin([if(d>1,f(d)+f(n/d),1+f(n-1))|d<-divisors(n),d<n]))

Probieren Sie es online!

Pari / GP , 213 Bytes

Edit: Ich bin schwer geschlagen worden .

f(n)={d;n<6&return(n);if(n<=#a,a[n]&return(a[n]),a=vector(n));for(i=1,n-1,a[i]||a[i]=f(i));a[n]=min(vecmin(vector(n\2,k,a[k]+a[n-k])),if(isprime(n),n,vecmin(vector((-1+#d=divisors(n))\2,i,a[d[i+1]]+a[d[#d-i]]))))}

Probieren Sie es online!

Python 2 , 181 Bytes

def F(N,n,s="",r=""):
 try:
	if n<1:return(eval(s)==N)*0**(`11`in s or"**"in s)*s
	for c in"()+*1":r=F(N,~-n,s+c)or r
 except:r
 return r
f=lambda N,n=1:F(N,n).count(`1`)or f(N,-~n)

Probieren Sie es online!

Wolfram Language (Mathematica) , 59 Bytes

3 Bytes gespart dank Martin Ender. Bei Verwendung der CP-1252-Codierung ±ist ein Byte erforderlich.

±1=1;±n_:=Min[1+±(n-1),±#+±(n/#)&/@Divisors[n][[2;;-2]]]

Probieren Sie es online!

Perl 5 , -p 78 Bytes

79 Bytes im alten Stil zählen ( +1z-p )

Die Tatsache, dass Perl $für alle skalaren Zugriffe ein Extra verwenden muss, schadet der Länge von Golfplätzen, die viel arithmetisches ...

Diese Methode ähnelt größtenteils den bereits veröffentlichten Methoden (versuchen Sie Multiplikation und Addition, um eine Zielzahl zu erstellen, nehmen Sie die billigste). Es wird jedoch nicht wiederholt heruntergefahren, sodass es für relativ große Eingaben verwendet werden kann.

Es wird auch nicht versucht, die Kosten für das Erstellen einer Zahl durch Addition oder Multiplikation zu minimieren, da Perl 5 keine eingebaute minund numerische Sortierung keine ausreichende ist (wie aus der Sortierung noch im Code ersichtlich ist). Stattdessen gehe ich einfach davon aus, dass ich die Multiplikation verwenden werde, wenn eine Zahl ein Faktor des Ziels ist. Das ist sicher, denn wenn zB 3ein Faktor von 12(so summiert er die Kosten von 3und 12/3) später in der Schleife ist, wird geprüft, 9=12-3welcher kein Faktor ist, also 9+3mit den gleichen Kosten 3+9, die sowieso ausprobiert werden. Dies kann jedoch für Ziele fehlschlagen <= 4(dies gilt nur für 1und 2). Das Hinzufügen $_zur Liste, um das zu minimieren, behebt das. Was bedauerlich ist, da ich das eigentlich nicht für die Basisfälle benötige, weil ich es bereits initialisiere@; mit den richtigen Startwerten kostet also 3 Bytes.

#!/usr/bin/perl -p
($_)=sort{$a-$b}$_,map{$;[$_]+$;[$'%$_?$'-$_:$'/$_]}//..$_ for@;=0..$_;$_=pop@

Probieren Sie es online!