Encontre o número de unidades para obter um número usando + e *

28

Introdução

Seu objetivo é encontrar o menor número necessário para adicionar ou multiplicar para obter o valor de entrada, este é A005245 .

Entrada

Um número inteiro positivo N .

Saída

O menor número de aqueles que devem ser adicionados / multiplicados para obter N .

Entrada de amostra

7

Saída de amostra

6

Explicação

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

Como isso requer 6, a saída é6

Casos de teste

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

Como este é um desafio de , o menor número de bytes vence.

Spyrali Chyuu
fonte
4
OEIS A005245
betseg
9
Bem-vindo à Programação de Puzzles e Code Golf! Como primeiro desafio, não há problema, mas, da próxima vez, use o Sandbox antes de postar desafios para obter feedback!
betseg
4
Eu sugiro que modifique isso para declarar explicitamente que você está procurando o número mínimo necessário. Caso contrário, simplesmente enviar o número original e afirmar que é o número de números que você precisa adicionar seria uma solução válida.
Salsicha
2
Existem exemplos em que, f(x) != x.primeFactorisation().sum()exceto 1?
Jrtapsell
1
@jrtapsell: sim. O exemplo dado de $ f (7) = 6 $ é um. Para qualquer valor principal (grande o suficiente) $ p $, você pode fatorar $ p-1 $ e adicionar um. Você pode fazer melhor ainda.
Ross Millikan

Respostas:

17

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

Experimente online!

Versão alternativa, 59 bytes (não verificado)

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

Isso funciona pelo menos até n = 1.000.000 , mas ainda tenho que provar que funciona para todos os n positivos .

Experimente online!

Dennis
fonte
Desculpe se estou perdendo algo simples, mas não é óbvio que isso tente todas as árvores de expressões viáveis. Em particular, temos uma camada externa n=a*j+bcom b<j, mas podemos precisar b>=j?
Xnor
Hum, só falharia se ambos b>=je b>=a. Mas você está certo, não é óbvio que isso não vai acontecer.
Dennis
Interessante que não haja contra-exemplos de até 1.000.000, gostaria de saber se realmente sempre funciona. Meu melhor pensamento para um contra-exemplo seria algo de forma a*b+c*dcom a,b,c,dtodas as expressões de soma e é muito eficiente.
xnor
10

Geléia , 16 14 bytes

Obrigado Dennis por salvar 2 bytes!

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

Experimente online!


Explicação lógica

Dado um número n :

  • Se for 1, a resposta é 1. De outra forma:

A representação é a + bou a × b, onde ae bsão expressões.

Considere todos os valores possíveis de ae b:

  • Se a representação estiver a + b, então ae bestá dentro do alcance [1 .. n-1].
  • Se a representação é a × b, ae bsão divisores próprios de nmaior do que 1.

Nos dois casos, a lista [[<proper divisors of n larger than 1>], [1, 2, ..., n-1]]é calculada ( ÆḌḊ,Ṗ), mapeie o link atual sobre cada número ߀€, adicione os pares corretos ( +U$) e obtenha o valor mínimo ( FṂo).

Explicação do código

ÆḌḊ,Ṗ߀€+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.
user202729
fonte
5

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

Muito ineficiente; Array(n>>1)acelera um pouco a um custo de um byte. Explicação: n%++ié diferente de zero se inão for um fator, o que n%++i/0é Infinity(e, portanto, verdadeiro e também definitivamente não é mínimo) se inão é um fator, mas NaN(e, portanto, falso) se ié um fator. Editar: salvou 12 bytes com inspiração em @ edc65.

Neil
fonte
Tentei executar isso em segundo plano para ver se era realmente capaz de calcular, f(50)mas infelizmente o Windows Update reiniciou o meu PC antes que ele pudesse terminar.
719 Neil
Você tentou uma única caminhada na matriz?
Edc65
@ edc65 Desculpe, mas não sei ao certo o que você está sugerindo e por quê.
194 Neil
Eu vejo 2 mapas, cada um escaneando a amatriz. Você não pode mesclar as avaliações nas 2 lambdas e tirar a min?
Edc65
@ edc65 Ah, sim, por algum motivo, pensei que aninhar o min não seria mais barato, mas consegui substituir (i+=2)por outro, ++ientão estou economizando 12 bytes no total, obrigado!
194 Neil
5

Pari / GP , 66 bytes

Uma porta da resposta Python de Dennis :

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

Experimente online!


Pari / GP , 72 bytes

Mais longo, mas mais eficiente:

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

Experimente online!

alefalpha
fonte
1
Dennis melhorou seu método e usando que você pode economizar 11 bytes: f(n)=vecmin(concat(n,[f(j)+f(n\j)+f(n%j)|j<-[2..n-1]])).
Jonathan Allan
4

Pari / GP , 213 bytes

Edit: Eu fui severamente espancado .

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

Experimente online!

MD XF
fonte
3

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)

Experimente online!

Jonathan Frech
fonte
@ pizzapants184 A função principal fnão deve ser anônima, pois se chama recursivamente.
Jonathan Frech 28/01
Ah, desculpe, eu não vi isso.
precisa saber é o seguinte
1

Perl 5 , -p 78 bytes

79 bytes in old style counting (+1 for -p)

O fato de o perl precisar usar um extra $para todo o acesso escalar realmente prejudica o comprimento dos campos de golfe que fazem muita aritmética ...

Esse método é mais parecido com os outros já publicados (tente multiplicação e adição para criar um número de destino, pegue o mais barato). No entanto, ele não recua repetidamente para baixo, para que possa ser usado para entradas relativamente grandes.

Ele também não tenta minimizar o custo de construção de um número por adição ou multiparificação, porque o perl 5 não possui built-in mine a classificação numérica é muitooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo ---- Em vez disso, assumo que, se um número é um fator do destino, usarei a multiplicação. Isso é seguro, pois, se, por exemplo, 3é um fator de 12(portanto, soma o custo de ) 3e 12/3mais tarde, ele considerará o 9=12-3que não será um fator; portanto, 9+3com o mesmo custo que 3+9será tentado de qualquer maneira. No entanto, isso pode falhar para os destinos <= 4(apenas para 1e 2). Adicionar $_à lista para minimizar as correções. O que é lamentável, já que eu realmente não preciso disso para os casos base, porque eu já inicializei@; com os valores iniciais adequados, por isso custa 3 bytes.

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

Experimente online!

Ton Hospel
fonte