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

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

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

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 + ")";
	}
}

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

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

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

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;
	}
}

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

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]

Реализуйте следующие методы:

1. Добавление нового элемента в начало списка.
2. Удаление первого/последнего элемента.
3. Получение значения первого/последнего элемента.
4. Получение размера списка.
5. Получение значения i-го элемента списка.
6. Удаление i-го элемента списка.

С помощью получившегося двусвязного списка напишите решение задачи Иосифа Флавия (описание задачи см. в следующей статье на стр. 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>

Список занятий