Хэл Фултон - Программирование на языке Ruby

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

Так что если вас пугает конец света, можете успокоиться. Да и в любом случае для перемещения 64 дисков потребуется 2 64-1 ходов. Небольшой расчет на калькуляторе покажет, что монахи будут заняты своим делом несколько миллионов лет.

Однако вернемся к правилам игры. (Сформулируем их, хотя эту загадку знал уже самый первый студент самого первого факультета информатики.) Имеется шест, на который надето несколько дисков; назовем его исходным. Мы хотим переместить все диски на целевой шест, используя еще один вспомогательный шест как место промежуточного хранения. Проблема в том, что за один ход можно перемещать только один диск; при этом нельзя класть больший диск на меньший.

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

def towers(list)

while !list.empty?

n, src, dst, aux = list.pop

if n == 1

puts "Перемещаем диск с #{src} на #{dst}"

else

list.push [n-1, aux, dst, src]

list.push [1, src, dst, aux]

list.push [n-1, src, aux, dst]

end

end

end

list = []

list.push([3, "a", "c", "b"])

towers(list)

Вот что напечатает эта программа:

Перемещаем диск с а на с

Перемещаем диск с а на b

Перемещаем диск с с на b

Перемещаем диск с а на с

Перемещаем диск с b на а

Перемещаем диск с b на с

Перемещаем диск с а на с

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

def towers(n, src, dst, aux)

if n==1

puts "Перемещаем диск с #{src} на #{dst}"

else

towers(n-1, src, aux, dst)

towers(1, src, dst, aux)

towers(n-1, aux, dst, src)

end

end

towers(3, "а", "с", "b")

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

Мы определим очередь примерно так же, как стек. Если вы хотите защититься от некорректного доступа к структуре данных, рекомендуем поступать аналогично.

class Queue

def initialize

@store = []

end

def enqueue(x)

@store << x

end

def dequeue

@store,shift

end

def peek

@store.first

end

def length

@store.length

end

def empty?

@store.empty?

end

end

Отметим, что класс Queueимеется в библиотеке threadдля поддержки многопоточных программ. Имеется даже вариант SizedQueueдля организации очереди ограниченного размера.

В упомянутых классах методы имеют короткие имена: enqи deq. У них есть также синонимы pushи pop, что лично мне кажется неоправданным. Это структура данных FIFO, а не LIFO, то есть именно очередь, а не стек.

Разумеется, класс Queueв библиотеке thread.rbбезопасен относительно потоков. Если вы хотите реализовать такой же класс Stack, рекомендую взять Queueв качестве отправной точки. Потребуется внести не так много изменений.

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

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

Терминология, описывающая деревья, богата, но понять ее легко. Элементы дерева называются узлами ; верхний или самый первый узел называется корневым или корнем . У узла могут быть потомки , расположенные ниже него, а непосредственные потомки называются детьми или дочерними узлами . Узел, не имеющий потомков, называется листовым или просто листом. Поддерево состоит из некоторого узла и всех его потомков. Посещение всех узлов дерева (например, с целью распечатки) называется обходом дерева .

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

Отметим, что во многих языках, например в С или Pascal, деревья реализуются с помощью адресных указателей. Но в Ruby (как и в Java) указателей нет, вместо них используются ссылки на объекты, что ничуть не хуже, а иногда даже лучше.

Ruby позволяет реализовать двоичное дерево разными способами. Например, хранить значения узлов можно в массиве. Но мы применим более традиционный подход, характерный для кодирования на С, только указатели заменим ссылками на объекты.

Что нужно для описания двоичного дерева? Понятно, что в каждом узле должен быть атрибут для хранения данных. Кроме того, в каждом узле должны быть атрибуты для ссылки на левое и правое поддерево. Еще необходим способ вставить новый узел в дерево и получить хранящуюся в дереве информацию. Для этого нам потребуется два метода.

В первом дереве, которое мы рассмотрим, эти методы будут реализованы неортодоксальным способом. Позже мы расширим класс Tree.

В некотором смысле дерево определяется алгоритмом вставки и способом обхода. В нашем первом примере (листинг 9.1) метод insertбудет осуществлять поиск в дереве «в ширину», то есть сверху вниз и слева направо. При этом глубина дерева растет относительно медленно, и оно всегда оказывается сбалансированием. Методу вставки соответствует итератор traverse, который обходит дерево в том же порядке.

class Tree

attr_accessor :left

attr_accessor :right

attr_accessor :data

def initialize(x=nil)

@left = nil

@right = nil

@data = x

end