Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > дерево с тремя детьми

Автор: Chameleon 5.12.2005, 00:36

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

что надо строить дерево с 3 детьми, но определееного вида

Код


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

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

, неполучается правильно поставить условия выхода из рекурсии smile

ПАМАГИТЕ

Автор: DeadSoul 5.12.2005, 00:47

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

Автор: Chameleon 5.12.2005, 00:52

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

Автор: DeadSoul 5.12.2005, 00:54

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

Автор: Chameleon 5.12.2005, 00:57

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

Автор: Mephistopheles 5.12.2005, 11:20

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

Автор: S.A.P. 5.12.2005, 11:53

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

Автор: Chameleon 5.12.2005, 12:04

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

Код


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

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

Автор: S.A.P. 5.12.2005, 13:03

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

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

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

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

Цитата

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

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

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

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

Автор: SDenis 5.12.2005, 14:50

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

)? тогда выход весьма прост -- если полученная на данном узле сумма большеравна какому то пороговому значению узел не создается smile

)) Затраты тоже 4 байтовое число на узел smile

)(как и указатель на предка)

Автор: Chameleon 5.12.2005, 21:18

Цитата

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

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

Цитата

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

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

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

Автор: S.A.P. 6.12.2005, 10:29

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

Код


#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;
}

Автор: Chameleon 15.12.2005, 14:09

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

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

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

Автор: blackofe 15.12.2005, 19:08

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

у меня VC2003 такую ошибку не дает ( smile

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

Код


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; // убрать из лога
}

Автор: S.A.P. 15.12.2005, 20:33

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

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

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

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

Автор: Chameleon 16.12.2005, 12:05

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