Формулировка задачи о ханойских башнях:
Есть три стержня A, B, и C. На стержень A надето N дисков, наверху самый маленький, каждый следующий диск больше предыдущего, а внизу самый большой. На другие стержни дисков не надето.
Hеобходимо перенести диски со стержня A на стержень C, пользуясь стержнем B, как вспомогательным, так, чтобы диски на стержне C располагались в том же порядке, в каком они располагаются на диске A перед перемещением.
При перемещении, никогда нельзя класть больший диск на меньший, диски перекладываются по одному. В основе решения задачи и реализации ее в программе лежит рекурсивный метод. Для того, чтобы переложить всю пирамиду, надо сначала переложить все, что выше самого большого диска, с первого на вспомогательный стержень, потом переложить это самое большой диск с первого на третий стержень, а потом переложить оставшуюся пирамиду со второго на третий стержень, пользуясь первым стержнем, как вспомогательным.
Применение рекурсии при определении связного списка:
Рекурсивное определение списка элементов (пусть элементами будут числа)
(Список) ::= (элемент) | //нерекурсивная часть,
(Список)(запятая)(элемент) | //рекурсивная часть
(элемент)(запятая)(Список) //рекурсивная часть
Если есть некоторый список, то можно получить новый список,
приписав элемент слева или справа
Пример:
Список 23, 35, 74, 2, 11 - это
элемент 23 запятая Список 35, 74, 2, 11
Список 35, 74, 2, 11 – это
элемент 35 запятая Список 74, 2, 11
Список 74, 2, 11 – это
Элемент 74 запятая Список 2, 11
Список 2, 11 - это
элемент 2 запятая Список 11
Список 11 – это элемент, т.е. частный случай списка
Понятие списка. Объявление элемента списка:
Рекурсивные данные: связный список
Список -упорядоченная совокупность, состоящая из элементов.
Длина списка - число элементов, содержащихся в списке, список нулевой длины называется пустым списком. К списку применимы операции включения, исключения. Основные операции (методы) для списков: добавить элемент (новый элемент становится первым в списке)удалить элемент (удаляется первый элемент списка, второй станет первым)дополнительные методы удалить все элементы копировать список проверить равенство списков добавить элемент в конец списка; удалить элемент из конца списка добавить или удалить элемент получить элемент по его номеру изменить порядок элементов на упорядочить элементы обратный найти позицию данного элемента в упорядоченном списке
Добавление элемента
1. Создается новый элемент, задается ссылка на него, и заполняется
информационная часть. Поле связи (next) пустое, т.е. = null
2. Ссылка из головы копируется в поле next нового элемента (стрелка 3).
Теперь на первый элемент списка указывают два элемента: голова списка
и новый элемент (стрелки 1 и 3).
3. Ссылка на новый элемент копируется в поле next головы, так что next начинает "указывать" на новый элемент (появляется стрелка
2, стрелка 1 исчезает).
После этого новый элемент становится первым элементом списка:
Голова указывает на новый элемент, новый элемент – на старый первый,
далее – как было в исходном списке.
Текст программы:
Определяемкласс – Элементсписка. Дляуниверсальностиполеinf –
типаObject(Object – базовый тип длявсехобъектныхтипов)
public class ListEl { //ListElement – элементсписка
Objectinf; //информационнаячасть
ListElnext; //ссылка на следующийэлемент
ListEl( ) { next = null; inf = null; } //конструктор
ListEl (Object ob) { inf = ob; next = null; } //конструктор
Первыйконструкторсоздает "пустой" элемент – обессылки == null
Второйконструктор в ссылкуinfкопируетссылкунаобъект,
заданныйкакаргументконструктора
//добавить элемент ob к списку hd
public static void printMyList ( ListEl a ) { //печатьсписка
ListEl c = a.next; //с – текущийэлементсписка
while( c != null ) { // покаестьэлементы,
System.out.print( c.inf + " "); // напечататьинфо-часть с
c = c.next; // и перейти к следующему
}; System.out.println( ); // когдавсеэлементы
// напечатаны, перейти к новой
// строке
//классObjectсодержитметодtoString, благодаря
//которомуprintlnможетвывестиобъект. При
//необходимости toString переопределяется
public static void main(String[ ] args){
ListEl list=new ListEl (); //создали≪голову≫списка
for (int i=0; i<10; i++) //10 раздобавляем к списку
// поодномуэлементу,
addToList (list, Integer.toString( i * i ) ) ; //помещаявinf-часть
//квадратыцелыхчисел
printMyList( list ); //печатаемсозданныйсписок
}
}