Рубрики

Программа для Ханойской Башни

Ханойская башня — это математическая головоломка, в которой три стержня и n дисков. Цель головоломки состоит в том, чтобы переместить весь стек к другому стержню, следуя следующим простым правилам:
1) Одновременно можно перемещать только один диск.
2) Каждый ход состоит в том, чтобы извлечь верхний диск из одного из стеков и поместить его поверх другого стека, т.е. диск можно перемещать только в том случае, если это самый верхний диск в стеке.
3) Запрещается размещать диск поверх меньшего диска.

Подходить :

Take an example for 2 disks :
Let rod 1 = 'A', rod 2 = 'B', rod 3 = 'C'.

Step 1 : Shift first disk from 'A' to 'B'.
Step 2 : Shift second disk from 'A' to 'C'.
Step 3 : Shift first disk from 'B' to 'C'.

The pattern here is :
Shift 'n-1' disks from 'A' to 'B'.
Shift last disk from 'A' to 'C'.
Shift 'n-1' disks from 'B' to 'C'.

Image illustration for 3 disks :

Примеры:

Input : 2
Output : Disk 1 moved from A to B
         Disk 2 moved from A to C
         Disk 1 moved from B to C

Input : 3
Output : Disk 1 moved from A to C
         Disk 2 moved from A to B
         Disk 1 moved from C to B
         Disk 3 moved from A to C
         Disk 1 moved from B to A
         Disk 2 moved from B to C
         Disk 1 moved from A to C

C ++

// C ++ рекурсивная функция для
// решить головоломку Ханойская башня
#include <bits/stdc++.h>

using namespace std;

  

void towerOfHanoi(int n, char from_rod,

                    char to_rod, char aux_rod) 

    if (n == 1) 

    

        cout << "Move disk 1 from rod " << from_rod << 

                            " to rod " << to_rod<<endl; 

        return

    

    towerOfHanoi(n - 1, from_rod, aux_rod, to_rod); 

    cout << "Move disk " << n << " from rod " << from_rod <<

                                " to rod " << to_rod << endl; 

    towerOfHanoi(n - 1, aux_rod, to_rod, from_rod); 

  
// Код драйвера

int main() 

    int n = 4; // Количество дисков

    towerOfHanoi(n, 'A', 'C', 'B'); // A, B и C - названия стержней

    return 0; 

  
// Это код, предоставленный rathbhupendra

С

#include <stdio.h>

  
// C рекурсивная функция для решения головоломки Ханойская башня

void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod)

{

    if (n == 1)

    {

        printf("\n Move disk 1 from rod %c to rod %c", from_rod, to_rod);

        return;

    }

    towerOfHanoi(n-1, from_rod, aux_rod, to_rod);

    printf("\n Move disk %d from rod %c to rod %c", n, from_rod, to_rod);

    towerOfHanoi(n-1, aux_rod, to_rod, from_rod);

}

  

int main()

{

    int n = 4; // Количество дисков

    towerOfHanoi(n, 'A', 'C', 'B');  // A, B и C - названия стержней

    return 0;

}

Джава

// Java рекурсивная программа для решения головоломки Ханойская башня

  

class GFG

{

    // Java рекурсивная функция для решения головоломки Ханойская башня

    static void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod)

    {

        if (n == 1)

        {

            System.out.println("Move disk 1 from rod " +  from_rod + " to rod " + to_rod);

            return;

        }

        towerOfHanoi(n-1, from_rod, aux_rod, to_rod);

        System.out.println("Move disk " + n + " from rod " +  from_rod + " to rod " + to_rod);

        towerOfHanoi(n-1, aux_rod, to_rod, from_rod);

    }

      

    // Метод драйвера

    public static void main(String args[])

    {

        int n = 4; // Количество дисков

        towerOfHanoi(n, 'A', 'C', 'B');  // A, B и C - названия стержней

    }

}

питон

# Рекурсивная функция Python для решения Ханойской башни

  

def TowerOfHanoi(n , from_rod, to_rod, aux_rod):

    if n == 1:

        print "Move disk 1 from rod",from_rod,"to rod",to_rod

        return

    TowerOfHanoi(n-1, from_rod, aux_rod, to_rod)

    print "Move disk",n,"from rod",from_rod,"to rod",to_rod

    TowerOfHanoi(n-1, aux_rod, to_rod, from_rod)

          
# Код драйвера

n = 4

TowerOfHanoi(n, 'A', 'C', 'B'

# A, C, B - название стержней

  
# Предоставлено Харшитом Агравалом

C #

// C # рекурсивная программа для решения
// пазл Ханойская башня

using System;

  

class geek

{

  

    // C # рекурсивная функция для решения

    // пазл Ханойская башня

    static void towerOfHanoi(int n, char from_rod, 

                             char to_rod, char aux_rod)

    {

        if (n == 1)

        {

            Console.WriteLine("Move disk 1 from rod " + from_rod 

                                           + " to rod " + to_rod);

            return;

        }

        towerOfHanoi(n-1, from_rod, aux_rod, to_rod);

        Console.WriteLine("Move disk " + n + " from rod " 

                          + from_rod + " to rod " + to_rod);

        towerOfHanoi(n-1, aux_rod, to_rod, from_rod);

    }

      

    // Метод драйвера

    public static void Main()

    {

        // Количество дисков

        int n = 4; 

          

        // A, B и C - названия стержней

        towerOfHanoi(n, 'A', 'C', 'B'); 

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php
// PHP-код для решения проблемы Ханойской башни.

  
// Рекурсивная функция для решения Ханойской башни

function towerOfHanoi($n, $from_rod, $to_rod, $aux_rod) {

      

    if ($n === 1) {

    echo ("Move disk 1 from rod $from_rod to rod $to_rod \n");

    return;

    

      

    towerOfHanoi($n-1, $from_rod, $aux_rod, $to_rod);

    echo ("Move disk $n from rod $from_rod to rod $to_rod \n");

    towerOfHanoi($n-1, $aux_rod, $to_rod, $from_rod);

  
}

  
// Код драйвера

  
// количество дисков

$n = 4;

  
// A, B и C - названия стержней

towerOfHanoi($n, 'A', 'C', 'B');

  
// Этот код предоставлен akash7981
?>

Выход:

 Move disk 1 from rod A to rod B
 Move disk 2 from rod A to rod C
 Move disk 1 from rod B to rod C
 Move disk 3 from rod A to rod B
 Move disk 1 from rod C to rod A
 Move disk 2 from rod C to rod B
 Move disk 1 from rod A to rod B
 Move disk 4 from rod A to rod C
 Move disk 1 from rod B to rod C
 Move disk 2 from rod B to rod A
 Move disk 1 from rod C to rod A
 Move disk 3 from rod B to rod C
 Move disk 1 from rod A to rod B
 Move disk 2 from rod A to rod C
 Move disk 1 from rod B to rod C

For n disks, total 2n – 1 moves are required.

Например: для 4 дисков требуется 2 4 — 1 = 15 ходов.

For n disks, total 2n-1 function calls are made.

Например: для 4 дисков выполняется 2 4-1 = 8 вызовов функций.
Статьи по Теме

Ссылки:
http://en.wikipedia.org/wiki/Tower_of_Hanoi

Эта статья предоставлена Rohit Thapliyal . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Программа для Ханойской Башни

0.00 (0%) 0 votes