Главная » C++ » Ханойская башня - Как не пропустить колышек при каждой рекурсии

Ханойская башня — Как не пропустить колышек при каждой рекурсии

Мое задание — решить башни Ханоя для любого числа с помощью рекурсии. Я написал свой код на C ++.

Правила:

  1. Невозможно сложить больший диск поверх меньшего.
  2. Невозможно переместить более одного диска одновременно.

**
3. Перемещайте диск только по одной колышке за раз, не возвращаясь к началу и не выходя из конца. <- Это то, с чем я сейчас борюсь.
**

Следующий: START -> peg1 <-> peg2 <-> peg3 -> КОНЕЦ

#include <iostream>
#include <time.h>
using namespace std;
void move(int, int, int, int, int, int);
int i, j, l, n;
const int start = 1, end = 5, aux1 = 2, aux2 = 3, aux3 = 4;
int main(){
double time = 0;
clock_t begin, stop;
begin = clock();
for(n = 10; n>=1; n--){
l = 0, i = 0, j = 0;
move(n, start, end, aux1, aux2, aux3);
cout << "Number of disks moved: " << n << endl;
cout << "Number of moves made: " << l << endl;
}
stop = clock();
time = (stop - begin)/1000.00;
cout << "Game solved in: " << time << " miliseconds";
return 0;
}
void move(int n, int start, int end, int aux1, int aux2, int aux3){
if(n>0){
l++;
if(i>=100){
j++;
if(l - j == i){
move(n-1, start, aux1, aux2, aux3, end);
cout << "Move disc " << n << " from peg " << start << " to peg " << end << endl;
move(n-1, aux1, aux2, aux3, end, start);
}
}
if(i<=100){
i++;
move(n-1, start, aux1, aux2, aux3, end);
cout << "Move disc " << n << " from peg " << start << " to peg " << end << endl;
move(n-1, aux1, end, aux3, aux2, start);
}
}
}

Пример для 3 дисков, код ставит

Move disc 1 from peg 1 to peg 3
Move disc 2 from peg 1 to peg 2
Move disc 1 from peg 3 to peg 2
Move disc 3 from peg 1 to peg 5
Move disc 1 from peg 2 to peg 4
Move disc 2 from peg 2 to peg 5
Move disc 1 from peg 4 to peg 5
Number of disks moved: 3
Number of moves made: 7

Пример того, что мне нужно поставить алгоритм для 3 дисков:

Move disc 1 from peg 1 to peg 2
Move disc 1 from peg 2 to peg 3
Move disc 1 from peg 3 to peg 4
Move disc 2 from peg 1 to peg 2
Move disc 2 from peg 2 to peg 3
Move disc 1 from peg 4 to peg 3
Move disc 1 from peg 3 to peg 2
Move disc 2 from peg 3 to peg 4
Move disc 1 from peg 2 to peg 3
Move disc 1 from peg 3 to peg 4
Move disc 3 from peg 1 to peg 2
Move disc 3 from peg 2 to peg 3
Move disc 1 from peg 4 to peg 3
Move disc 1 from peg 3 to peg 2
Move disc 2 from peg 4 to peg 3
Move disc 1 from peg 2 to peg 3
Move disc 1 from peg 3 to peg 4
Move disc 2 from peg 3 to peg 2
Move disc 1 from peg 4 to peg 3
Move disc 1 from peg 3 to peg 2
Move disc 3 from peg 3 to peg 4
Move disc 3 from peg 4 to peg 5
Move disc 1 from peg 2 to peg 3
Move disc 1 from peg 3 to peg 4
Move disc 2 from peg 2 to peg 3
Move disc 1 from peg 4 to peg 3
Move disc 1 from peg 3 to peg 2
Move disc 2 from peg 3 to peg 4
Move disc 2 from peg 4 to peg 5
Move disc 1 from peg 2 to peg 3
Move disc 1 from peg 3 to peg 4
Move disc 1 from peg 4 to peg 5
Number of disks moved: 3
Number of moves made: 32

Я так растерялся, я понятия не имею, как сделать так, чтобы код не позволял диску пропускать привязку. Это, вероятно, смотрит мне прямо в лицо, но я не могу понять это.

Пожалуйста, не обращайте внимания на циклы for ‘i’ и ‘j’, они были сделаны так, что если результаты станут слишком большими, будут напечатаны первые 100 ходов и последние 100 ходов.

Спасибо!

0

Решение

В основном для каждого звонка вам необходимо выполнить следующие шаги:

  1. Переместите стопку дисков n-1 на 4-ую колышек (или 2-ую при движении назад)

  2. Переместите n-й диск в середину (3-й колышек)

  3. Переместите стек n-1 обратно во 2-ую колышек (то есть 4-й при движении назад)

  4. Переместить n-й диск к месту назначения

  5. Переместить стек n-1 к месту назначения

Таким образом, вам нужно 3 рекурсивных звонков без напоминания.

function hanoi5(n) {
let out = []
move(n, 0, 4)
console.log(out.length + " steps")
console.log(out.join("\n"))
function move(n, from, to) {
if (n == 1) {
let dir = from < to ? 1 : -1
for (let i = from; i != to; i += dir)
out.push("move disc 1 from peg " + (i+1) + " to peg " + (i+1+dir))
} else if (from < to) {
move(n - 1, from, 3)
for (let i = from; i < 2; i++)
out.push("move disc " + n + " from peg " + (i+1) + " to peg " + (i+2))
move(n - 1, 3, 1)
for (let i = 2; i < to; i++)
out.push("move disc " + n + " from peg " + (i+1) + " to peg " + (i+2))
move(n - 1, 1, to)
} else {
move(n - 1, 3, 1)
out.push("move disc " + n + " from peg 3 to peg 2")
move(n - 1, 1, 3)
out.push("move disc " + n + " from peg 2 to peg 1")
move(n - 1, 3, 1)
}
}
}

hanoi5(3)
0

Другие решения

Других решений пока нет …

Источник
По вопросам рекламы [email protected]
Web-Answers © 2024 Наверх