tree_sum_test.js

// Даны три целые числа a, b, c  больше 0. 
// Есть два варианта либо добавлять b к a (a+=b), либо добавлять a к b (b+=a).  
// В результате  получаются новые значение а  и b. 
// Напишите программу, которая выведет YES или NO в зависимости от того можете ли получить  значение c,  добавляя  a к b  или b к a друг к другу.

var a = 5;
var b = 7;
var c = 123;

/*
    VALIDATION CODE BEGIN
*/
var validation_msg = { true: 'Valid', false: 'Invalid' }
function print_check(a, b, c, e) {
    let res = check(a, b, c)
    console.log(a, b, c, res, validation_msg[res == e]);
}
/*
    VALIDATION CODE END
*/


// version 1
function print(msg) {
    console.log(msg)
}
function tree_traverse(a, b, c) {
    let sum = a + b;
    if (sum == c) {
        return true;
    }
    if ((sum) > c) {
        return false;
    }
    // left
    var res = tree_traverse(sum, b, c);
    if (res) return true;
    // right
    res = tree_traverse(a, sum, c);
    if (res) return true;
    return false;
}
//
function check(a, b, c) {
    // проверка на адекватность.
    if ((c < (a + b)) |
        (c < 0 & (a + b) > 0)
    ) {
        print('NO')
        return false;
    }
    var res = tree_traverse(a, b, c)
    if (res) {
        print('YES')
        return res
    }
    print('NO')
    return res
}

function roughSizeOfObject(object) {
    const objectList = [];
    const stack = [object];
    let bytes = 0;
  
    while (stack.length) {
      const value = stack.pop();
  
      switch (typeof value) {
        case 'boolean':
          bytes += 4;
          break;
        case 'string':
          bytes += value.length * 2;
          break;
        case 'number':
          bytes += 8;
          break;
        case 'object':
          if (!objectList.includes(value)) {
            objectList.push(value);
            for (const prop in value) {
              if (value.hasOwnProperty(prop)) {
                stack.push(value[prop]);
              }
            }
          }
          break;
      }
    }
  
    return bytes;
  }

// version 2

var root = {}

var a = 5;
var b = 7;
var c = 22;
function tree_traverse_obj(a, b, c) {

    root = {
            'a': a, 'b': b, 'c': c, 
            'l': void (0), // left
            'r': void (0), // right
            'p': void (0)  // parent
        }
    // cur = это типа курсора, на который мы сейчас указываем. В начале мы указываем на корень дерева.
    var cur = root;
    var i = 1; // число созданных веток, просто, для интересу
    while (true) {

        // если текущий курсор пустой - значит мы ссылаемся на parent нашего root объекта.
        // а значит - мы вернулись в самое начало из всех наших веток - получается мы не нашли решение
        if (typeof (cur) == "undefined") {
            console.log(a, b, c, 'NO', i)//, roughSizeOfObject(root))
            break;
        }

        cur['i'] = i;
        // console.log(cur);

        // если а+б больше ц - тогда мы возвращаемся к родителю
        if (cur['a'] + cur['b'] > cur['c']) {
            cur = cur['p']; // back to parrent
            continue
        }

        // если а+б == ц - тогда мы нашли одно из возможных решений, значит - закончили наконец.
        if (cur['a'] + cur['b'] == cur['c']) {
            console.log(a, b, c, 'YES', i)//, roughSizeOfObject(root));
            break;
        }

        // если дошли до сюда - значит уже пора углубляться в правую и/или левую ветки
        // сначало - левая

        if (typeof (cur['l']) == "undefined") {

            cur['l'] = { 'a': cur['a'] + cur['b'], 'b': cur['b'], 'c': cur['c'], 'l': void (0), 'r': void (0), 
                        p: cur // сохраняем ссылку на родителя
                        };
            i++;
            
            // курсор показывает на левую ветку
            cur = cur['l']
            continue
        }

        if (typeof (cur['r']) == "undefined") {
            cur['r'] = { 'a': cur['a'], 'b': cur['b'] + cur['a'], 'c': cur['c'], 'l': void (0), 'r': void (0),
                        p: cur // сохраняем ссылку на родителя
                        };
            i++;
            // меняем курсор на левую правую ветку
            cur = cur['r']
            continue
        }

        // если мы дошли до сюда, значит - правая и левая ветки уже были просмотренны, и там ответа не нашлось.
        // к примеру на данном уровне текущий курсор - a = 100 b = 120 c=319 тогда 
        //      левая ветка a=220, b=120, c=319: 340>219 - поднялась к родителю (тоесть к текущему курсору) (стр. 126)
        //      правая ветка a=100, b=220, c=319: 320>319 - тоже поднялась к родителю (тоесть к текущему курсору) (стр. 126)
        //      тогда мы дошли до этой строки, и нужно подниматься к родителю (родителю текущего курсора)
        // нужно подниматься к родителю.
        cur = cur['p']; // back to parrent
    }

    return root;
}

// ебать большое число
let r = tree_traverse_obj(5, 7, 5*100000+7*100000, true)
r = tree_traverse_obj(5, 7, 123, true)
r = tree_traverse_obj(1, 1, 2, true)
r = tree_traverse_obj(2, 2, 5, false)
r = tree_traverse_obj(2, 2, -5, false)
r = tree_traverse_obj(2, 2, 9, false)
r = tree_traverse_obj(2, 2, 99, false)
r = tree_traverse_obj(2, 2, 999, false)
r = tree_traverse_obj(2, 2, 9999, false)
r = tree_traverse_obj(0, 0, -5, false)

// ебать большое число не работает на рекурсии
print_check(5, 7, 5*100000+7*100000, true)

// print_check(1, 1, 2, true)
// print_check(2, 2, 5, false)
// print_check(2, 2, -5, false)
// print_check(0, 0, -5, false)