====== Занятие I (весна 2014 г.) ======

Классы в языке Java могут быть шаблонными (generic), т.е. иметь типовые параметры. При создании объекта такого класса нужно указывать конкретные значения его типовых параметров.

Пример использования шаблонных классов: класс, предназначенный для хранения упорядоченной пары объектов

<code java>
public class TwoTuple<A,B> {
	public final A first;
	public final B second;
	public TwoTuple(A a, B b) { first = a; second = b; }
	public String toString() {
		return "(" + first + ", " + second + ")";
	}
}
</code>

Пример работы с этим классом:

<code java>
TwoTuple<Integer, String> tuple = new TwoTuple<Integer, String>(new Integer(10), "some text");
System.out.println(tuple.toString()); // напечатается (10, some text)
</code>

===== Задание. Часть 1 =====

Приведем одну из возможных реализаций двусвязного списка:

<code java>
public class MyLinkedList<E> {
	private static class Node<E>{
		E element = null;
		Node<E> next = null;
		Node<E> previous = null;
		
		Node (E element0){
			element = element0;
		}
	}
	
	private Node<E> head = null;
	private Node<E> tail = null;
	
	private int size = 0;
	
	public void addLast(E element){// добавляет новый элемент в конец списка
		Node<E> tmpNode = new Node<E>(element);
		if(tail == null){
			head = tmpNode;
			tail = head;
		} else{
			tail.next = tmpNode;
			tmpNode.previous = tail;
			tail = tmpNode;
		}
	}

	public String toString(){// "преобразует" список в строку
		if(head == null)
			return null;
		
		Node<E> tmpNode = head;
		String tmpString = "[" + tmpNode.element.toString();
		
		while (tmpNode != tail){
			tmpNode = tmpNode.next;
			tmpString = tmpString.concat(", " + tmpNode.element.toString());
		};
		tmpString = tmpString.concat("]");
		
		return tmpString;
	}
}
</code>

Пример использования:

<code java>
MyLinkedList<Integer> list = new MyLinkedList<Integer>();
for (int i = 0; i < 10; i++)
	list.addLast(new Integer(i));
System.out.println(list.toString());// напечатается [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
</code>

Реализуйте следующие методы:
  - Добавление нового элемента в начало списка.
  - Удаление первого/последнего элемента.
  - Получение значения первого/последнего элемента.
  - Получение размера списка.
  - Получение значения ''i''-го элемента списка.
  - Удаление ''i''-го элемента списка.


===== Задание. Часть 2 =====

С помощью получившегося двусвязного списка напишите решение задачи Иосифа Флавия (описание задачи см. в следующей [[http://home.gwu.edu/~maxal/josephus.pdf|статье]] на стр. 1).

==== Примеры для проверки работы программы ====

Далее считаем, что ''n'' - число человек, ''m'' - шаг считалки, <latex>J(n,m)</latex> - искомое значение.

  * <latex> J(n,2) = 1 + 2n - 2^{1+\lfloor \log_{2} n\rfloor};</latex>
  * <latex> J(10,5) = 3,\ \ J(10,7) = 9, \ \ J(10,10)=8;</latex>
  * <latex> J(12,7) = 12,\ \ J(13,9) = 11.</latex>



;#;
[[java:elective|Список занятий]]
;#;