Рассмотрим последовательность чисел x[0]
, x[1]
, ..., x[n-1]
, сгенерированных при помощи следующей формулы:
x[0]
= p,
x[i]
= (a * x[i-1]
* x[i-1]
+ b * x[i-1]
+ c) mod m, где 0 < i < n
Создайте из этих чисел Связный Список: List = x[0]
→ x[1]
→ ... → x[n-1]
.
Пусть k = x[n]
mod n. Если x[n]
< m / 2, то tail → next
пусть указывает на k-ый элемент. Иначе tail → next
= NULL. Установите согласно этому условию значение указателя tail → next
.
Рассмотрим пример: p = 1, a = 1, b = 1, c = 1, m = 100, n = 5. Здесь List = 1 → 3 → 13 → 83 → 73, x[n]
= 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 иначе.