Votre tâche consiste à construire un nombre naturel en utilisant le plus petit nombre possible et uniquement les opérateurs +ou -. Par exemple, le nombre sept peut être écrit 1+1+1+1+1+1+1=7, mais il peut également s'écrire 11-1-1-1-1=7. Le premier utilise 7ceux, tandis que le dernier utilise uniquement 6. Votre tâche est de renvoyer le nombre minimum de ceux qui peuvent être utilisés compte tenu de l'entrée d' un certain nombre naturel, n.

Il s'agit du code golf, donc le code valide le plus court en octets l'emporte.

Cas de test

Entrée => Sortie

0 => 2 (since 1-1=0)
7 => 6
121 => 6
72 => 15
1000 => 7
2016 => 21

JavaScript (ES6), 127 126 87 octets

f=(n,z=2,m=n*9+'',r=m.replace(/./g,1))=>n?m.length+(m<'55'?f(n- --r/10,0)-1:f(r-n,0)):z

Input: <input type="number" oninput="result.textContent=f(this.value)"> Result: <span id="result"></span>

Devrait fonctionner à environ 10 ^{14 15} à quel point vous commencez à courir dans les limites entières de JavaScript. Explication:

f=(                             Recursive function
 n,                             Parameter
 z=2,                           Zero workaround
 m=n*9+'',                      Magic
 r=m.replace(/./g,1)            Find repunit not less than than n
)=>n?                           Nothing to do if n is zero
 m.length+                      Assume subtracting from repunit
 (m<'55'?                       Should we subtract from repunit?
  f(n- --r/10,0)                No, so subtract previous repuint
   -1:                          Which is one 1 shorter
  f(r-n,0)):                    Subtract from repunit
 z                              Return special case if n is zero

Cela utilise la n*9magie deux fois; premièrement, cela me donne la longueur de la prochaine répétition, deuxièmement, si les deux premiers chiffres de n*9sont 55ou plus, alors nous devons soustraire nde cette prochaine répétition, sinon nous devons soustraire la répétition précédente (qui est calculée en soustrayant 1 et en divisant par 10). Cela devrait fonctionner jusqu'à 10 ¹⁵ .

Pyth, 19 16 octets

ffqQvs+R1Y^c3"+-

Suite de tests

Algorithme de force brute. Les chaînes nécessaires sont générées en prenant toutes les listes dont les éléments sont ['+', '-', '']de longueur égale au nombre de 1 testés, en ajoutant un 1 à chacun et en concaténant à une seule chaîne. Ces chaînes sont ensuite évaluées et comparées à l'entrée. Cette opération est répétée jusqu'à ce qu'une chaîne réussie soit trouvée.

Certaines chaînes avec un interligne +ou -sont testées, mais ce n'est pas un problème. Ce serait le cas si l'entrée était négative.

Il peut atteindre une longueur de 9 avant de devenir trop lent.

Explication:

ffqQvs+R1Y^c3"+-
ffqQvs+R1Y^c3"+-"T    Implicit variable introduction
                      Q = eval(input())
f                     Starting with T = 1 and counting upwards, repeat until true.
                      The value of T where the result is first true is output.
           c3"+-"     Chop "+-" into thirds, giving ['+', '-', '']
          ^      T    Form every list with those elements of length T.
 f                    Filter over those lists, lambda var Y.
      +R1Y            Append a 1 to each element of the list.
     s                Concatenate.
    v                 Eval.
  qQ                  Compare for equality with the input.
                      The inner filter will let through the successful cases.
                      The outer filter will stop when there is a successful case.

JavaScript (ES6), 92 octets

f=(n,i=3)=>eval([...s=i.toString(3)].map(d=>"-+"[d]||"").join`1`+".0")-n?f(n,i+1):s.length-1

n = <input type="number" oninput="R.textContent=f(this.value)" /><pre id="R"></pre>

Explication

Fonction récursive. Cela génère toutes les permutations possibles de 1s séparées par soit +, -soit rien. Il le fait en incrémentant un nombre en base 3, en le transformant en un tableau de chiffres, en convertissant chaque chiffre 0en -, 1en +et 2en une chaîne vide, puis en les joignant avec 1s. La chaîne résultante est evald comme une instruction JavaScript qui renvoie le résultat de l'équation.

Parce que les opérateurs sont joints avec 1s entre (comme +1+1+1+), il y a length - 1 1s. Le premier opérateur est ignoré (parce que +1= 1, <nothing>1= 1et c'est un nombre donc il n'y aura jamais de début 0pour -) et l'opérateur final est également ignoré (en ajoutant .0à l'équation).

Version à sortie plus élevée, 96 octets

L'autre version ne peut pas renvoyer des sorties supérieures à ~ 10 en raison de la limite de pile d'appels de récursivité. Cette version utilise une boucle for au lieu d'une récursivité, elle peut donc renvoyer des sorties jusqu'à ~ 33. Le temps requis augmente de façon exponentielle, donc je ne recommande pas de le tester.

n=>eval('for(a=3;eval([...s=a.toString(3)].map(d=>"-+"[d]||"").join`1`+".0")-n;)a++;s.length-1')