#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)
4 месяца назад
А почему для одного диска решение всегда находится, а для двух уже нет, делал 20 запусков с вводом количества дисков 2, и во всех таких запусках появлялось сообщение "No solution found"?
ОЧЕНЬ НАДО, Я ДАЖЕ БЕЗ ПОНЯТИЯ КАК ЭТО РЕАЛИЗОВАТЬ!