Ханойская башня.

Головоломка придумана французским математиком Эдуардом Люка в 1883 году. Имеется пирамидка в виде колышка с насаженными на нее дисками разного размера.

Ханойская башня

На колышек А диски насажены по уменьшению размера снизу вверх. Колышки B и С сначала пустые. Требуется переложить все диски с колышка А на колышек С по следующему правилу. Разрешается перекладывать диск на другой колышек, если тот пустой или на колышке диск большего размера, можно класть только на больший диск. Нужно узнать сколько перемещений придется сделать для перемещения всех дисков.

Сразу бросается в глаза, что для хранения номеров (размеров) дисков нужно использувать стек - структуру данных, реализующую принцип LIFO - последний пришел, первый вышел. Для этого создадим класс Stack. В нем в качестве хранилища данных используем массив данных типа number. В классе Stack определим функции size, push, pop, peek, isEmpty типичные для стека. Функция fillStackA заполняет стек А числами, соответствующими размерам дисков. Функции fAB, fBA и т.д. осуществляют перенос верхнего элемента из стека А на стек В и так далее в соответствии с названием.

Проведя несколько экспериментов и переложив башни с разным количеством дисков можно заметить, что для четного количества колец выполняется рекурсивная последовательность перестановок А-В, А-С, В-С. Для нечетного количества дисков последовательность А-С, А-В, В-С. Направление перестановки осуществляется в соответствии с правилами, описанными выше. По окончании соответствующей тройки перестановок функция рекурсивно повторяется. Как только колышки А и В оказываются пустыми, завершаем выполнение функции.

В функции changePlaces закодированы описанные действия. Остальные операторы в главной функции интуитивно понятны.

Ханойская башня

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

function haoitower(){
class Stack{
    private storage: number[] = [];
    constructor(private capacity: number = Infinity){}
    
    size(): number {
        return this.storage.length;
    }
    
    push(item: number): void{
        if(this.size() === this.capacity){
        throw Error("Stack has reached max capacity");
    }
    this.storage.push(item);
    }
    
    pop(): number | undefined{
        return this.storage.pop();
    }

    peek(): number | undefined{
        return this.storage[this.size() - 1];
    }

    isEmpty(): boolean{
        return this.size() === 0 ? true : false;
    }
}



function fillStackA(sizeStack: number): void{
    while(sizeStack > 0){
        stackA.push(sizeStack--);
    }
}

function fAB(): void{
    let temp: number = stackA.pop();
    stackB.push(temp);
}

function fBA(): void{
    let temp: number = stackB.pop();
    stackA.push(temp);
}

function fAC(): void{
    let temp: number = stackA.pop();
    stackC.push(temp);
}

function fCA(): void{
    let temp: number = stackC.pop();
    stackA.push(temp);
}

function fBC(): void{
    let temp: number = stackB.pop();
    stackC.push(temp);
}

function fCB(): void{
    let temp: number = stackC.pop();
    stackB.push(temp);
}

function changePlaces(sizeStack: number): void{
    //А-В, А-С, В-С для четного количества колец
    //А-С, А-В, В-С для нечетного
    //направление перестановки зависит от величины колец
    if(sizeStack % 2 == 0){
        //если количество колец четное
        //A-B
        if ((stackA.isEmpty() && stackB.isEmpty()) || (stackA.isEmpty() && stackC.isEmpty())){
                return;
        } else {
            cntr++;
            if (!stackA.isEmpty() && ((stackB.isEmpty()) || (stackA.peek() < stackB.peek()))){
                fAB();
            } else {
                fBA();
            }
        }
        //A-C
        if ((stackA.isEmpty() && stackB.isEmpty()) || (stackA.isEmpty() && stackC.isEmpty())){
            return;
        } else {
            cntr++;
            if (!stackA.isEmpty() && ((stackC.isEmpty()) || (stackA.peek() < stackC.peek()))){
                fAC();
            } else {
                fCA();
            }
        }
        //B-C
        if ((stackA.isEmpty() && stackB.isEmpty()) || (stackA.isEmpty() && stackC.isEmpty())){
            return;
        } else {
            cntr++;
            if (!stackB.isEmpty() && ((stackC.isEmpty()) || (stackB.peek() < stackC.peek()))){
                fBC();
            } else {
                fCB();
            }
        }
    } else {
    //если количество колец нечетное
    //A-C
        if ((stackA.isEmpty() && stackB.isEmpty()) || (stackA.isEmpty() && stackC.isEmpty())){
            return;
        } else {
            cntr++;
            if (!stackA.isEmpty() && ((stackC.isEmpty()) || (stackA.peek() < stackC.peek()))){
                fAC();
            } else {
                fCA();
            }
        }
    //A-B
        if ((stackA.isEmpty() && stackB.isEmpty()) || (stackA.isEmpty() && stackC.isEmpty())){
            return;
        } else {
            cntr++;
            if (!stackA.isEmpty() && ((stackB.isEmpty()) || (stackA.peek() < stackB.peek()))){
                fAB();
            } else {
                fBA();
            }
        }
    //B-C
        if ((stackA.isEmpty() && stackB.isEmpty()) || (stackA.isEmpty() && stackC.isEmpty())){
            return;
        } else {
            cntr++;
            if (!stackB.isEmpty() && ((stackC.isEmpty()) || (stackB.peek() < stackC.peek()))){
                fBC();
            } else {
                fCB();
            }
        }
    }
    changePlaces(sizeStack);
}

let stackA = new Stack();
let stackB = new Stack();
let stackC = new Stack();
let sizeStack: number;
let cntr: number = 0;
sizeStack = Number((document.getElementById("input1") as HTMLInputElement).value);
fillStackA(sizeStack);
console.log(stackA);
changePlaces(sizeStack);
console.log("cntr = " + cntr);
(document.getElementById("input3") as HTMLInputElement).value = String(cntr);
}

Количество дисков в пирамиде:

Количество перестановок: