Buggy Binärbaum

Question

Ich versuche codeforces 737A mit Hilfe von Javascript zu lösen, die ab an einem anderen Eingang aus gegebener Eingabe von recrusing den Baum der und 10*x+1, eine binäre Suche tut, aber es scheint, dass mein Programm nur durch denjenigen suchen Knoten bei , und diese 10*x+1 scheint ignoriert. Interessant und WARUM? Vielen Dank.

var tt = readline().split(' '); 
var a = parseInt(tt[0]); 
var b = parseInt(tt[1]); 

print(f([],a,b)); 
function f(arr,x,b){ 
    if (x>b){ 
     return []; 
    }else if (x==b){ 
     return _add(arr,x); 
    }else{ 
     return (f(_add(arr,x),(2*x),b) || f(_add(arr,x),(10*x+1),b)); 
    } 
} 

function _add(array,x){ 
    var _arr = array.slice(); 
    _arr.push(x); 
    return _arr; 
} 

Answer 1

Sie müssen false anstelle eines leeren Arrays zurückgeben. Das leere Array wird in true aufgelöst, was bedeutet, dass Sie nur den linken Zweig iterieren.

(BTW, keine Notwendigkeit für andere Teile, wenn dann Teile zurück.)

function go(a, b) { 
 
    //var tt = readline().split(' '); 
 
    //var a = parseInt(tt[0]); 
 
    //var b = parseInt(tt[1]); 
 

 
    function f(arr, x, b) { 
 
     if (x > b) { 
 
      return false; // no []!!! 
 
     } 
 
     if (x == b) { 
 
      return _add(arr, x); 
 
     } 
 
     return (f(_add(arr, x), (2 * x), b) || f(_add(arr, x), (10 * x + 1), b)); 
 
    } 
 

 
    function _add(array, x) { 
 
     var _arr = array.slice(); 
 
     _arr.push(x); 
 
     return _arr; 
 
    } 
 

 
    return f([], a, b); 
 
} 
 
console.log(go(2, 162)); 
 
console.log(go(4, 42)); 
 
console.log(go(100, 40021));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

Zwei Fragen:

1. Iness. In javascript sind die Falsy-Werte false, null, undefined, 0, NaN und leere Strings (""). Alle anderen Werte sind wahr.

   Sie sind ein Array für den Basisfall Rückkehr:

   return []; 
   

   dies immer der Fall sein, so wird.

2. Wie der || Operator funktioniert. Der Operator || schließt kurz. Wenn der linke Wert truthig ist, wird er daher zurückgegeben und nicht der rechte Code ausgewertet.

   Sie schrieb:

   f(_add(arr,x),(2*x),b) || f(_add(arr,x),(10*x+1),b) 
   

   Da in allen Fällen f() nie etwas zurückgeben falsy, dass die Expression im Grunde ist:

   true || f(_add(arr,x),(10*x+1),b) 
   

   Da die solche || Operator nie den Fall 10*x+1 auswertet.

Um den Code zu arbeiten Sie eine Funktion benötigen zu machen entweder schreiben einen nicht leeren Array zu wählen, anstatt den || Betreiber der Verwendung oder f() return false oder 0 für den Basisfall anstelle eines leeren Array machen (die kann oder nicht brechen den Algorithmus, ich weiß nicht, da ich den Algorithmus nicht kenne).