Угадай, где выход! (Поиск листа бинарного дерева, содержащего выход из лабиринта)

@Dennis Ritchie · Регистрация: 27.07.2014

Студворк — интернет-сервис помощи студентам

Угадай, где выход!

Amr купил новую компьютерную игру "Угадай, где выход!". Цель игры— найти выход из лабиринта, похожего на полное двоичное дерево высоты h. Изначально игрок стоит в корне дерева, выход из дерева расположен в некотором листе дерева.

Пронумеруем все листы слева направо числами от 1 до 2^h. Выход расположен в некоторой вершине n, где 1 ≤ n ≤ 2^h.

Amr пользуется следующим простым алгоритмом выбора пути. Рассмотрим бесконечную строку "LRLRLRLRL..." (состоящую из чередующихся символов 'L' и 'R'). Amr последовательно выполняет символы строки по следующим правилам:

Символ 'L' означает "перейти к левому сыну текущей вершины";
Символ 'R' означает "перейти к правому сыну текущей вершины";
Если вершину, в которую ведёт текущая команда, Amr уже до этого посещал, то он пропускает текущую команду, в противном случае он переходит в эту вершину;
Если Amr пропустил две последовательные команды, то он возвращается к предку текущей вершины перед тем, как выполнять следующую команду;
Если он оказался в листе, который не является выходом, он сразу возвращается к предку текущей вершины;
Если он достиг выхода, игра заканчивается.

Теперь Amr интересно: если он будет следовать этому алгоритму, сколько вершин он посетит до того, как достичь выхода?

Входные данные
Ввод состоит из двух целых чисел, h, n (1 ≤ h ≤ 50, 1 ≤ n ≤ 2^h).

Выходные данные
Выведите единственное целое число, обозначающее количество вершин (не включая лист, в котором расположен выход), которые Amr посетит перед тем, как добраться до выхода, следуя этому алгоритму.

Примеры тестов

Входные данные	Выходные данные
1 2	2
2 3	5
3 6	10
10 1024	2046

Примечание
Полное двоичное дерево высоты h— это двоичное дерево, состоящее из h + 1 уровня. Уровень 0 состоит из единственной вершины, которая называется корень, уровень h состоит из 2h вершин, которые называются листьями. Каждая вершина, не являющаяся листом, имеет ровно двух потомков, левого и правого.

Следующая картина иллюстрирует третий тест из условия. Вершины помечены в порядке их посещения.

Угадай, где выход! (Поиск листа бинарного дерева, содержащего выход из лабиринта)

Никогда раньше не решал задачи на деревья, но вот решил начать. Самая большая проблема в том, что я никак не могу понять примеры тестов

. А всё потому, что я, наверное, неправильно строю деревья.
Я прочитал эту строчку:

Пронумеруем все листы слева направо числами от 1 до 2^h.

И вот, что я нарисовал, следую этому предложению, для трёх тестовых примеров:

Я так понимаю, что это неправильно. Объясните, пожалуйста, как правильно нужно нумеровать дерево и в какой последовательности обходить это дерево для трёх тестовых примеров. Если несложно, то нарисуйте хотя бы в Paint'e рисунок со стрелочками или попробуйте описать комментариями.

@wingblack · 26.01.2015, 11:25

Сообщение от Dennis Ritchie

Я так понимаю, что это неправильно. Объясните, пожалуйста, как правильно нужно нумеровать дерево и в какой последовательности обходить это дерево для трёх тестовых примеров.

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

Вот две картинки, в одной заполнение дерева числами при h=5, во второй стрелками показано в какую ветку пойдет игрок при первом посещении узла, цифры - порядок первичного посещения узлов. (К слову, все узлы, кроме листьев, посещаются 3 раза - первый проход, возврат для захода в соседнюю ветку, и возврат "вверх")

@wingblack · 26.01.2015, 11:40

У тебя описан алгоритм вполне подробно, просто следуй ему при обходе и все.
- поочередно идем налево и направо
- если уже посещали вершину куда хотим идти - пропустить ход
- если попустили два раза - идем наверх
- если попали в лист (а это "край" дерева) и лист не выход - идем наверх
- если нашли выход - конец игре.

Поправка на рисунках, не h=5, а h=4

@Dennis Ritchie · 26.01.2015, 11:47 **[ТС]**

Сообщение от wingblack

Главное понять что рисунок примера показывает последовательность посещения вершин, а твой - содержимое дерева.

Это я и так понимаю.

Сообщение от wingblack

Оба рисунка правильные.

Просто я думал, что неправильно заполняю дерево на своём рисунке.

Сообщение от wingblack

в одной заполнение дерева числами при h=5

По-моему, h = 4. Первый корневой уровень считается нулевым.

Сообщение от wingblack

У тебя описан алгоритм вполне подробно, просто следуй ему при обходе и все.

Большое спасибо. Буду разбираться и придумываться собственное решение.

Вот крутое чужое решение

:

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
#include <iostream>
 
using namespace std;
 
int main()
{
    long long h, n;
    cin >> h >> n;
    n--;
    
    int mv = 0;
    long long ans = 0;
 
    for (int i = h - 1; i >= 0; i--) {
        int real = !!(n & (1LL << i));
        if (mv != real) {
            ans += ((1LL << (i + 1)) - 1);
            mv ^= 1;
        }
        mv ^= 1;
        ans++;
    }
    
    cout << ans << endl;
    return 0;
}

Конечно, как работает это решение я не знаю, но хочу узнать, что означает 1LL в C++. Первый раз такое увидел.

Байт · 26.01.2015, 14:24

Сообщение от Dennis Ritchie

что означает 1LL в C++

Может быть long long? А вот что такое !! ?

Добавлено через 2 минуты

Сообщение от Байт

А вот что такое !! ?

Кажется, догадался. Двойное отрицание. Приведение к 1. Эквивалент

C
1
int real = (n & (1LL << i)) ? 1 : 0;

@Dennis Ritchie · 26.01.2015, 14:29 **[ТС]**

Сообщение от Байт

Может быть long long?

Я нашёл. 1LL - это цифра "1" размера long long.

Сообщение от Байт

А вот что такое !! ?

Я тоже ломал голову, но так и не понял. Сомневаюсь, что чемпион мира по программированию мог опечататься.

Добавлено через 2 минуты

Сообщение от Байт

Кажется, догадался. Двойное отрицание. Приведение к 1.

Логично.

@wingblack · 27.01.2015, 14:11

Сообщение от Dennis Ritchie

Вот крутое чужое решение :

Красиво, но нужно долго курить чтобы понять. Я только понял что подтвердились мои догадки что тут не следует тупо дерево строить и бегать по нему. А также что спускаясь по дереву мы либо умножаем на 2 либо умножаем на 2 и прибавляем 1.

@Dennis Ritchie · 27.01.2015, 18:02 **[ТС]**

Сообщение от wingblack

А также что спускаясь по дереву мы либо умножаем на 2 либо умножаем на 2 и прибавляем 1.

Я сейчас пытаюсь вкурить более простое решение, которое основано на умножении на 2. Сам я вряд ли смог бы написать такую программу без хорошего знания алгоритмов, поэтому постараюсь хотя более простое решение разобрать:

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
#include <iostream>
 
using namespace std;
 
const int len = 51;
 
long long tree[len], ans, h, n;
 
void dfs(int dep, long long l, bool left)
{
    ++ans;
    if (dep == h)
        return;
    if (n < l + tree[h - dep - 1]) {
        if (left == true)
            ans += tree[h - dep] - 1;
        dfs(dep + 1, l, true);
    }
    else {
        if (left == false)
            ans += tree[h - dep] - 1;
        dfs(dep + 1, l + tree[h - dep - 1], false);
    }
}
 
int main()
{
    cin >> h >> n;
 
    tree[0] = 1;
    for (int i = 1; i < len; ++i)
        tree[i] = tree[i - 1] * 2;
 
    ans = 0;
 
    dfs(0, 1, false);
 
    cout << ans - 1 << endl;
 
    return 0;
}

Добавлено через 3 часа 34 минуты
Как оказалось, это решение тоже не очень простое. Крутил я его в отладчике и так и этак, и ничего толком не понял. Понял, что в массиве содержится левая кромка полного дерева из степеней двойки от tree[0] = 1 до tree[50] = 1125899906842624.
Объясните, пожалуйста, что содержится в переменной l и что считается в этом выражении l + tree[h - dep - 1].

@wingblack · 28.01.2015, 08:59

Сделай распечатку хода выполнения процедуры dfs() - вход-выход в процедуру, каждый чих, и все переменные в этом чихе записывать в файл.

@Dennis Ritchie · 28.01.2015, 17:40 **[ТС]**

Сообщение от wingblack

Сделай распечатку хода выполнения процедуры dfs() - вход-выход в процедуру, каждый чих, и все переменные в этом чихе записывать в файл.

А как это сделать: в Linux нужно лезть, или в Visual Studio есть такая опция?

Байт · 28.01.2015, 19:35

Сообщение от Dennis Ritchie

А как это сделать:

Если я правильно понял предыдущего оратора, надо просто в фунции dsf расставить printf-ы, поясняющие ситуацию с выводом значений переменных, которые обоснуют выбор ветки. Посколько вывода может оказаться очень немало, запустить прогу надо так:
proga >file.txt
Ну и в этом файле будет весь протокол работы и вся логика этой работы.

@Dennis Ritchie · 28.01.2015, 19:42 **[ТС]**

Сообщение от Байт

надо просто в фунции dsf расставить printf-ы...

Я про это не подумал. Спасибо.

Сообщение от Байт

proga >file.txt

Можно сделать проще:

C++
1
freopen("output.txt", "w", stdout);

Байт · 28.01.2015, 20:04

Сообщение от Dennis Ritchie

Можно сделать проще:

Конечно!

@Dennis Ritchie · 29.01.2015, 05:25 **[ТС]**

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
#include <iostream>
 
using namespace std;
 
const int len = 51;
 
long long tree[len], ans, h, n;
 
void dfs(int dep, long long l, bool left)
{
    ++ans;
    cout << "dep(" << dep << ")     l(" << l << ")      left(" << left << ")        ans(" << ans << ")\n\n";
    cout << "if ( dep(" << dep << ") == h(" << h << ") )\n";
    if (dep == h) {
        cout << "{\n    return;\n}\n\n\n";
        return;
    }
    cout << "   ...\nif ( n(" << n << ") < l(" << l << ") + tree[h(" << h << ") - dep(" << dep << ") - 1] (" << tree[h - dep - 1] << ") )";
    if (n < l + tree[h - dep - 1]) {
        cout << " {\n   if ( left(" << left << ") == true )";
        if (left == true) {
            cout << " {\n       ans(" << ans << ") += tree[h - dep] (" << tree[h - dep] << ") - 1;\n";
            ans += tree[h - dep] - 1;
            cout << "       ans(" << ans << ")\n    }\n";
        }
        cout << "   dfs( dep(" << dep << ") + 1, l(" << l << "), true );\n}\n\n\n";
        dfs(dep + 1, l, true);
    }
    else {
        cout << "\n ...\nelse {\n   if (left(" << left << ") == false) {\n";
        if (left == false) {
            cout << "       ans(" << ans << ") += tree[h - dep] (" << tree[h - dep] << ") - 1;\n";
            ans += tree[h - dep] - 1;
            cout << "       ans(" << ans << ")\n    }\n";
        }
        cout << "   dfs( dep(" << dep << ") + 1, l(" << l << ") + tree[h(" << h << ") - dep(" << dep << ") - 1] (" << tree[h - dep - 1] << "), false );\n}\n\n\n";
        dfs(dep + 1, l + tree[h - dep - 1], false);
    }
}
 
int main()
{
    freopen("out.txt", "w", stdout);
 
    cin >> h >> n;
 
    tree[0] = 1;
    for (int i = 1; i < len; ++i)
        tree[i] = tree[i - 1] * 2;
 
    ans = 0;
 
    dfs(0, 1, false);
 
    cout << "ans = " << ans - 1 << "\n";
 
    return 0;
}

Как-то так:

@Dennis Ritchie · 29.01.2015, 07:58 **[ТС]**

Так лучше:

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
#include <iostream>
#include <Windows.h>
 
using namespace std;
 
const int len = 51;
 
long long tree[len], ans, h, n;
 
void dfs(int dep, long long l, bool left)
{
    ++ans;
    cout << "dep(" << dep << ")     l(" << l << ")      left(" << left << ")        ans(" << ans << ")\n\n";
    cout << "if ( dep(" << dep << ") == h(" << h << ") )";
    if (dep == h) {
        cout << " \n    return;\n\n\n";
        return;
    }
    cout << "\n ...\nif ( n(" << n << ") < l(" << l << ") + tree[h(" << h << ") - dep(" << dep << ") - 1] (" << tree[h - dep - 1] << ") )";
    if (n < l + tree[h - dep - 1]) {
        cout << " {\n   if ( left(" << left << ") == true )";
        if (left == true) {
            cout << " {\n       ans(" << ans << ") += tree[h - dep] (" << tree[h - dep] << ") - 1;\n";
            ans += tree[h - dep] - 1;
            cout << "       ans(" << ans << ")\n    }\n";
        }
        else
            cout << "\n     ...\n";
        cout << "   dfs( dep(" << dep << ") + 1, l(" << l << "), true );\n}\n\n\n";
        dfs(dep + 1, l, true);
    }
    else {
        cout << "\n ...\nelse {\n   if (left(" << left << ") == false)";
        if (left == false) {
            cout << " {\n       ans(" << ans << ") += tree[h - dep] (" << tree[h - dep] << ") - 1;\n";
            ans += tree[h - dep] - 1;
            cout << "       ans(" << ans << ")\n    }\n";
        }
        else
            cout << "\n     ...\n";
        cout << "   dfs( dep(" << dep << ") + 1, l(" << l << ") + tree[h(" << h << ") - dep(" << dep << ") - 1] (" << tree[h - dep - 1] << "), false );\n}\n\n\n";
        dfs(dep + 1, l + tree[h - dep - 1], false);
    }
}
 
int main()
{
    while (true) {
        cin >> h >> n;
        freopen("out.txt", "w", stdout);
 
        tree[0] = 1;
        for (int i = 1; i < len; ++i)
            tree[i] = tree[i - 1] * 2;
 
        ans = 0;
 
        dfs(0, 1, false);
 
        cout << "ans = " << ans - 1 << "\n";
 
        ShellExecute(HWND_DESKTOP, NULL, "out.txt", NULL, NULL, SW_SHOWNORMAL);
    }
 
    return 0;
}

Добавлено через 1 час 3 минуты
Не понимаю: а почему при h = 3 и n = 8 ответ 14? По-моему, ответ должен быть 7. Ведь игрок не должен посетить правую ветку, а из ответа следует, что он проходит правую ветку полностью.

@wingblack · 29.01.2015, 08:33

Проверь другие числа

h=3 n=8 ответ 14 как раз соответствует ответу на картинке что я давал Угадай, где выход! (Поиск листа бинарного дерева, содержащего выход из лабиринта)

@Dennis Ritchie · 29.01.2015, 09:16 **[ТС]**

Сообщение от wingblack

h=3 n=8 ответ 14 как раз соответствует ответу на картинке что я давал

Так на вашей картинке h = 4, т. е. последний ряд содержит 2⁴ листьев. А при h = 3 дерево содержит 2³ листьев. Как же тогда этот ответ может соответствовать вашей картинке?

@Dennis Ritchie · 29.01.2015, 09:48 **[ТС]**

Что не так в моей логике?

@Dennis Ritchie · 29.01.2015, 18:20 **[ТС]**

Выходит, что я неправильно понял алгоритм обхода, так как я не понимаю, почему при h = 1 и n = 2 ответ будет 2.
Ведь посещается только первая вершина (вторая вершина - это выход), так почему ответ два.

@Dennis Ritchie · 29.01.2015, 20:40 **[ТС]**

Надо было внимательнее читать условие задачи. Нумеруются только листы:

Пронумеруем все листы слева направо числами от 1 до 2^h. Выход расположен в некоторой вершине n, где 1 ≤ n ≤ 2^h.

Новые блоги и статьи Все статьи Все блоги /
http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Первый деплой lagorue 16.01.2026 Не спеша развернул своё 1ое приложение в kubernetes. А дальше мне интересно создать 1фронтэнд приложения и 2 бэкэнд приложения развернуть 2 деплоя в кубере получится 2 сервиса и что-бы они. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит: токи, напряжения и их 1 и 2 производные при t = 0;. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .

@wingblack 294 / 265 / 48 Регистрация: 09.04.2013 Сообщений: 1,038
	26.01.2015, 11:40
	У тебя описан алгоритм вполне подробно, просто следуй ему при обходе и все. - поочередно идем налево и направо - если уже посещали вершину куда хотим идти - пропустить ход - если попустили два раза - идем наверх - если попали в лист (а это "край" дерева) и лист не выход - идем наверх - если нашли выход - конец игре. Поправка на рисунках, не h=5, а h=4 1

@wingblack 294 / 265 / 48 Регистрация: 09.04.2013 Сообщений: 1,038
	28.01.2015, 08:59
	Сделай распечатку хода выполнения процедуры dfs() - вход-выход в процедуру, каждый чих, и все переменные в этом чихе записывать в файл. 1

@wingblack 294 / 265 / 48 Регистрация: 09.04.2013 Сообщений: 1,038
	29.01.2015, 08:33
	Проверь другие числа h=3 n=8 ответ 14 как раз соответствует ответу на картинке что я давал Угадай, где выход! (Поиск листа бинарного дерева, содержащего выход из лабиринта) 0

@Dennis Ritchie 555 / 148 / 58 Регистрация: 27.07.2014 Сообщений: 2,446
	29.01.2015, 09:48 [ТС]
	Что не так в моей логике? Миниатюры 0

@Dennis Ritchie 555 / 148 / 58 Регистрация: 27.07.2014 Сообщений: 2,446
	29.01.2015, 18:20 [ТС]
	Выходит, что я неправильно понял алгоритм обхода, так как я не понимаю, почему при h = 1 и n = 2 ответ будет 2. Ведь посещается только первая вершина (вторая вершина - это выход), так почему ответ два. Миниатюры 0

Угадай, где выход! (Поиск листа бинарного дерева, содержащего выход из лабиринта)

Решение