У меня есть проблема с домашней работой, которая заключается в рекурсивном решении Ханойских башен для графа G = {V, E}, где V = {Start, Aux1, Aux2, Aux3, Dest} и E = {(Start, Aux1), (Aux1, Aux2), (Aux2, Aux3), (Aux3, Aux1), (Aux3, Dest)}.После разработки алгоритма я должен обеспечить его временную и пространственную сложность.
Как вы можете видеть, это ориентированный граф, который ставит задачу Ханойской башни с 5 колышками с особыми условиями, что диски могут двигаться только напрямую.например, недопустимо переходить обратно на aux2 напрямую с aux3 или на aux1 прямо с aux2.Другими словами, есть «внутренний цикл», образованный aux1 -> aux2 -> aux3 -> aux1.Кроме того, невозможно вернуться к началу, как только диск покинул указанную привязку, и, наконец, как только диск достигает dest, он там блокируется и не может вернуться назад.Я уже решил проблему в том смысле, что я написал алгоритм на Java для записи ходов в файл.Однако моя проблема в том, что я не совсем уверен, как подсчитать рекурсивные вызовы, чтобы получить уравнение рекурсивных отношений, чтобы решить сложность времени и пространства, потому что мой первоначальный вызов функции делает вызовы других рекурсивных функций, которые, в свою очередь,Также звоните сами или взаимозаменяемо.Вот мой код
import java.io.IOException;
import java.io.PrintWriter;
public class TowersOfHanoi{
private static String to = " --> ";
PrintWriter outputFile;
private int n;
private String source, aux1, aux2, aux3, destination;
private String outputName;
TowersOfHanoi(String source, String aux1, String aux2, String aux3, String dest, int n){
this.n = n;
this.source = source;
this.aux1 = aux1;
this.aux2 = aux2;
this.aux3 = aux3;
this.destination = dest;
outputName = "Towers of Hanoi_"+n+".txt";
}
void solve() throws IOException {
outputFile = new PrintWriter(outputName);
outputFile.println("Towers of Hanoi solution for n = " + this.n + ":");
outputFile.println();
outputFile.flush();
if(n == 1){
outputFile.println("Disk " + n + ": " + source + to + aux1 + to + aux2 + to + aux3 + to + destination);
outputFile.flush();
return;
}
hop_3(n-1, source, aux1, aux2, aux3);
outputFile.println("Disk " + n + ": " + source + to + aux1 + to + aux2);
outputFile.flush();
hop_1(n-1, aux3, aux1, aux2);
outputFile.println("Disk " + n + ": " + aux2 + to + aux3 + to + destination);
outputFile.flush();
exit(n-1, aux1, aux2, aux3, destination);
}
private void hop_3(int n, String source, String aux1, String aux2, String aux3) throws IOException {
if(n == 1){
outputFile.println("Disk " + n + ": " + source + to + aux1 + to + aux2 + to + aux3);
outputFile.flush();
return;
}
hop_3(n-1, source, aux1, aux2, aux3);
outputFile.println("Disk " + n + ": " + source + to + aux1 + to + aux2);
outputFile.flush();
hop_1(n-1, aux3, aux1, aux2);
outputFile.println("Disk " + n + ": " + aux2 + to + aux3);
outputFile.flush();
hop_2(n-1, aux1, aux2, aux3);
}
private void hop_2(int n, String from, String aux, String end) throws IOException{
if(n == 1){
outputFile.println("Disk " + n + ": " + from + to + aux + to + end);
outputFile.flush();
return;
}
hop_2(n-1, from, aux, end);
outputFile.println("Disk " + n + ": " + from + to + aux);
outputFile.flush();
hop_1(n-1, end, from, aux);
outputFile.println("Disk " + n + ": " + aux + to + end);
outputFile.flush();
hop_2(n-1, from, aux, end);
}
private void hop_1(int n, String from, String end, String aux) throws IOException {
if(n == 1){
outputFile.println("Disk " + n + ": " + from + to + end);
outputFile.flush();
return;
}
hop_2(n-1, from, end, aux);
outputFile.println("Disk " + n + ": " + from + to + end);
outputFile.flush();
hop_2(n-1, aux, from, end);
}
private void exit(int n, String from, String aux1, String aux2, String end) throws IOException {
if(n == 1){
outputFile.println("Disk " + n + ": " + from + to + aux1 + to + aux2 + to + end);
outputFile.flush();
return;
}
hop_2(n-1, from, aux1, aux2);
outputFile.println("Disk " + n + ": " + from + to + aux1);
outputFile.flush();
hop_1(n-1, aux2, from, aux1);
outputFile.println("Disk " + n + ": " + aux1 + to + aux2 + to + end);
outputFile.flush();
exit(n-1, from, aux1, aux2, end);
outputFile.flush();
outputFile.close();
}
}
Как видите, решение, которое мне пришлось найти, довольно сложное и повторяющееся.Возможно, это даже не самый лучший подход, но это единственный способ, который заставил меня работать, что также имело смысл.Сейчас я действительно борюсь, потому что сложность времени и пространства зависит от числа дисков n, но я не знаю, как подсчитать рекурсивные вызовы в этом конкретном случае, чтобы получить уравнение рекурсивного отношения.
PS Вот вывод для n = 1 и n = 3 соответственно:
Башни решения Ханоя для n = 1:
Диск 1: Пуск -> Вспомогательный1 -> Вспомогательный2 -> Вспомогательный3-> Пункт назначения
Решение "Ханойские башни" для n = 3:
Диск 1: Пуск -> Вспомогательный1 -> Вспомогательный2 -> Вспомогательный3 Диск 2: Старт -> Вспомогательный1 --> Вспомогательный2 Диск 1: Вспомогательный3 -> Вспомогательный1 Диск 2: Вспомогательный2 -> Вспомогательный3 Диск 1: Вспомогательный1 -> Вспомогательный2 -> Вспомогательный3 Диск 3: Пуск -> Вспомогательный1 -> Вспомогательный2 Диск 1: Вспомогательный3 ->Вспомогательный1 -> Вспомогательный2 Диск 2: Вспомогательный3 -> Вспомогательный1 Диск 1: Вспомогательный2 -> Вспомогательный3 -> Вспомогательный1 Диск 3: Вспомогательный2 -> Вспомогательный3 -> Диск назначения 1: Вспомогательный1 -> Вспомогательный2 -> Вспомогательный3 Диск2: Вспомогательный1 -> Auxiliary2 Диск 1: вспомогательный3 -> вспомогательный1 Диск 2: вспомогательный2 -> вспомогательный3 -> целевой диск 1: вспомогательный1 -> вспомогательный2 -> вспомогательный3 -> конечный пункт
Заранее благодарен всему сообществу!