Last active
January 3, 2024 19:48
-
-
Save shmalex/028bc37e722852f61e9a763a5f982dac to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Даны три целые числа 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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment