Помогите разобраться с алгоритмом

[argab]

Друзья, в общем подкинули мне задачку, с которой за один вечер боюсь не уложиться.

Напишите ф-ю, к-рая принимала бы один параметр - натуральное число, на выходе же давала бинарное дерево, значение в корне которого было бы равно передаваемому числу, а структуры задавались бы таким образом, что сумма значений узлов-потомков равнялась значению родительского узла.

9
/ \
4 5
/ \ / \
2 2 2 3
/ \ / \ /\ /\
1 1 1 1 1 1 1 2
/\
1 1
У кого-нибудь есть соображения на этот счет?

[рони]

argab,
рекурсия деления числа на 2 пока больше 1

[рони]

argab,
примерно так

<script>
   function fn(num)
   {  var obj = {};
      var a = num/2|0, b = num - a;
      obj[a] = a > 1 ? fn(a) : a;
      obj[b+' '] = b > 1 ? fn(b) : b;
      return obj
   }
   console.log(fn(9))
   document.write(JSON.stringify(fn(9),null,1))
</script>

[argab]

Ого! Не ожидал такого быстрого ответа, Спасибо! Скажите, есть ли где-нибудь подробное описание подобного алгоритма. Я с алгоритмами никогда не работал. В интернете искал, но там все про дельфи и паскаль.

[argab]

"рекурсия деления числа на 2 пока больше 1" - как ни странно, эта мысль у меня тоже сразу возникла, но с реализацией у меня проблемы были. Спасибо, что помогли.

А что означает сея конструкция: num/2|0.

[рони]

есть ли где-нибудь подробное описание

может где-то и есть, искать надо и вывод результата в предложенном варианте не самый лучший, а именно obj[b+' '], но другого на скорую руку не нашёл для случая когда a и b одинаковые

[рони]

А что означает сея конструкция

а вы поэкспериментируйте какой она результат выдаёт
замена Math.floor(num/2) -- наименьшее целое после деления на 2

[argab]

И вот этот момент не понятен: obj[b+' ']. Зачем нужен пробел?

[рони]

argab,
округление

[argab]

Вы наверно будете смеяться, но вот что я состряпал когда пытался:

var values = [],
i = 0;

function binaryTree(num)
{
sum = Math.floor(num/2);
ssum = ((sum*2)!=num) ? num - sum : sum;
if(num==1) return;

values[i] = [];
values[i].push(sum);
values[i].push(ssum);
++i;
binaryTree(sum);
}
binaryTree(9);
console.log(JSON.stringify(values,null,1));

Потом поздно было, решил башку не ломать, и написал сюда))