越野车二叉树

Question

我正在尝试使用 javascript 求解 codeforces 737A，它正在从给定的输入 [=] 中对 2*x 和 10*x+1 的树进行二分搜索13=] 到另一个输入 b，但似乎我的程序只能搜索 2*x 处的那些节点，而那些 10*x+1 似乎被忽略了。有趣，为什么？谢谢。

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

您需要 return false 而不是空数组。空数组解析为 true，这意味着您只迭代左分支。

（顺便说一句，不需要 else 部分 if then 部分 return。）

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

两个问题：

真实。在 javascript 中，虚假值是 false、null、undefined、0、NaN 和空字符串 ("")。所有其他值都为真。

您正在 return 为基本情况创建一个数组：
```
return [];
```
所以这永远是真的。
|| 运算符的工作原理。 || 运算符短路。因此，如果左边的值是真值，它将 return 它而不计算右边的代码。

您写道：
```
f(_add(arr,x),(2*x),b) || f(_add(arr,x),(10*x+1),b)
```
因为在所有情况下 f() 从不 return 任何虚假的表达基本上是：
```
true || f(_add(arr,x),(10*x+1),b)
```
因此 || 运算符从不计算 10*x+1 案例。

要使代码正常工作，您需要编写一个函数来选择非空数组而不是使用 || 运算符，或者使 f() return false or 0 for基本情况而不是空数组（这可能会或可能不会破坏算法，我不知道，因为我不知道算法）。

越野车二叉树

Buggy binary tree

javascript

arrays

binary-tree