Znajdź liczbę, aby uzyskać numer, używając + i *

28

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 , wygrywa najmniejsza liczba bajtów.

Spyrali Chyuu
źródło
4
OEIS A005245
betseg
9
Witamy w Programowaniu zagadek i Code Golf! Jako pierwsze wyzwanie jest w porządku, ale następnym razem skorzystaj z piaskownicy przed opublikowaniem wyzwań, aby uzyskać opinie!
betseg
4
Proponuję zmodyfikować to, aby wyraźnie stwierdzić, że szukasz minimalnej liczby wymaganych. W przeciwnym razie po prostu wyprowadzenie oryginalnego numeru i twierdzenie, że jest to liczba tych, które należy dodać razem, byłoby prawidłowym rozwiązaniem.
Kudłaty
2
Czy istnieją przykłady, f(x) != x.primeFactorisation().sum()z wyjątkiem 1?
jrtapsell
1
@jrtapsell: tak. Podany przykład $ f (7) = 6 $ to jeden. Dla każdego (wystarczająco dużego) pierwszego $ p $ możesz dodać $ p-1 $ i dodać jeden. Być może możesz jeszcze lepiej.
Ross Millikan

Odpowiedzi:

17

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!

Dennis
źródło
Przepraszam, jeśli brakuje mi czegoś prostego, ale nie jest oczywiste, że wypróbowuje ono każde wykonalne drzewo wyrażeń. W szczególności mamy zewnętrzną warstwę n=a*j+bz b<j, ale możemy potrzebować b>=j?
xnor
Hm, to by się nie powiodło, gdyby jedno b>=ji drugie b>=a. Ale masz rację, nie jest oczywiste, że tak się nie stanie.
Dennis
Ciekawe, że nie ma kontrprób do 1 000 000, zastanawiam się, czy tak naprawdę zawsze działa. Moim najlepszym pomysłem na kontrprzykład byłaby forma a*b+c*dze a,b,c,dwszystkimi wyrażeniami sumowania i są one bardzo wydajne.
xnor
10

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.
użytkownik202729
źródło
5

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.

Neil
źródło
Próbowałem uruchomić to w tle, aby sprawdzić, czy faktycznie można go obliczyć, f(50)ale niestety Windows Update uruchomił ponownie komputer, zanim mógł się skończyć.
Neil,
Czy próbowałeś choć raz przejść się po tablicy?
edc65
@ edc65 Przepraszam, ale nie jestem pewien, co sugerujesz i dlaczego.
Neil
Widzę 2 mapy, z których każda skanuje atablicę. Czy nie możesz scalić ocen w 2 lambdach i wziąć min?
edc65
@ edc65 Ach tak, z jakiegoś powodu myślałem, że zagnieżdżanie min nie będzie tańsze, ale mogę zastąpić (i+=2)innym, ++iwięc oszczędzam w sumie 12 bajtów, dzięki!
Neil
5

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!

alephalpha
źródło
1
Dennis poprawiła swoją metodę i używając które można zapisać 11 bajtów: f(n)=vecmin(concat(n,[f(j)+f(n\j)+f(n%j)|j<-[2..n-1]])).
Jonathan Allan
4

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!

MD XF
źródło
3

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!

Jonathan Frech
źródło
@ pizzapants184 Główna funkcja fnie może być anonimowa, ponieważ wywołuje się rekurencyjnie.
Jonathan Frech
Ach, przepraszam, nie widziałem tego.
pizzapants184
1

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!

Ton Hospel
źródło