Объектно-ориентированное программирование.Язык Смолток

         

Рекурсия


Рекурсия

Рекурсия - это основной механизм программирования итерационных конструкций языка Смолток. Рассмотрим реализацию метода Fibo класса Integer.

-- Фибоначчи

-- выдать N число Фибоноччи, где N - объект-адресат

-- Числа Фибоначчи задаются следующей последовательностью:

-- x1=1, x2=1, xi=xi-1+xi-2

Fibo

self<3          ifTrue: [ ^1 ]

ifFalse: [ ^ (self - 1) Fibo + (self - 2) Fibo ]

Теперь можно выполнить следующее выражение:

#(1 2 3 4 5 6 7 10 20) собрать: [ :m| m Fibo ]

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

Постановка задачи. Имеется 3 штырька, на штырьке #1 расположены кольца разного диаметра в порядке убывания их размера снизу вверх. Требуется переложить кольца со штырька #1 на штырек #2, пользуясь штырьком #3 как промежуточным, таким образом, чтобы кольца на штырьке #2 располагались в порядке убывания их диаметра и чтобы в процессе перекладывания кольцо большего диаметра никогда не накладывалось на кольцо меньшего диаметра.

1 Этап. Спецификация метода

a)     объект-адресат - это целое число (количество колец). Следовательно, данный метод будет принадлежать классу целых чисел.

b)    объекты-параметры - символы '1', '2', '3' (информация: с какого штырька на какой нужно переложить кольцо и какой использовать как дополнительный)



c)     результат - вывод на экран информации о последовательности выполнения данной задачи.

Следовательно, вызов метода будет осуществляться следующим образом:

10 ханойC: '1' на: '2' через: '3'

2 Этап. Реализация метода ханойС: x на: y через: z.

Данная задача решается рекурсивно.

a)     Базис. Если число колес равно 1, то нужно просто переложить это кольцо c х на y.

b)    Если число колес равно К, то нужно переложить со штырька х на штырек z K-1 колец, а затем переложить самое большое K-е кольцо на y и переложить все остальные K-1 колец на y.


ханойС: x на: y через: z

"головоломка 'Ханойские башни'"

self := 1

ifTrue: [ СистемнаяИнформация поместитьВсеПоследующие:

'Переложить со штырька ',x,' на штырек ',y;

символВК. ]

ifFalse: [ (self - 1) ханойС: x на: z через: y.

СистемнаяИнформация поместитьВсеПоследующие:

'Переложить со штырька ',x,' на штырек ',y;

символВК.

(self - 1) ханойС: z на: y через: x ]

Теперь можно добавить полученный метод в класс Integer (Целое) и выполнить программу для числа колец, равного, например, 10:

10 ханойС: '1' на: '2' через: '3'

Реализация этого метода в системе Smalltalk Express выглядит следующим образом:

hanoiFrom: x to: y by: z result: aStream

"головоломка 'Ханойские башни'"

self == 1

ifTrue: [ 'Переложить со штырька ' printOn: aStream.

x printOn: aStream.

'на штырек ' printOn: aStream.

y printOn: aStream.

(10 asCharacter) printOn: aStream.]

ifFalse: [ (self - 1) hanoiFrom: x to: z by: y result: aStream.

'Переложить со штырька ' printOn: aStream.

x printOn: aStream.

'на штырек ' printOn: aStream.

y printOn: aStream.

(10 asCharacter) printOn: aStream.

(self - 1) hanoiFrom: z to: y by: x result: aStream.]

Пример работы (пункт Show – "Показать"):

|aStream|

aStream := WriteStream on: String new.

10 hanoiFrom: 1 to: 2 by: 3 result: aStream.

aStream contents.

И, для полноты картины, приведем пример этой программы на языке Паскаль:

Program Han;

const Step : integer = 0; {Глобальный счетчик итераций - шагов}

procedure Hanoi(N : integer; X, Y, Z : char);

{ X-откуда, Y-куда, Z-через}

begin

if N=1 then

begin

                                Step:= Step +1;

                                writeln(Step:3,' Переложить со штырька ',X,' на штырек ',Y);

end

else

begin

                                Hanoi(N-1, X,Z,Y);

                                Step:= Step +1;

                                writeln(Step:3,' Переложить со штырька ',X,' на штырек ',Y);

                                Hanoi(N-1, Z,Y,X);

end;

end;

var N : integer;

begin

                writeln;

                writeln('ХАНОЙСКИЕ БАШНИ');

                writeln;

                write('Введите число колец: ');

                readln(N);

                Hanoi(N,'A','B','C');

end.


Содержание раздела