Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

Задача с кубиками - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Эйлеров путь. Нужны комментарии кода http://www.cyberforum.ru/cpp-beginners/thread876509.html
Имеется правильный код решения задачи по поиску Эйлерова пути. Прошу прокомментировать важные аспекты кода, то есть, что выполняет тот или иной цикл и т.п. Заранее благодарен! Условие: Задан...
C++ Возврат созданного в функции массива Верна ли следующая конструкция? void LoadArray(float* array, int & count) { int fcount = 30;//данная цифра подсчитывается при открытии файла. count = fcount; array = new float; ... http://www.cyberforum.ru/cpp-beginners/thread876501.html
C++ Проверьте задачку (написать функцию, которая возвращает индекс строки t к строке s, и "-1", если t в s не входит)
Написать функцию, которая возвращает индекс строки t к строке s, и "-1", если t в s не входит. Вот код программы: int stroka(char *s,char *t) {int k=0, n=0; while (*t++==*s++) { n=k; }...
C++ комментарии к программе(желательно построчно)
#include <iostream> using namespace std; #include <iomanip> template <typename T> class Stack { private: T *stackPtr; int size; T top;
C++ Ошибка при создании 2-го элемента динамического списка http://www.cyberforum.ru/cpp-beginners/thread876489.html
НЕ могу понять откуда как исправить данную ошибка . Выскакивает как мне кажется при попытке динамически выделить память для указателя на структуру повторно Node *pv = new Node . Компилировал на DEV...
C++ Найти нужные числа из множества случайных Доброго времени суток! Ребята, помогите, пожалуйста, решить задачу) Изначально задание выглядит так: "Эксперимент состоит из подсчета числа бросков двух костей до выпадения двух шестерок. Провести... подробнее

Показать сообщение отдельно
gazlan
3132 / 1908 / 285
Регистрация: 27.08.2010
Сообщений: 5,132
Записей в блоге: 1
24.05.2013, 22:04
1. Граф или матрица - неважно, это эквивалентные представления.

2. Я думаю, тут возможны сокращающие перебор оптимизации.

Например, можно вычеркнуть все кубики, не содержащие ни одной буквы имени.
Для всех кубиков, содержащих только одну букву имени, их место уже определено.
Можно убедиться, что "разных" кубиков не меньше чем разных букв в имени.

Т.е., при "удачном" раскладе можно убедиться, что решения нет, без фактического решения задачи.
Ну и, любой отброшенный кубик сокращает число вариантов для перебора.

3. Мне кажется, удобнее работать с деревом выбора. На каждом i-ом шаге есть r[i] (r < N) вариантов выбора кубика (т.е. r[i] дочерних узлов). Строим дерево и рекурсивно обходим его в глубину.

Если на каком-то маршруте удалось построить имя - задача решена, выводим решение. Если нет - возвращаемся назад (по стеку) и пробуем следующий маршрут. Если обойдено все дерево и не удалось построить имя - нет решения.
1
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru