Комбінаторика: перестановки. Дано N чисел. Одержати всі можливі перестановки. Установлено, що кількість таких перестановок N!.

Нехай є числа 1, 2, 3, 4; тобто N= 4. Якщо повинні бути набори по 4 елементи, то може бути 4 різних набори з різними числами на першому місці:1***, 2***, 3***, 4***.

У трьох позиціях, що залишилися, число з першої позиції бути присутнім не може, тобто набір можливих чисел, що можуть бути в позиціях позначених “*” зменшився на один елемент. Так, для першого набору (1***) можливі такі набори: 12**, 13**, 14**. Далі аналогічно будуть отримані набори: 123*, 124*. І на сам кінець – 1234.

В наведеному розсуді було розглянуто роботу з першим елементом кожного наступного набору. Так само необхідно зробити зі всіма наборами. Програмний приклад 6.6 ілюструє наведений алгоритм.

{===== Програмний приклад 6.6 =====}

procedure perest(m:tm; beg,en:byte);

var

x,i:byte;

begin

if beg=en then

begin

for i:=1 to en do write(m[i]:4); writeln

end else

for i:= beg to en do

begin x:= m[i]; m[i]:=m[beg]; m[beg]:=x;

perest(m,beg+1,en)

end;

end;

Для випадку N = 3 буде 6 перестановок, для N = 4 – 24 перестановки (N!).

Ханойська вежа.Мається три стрижні start, middle, end. На початковому стрижні лежать три диски в порядку збільшення діаметра знизу нагору. Задача: перемістити всі диски на останній стрижень. Умова: перекладати можна по одному диску, більший диск не може лежати на меншому.

Передбачається, що диски перекладаються на кінцевий стрижень, при цьому середній стрижень служить проміжним стрижнем.

start – middle – end.

Якщо N = 1, умова останова, при якому диск із початкового диска переноситься на кінцевий start – end. Але такий випадок можливий, якщо N – 1диск лежать на середньому стрижні. Таким чином, на першому кроці N – 1 диск переносять на середній стрижень, кінцевий диск – на проміжний:

start – end– middle.

На другому кроці диск із початкового стрижня переносяться на кінцевий: start – end.

На третьому кроці N – 1 дисків із середнього переносяться на останній, перший – проміжний. middle – end– start.

У програмному прикладі 6.7 подано приклад програмування задачі «Ханойська вежа».

{===== Програмний приклад 6.7 =====}

start='start';

middl='middle';

en='end';

procedure hanoi(n:byte; s,m,e:string);

begin

if n = 1 then writeln(s,'->',e) else

begin

hanoi(n - 1,s,e,m);

writeln(s,'->',e);

hanoi(n - 1,m,s,e);

end; end;

Приклад роботи функції: при виклику hanoi(3,start,middl,en); що означає перекладання 3 дисків дасть 7 ходів, для 10 дисків буде 1023 ходів. Кількість ходів = 2ⁿ – 1.