Цикл в связном списке
Цикл в связном списке
Рассмотрим последовательность чисел x0
, x1
, ..., xn-1
, сгенерированных при помощи следующей формулы:
x0
= p,
xi
= (a * xi-1
* xi-1
+ b * xi-1
+ c) mod m, где 0 < i < n
Создайте из этих чисел Связный Список: List = x0
→ x1
→ ... → xn-1
.
Пусть k = xn
mod n. Если xn
< m / 2, то tail → next
пусть указывает на k-ый элементt. Иначе tail → next
= NULL. Установите согласно этому условию значение указателя tail → next
.
Рассмотрим пример: p = 1, a = 1, b = 1, c = 1, m = 100, n = 5. Здесь List = 1 → 3 → 13 → 83 → 73, xn
= 3, поэтому k = 3 < 100 / 2 = m / 2 и tail → next
указывает на третий элемент, равный 83 (позиции элементов в Списке начинаются с 0).
Реализуйте метод hasCycle
, который определит имеется ли в Списке цикл.
Напишите код согласно следующего интерфейса:
class Node
{
public:
int data;
Node *next;
Node() : next(NULL) {};
Node(int data, Node *next = NULL) : data(data), next(next) {};
};
class List
{
public:
Node *head, *tail;
List() : head(NULL), tail(NULL) {};
void addToTail(int val); // Добавьте число val в конец Связного Списка
int hasCycle(void) // Вернуть 1 если список имеет цикл, иначе вернуть 0
};
Вы можете создавать (использовать) по необходимости дополнительные методы.
Входные данные
В одной строке заданы шесть чисел: p, a, b, c, m, n. Все числа целые в промежутке от 0 до 1000, m и n больше 0.
Выходные данные
Выведите 1, если Связный Список имеет цикл, и 0 иначе.
1 1 1 1 100 5
1