в универе дали одно задание, после недолгих раздумий пришел к выводу что надо строить дерево с 3 детьми, но определееного вида

Код

____0_____                 /     |    \                1     2     3            /   |  \  ...    ...           1   2   3

главное условие чтобы сумма всех узлов от листа до корня не превышала заданного N
мучаюсь уже не один день , неполучается правильно поставить условия выхода из рекурсии
ПАМАГИТЕ

Chameleon, дерево должно быть сортированным?

структура узла четкая: первый потомок =1, второй =2, третий=3, как на "рисунке"

Кроме этого ограничения есть?

нет, самое главное условие это сумма всех узлов от листа до корня, который =0 непревосходит N

В чём прблема-то? Переходишь на след. узел(кстати что под этим подразумевается), увеличиваешь переменную на единицу и сравниваешь.

Chameleon у каждого узла должно быть строго 3 ветки или просто до 3-х веток?

до 3-х
еслм N=3 то надо получить

Код

0        __  /      |          \      1            2          3     /  \         /    1   2        1    /   1

и еще одно небольшое дополнение не столь важное в в узлах должет быль указатель на предка, а не толко на потомка

Я совсем запутался .

Цитата(Chameleon @ 5.12.2005, 00:36)

главное условие чтобы сумма всех узлов от листа до корня не превышала заданного N

это я понимаю как сумма ВСЕХ улов.

Цитата

если N=3 то надо получить                     0       __  /      |          \     1            2          3     /  \        /   1  2        1   /   1

а это я уже понимаю - количество уровней + 1. А сумма узлов тут - 8.

Что ты понимаешь под N? Сумму узлов или количество уровней?

А почему нельзя хранить в каждом узле "сумму " полученную на всех предыдущих узлах)? тогда выход весьма прост -- если полученная на данном узле сумма большеравна какому то пороговому значению узел не создается)) Затраты тоже 4 байтовое число на узел)(как и указатель на предка)

Цитата

А почему нельзя хранить в каждом узле "сумму " полученную на всех предыдущих узлах

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

Цитата

Что ты понимаешь под N? Сумму узлов или количество уровней?

количество уровней действительно N+1,но сумма пути по узлам от всех ЛИСТЬЕВ до корня=N. если взять любой лист то сумма узлов до корня =N. корень = 0 птому что так путь не увеличивается, увеличивается только кол-во уровней.

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

Тут дерево строить не надо, в памяти надо хранить текущий список, который будет формироваться в процессе перебора. Вот решение

Код

#include <iostream> using namespace std; const int num_steps = 6; // количество ступенек const int step_len = 3; // максимальная длина прыжка int steps_log[num_steps] = {0}; // лог прыжков void jump( int depth, int step ) {     // если допрыгали до конца, распечатать лог     if ( step == 0 ) {         for ( int i = 0; i < num_steps; i++ )             if ( steps_log[i]!=0 ) cout << steps_log[i];         cout << endl;     }          // перебирать возможные прыжки     for ( int i = 1; i <= step_len && step-i >= 0; i++ ) {         steps_log[depth] = i; // записать прыжок в лог         jump( depth + 1, step - i ); // прыгать дальше     }     steps_log[depth] = 0; // убрать из лога }     int main( int argc, char *argv[] ) {     jump( 0, num_steps );     system( "PAUSE" );     return EXIT_SUCCESS; }

спасибо за программу, работает прнкрасно, тока есть какойто баг который я не пойму откуда идет
если длинна лога нечетная то при освобождение памяти терминал ругается

введите длинну лестници: 3
111
12
21
3
колличество всевозможных прыжков по лестнице 4
*** glibc detected *** free(): invalid next size (fast): 0x09bfd008 ***
Aborted

а при четной длинне все нрмально
bash-3.00$ ./s.out
введите длинну лестници: 2
11
2
колличество всевозможных прыжков по лестнице 2

Цитата(Chameleon @ 15.12.2005, 14:09)

спасибо за программу, работает прнкрасно, тока есть какойто баг который я не пойму откуда идет если длинна лога нечетная то при освобождение памяти терминал ругается введите длинну лестници: 3 111 12 21 3 колличество всевозможных прыжков по лестнице 4 *** glibc detected *** free(): invalid next size (fast): 0x09bfd008 *** Aborted

у меня VC2003 такую ошибку не дает ( ), но мне кажется, имеется проблемное место:

Код

void jump( int depth, int step ) {     // если допрыгали до конца, распечатать лог     if ( step == 0 ) {         for ( int i = 0; i < num_steps; i++ )             if ( steps_log[i]!=0 ) cout << steps_log[i];         cout << endl;         // здесь я бы поставил return         return; // см. строчку steps_log[depth] = 0; // убрать из лога     }          // перебирать возможные прыжки     for ( int i = 1; i <= step_len && step-i >= 0; i++ ) {         steps_log[depth] = i; // записать прыжок в лог         jump( depth + 1, step - i ); // прыгать дальше     }     // вот здесь возможна некорректная работа с памятью, если depth равен размерности массива     steps_log[depth] = 0; // убрать из лога }

Цитата(blackofe @ 15.12.2005, 19:08)

но мне кажется, имеется проблемное место:

ага, есть такое дело. +

Добавлено @ 20:35
Chameleon замени функцию jump на ту, что дал blackofe.

ага было такое дело, массив на 1 длянне создал и все нормально стало