Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.86/7: Рейтинг темы: голосов - 7, средняя оценка - 4.86
Dennis Ritchie
549 / 141 / 58
Регистрация: 27.07.2014
Сообщений: 2,446
1

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

26.01.2015, 07:20. Просмотров 1357. Ответов 21
Метки нет (Все метки)

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

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

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

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

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

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

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

Примеры тестов
Входные данныеВыходные данные
1 22
2 35
3 610
10 10242046

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

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

Угадай, где выход! (Поиск листа бинарного дерева, содержащего выход из лабиринта)
Никогда раньше не решал задачи на деревья, но вот решил начать. Самая большая проблема в том, что я никак не могу понять примеры тестов . А всё потому, что я, наверное, неправильно строю деревья.
Я прочитал эту строчку:
Пронумеруем все листы слева направо числами от 1 до 2h.
И вот, что я нарисовал, следую этому предложению, для трёх тестовых примеров:

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


Я так понимаю, что это неправильно. Объясните, пожалуйста, как правильно нужно нумеровать дерево и в какой последовательности обходить это дерево для трёх тестовых примеров. Если несложно, то нарисуйте хотя бы в Paint'e рисунок со стрелочками или попробуйте описать комментариями.
0
Лучшие ответы (1)
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.01.2015, 07:20
Ответы с готовыми решениями:

Найти выход из лабиринта
Как можно искать выход из лабиринта, который задается отрезками. То есть надо найти даже не выход,...

Выход из лабиринта
Помогите допилить.Нужен алгоритм нахождения выхода и лабиринта.За ранее спасибо! Вот сам лабиринт:...

Выход из лабиринта
Здравствуйте! Я сделал игру по видео уроку, где контролируя кнопками смайлик w, a, s, d достигнув...

Выход из лабиринта
Дан лабиринт M: array of boolean; (true - стена false - свободно) Начало в верхнем левом угле...

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

21
Dennis Ritchie
549 / 141 / 58
Регистрация: 27.07.2014
Сообщений: 2,446
30.01.2015, 02:33  [ТС] 21
Наконец-то я разобрался с решением. Это очень красивый дискретный алгоритм.
0
Dennis Ritchie
549 / 141 / 58
Регистрация: 27.07.2014
Сообщений: 2,446
01.02.2015, 02:06  [ТС] 22
Теперь нужно разобраться со сложным решением :
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
#include <iostream>
#include <Windows.h>
 
using namespace std;
 
int main() {
 
    int h, mv;
    long long n, ans;
 
    while (true) {
        mv = ans = 0;
 
        cin >> h >> n;
 
        freopen("out.txt", "w", stdout);
 
        n--;
 
        for (int i = h - 1; i >= 0; --i) {
            cout << "for ( int i = h(" << h << ") - 1; i >= 0; --i(" << i << ") ) {\n";
            cout << "   int real = !!( n(" << n << ") & (1LL << i(" << i << ")) (" << (1LL << i) << ") ) !(" << !(n & (1LL << i)) << ") !!(" << !!(n & (1LL << i)) << ");\n";
            int real = !!(n & (1LL << i));
            cout << "   if ( mv(" << mv << ") != real(" << real << ") )";
            if (mv != real) {
                cout << " {\n       ans(" << ans << ") += ( (1LL << (i(" << i << ") + 1) (" << (1LL << (i + 1)) << ") ) - 1) (" << ((1LL << (i + 1)) - 1) << ");\n";
                ans += ((1LL << (i + 1)) - 1);
                cout << "       mv(" << mv << ") ^= 1;\n";
                mv ^= 1;
                cout << "       mv = " << mv << "\n }\n";
            }
            else
                cout << "\n     ...\n";
            cout << "   mv(" << mv << ") ^= 1;\n";
            mv ^= 1;
            cout << "   mv = " << mv << "\n ans(" << ans << ")\n";
            ans++;  cout << "   ans++ (" << ans << ");\n}\n\n";
        }
 
        cout << '\n' << ans << '\n';
 
        ShellExecute(HWND_DESKTOP, NULL, "out.txt", NULL, NULL, SW_SHOWNORMAL);
    }
 
    return 0;
}
0
01.02.2015, 02:06
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.02.2015, 02:06

Простой выход из лабиринта
Суть задачи: дан массив &quot;0&quot; - проход &quot;-1&quot; - стенка, &quot;-2&quot; - путь, нужно найти выход. Точка входа...

Найти выход из лабиринта
Пожалуйста помогите решить. Перевод. Вопрос задачи: наити выход роботу из лабиринта. Робот...

Выход из лабиринта .Волновой алгоритм
Есть задача на поиск выхода из лабиринта. Я попытался реализовать волновой алгоритм...но он у меня...


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

Или воспользуйтесь поиском по форуму:
22
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.