29 янв. 2008 г.

Какова длина циклического массива ?

Подкинул давеча Павел Куракин интересное упражнение для хвоста:

Есть закольцованный массив целых чисел
→ x1 x2 x3 … xN →  x1 x2 x3 … xN → x1 x2 x3 … xN

или переформулировав по иному: на полоске бумаги написаны целые числа, концы этой полоски склеены в кольцо (но место склейки установить невозможно, как и невозможно держаться более, чем за одно место данного кольца или видеть его размеры)
Разрешённые операции:
  • Перемещение по массиву в любом направлении
  • Чтение и запись в исходный массив
  • Использовать свои переменные
Необходимо определить базовую длину массива в кольце (N), причём, по окончании массив должен иметь первоначальный вид.

Если описывать на java:
public final class CirculedList {

private final int[] array;

private int cursor;

public CirculedList(final int[] array) {
this.array = array;
}

public int getValue(){
return this.array[this.cursor];
}

public void setValue(final int value){
this.array[this.cursor] = value;
}

public void next(){
this.cursor++;
if (this.cursor >= this.array.length) this.cursor = 0;
}

public void prev(){
this.cursor--;
if (this.cursor < 0) this.cursor = this.array.length - 1;
}
}
Экземпляр класса был корректно создан массивом != null, и некоторое кол-во раз был вызван метод next()

Комментариев нет: