Count minimale Operationen erforderlich, um die Zielnummer zu erreichen

Question

Ich arbeite derzeit an einer Funktion in JavaScript, die ein Array von Zahlen nimmt, zum Beispiel: [5, 10, 18, 25, 30] und gibt dann ein Array zurück, das die Anzahl der erforderlichen minimalen Operationen enthält von 0 zu der Zielnummer, indem nur 1 hinzugefügt oder mit 2 multipliziert wird.

Zum Beispiel würde die Nummer 5 aus dem Array 4 zurückgeben, weil Sie 0 + 1 = 1 x 2 = 2 x 2 = 4 + 1 = 5 tun würden.

Wenn das übergebene Array [5,5,5] war, wäre das Ausgabe-Array [4,4,4].

Ich habe nach möglichen Lösungen für dieses Problem gesucht, von denen einige Iteration und andere Rekursion verwendet. Ich habe hier eine Antwort auf eine ähnliche Frage gefunden Code Review - Find sequence by adding 5 or multiplying by 3.

Der einzige Unterschied ist das Hinzufügen von 5 oder Multiplikation mit 2, und es beginnt von 1 im Gegensatz zu 0. Ich habe versucht, diese Lösung an meine Bedürfnisse anzupassen, aber aus irgendeinem Grund wird der Code nur immer add 1 und niemals times 2. Also, für den Eingang 5 bin ich mit 0 + 1 = 1 + 1 = 2 + 1 = 3 + 1 = 4 + 1 = 5 zurückgegeben, die offensichtlich nicht die kürzeste Lösung ist.

Schließlich brauche ich dies, um ein Array zurückzugeben, da die Eingabe auch ein Array sein wird, aber ich habe Mühe, sogar diese Anpassung der obigen Antwort zu arbeiten, nur mit einer einzigen ganzen Zahl als Parameter.

Wenn ich pass 5 in dieser Funktion, die ich mit 5 anstelle der kürzesten Lösung zurück bin die 4 ist, weil es immer nur adds 1.

Der Code, den ich im Moment haben, ist:

function findSequence(goal) { 
    function find(start, history) { 
    if (start == goal) { 
     return history; 
    } 
    if (start > goal) { 
     return null; 
    } 
    return find(start + 1, "(" + history + " + 1)") || 
      find(start * 2, "(" + history + " * 2)"); 
    } 
    return find(0, "0"); 
} 

Wie kann ich diese Arbeit machen? Ich brauche die kürzesten Folgezählung von 0 auf die Zielnummer erhalten zurückzukehren, indem nur Zugabe von 1 oder Multiplikation 2

Answer 1

Wie wäre es etwa so:

function findMoves(target) 
{ 
    arr = []; 
    while (target != 1) 
    { 
     if (target %2 == 0) 
     { 
      target /= 2; 
      arr.unshift(target + " x " + 2); 
      continue; 
     } 
     target -= 1; 
     arr.unshift(target + " + " + 1); 
    } 
    arr.unshift("0 + 1"); 
    return arr; 
} 

res = findMoves(9); 

console.log(
    "TotalMoves: " + res.length + "\n" + 
    "What moves: " + res.join(', ')); 

Drucke:

TotalMoves: 5 
What moves: 0 + 1, 1 x 2, 2 x 2, 4 x 2, 8 + 1 

Answer 2

Dies ist wahrscheinlich einfacher, in umgekehrter Richtung zu tun. Beginnen Sie mit Ihrem Ziel und wenden Sie entweder minus 1 oder dividieren durch 2 an, bis Sie auf Null drücken. Sobald Sie diese Sequenz gefunden haben, kehren Sie sie um und verwenden Sie inverse Ops (plus 1, mal 2), um zu Ihrem Ziel zurückzukehren.

function getNext(num) { 
 
    if (num === 0) return "end" 
 
    if (num % 2 === 1) return "minus" 
 
    return "div" 
 
} 
 

 
function makeSequence(num, ls) { 
 
    const next = getNext(num); 
 
    if (next === "end") return ls; 
 
    ls.push(next) 
 
    
 
    if (next === "div") return makeSequence(num/2, ls); 
 
    if (next === "minus") return makeSequence(num-1, ls); 
 
} 
 

 
function reverseSequence(sqn) { 
 
    return sqn.reverse().map(x => x === "minus" ? "plus" : "times"); 
 
} 
 

 
var sqn = makeSequence(5, []); 
 
var reversedSqn = reverseSequence(sqn) 
 

 
console.log("Takes", reversedSqn.length, "steps with target of 5"); 
 
console.log("Steps are:", reversedSqn);  
 

 
var bigSqn = makeSequence(200, []); 
 
var bigReversedSqn = reverseSequence(bigSqn); 
 

 
console.log("Takes", bigReversedSqn.length, "steps with target of 200"); 
 
console.log("Steps are:", bigReversedSqn);