pengantar

Tujuan Anda adalah untuk menemukan jumlah paling sedikit yang Anda perlu tambahkan atau gandakan bersama untuk mendapatkan nilai input, ini adalah A005245 .

Memasukkan

Salah satu bilangan bulat positif N .

Keluaran

Jumlah terkecil yang yang harus ditambahkan / dikalikan untuk mendapatkan N .

Input Sampel

7

Output Sampel

6

Penjelasan

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

Karena ini memerlukan 6yang, outputnya6

Uji kasus

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

Karena ini adalah tantangan kode-golf , jumlah byte terendah menang.

Python 2 , 74 70 byte

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

Cobalah online!

Versi alternatif, 59 byte (tidak diverifikasi)

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

Ini bekerja setidaknya hingga n = 1.000.000 , tetapi saya belum membuktikan bahwa itu bekerja untuk semua n positif .

Cobalah online!

Jelly , 16 14 byte

Terima kasih Dennis untuk menghemat 2 byte!

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

Cobalah online!

Penjelasan logis

Diberi nomor n :

• Jika ya 1, jawabannya adalah 1. Jika tidak:

Representasi adalah salah satu a + batau a × b, di mana adan bmerupakan ekspresi.

Pertimbangkan semua nilai yang mungkin adan b:

• Jika representasi a + b, maka adan bdalam jangkauan [1 .. n-1].
• Jika representasi adalah a × b, adan bpembagi yang tepat nlebih besar dari 1.

Dalam kedua kasus, daftar [[<proper divisors of n larger than 1>], [1, 2, ..., n-1]]dihitung ( ÆḌḊ,Ṗ), petakan tautan saat ini di atas setiap angka ߀€, tambahkan pasangan yang benar bersama-sama ( +U$) dan dapatkan nilai minimum ( FṂo).

Penjelasan kode

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

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

Sangat tidak efisien; Array(n>>1)mempercepatnya sedikit dengan biaya satu byte. Penjelasan: n%++ibukan nol jika ibukan merupakan faktor, begitu n%++i/0juga Infinity(dan karena itu benar, dan juga pasti tidak minimal) jika ibukan merupakan faktor, tetapi NaN(dan karena itu palsu) jika imerupakan faktor. Sunting: Disimpan 12 byte dengan inspirasi dari @ edc65.

Pari / GP , 66 byte

Port jawaban Dennis Python :

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

Cobalah online!

Pari / GP , 72 byte

Lebih lama, tetapi lebih efisien:

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

Cobalah online!

Pari / GP , 213 byte

Sunting: Saya sudah dipukuli habis-habisan .

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

Cobalah online!

Python 2 , 181 byte

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)

Cobalah online!

Bahasa Wolfram (Mathematica) , 59 byte

Disimpan 3 byte berkat Martin Ender. Menggunakan pengkodean CP-1252, di mana ±satu byte.

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

Cobalah online!

Perl 5 , -p 78 byte

79 byte dalam penghitungan gaya lama ( +1untuk -p)

Fakta bahwa perl harus menggunakan ekstra $untuk semua akses skalar benar-benar menyakiti panjang golf yang melakukan banyak aritmatika ...

Metode ini sebagian besar seperti yang lain yang sudah diposting (coba multiplikasi dan penambahan untuk membangun nomor target, ambil yang termurah). Namun tidak berulang berulang sehingga dapat digunakan untuk input yang relatif besar.

Itu juga tidak mencoba untuk meminimalkan biaya membangun nomor dengan penambahan atau multiplikasi karena perl 5 tidak memiliki builtin mindan numeric sort adalah looooooong (seperti yang terlihat dari sortir yang masih dalam kode). Sebaliknya saya hanya berasumsi jika angka merupakan faktor target yang akan saya gunakan multiplikasi. Itu aman karena jika mis 3adalah faktor 12(sehingga menjumlahkan biaya 3dan 12/3) kemudian dalam loop itu akan mempertimbangkan 9=12-3yang tidak akan menjadi faktor, sehingga 9+3dengan biaya yang sama seperti 3+9akan dicoba. Namun itu mungkin gagal untuk target <= 4(hanya untuk 1dan 2). Menambahkan $_ke daftar untuk meminimalkan perbaikan itu. Yang disayangkan karena saya tidak benar-benar membutuhkannya untuk kasus dasar karena saya sudah menginisialisasi@; dengan nilai awal yang tepat sehingga harganya 3 byte.

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

Cobalah online!