Wprowadzenie

Twoim celem jest znalezienie najmniejszej liczby tych, które musisz dodać lub pomnożyć, aby uzyskać wartość wejściową, to A005245 .

Wkład

Jeden dodatnia N .

Wydajność

Najmniejsza liczba tych, które muszą być dodane / mnożone dostać N .

Przykładowe dane wejściowe

7

Przykładowe dane wyjściowe

6

Wyjaśnienie

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

Ponieważ wymaga to 6jednego, wynikiem jest6

Przypadki testowe

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

Ponieważ jest to wyzwanie związane z golfem , wygrywa najmniejsza liczba bajtów.

Python 2 , 74 70 bajtów

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

Wypróbuj online!

Wersja alternatywna, 59 bajtów (niezweryfikowana)

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

Działa to przynajmniej do n = 1 000 000 , ale muszę jeszcze udowodnić, że działa dla wszystkich dodatnich n .

Wypróbuj online!

Galaretka , 16 14 bajtów

Dzięki Dennis za uratowanie 2 bajtów!

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

Wypróbuj online!

Wyjaśnienie logiczne

Biorąc pod uwagę liczbę n :

• Jeśli jest to 1odpowiedź brzmi 1. Inaczej:

Reprezentacja to albo, a + balbo a × bgdzie ai bsą wyrażeniami.

Rozważ wszystkie możliwe wartości ai b:

• Jeśli reprezentacja jest a + b, wtedy ai bsą w zakresie [1 .. n-1].
• Jeżeli reprezentacja jest a × b, ai bsą odpowiednie dzielniki liczby nwiększe niż 1.

W obu przypadkach lista [[<proper divisors of n larger than 1>], [1, 2, ..., n-1]]jest obliczana ( ÆḌḊ,Ṗ), zamapuj bieżący link na każdym numerze ߀€, dodaj poprawne pary razem ( +U$) i uzyskaj minimalną wartość ( FṂo).

Wyjaśnienie kodu

ÆḌḊ,Ṗ߀€+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 bajtów

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))))

Bardzo nieefektywny; Array(n>>1)nieznacznie przyspiesza kosztem bajtu. Objaśnienie: n%++ijest niezerowy, jeśli inie jest czynnikiem, podobnie n%++i/0jest Infinity(i dlatego jest prawdomówny, a także zdecydowanie nie minimalny), jeśli inie jest czynnikiem, ale NaN(a zatem fałszem), jeśli ijest czynnikiem. Edycja: Zapisano 12 bajtów z inspiracją z @ edc65.

Pari / GP , 66 bajtów

Port odpowiedzi Pytona Dennisa :

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

Wypróbuj online!

Pari / GP , 72 bajty

Dłuższy, ale bardziej wydajny:

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

Wypróbuj online!

Pari / GP , 213 bajtów

Edycja: Zostałem ciężko pobity .

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]]))))}

Wypróbuj online!

Python 2 , 181 bajtów

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)

Wypróbuj online!

Wolfram Language (Mathematica) , 59 bajtów

Zaoszczędzono 3 bajty dzięki Martinowi Enderowi. Korzystanie z kodowania CP-1252, gdzie ±jest jeden bajt.

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

Wypróbuj online!

Perl 5 , -p 78 bajtów

79 bajtów w starym stylu liczenia ( +1dla -p)

Fakt, że Perl musi korzystać z dodatkowego $dostępu do wszystkich skalarów, naprawdę szkodzi długości golfów, które wykonują dużo arytmetyki ...

Ta metoda jest podobna do innych już opublikowanych (spróbuj pomnożyć i dodać, aby zbudować liczbę docelową, weź najtańszą). Jednak nie powtarza się wielokrotnie, więc można go używać do stosunkowo dużych nakładów.

Nie próbuje również zminimalizować kosztu budowy liczby przez dodanie lub zwielokrotnienie [lication, ponieważ perl 5 nie ma wbudowanego, mina sortowanie numeryczne jest dłuższe (jak widać z sortowania wciąż w kodzie). Zamiast tego zakładam tylko, czy liczba jest czynnikiem celu, którego użyję mnożenia. Jest to bezpieczne, ponieważ jeśli np. 3Jest czynnikiem 12(więc sumuje koszt 3i 12/3) później w pętli, rozważy, 9=12-3który nie będzie czynnikiem, więc 9+3przy takim samym koszcie, jak 3+9i tak zostanie wypróbowany. Może to jednak nie powieść się w przypadku celów <= 4(dotyczy to tylko 1i 2). Dodanie$_ do listy w celu zminimalizowania naprawia to. Co jest niefortunne, ponieważ tak naprawdę nie potrzebuję tego w przypadku bazowych przypadków, ponieważ już zainicjowałem@; z prawidłowymi wartościami początkowymi, więc kosztuje 3 bajty.

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

Wypróbuj online!