Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Помогите, пожалуйста, написать программу по нижеописанной задаче!

tylos Мастер (1718), закрыт 1 год назад
Здравствуйте, напишите пожалуйста программу на c++, которая создает граф всех возможных состояний головоломки "Ханойская башня", где узлы графа это состояния cистемы колышков, а ребра являются перестановками дисков и потом по этому же графу ищет наикратчайший путь до выигрышного состояния. Изначально есть 3 колышка и n-количество дисков, которое задает пользователь, все диски находятся на колышке А, задача состоит в том, чтобы переставить все диски с колышка А на колышек С.

ОЧЕНЬ НАДО, Я ДАЖЕ БЕЗ ПОНЯТИЯ КАК ЭТО РЕАЛИЗОВАТЬ!
Дополнен 1 год назад
Короче, я немного поменял код Exponenta и теперь каждый узел хранит в себе как состояние системы, так и путь до самого узла, и потом как только дохожу до победного узла считываю информацию о пути из него, количество колышек теперь пользователь не может задать и оно равно 3.
Вот сам код: https://yadi.sk/d/m2c4gqxR_0ngXg
Лучший ответ
СОВА ⭐ [expert] Мастер (2479) 1 год назад
 #include  
#include
#include
#include

using namespace std;

// Структура, представляющая состояние системы колышков
struct State {
vector> pegs; // Колышки
string move; // Ход, приведший к данному состоянию

State(const vector>& p, const string& m) : pegs(p), move(m) {}
};

// Функция для создания всех возможных состояний головоломки "Ханойская башня"
vector generateStates(const State& state) {
vector nextStates;

const vector>& pegs = state.pegs;
int numPegs = pegs.size();

for (int from = 0; from < numPegs; ++from) {
for (int to = 0; to < numPegs; ++to) {
if (from != to && !pegs[from].empty()) {
vector> newPegs = pegs;
int disk = newPegs[from].back();
newPegs[from].pop_back();
newPegs[to].push_back(disk);

string move = "Move disk " + to_string(disk) + " from peg " + to_string(from) + " to peg " + to_string(to);

nextStates.push_back(State(newPegs, move));
}
}
}

return nextStates;
}

// Функция для проверки, является ли состояние выигрышным
bool isWinningState(const State& state, int numDisks, int winPeg) {
return state.pegs[winPeg].size() == numDisks;
}

// Функция для поиска наикратчайшего пути до выигрышного состояния
string findShortestPath(int numPegs, int numDisks, int winPeg) {
vector> initialPegs(numPegs);

for (int i = numDisks; i >= 1; --i) {
initialPegs[0].push_back(i);
}

State initialState(initialPegs, "");

queue q;
q.push(initialState);

unordered_set visited;
visited.insert("");

while (!q.empty()) {
State currState = q.front();
q.pop();

if (isWinningState(currState, numDisks, winPeg)) {
return currState.move;
}

vector nextStates = generateStates(currState);

for (const State& nextState : nextStates) {
if (visited.find(nextState.move) == visited.end()) {
q.push(nextState);
visited.insert(nextState.move);
}
}
}

return "No solution found.";
}

int main() {
int numPegs, numDisks;
cout << "Enter the number of pegs: ";
cin >> numPegs;

cout << "Enter the number of disks: ";
cin >> numDisks;

cout << "Finding the shortest path..." << endl;
string shortestPath = findShortestPath(numPegs, numDisks, numPegs - 1);

cout << "Shortest path: " << shortestPath << endl;

return 0;
}
tylosМастер (1718) 1 год назад
А почему для одного диска решение всегда находится, а для двух уже нет, делал 20 запусков с вводом количества дисков 2, и во всех таких запусках появлялось сообщение "No solution found"?
СОВА ⭐ [expert] Мастер (2479) tylos, это связано с особенностями головоломки Ханойской башни. Для двух колышков и двух дисков решение существует только тогда, когда выигрышный колышек находится в середине. В этом случае диски можно перемещать напрямую между колышками без необходимости использования третьего колышка. Однако алгоритм использует поиск в ширину, который будет исследовать все возможные переходы между колышками, и решения для этого случая не будет найдено.
tylosМастер (1718) 1 год назад
Спасибо, я немного переделал код, но без твоей помощи, не знал бы что делать))
Остальные ответы
Red Мастер (1032) 1 год назад
Для создания графа необходимо определить его вершины и ребра. Вершины могут быть представлены как узлы, а ребра - как связи между узлами.

Способы создания графа:

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

2. Список смежности: это список вершин, каждая из которых связана со списком ее соседних вершин.

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

После создания графа можно использовать различные алгоритмы для его анализа, такие как поиск в глубину, поиск в ширину, алгоритм Дейкстры и т.д.
tylosМастер (1718) 1 год назад
Так вопрос не в том, что нужно сделать, а как нужно сделать
Похожие вопросы