Ханойская башня: рекурсивный алгоритм

recursion towers-of-hanoi

156078 просмотра

25 ответа

Хотя у меня нет никаких проблем с пониманием рекурсии, я, кажется, не могу обернуться вокруг рекурсивного решения проблемы Ханойской башни. Вот код из Википедии :

procedure Hanoi(n: integer; source, dest, by: char);
Begin
    if (n=1) then
        writeln('Move the plate from ', source, ' to ', dest)
    else begin
        Hanoi(n-1, source, by, dest);
        writeln('Move the plate from ', source, ' to ', dest);
        Hanoi(n-1, by, dest, source);
    end;
End;

Я понимаю базовый случай и концепцию разбиения проблемы на более мелкие части, пока вы не сможете переместить один диск. Однако я не могу понять, как два рекурсивных вызова в неосновном случае работают вместе. Возможно, кто-то может мне помочь? Благодарю.

Автор: titaniumdecoy Источник Размещён: 12.11.2019 09:09

Ответы (25)


46 плюса

Решение

На самом деле, раздел, откуда вы взяли этот код, также предлагает объяснение:

Чтобы переместить n дисков из колышка A в колышек C:

  1. переместить n − 1 дисков из A в B. Это оставит диск #n один на колышке A
  2. переместить диск №n с А на С
  3. переместите n − 1 дисков из B в C, чтобы они находились на диске #n

Совершенно очевидно, что сначала нужно удалить n - 1 диск, чтобы получить доступ к n- му. И что вам нужно сначала переместить их на другую колышек, чем там, где вы хотите, чтобы появилась полная башня.

Код в вашем посте имеет три аргумента, помимо количества дисков: исходный , конечный и временный, между которыми можно хранить диски (где подходит каждый диск размером n - 1).

На самом деле рекурсия происходит дважды, там, один раз до writeln, один раз после. Тот, что перед writeln, переместит n - 1 диск на временную привязку, используя конечную привязку в качестве временного хранилища (аргументы в рекурсивном вызове расположены в другом порядке). После этого оставшийся диск будет перемещен к колышку назначения, и после этого вторая рекурсия заставит переместить всю башню, перемещая башню n - 1 от временной колышка к колышку назначения выше диска n.

Автор: Joey Размещён: 03.08.2009 04:40

31 плюса

год назад у меня был курс функционального программирования и я нарисовал эту иллюстрацию для алгоритма. Надеюсь, это поможет!

(0)  _|_         |          |
    __|__        |          |
   ___|___       |          |
  ____|____  ____|____  ____|____

(1.1) |          |          |
    __|__        |          |
   ___|___      _|_         |
  ____|____  ____|____  ____|____ (A -> B)

(1.2) |          |          |
      |          |          |
   ___|___      _|_       __|__
  ____|____  ____|____  ____|____ (A -> C)

(1.3) |          |          |
      |          |         _|_
   ___|___       |        __|__
  ____|____  ____|____  ____|____ (B -> C)



(2.1) |          |          |
      |          |         _|_
      |       ___|___     __|__
  ____|____  ____|____  ____|____ (A -> B)



(3.1) |          |          |
      |          |          |
     _|_      ___|___     __|__
  ____|____  ____|____  ____|____ (C -> A)

(3.2) |          |          |
      |        __|__        |
     _|_      ___|___       |
  ____|____  ____|____  ____|____ (C -> B)

(3.3) |         _|_         |
      |        __|__        |
      |       ___|___       |
  ____|____  ____|____  ____|____ (A -> B)

Задача о 3 кольцах была разбита на задачу о 2 кольцах (1.x и 3.x)

Автор: f0b0s Размещён: 03.08.2009 04:50

14 плюса

Хорошее объяснение рекурсивной реализации Ханоя можно найти по адресу http://www.cs.cmu.edu/~cburch/survey/recurse/hanoiimpl.html .

Итак, если вы хотите переместить нижнюю пластину с палки A на палочку B, вам сначала нужно переместить все меньшие пластины сверху нее с A на C. Второй рекурсивный вызов - переместить пластины, которые вы переместили на C обратно на B после того, как ваш базовый корпус переместил одну большую пластину с A на B.

Автор: matthock Размещён: 03.08.2009 04:43

13 плюса

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

Базовый случай: ваша башня имеет размер 1. Таким образом, вы можете сделать это за один ход, от источника напрямую к месту назначения.

Рекурсивный случай: ваша башня имеет размер n> 1. Таким образом, вы перемещаете верхнюю башню размера n-1 в дополнительный колышек (мимо), перемещаете нижнюю «башню» размера 1 к конечному колышку и перемещаете верхнюю башню от до до дест.

Итак, в простом случае у вас есть башня высотой 2:

 _|_    |     |
__|__   |     |
===== ===== =====

Первый шаг: переместите верхнюю башню 2-1 (= 1) на дополнительный колышек (средний, скажем так).

  |     |     |
__|__  _|_    |
===== ===== =====

Далее: переместить нижний диск к месту назначения:

  |     |     |
  |    _|_  __|__
===== ===== =====

И, наконец, переместите верхнюю башню (2-1) = 1 к месту назначения.

  |     |    _|_
  |     |   __|__
===== ===== =====

Если вы подумаете об этом, даже если в башне было 3 или более, всегда будет пустой дополнительный колышек или колышек со всеми более крупными дисками для рекурсии, которую можно использовать при смене башен вокруг.

Автор: Sean Размещён: 03.08.2009 04:41

4 плюса

Предположим, что мы хотим переместить диск с A на C через B, а затем:

  1. переместите меньший диск к B.
  2. переместить другой диск в C.
  3. переместить B в C.
  4. перейти от А до Б.
  5. переместить все из C в A.

Если вы повторите все вышеописанные шаги, диск перейдет.

Автор: Deeraj Kumar Choudhary Размещён: 28.11.2012 08:54

3 плюса

Я чувствую боль!

Хотя это старый пост, я думаю, что на самом деле нужно понять, что это не подход «переместить это к этому», а ответ заключается в использовании побочного эффекта рекурсии.

Неоценимую помощь мне оказал «Маленький интриган», который учит думать и писать рекурсивные функции.

Однако это учит читателя использовать результаты возвращенного результата в следующем рекурсивном вызове.

В Ханойской башне ответ не в возвращенном результате как таковом, а в наблюдении за возвращенным результатом.

Магия происходит в succesive из уточнению в функциональных параметрах.

Да, проблема действительно в трех частях:

  • перемещая меньшую башню к запасной опоре
  • перемещение последнего диска в место назначения
  • перемещая оставшуюся башню на запасной колышек к колышку назначения.

На схеме:

(define (th n a b c)
    (if (zero? n) 'done
        (begin
           (th (- n 1) a c b)
           (display (list a c))
           (newline)
           (th (- n 1) b a c))))
(th 5 'source 'spare 'destination)

Тем не менее, именно отображение параметров функции является решением проблемы и принципиально понимает структуру вызовов в виде двойного дерева.

Решение также передает мощь proof by inductionи теплый жар всем программистам, которые боролись с традиционными структурами управления.

Кстати, решить проблему вручную вполне удовлетворительно.

  • посчитать количество дисков
  • если даже, переместите первый диск в запасной колышек, сделайте следующий законный ход (не включая верхний диск). Затем переместите верхний диск к колышку назначения, сделайте следующий законный ход (nittd). Затем переместите верхний диск к исходному колышку, сделайте следующий законный ход (nittd) ...
  • если нечетно, переместите первый диск к колышку назначения, сделайте следующий законный ход (не включая верхний диск). Затем переместите верхний диск на запасную колышек, сделайте следующий законный ход (nittd). Затем переместите верхний диск к исходному колышку, сделайте следующий законный ход (nittd) ...

Лучше всего, если вы всегда держите верхний диск одной и той же рукой и всегда двигаете эту руку в одном направлении.

Окончательное количество ходов для nдисков находится на полпути через этот процесс.2^n - 1move n disc to destination

Наконец, забавно, как объяснение проблемы коллеге, вашей жене / мужу или даже собаке (даже если они ее не слушают) может укрепить просветление.

Автор: potong Размещён: 15.01.2014 09:01

2 плюса

Прочитав все эти объяснения, я подумал, что должен взвесить метод, который мой профессор использовал для объяснения рекурсивного решения Башен Ханоя. Здесь снова алгоритм с n, представляющим количество колец, и A, B, C, представляющим колышки. Первый параметр функции - это количество звонков, второй параметр представляет исходный колышек, третий - конечный, а четвертый - резервный.

procedure Hanoi(n, A, B, C);
  if n == 1
    move ring n from peg A to peg B
  else
    Hanoi(n-1, A, C, B);
    move ring n-1 from A to C
    Hanoi(n-1, C, B, A);
end;

В аспирантуре меня учили, чтобы никогда не было стыдно мыслить маленькими. Итак, давайте рассмотрим этот алгоритм для n = 5. Сначала задайте себе вопрос: хочу ли я переместить 5-е кольцо с А на В, где остальные 4 кольца? Если 5-е кольцо занимает колышек A, и мы хотим переместить его в колышек B, то остальные 4 кольца могут быть только на колышке C. В алгоритме выше функции Ханоя (n-1, A, C, B)пытается переместить все эти 4 других кольца на колышек C, поэтому кольцо 5 сможет переместиться из A в B. Следуя этому алгоритму, мы смотрим на n = 4. Если кольцо 4 будет перемещено из A в C, где кольца 3 и меньше? Они могут быть только на колышке B. Далее, для n = 3, если кольцо 3 будет перемещено из A в B, где находятся кольца 2 и 1? На привязке конечно. Если вы продолжите следовать этой схеме, вы можете визуализировать, что делает рекурсивный алгоритм. Этот подход отличается от подхода новичка тем, что он смотрит на последний диск первым, а первый диск последним.

Автор: MNRC Размещён: 07.02.2015 12:26

2 плюса

Думайте об этом как о стеке с диаметром дисков, представленным целыми числами (4,3,2,1). Первый вызов рекурсии будет вызван 3 раза и, таким образом, заполнит стек времени выполнения следующим образом.

  1. Первый звонок: 1. Второй звонок: 2,1. и третий звонок: 3,2,1.

После окончания первой рекурсии содержимое стека времени выполнения выталкивается на средний полюс от наибольшего диаметра к наименьшему (сначала в последнем из вышедших). Далее диск диаметром 4 перемещается к месту назначения.

Второй рекурсивный вызов такой же, как и первый, за исключением перемещения элементов от среднего полюса к месту назначения.

Автор: Ahmad Размещён: 18.06.2012 12:57

1 плюс

Первый рекурсивный вызов перемещает все части, кроме самой большой, из источника в, используя dest в качестве вспомогательной стопки. Когда все будет готово, все части, кроме самой большой, будут лежать, а самая большая будет бесплатной. Теперь вы можете переместить самую большую в dest и использовать другой рекурсивный вызов, чтобы переместить все фигуры из by в dest.

Рекурсивные вызовы не будут ничего знать о самой большой части (то есть они будут игнорировать ее), но это нормально, потому что рекурсивные вызовы будут иметь дело только с частями меньшего размера и, таким образом, могут свободно перемещаться на большую часть и выходить из нее.

Автор: sepp2k Размещён: 03.08.2009 04:43

1 плюс

Это просто. Предположим, вы хотите перейти от А к С

если есть только один диск, просто переместите его.

Если есть более одного диска, сделайте

  • переместить все диски (n-1 дисков), кроме нижнего от A до B
  • переместить нижний диск от А до С
  • переместите n-1 диски с первого шага с А на С

Имейте в виду, что при перемещении дисков n-1 nth вообще не будет проблемой (если он больше всех остальных)

Обратите внимание, что перемещение дисков n-1 повторяется с той же проблемой снова, пока n-1 = 1, и в этом случае вы будете первым, если (где вы должны просто переместить его).

Автор: Samuel Carrijo Размещён: 03.08.2009 04:47

1 плюс

Ответ на вопрос, откуда программа знает, что четное значение равно «src» - «aux», а нечетное - «src» - «dst» для начального хода, лежит в программе. Если вы сломаете кулачный ход с 4 дисками, то это будет выглядеть так:

hanoi(4, "src", "aux", "dst");
if (disc > 0) {
    hanoi(3, 'src', 'dst', 'aux');
        if (disc > 0) {
            hanoi(2, 'src', 'aux', 'dst');
                if (disc > 0) {
                    hanoi(1, 'src', 'dst', 'aux');
                        if (disc > 0) {
                            hanoi(0, 'src', 'aux', 'dst');
                                END
                        document.writeln("Move disc" + 1 + "from" + Src + "to" + Aux);
                        hanoi(0, 'aux', 'src', 'dst');
                                END
                        }

также первый ход с 4 дисками (даже) идет от Src до Aux.

Автор: dspkwa Размещён: 06.01.2013 11:58

1 плюс

Как предложили некоторые из наших друзей, я удалил два предыдущих ответа и собираюсь здесь.

Это дает вам четкое понимание.

Какой общий алгоритм ....

Алгоритм:

solve(n,s,i,d) //solve n discs from s to d, s-source i-intermediate d-destination
{
    if(n==0)return;
    solve(n-1,s,d,i); // solve n-1 discs from s to i Note:recursive call, not just move
    move from s to d; // after moving n-1 discs from s to d, a left disc in s is moved to d
    solve(n-1,i,s,d); // we have left n-1 disc in 'i', so bringing it to from i to d (recursive call)
}

вот рабочий пример Нажмите здесь

Автор: Vivek MVK Размещён: 05.05.2014 10:31

1 плюс

public static void hanoi(int number, String source, String aux, String dest)
{
    if (number == 1)
    {
        System.out.println(source + " - > "+dest);
    }
    else{
        hanoi(number -1, source, dest, aux);
        hanoi(1, source, aux, dest);
        hanoi(number -1, aux, source, dest);
    }
}
Автор: Rafael Amsili Размещён: 13.11.2014 05:57

1 плюс

void TOH(int n, int a, int b){
        /*Assuming a as source stack numbered as 1, b as spare stack numbered as 2 and  c as target stack numbered as 3. So once we know values of a and b, we can determine c as there sum is a constant number (3+2+1=)6.
       */
int c = 6-a-b;
if(n==1){
    cout<<"Move from "<<a<<" to "<<b<<"\n";
}
else{
    // Move n-1 disks from 1st to 2nd stack. As we are not allowed to move more than one disks at a time, we do it by recursion. Breaking the problem into a simpler problem.
    TOH(n-1, a, c);
    // Move the last alone disk from 1st to 3rd stack.
    TOH(1, a, b);
    // Put n-1 disks from 2nd to 3rd stack. As we are not allowed to move more than one disks at a time, we do it by recursion. Breaking the problem into a simpler problem.        
    TOH(n-1, c, b);
}
}
int main() {

TOH(2, 1, 3);
cout<<"FINISHED                        \n";
TOH(3, 1, 3);
cout<<"FINISHED                        \n";
TOH(4, 1, 3);
return 0;
}
Автор: Aditya Raj Размещён: 24.08.2015 04:37

1 плюс

Здесь идет объяснение. Посмотри на картинку ->

введите описание изображения здесь

Позвонив Movetower(3,a,b,c), вы намереваетесь переместить все 3 диска с башни Aна башню B. Так что последовательные звонки ->

1. Movetower(3,a,b,c)  // No Move needed
2. Movetower(2,a,c,b)  // No move needed
3. Movetower(1,a,b,c)  // Here is the time to move, move disc1 from a to b
4. Movetower(2,a,c,b)  // Returning to this call again, this is the time to move disc2 from a to c
5. Movetower(1,b,c,a)  // Again the time to move, this time disc1 from b to c
6. Movetower(3,a,b,c)  // Returning to this call again, this is the time to move disc3 from a to b
7. Movetower(2,c,b,a)  // Not the time to move
8. Movetower(1,c,a,b)  // Here is the time to move, move disc1 from c to a
9. Movetower(2,c,b,a)  // Returning to this call again, this is the time to move disc2 from c to b
10.Movetower(1,c,a,b)  // Here is the time to move, move disc1 from a to b

Надеюсь, это поможет :)

Для анимации: https://www.cs.cmu.edu/~cburch/survey/recurse/hanoiex.html

Автор: jbsu32 Размещён: 30.08.2016 05:20

1 плюс

Есть три башни, а именно башня источника, башня назначения и вспомогательная башня. В исходной башне есть все диски, и ваша цель - переместить все диски в башню назначения и убедиться, что вы никогда не поместите больший диск поверх меньшего диска. Мы можем решить эту проблему с помощью рекурсии в следующих шагах:

У нас есть n дисков на исходной башне

Базовый случай: n = 1 Если в исходной башне находится только один диск, переместите его в конечную башню.

Рекурсивный случай: n> 1

  • Переместите верхние диски n-1 от башни-источника к башне-помощнику.
  • Переместите единственный оставшийся, n-й диск (после шага 1) в вышку
  • Переместите диски n-1, которые сейчас находятся в вспомогательной башне, в целевую
    башню, используя исходную башню в качестве помощника.

Исходный код на Java:

private void towersOfHanoi(int n, char source, char destination, char helper) {
    //Base case, If there is only one disk move it direct from source to destination
    if(n==1){
        System.out.println("Move from "+source+" to "+destination);
    }
    else{
        //Step1: Move the top n-1 disks from source to helper
        towersOfHanoi(n-1, source, helper, destination);
        //Step2: Move the nth disk from source to destination
        System.out.println("Move from "+source+" to "+destination);
        /*Step3: Move the n-1 disks(those you moved from source to helper in step1) 
         * from helper to destination, using source(empty after step2) as helper
         */
        towersOfHanoi(n-1, helper, destination, source);
    }
}
Автор: bpjoshi Размещён: 08.03.2017 12:13

0 плюса

Будучи студентом CS, вы, возможно, слышали о математической индукции. Рекурсивное решение Ханойской башни работает аналогично - только другая часть состоит в том, чтобы по-настоящему не потеряться с В и С, как в случае с полной башней.

Автор: weismat Размещён: 03.08.2009 04:47

0 плюса

В простом смысле идея состоит в том, чтобы заполнить еще одну башню из трех определенных башен в том же порядке, что и присутствующие, без большего диска, перекрывающего маленький диск в любой момент во время процедуры.

Пусть «A», «B» и «C» - три башни. Первоначально буква «А» будет содержать «n» дисков. «B» можно использовать как промежуточную башню, а «C» - целевую башню.

Алгоритм выглядит следующим образом:

  1. Переместите n-1 диски из башни 'A' в 'B', используя 'C'
  2. Переместите диск с «А» на «С»
  3. Переместите n-1 диски из башни «B» в «C», используя «A»

Код следующий в Java:

открытый класс TowerOfHanoi {

public void TOH(int n, int A , int B , int C){
    if (n>0){
        TOH(n-1,A,C,B);
        System.out.println("Move a disk from tower "+A +" to tower " + C);
        TOH(n-1,B,A,C);
    }
}

public static void main(String[] args) {
    new TowerOfHanoi().TOH(3, 1, 2, 3);
}   

}

Автор: mohit verma Размещён: 08.10.2014 06:37

0 плюса

Вот мой код решения проблемы Towers of Hanoi с использованием рекурсии с golang. `основной пакет

import "fmt"

func main() {
    toi(4, "src", "dest", "swap")
}

func toi(n int, from, to, swap string) {
    if n == 0 {
        return
    }
    if n == 1 {
        fmt.Printf("mov %v %v -> %v\n", n, from, to)
        return
    }
    toi(n-1, from, swap, to)
    fmt.Printf("mov %v %v -> %v\n", n, from, to)
    toi(n-1, swap, to, from)
}`
Автор: Gaurav Sinha Размещён: 15.09.2017 10:13

0 плюса

Этот пример python3 использует рекурсивное решение:

# Hanoi towers puzzle
# for each n, you have to move n-1 disks off the n disk onto another peg
# then you move the n disk to a free peg
# then you move the n-1 disks on the other peg back onto the n disk

def hanoi(n):
    if n == 1:
        return 1
    else:
        return hanoi(n-1) + 1 + hanoi(n-1)


for i in range(1, 11):
    print(f"n={i}, moves={hanoi(i)}")

Выход:

n=1, moves=1
n=2, moves=3
n=3, moves=7
n=4, moves=15
n=5, moves=31
n=6, moves=63
n=7, moves=127
n=8, moves=255
n=9, moves=511
n=10, moves=1023

Но, конечно, самый эффективный способ определить, сколько ходов, это осознать, что ответы всегда 1 меньше 2 ^ n. Таким образом, математическое решение 2 ^ n - 1

Автор: Angus Comber Размещён: 22.12.2018 12:19

0 плюса

Только что посмотрел это видео сегодня: рекурсия «Super Power» (на Python) - Computerphile, и я думаю, что мы обязательно должны иметь здесь код профессора Торстена Альтенкирх, так как это очень красивый и элегантный фрагмент кода рекурсии, и не всегда у нас есть качество видео, чтобы показать в ответе.

def move(f,t) : 
    print("move disc from {} to {}!".format(f,t))

def hanoi(n,f,h,t) : 
    if n==0 : 
        pass
    else :
        hanoi(n-1,f,t,h)
        move(f,t)
        hanoi(n-1,h,f,t)

наша hanoiфункция имеет 4 параметра:

  • n: количество дисков
  • f: место происхождения дисков (от)
  • h: промежуточный шаг «через» (помощник)
  • t: конечная позиция, где мы хотим, чтобы диски были в конце (цель)
>>> hanoi(4,"A","B","C")
move disc from A to B!
move disc from A to C!
move disc from B to C!
move disc from A to B!
move disc from C to A!
move disc from C to B!
move disc from A to B!
move disc from A to C!
move disc from B to C!
move disc from B to A!
move disc from C to A!
move disc from B to C!
move disc from A to B!
move disc from A to C!
move disc from B to C!

введите описание изображения здесь

Автор: costargc Размещён: 06.10.2019 04:39

-1 плюса

Tower (N,source,aux.dest):

  1.  

    if N =1 Then
       Write : Source -> dest
       return
    end of if
    
  2. переместить диск N-1 из исходного источника в дополнительный

    call Tower (N-1, source, dest, aux)
    
  3. написать источник -> Dest
  4. переместить диски N-1 из peg aux в peg dest

    call Tower (N-1, source, dest, aux)
    
  5. вернуть
Автор: Muhammad Saleem Akhtar Размещён: 13.01.2011 03:00

-1 плюса

/ ** * * / package com.test.recursion;

/ ** * @author kamals1986 Рекурсивный алгоритм для задачи о Ханойской башне Алгоритм * растет по степени (2, n). * / публичный класс TowerOfHanoi {

private static String SOURCE_PEG = "B";

private static String SPARE_PEG = "C";

private static String TARGET_PEG = "A";

public void listSteps(int n, String source, String target, String spare) {
    if (n == 1) {
        System.out.println("Please move from Peg " + source + "\tTo Peg\t"
                + target);
    } else {
        listSteps(n - 1, source, spare, target);
        listSteps(1, source, target, spare);
        listSteps(n - 1, spare, target, source);
    }
}

public static void main(String[] args) {
    long startTime = System.currentTimeMillis();
    new TowerOfHanoi().listSteps(18, SOURCE_PEG, TARGET_PEG, SPARE_PEG);

    long endTime = System.currentTimeMillis();

    System.out.println("Done in " + (endTime - startTime) / 1000
            + "\t seconds");
}

}

Автор: kamals1986 Размещён: 17.05.2015 08:33

-1 плюса

def Hanoi(n, A, B, C):
    if(n==1): print "move plates to empty peg"
    else:
       Hanoi(n-1, A, B, C)
       print "move"+str(n)+" to peg "+C
       Hanoi(n-1, B, C, A)
Автор: Mick Lin Размещён: 14.10.2016 04:33

-2 плюса

Я тоже пытаюсь получить рекурсию.

Я нашел способ, я думаю,

я думаю об этом как о цепочке шагов (шаг не постоянен, он может меняться в зависимости от предыдущего узла)

Я должен выяснить 2 вещи:

  1. предыдущий узел
  2. вид шага
  3. после шага, что еще до вызова (это аргумент для следующего вызова

пример

факториал

1,2,6,24,120 ......... или

1,2 * (1), 3 * (2 * 1), 4 * (3 * 2 * 1,5 * (4 * 3 * 2 * 1)

шаг = кратно последнему узлу

после шага, что мне нужно, чтобы перейти к следующему узлу, аннотация 1

Хорошо

function =

n*f(n-1) 

its 2 steps process
from a-->to step--->b

Я надеялся, что это поможет, просто подумайте о 2 thnks, не как добраться от узла к узлу, но узел -> шаг -> узел

узел -> шаг - это тело функции step -> узел - это аргументы другой функции

пока :) надеюсь, я помог

Автор: user1885941 Размещён: 07.12.2012 04:03
Вопросы из категории :
32x32