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

Программирование на языке Ruby

на обложку

Фултон Хэл

Шрифт:

Так что если вас пугает конец света, можете успокоиться. Да и в любом случае для перемещения 64 дисков потребуется 264– 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

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

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

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

9.2.4. Более строгая реализация очереди

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

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

Отметим, что класс

Queue

имеется в библиотеке

thread

для поддержки многопоточных программ. Имеется даже вариант

SizedQueue

для организации очереди ограниченного размера.

В упомянутых классах методы имеют короткие имена:

enq

deq

. У них есть также синонимы

push

pop

, что лично мне кажется неоправданным. Это структура данных FIFO, а не LIFO, то есть именно очередь, а не стек.

Разумеется, класс

Queue

в библиотеке

thread.rb

безопасен относительно потоков. Если вы хотите реализовать такой же класс

Stack

, рекомендую взять

Queue

в качестве отправной точки. Потребуется внести не так много изменений.

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

9.3. Деревья

Я не увижу никогда, наверное, Поэму столь прекрасную как дерево. Джойс Килмер, «Деревья» [11]

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

Пер. Я. Фельдмана. — Прим. ред.

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