Счетные башни Ханоя-Ява
Я тестирую программу Towers of Hanoi. Мне уже помогли измерить время программы, но это не то, чего хотел мой профессор, он хотел посчитать итерации. Я не могу получить его, и мне нужно "общее количество ходов", которое запустит моя программа, но она не будет правильно распечатываться. Ребята, вы можете мне помочь? Спасибо, любезно.
Это код, который я использовал:
package stackru;
import java.util.*;
public class towers {
public static int N;
public static Stack<Integer>[] integer = new Stack[4];
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
integer[1] = new Stack<>();
integer[2] = new Stack<>();
integer[3] = new Stack<>();
System.out.print("Enter 5 integers: ");
int num = input.nextInt();
N = num;
StackMove(num);
}
public static void StackMove(int N) {
for (int d = N; d > 0; d--)
integer[1].push(d);
PrintStack();
move(N, 1, 2, 3);
}
public static void move(int N, int a, int b, int c) {
if (N > 0) {
move(N - 1, a, c, b);
int d = integer[a].pop();
integer[c].push(d);
PrintStack();
move(N - 1, b, a, c);
}
}
public static void PrintStack() {
System.out.println(" A | B | C");
System.out.println("---------------");
for (int i = N - 1; i >= 0; i--) {
String d1 = " ", d2 = " ", d3 = " ";
try {
d1 = String.valueOf(integer[1].get(i));
} catch (Exception e) {
}
try {
d2 = String.valueOf(integer[2].get(i));
} catch (Exception e) {
}
try {
d3 = String.valueOf(integer[3].get(i));
} catch (Exception e) {
}
System.out.println(" " + d1 + " | " + d2 + " | " + d3);
}
System.out.print("\n");
}
}
Вывод должен быть таким:
3 ответа
Не по теме комментарии
Вот некоторые комментарии к вашему коду, которые не решают вашу проблему, но вам нужно сказать. (по теме комментариев ниже)
наименование идентификаторов
Принять соглашения об именах Java!
например.:
- имена классов начинаются с заглавной буквы, а имена методов начинаются с строчной (вы сделали наоборот)
- переменные также начинаются со строчной буквы, только константы
ALL_UPPER_CASE
Тогда не используйте однобуквенные имена для переменных.
Выбирая имена для ваших переменных, берите их из проблемной области.
Каково значение переменной integer?
Более правильное имя будет stacks здесь (обратите внимание на множественное число 's'), но не потому, что он содержит объект Stack класс, но потому что вы моделируете стек.
Ваша (класс) переменная члена N мешает параметру N некоторых методов. И вот единственный момент, когда допустимо нарушение соглашений об именах Java: вы можете поставить префикс-переменную с подчеркиванием (_). Это позволит эффективно избежать такого рода помех.
избегать странных шаровых решений
Этот удвоенный идентификатор N приводит к двум различным подходам в вашей программе:
- некоторые из ваших методов обращаются к переменной-члену
N, - некоторые другие методы имеют параметр того же типа и того же имени.
Для любой программы выберите любой из этих методов доступа.
Представьте, что произойдет, если вам нужно изменить N, Ваша программа будет вести себя странно, и вам будет трудно найти ошибку.
не используйте исключения как управление потоком
String d1 = " ", d2 = " ", d3 = " "; try { d1 = String.valueOf(integer[1].get(i)); } catch (Exception e) { }
С этим кодом вы сохраняете пространство в d1 в случае, если в первом стеке недостаточно элементов. Вы должны лучше использовать if заявление, чтобы сделать это:
String d1 = " ", d2 = " ", d3 = " ";
if( i < integer[1].size() ){
d1 = String.valueOf(integer[1].get(i));
}
Это не только сохраняет строку в вашем коде, но и лучше передает ваш исходный код.
привыкнуть к нулю на основе индексации.
Вы объявили свой массив integer размера 4 чтобы иметь доступ к его элементам путем естественного подсчета
public static void main(String[] args) { Scanner input = new Scanner(System.in); integer[1] = new Stack<>(); integer[2] = new Stack<>(); integer[3] = new Stack<>();
Проблема здесь в том, что у вас есть дополнительный элемент в этом массиве, который не используется. И что еще хуже, это первый элемент в этом массиве.
В Java есть несколько умных подпрограмм, работающих с массивами (и коллекциями), которые будут иметь проблемы или, по крайней мере, будут нуждаться в специальной обработке, если ваш первый элемент массива должен игнорироваться следующим образом.
Вы можете легко обойти это, используя другую технику: замените магические числа на константы
Вы можете определить константы в вашем классе следующим образом:
public class towers {
private static final int STACK_ONE = 0;
private static final int STACK_TWO = 1;
private static final int STACK_TREE = 2;
это изменит ваш код следующим образом:
integer[STACK_ONE] = new Stack<>();
integer[STACK_TWO] = new Stack<>();
integer[STACK_TREE] = new Stack<>();
//...
d1 = String.valueOf(integer[STACK_ONE].get(i));
Кто-то может предложить тип перечисления Java, но это довольно сложно при использовании с массивами.
На тему комментария
Поскольку вы выбираете мой ответ в качестве решения, я чувствую, что должен внести свой вклад в это...; о)
где добавить фактический подсчет
вопрос: где в коде вы делаете исчисляемый ход?
Очевидно, это move метод. Но не каждый вызов метода move является исчисляемым шагом. Вы можете считать ход только если вы введете if блок внутри. Так что это место, где вы должны добавить "код счета".
как осуществить подсчет?
Есть четыре подхода к этому. В порядке сложности:
- арифметический расчет
- дополнительная переменная-член,
- дополнительный параметр и возвращаемое значение
- прохождение встречного объекта.
Поскольку основная задача является детерминированной, количество ходов можно просто рассчитать. Это решение предоставлено Lew Bloch.
дополнительная переменная-членВы можете добавить другую переменную-член, например N:
public class towers
{
public static int N;
public static int moveCounter = 0;
В позиции, указанной в предыдущем разделе, вы просто добавляете единицу к текущему значению этой новой переменной-члена.
дополнительный параметр и возвращаемое значение
Это решение предоставлено Dani
прохождение встречного объекта.
Это как-то похоже на предыдущее решение за исключением того, что нам не нужно что-то возвращать. Но нам нужен дополнительный класс для этого. Поэтому это решение является сложным для этой простой задачи, но я добавлю его для записей.
public class towers {
private static class Counter{
private int counter = 0;
void increment(){ counter++;}
int counted() { return counter; }
}
// ...
Counter numberOfMoves= new Counter(num,);
StackMove(num,numberOfMoves);
System.out.println("Number of moves: "+ numberOfMoves.counted());
// ...
public static void StackMove(int N, Counter numberOfMoves) {
for (int d = N; d > 0; d--)
integer[1].push(d);
PrintStack();
move(N, 1, 2, 3, numberOfMoves);
}
public static void move(int N, int a, int b, int c, Counter numberOfMoves) {
if (N > 0) {
move(N - 1, a, c, b, numberOfMoves);
int d = integer[a].pop();
integer[c].push(d);
PrintStack();
move(N - 1, b, a, c, numberOfMoves);
numberOfMoves.count();
}
}
// ...
КОД
import java.util.Stack;
import java.util.*;
public class TowersOfHanoiPrint {
public static int N;
public static Stack<Integer>[] integer = new Stack[4];
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
integer[1] = new Stack<>();
integer[2] = new Stack<>();
integer[3] = new Stack<>();
System.out.print("Enter 5 integers: ");
int num = input.nextInt();
N = num;
System.out.println("Number of moves: "+StackMove(num));
}
public static int StackMove(int N) {
for (int d = N; d > 0; d--)
integer[1].push(d);
PrintStack();
return move(N, 1, 2, 3);
}
public static int move(int N, int a, int b, int c) {
if (N > 0) {
int numberMovesA = move(N - 1, a, c, b);
int d = integer[a].pop();
integer[c].push(d);
PrintStack();
int numberMovesB = move(N - 1, b, a, c);
return (numberMovesA + numberMovesB + 1);
}
return 0;
}
public static void PrintStack() {
System.out.println(" A | B | C");
System.out.println("---------------");
for (int i = N - 1; i >= 0; i--) {
String d1 = " ", d2 = " ", d3 = " ";
try {
d1 = String.valueOf(integer[1].get(i));
} catch (Exception e) {
}
try {
d2 = String.valueOf(integer[2].get(i));
} catch (Exception e) {
}
try {
d3 = String.valueOf(integer[3].get(i));
} catch (Exception e) {
}
System.out.println(" " + d1 + " | " + d2 + " | " + d3);
}
System.out.print("\n");
}
}
ВЫХОД
Enter 5 integers: 6
A | B | C
---------------
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
A | B | C
---------------
| |
2 | |
3 | |
4 | |
5 | |
6 | 1 |
A | B | C
---------------
| |
| |
3 | |
4 | |
5 | |
6 | 1 | 2
A | B | C
---------------
| |
| |
3 | |
4 | |
5 | | 1
6 | | 2
A | B | C
---------------
| |
| |
| |
4 | |
5 | | 1
6 | 3 | 2
A | B | C
---------------
| |
| |
1 | |
4 | |
5 | |
6 | 3 | 2
A | B | C
---------------
| |
| |
1 | |
4 | |
5 | 2 |
6 | 3 |
A | B | C
---------------
| |
| |
| |
4 | 1 |
5 | 2 |
6 | 3 |
A | B | C
---------------
| |
| |
| |
| 1 |
5 | 2 |
6 | 3 | 4
A | B | C
---------------
| |
| |
| |
| |
5 | 2 | 1
6 | 3 | 4
A | B | C
---------------
| |
| |
| |
2 | |
5 | | 1
6 | 3 | 4
A | B | C
---------------
| |
| |
1 | |
2 | |
5 | |
6 | 3 | 4
A | B | C
---------------
| |
| |
1 | |
2 | |
5 | | 3
6 | | 4
A | B | C
---------------
| |
| |
| |
2 | |
5 | | 3
6 | 1 | 4
A | B | C
---------------
| |
| |
| |
| | 2
5 | | 3
6 | 1 | 4
A | B | C
---------------
| |
| |
| | 1
| | 2
5 | | 3
6 | | 4
A | B | C
---------------
| |
| |
| | 1
| | 2
| | 3
6 | 5 | 4
A | B | C
---------------
| |
| |
| |
| | 2
1 | | 3
6 | 5 | 4
A | B | C
---------------
| |
| |
| |
| |
1 | 2 | 3
6 | 5 | 4
A | B | C
---------------
| |
| |
| |
| 1 |
| 2 | 3
6 | 5 | 4
A | B | C
---------------
| |
| |
| |
| 1 |
3 | 2 |
6 | 5 | 4
A | B | C
---------------
| |
| |
| |
| |
3 | 2 | 1
6 | 5 | 4
A | B | C
---------------
| |
| |
| |
2 | |
3 | | 1
6 | 5 | 4
A | B | C
---------------
| |
| |
1 | |
2 | |
3 | |
6 | 5 | 4
A | B | C
---------------
| |
| |
1 | |
2 | |
3 | 4 |
6 | 5 |
A | B | C
---------------
| |
| |
| |
2 | 1 |
3 | 4 |
6 | 5 |
A | B | C
---------------
| |
| |
| |
| 1 |
3 | 4 |
6 | 5 | 2
A | B | C
---------------
| |
| |
| |
| |
3 | 4 | 1
6 | 5 | 2
A | B | C
---------------
| |
| |
| |
| 3 |
| 4 | 1
6 | 5 | 2
A | B | C
---------------
| |
| |
| |
| 3 |
1 | 4 |
6 | 5 | 2
A | B | C
---------------
| |
| |
| 2 |
| 3 |
1 | 4 |
6 | 5 |
A | B | C
---------------
| |
| 1 |
| 2 |
| 3 |
| 4 |
6 | 5 |
A | B | C
---------------
| |
| 1 |
| 2 |
| 3 |
| 4 |
| 5 | 6
A | B | C
---------------
| |
| |
| 2 |
| 3 |
| 4 | 1
| 5 | 6
A | B | C
---------------
| |
| |
| |
| 3 |
| 4 | 1
2 | 5 | 6
A | B | C
---------------
| |
| |
| |
| 3 |
1 | 4 |
2 | 5 | 6
A | B | C
---------------
| |
| |
| |
| |
1 | 4 | 3
2 | 5 | 6
A | B | C
---------------
| |
| |
| |
| 1 |
| 4 | 3
2 | 5 | 6
A | B | C
---------------
| |
| |
| |
| 1 | 2
| 4 | 3
| 5 | 6
A | B | C
---------------
| |
| |
| | 1
| | 2
| 4 | 3
| 5 | 6
A | B | C
---------------
| |
| |
| | 1
| | 2
| | 3
4 | 5 | 6
A | B | C
---------------
| |
| |
| |
| | 2
1 | | 3
4 | 5 | 6
A | B | C
---------------
| |
| |
| |
| |
1 | 2 | 3
4 | 5 | 6
A | B | C
---------------
| |
| |
| |
| 1 |
| 2 | 3
4 | 5 | 6
A | B | C
---------------
| |
| |
| |
| 1 |
3 | 2 |
4 | 5 | 6
A | B | C
---------------
| |
| |
| |
| |
3 | 2 | 1
4 | 5 | 6
A | B | C
---------------
| |
| |
| |
2 | |
3 | | 1
4 | 5 | 6
A | B | C
---------------
| |
| |
1 | |
2 | |
3 | |
4 | 5 | 6
A | B | C
---------------
| |
| |
1 | |
2 | |
3 | | 5
4 | | 6
A | B | C
---------------
| |
| |
| |
2 | |
3 | | 5
4 | 1 | 6
A | B | C
---------------
| |
| |
| |
| | 2
3 | | 5
4 | 1 | 6
A | B | C
---------------
| |
| |
| | 1
| | 2
3 | | 5
4 | | 6
A | B | C
---------------
| |
| |
| | 1
| | 2
| | 5
4 | 3 | 6
A | B | C
---------------
| |
| |
| |
| | 2
1 | | 5
4 | 3 | 6
A | B | C
---------------
| |
| |
| |
| |
1 | 2 | 5
4 | 3 | 6
A | B | C
---------------
| |
| |
| |
| 1 |
| 2 | 5
4 | 3 | 6
A | B | C
---------------
| |
| |
| |
| 1 | 4
| 2 | 5
| 3 | 6
A | B | C
---------------
| |
| |
| | 1
| | 4
| 2 | 5
| 3 | 6
A | B | C
---------------
| |
| |
| | 1
| | 4
| | 5
2 | 3 | 6
A | B | C
---------------
| |
| |
| |
| | 4
1 | | 5
2 | 3 | 6
A | B | C
---------------
| |
| |
| | 3
| | 4
1 | | 5
2 | | 6
A | B | C
---------------
| |
| |
| | 3
| | 4
| | 5
2 | 1 | 6
A | B | C
---------------
| |
| | 2
| | 3
| | 4
| | 5
| 1 | 6
A | B | C
---------------
| | 1
| | 2
| | 3
| | 4
| | 5
| | 6
Number of moves: 63