Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.85/13: Рейтинг темы: голосов - 13, средняя оценка - 4.85
0 / 0 / 1
Регистрация: 07.07.2013
Сообщений: 15

Дерево турнира

12.12.2017, 14:29. Показов 2741. Ответов 3
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Доброго времени суток! Есть проблема с одним заданием:

Теннисный турнир проходит по олимпийской системе с выбыванием. Известен рейтинг каждого игрока. Результаты турнира записаны с помощью дерева. Участникам соответствуют листья дерева. Выдать список сенсаций турнира, когда побеждал игрок с низшим рейтингом. Определить самый сенсационный результат по максимальной разнице рейтингов.

Реализовал обычное бинарное дерево, у которого в звене есть два информационных поля: name и x(рейтинг игрока),а как правильно заполнить его - ума не приложу, ведь по сути мне надо его как-то снизу начинать заполнять, но с бинарными деревьями, на сколько я знаю, так делать нельзя, да и извращение это какое-то.

1
/ \
1 3
/ \ / \
1 2 3 4

Это то,как я вижу это это дерево, которое должно получится. Т.е. Изначально есть 4 игрока, 1 играет со 2, 3 с 4. В первой паре победитель - игрок 1, во второй - игрок 3, они поднимаются вверх по таблице, как бы проходят в следующий тур, потом играют между собой и соответственно победитель снова поднимается вверх, ну и является чемпионом.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <iostream>
#include <conio.h>
using namespace std;
 
struct Node
{
    int x;
    char* name;
    Node *l, *r;
};
Int n=0;
void show(Node *&Tree) 
{
    if (Tree != NULL)
    {
        show(Tree->l);
        cout << Tree->name << " " << Tree->x << endl;
        show(Tree->r);
    }
}
 
void del(Node *&Tree) {
    if (Tree != NULL)
    {
        del(Tree->l);
        del(Tree->r);
        n--;
        delete Tree;
    }
 
}
 
void add_node(int x, char* name, Node *&tree)
{
    if (tree == NULL)
    {
        tree = new Node;
        tree->x = x;
        tree->name = name;
        n++;
        tree->l = tree->r = NULL;
    }
    else
    {
        if (x < tree->x)
        {
            if (tree->l != NULL) {
                add_node(x, name, tree->l);
                tree->n++;
 
            }
            else
            {
                tree->l = new Node;
                tree->l->l = tree->l->r = NULL;
                tree->l->x = x;
                tree->l->name = name;
                n++;
            }
        }
 
        if (x > tree->x)
        {
            if (tree->r != NULL) {
                add_node(x, name, tree->r);
                n++;
 
            }
            else
            {
                tree->r = new Node;
                tree->r->l = tree->r->r = NULL;
                tree->r->x = x;
                tree->r->name = name;
                n++;
 
            }
        }
    }
}
 
int MinEl(Node*& tree) {
    if (tree != NULL)
    {
        MinEl(tree->l);
        if (min > tree->x)
            min = tree->x;
        MinEl(tree->r);
    }
    return min;
}
 
bool isPowerOfTwo(int v) {
    if (v && !(v & (v - 1))) {
        return true;
    }
    else {
        return false;
    }
}
 
void task(Node*& tree) {
    // количество игроков должно быть = степени двойки (2,4,8,16..)
 
    if (isPowerOfTwo(n)) {
 
//?
 
 
    }
    else {
        cout << "Nel'zya ispol'zovat' dannyu sistemy :(";
    }
}
 
int main()
{
    Node *Tree = NULL;
 
    add_node(4, "Logan", Tree);
    add_node(1, "Mark", Tree);
    add_node(2, "George", Tree);
    add_node(3, "Kelly", Tree);
 
 
    
    show(Tree);
 
    del(Tree);
    _getch();
}
Прошу помощи. Хотя бы растолковать что мне с этим деревом делать..
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
12.12.2017, 14:29
Ответы с готовыми решениями:

Дерево турнира с выбыванием
Не совсем понимаю, как осуществить процедуру заполнения дерева. Точнее, не понимаю, как поместить в корень максимальный элемент. Имеется...

Таблица хоккейного турнира
Есть задача. В турнире по хоккею участвовало K команд, каждая сыграла с каждой по одному матчу. За победу команда получала 2...

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

3
6 / 6 / 4
Регистрация: 11.12.2017
Сообщений: 29
12.12.2017, 18:59
Если рассматривать дерево по уровням, то на каждом уровне все игроки уникальны. Победитель это уровень 0, финал 1, полуфинал 2. Нужно написать такую функцию добавления:

add_node(int x, char* name, Node *&tree, char* name2, int level);

level - на каком уровне искать игрока с именем name2. Потом проверять левый и правый лист на содержимое.
1
0 / 0 / 1
Регистрация: 07.07.2013
Сообщений: 15
13.12.2017, 08:37  [ТС]
dotmode, а как мне тогда с таким добавлением присвоить рейтинг этим игрокам?
Добавить ещё одну переменную и так же как и "Х", передавать её и это будет рейтинг второго игрока?
Т.е. По сути это добавление сразу пары игроков? Я присааиваю им level, например 2, потом тот кто выиграл переходит на level 1, но как тогда с ними работать дальше? Проходить по обеим веткам и искать там игроков с одинаковым level?
0
6 / 6 / 4
Регистрация: 11.12.2017
Сообщений: 29
13.12.2017, 22:14
1). Добавляем от корня, т. е. сначала победитель потом финалисты ...
2). Добавление можно разбить на две под задачи поиск нужного узла и добавление (по 2, кроме корня)
Node * find_node(Node *&tree, char* name, int levelToFind, int curLevel =0).
1. Начинаем с корня, если levelToFind != curLevel идем глубже find_node(tree, name, levelToFind, curLevel++)
2. Если равны тогда проверяем name, если равны возвращаем результат.
3. Если не нашли возвращаем NULL

Конечно, это возможно не самый лучший вариант, и не единственный.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
13.12.2017, 22:14
Помогаю со студенческими работами здесь

Обработка итоговой таблицы шахматного турнира
Составить программу обработки итоговой таблицы шахматного турнира. В программе предусмотреть ввод исходных данных турнира (фамилии...

По итогам MCA турнира составить итоговую таблицу
Согласно регламенту каждая задача оценивается определённым количеством баллов. Правильно решённая задача даёт команде именно столько...

Сортировка числовых массивов методом турнира с выбыванием
Помогите пожалуйста, очень срочно!!! Нужно написать программу на С++ Сортировка числовых массивов методом турнира с выбыванием. Все...

Матрицы: распределить участников турнира по убыванию набранных очков
при записи данных о соревнованиях по шахматам формируется матрица турнирного особого вида. результат матча может быть 1 (выигранная...

Бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой
Дано бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой.


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Новые блоги и статьи
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image
8Observer8 10.02.2026
Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .
Установка Qt-версии Lazarus IDE в Debian Trixie Xfce
volvo 10.02.2026
В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer
8Observer8 08.02.2026
Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru