Question

С++ Ханойские башни Головоломка “Ханойские башни” состоит из трёх стержней, пронумерованных числами 1, 2, 3. На стержень 1 надета пирамидка из n дисков различного диаметра в порядке возрастания диаметра дисков, если рассматривать их сверху вниз. Диски можно перекладывать с одного стержня на другой по одному, при этом диск нельзя класть на диск меньшего диаметра. Необходимо переложить всю пирамидку со стержня 1 на стержень 3, используя стержень 2 как вспомогательный, за минимальное число перекладываний. Напишите функцию, которая решает головоломку: для данного числа дисков n печатает последовательность перекладываний в формате a b c, где a — номер перекладываемого диска, b — номер стержня, с которого снимается данный диск, c — номер стержня, на который надевается данный диск. Например, строка 1 2 3 означает перемещение диска номер 1 со стержня 2 на стержень 3. В одной строке печатается одна команда. Диски пронумерованы числами от 1 до n в порядке возрастания диаметров.

Answer 1

Ответ:

#include <iostream>

 

using namespace std;

 

void hanoi_towers(int quantity, int from, int to, int buf_peg)  //quantity-число колец, from-начальное положение колец(1-3),to-конечное положение колец(1-3)

{                               //buf_peg - промежуточный колышек(1-3)

   if (quantity != 0)

   {

       hanoi_towers(quantity-1, from, buf_peg, to);

 

       cout << from << " -> " << to << endl;

 

       hanoi_towers(quantity-1, buf_peg, to, from);

   }

}

 

int main()

{

       setlocale(LC_ALL,"rus");

   int start_peg, destination_peg, buffer_peg, plate_quantity;

   cout << "Номер первого столбика:" << endl;

   cin  >> start_peg;

   cout << "Номер конечного столбика:" << endl;

   cin  >> destination_peg;

   cout << "Номер промежуточного столбика:" << endl;

   cin  >> buffer_peg;

   cout << "Количество дисков:" << endl;

   cin  >> plate_quantity;

 

   hanoi_towers(plate_quantity, start_peg, destination_peg, buffer_peg);

return 0;

}

Объяснение:

Answer 2

Классическая задача о Ханойских башнях решается с использованием рекурсии. Вот пример решения на C++:

cppCopy code
#include <iostream>

void moveDisk(int disk, int source, int destination) {
    std::cout << disk << " " << source << " " << destination << std::endl;
}

void hanoi(int n, int source, int auxiliary, int destination) {
    if (n == 1) {
        moveDisk(n, source, destination);
    } else {
        hanoi(n - 1, source, destination, auxiliary);
        moveDisk(n, source, destination);
        hanoi(n - 1, auxiliary, source, destination);
    }
}

int main() {
    int n;
    std::cout << "Введите количество дисков: ";
    std::cin >> n;
    std::cout << "Последовательность перекладываний:" << std::endl;
    hanoi(n, 1, 2, 3);
    return 0;
}

В этом коде hanoi - это рекурсивная функция, которая перемещает n дисков с исходного стержня (source) на конечный стержень (destination), используя вспомогательный стержень (auxiliary). Функция moveDisk используется для печати перемещения диска из одного стержня на другой. Когда n становится равным 1, функция hanoi просто перемещает один диск с исходного стержня на конечный стержень. Рекурсия используется для решения подзадач с меньшим числом дисков.