Господа, задача слушающая.
Мне даже немного стыдно, но увы – я не могу придумать решение.
Периодом массива a=(a1, a2,…, an) называется такой его кратчайший подмассив b=(a1, a2,…, ak), что k делит n, а будучи записанным n/k раз подряд он в точности окажется равным a.
Например, у массива (1, 2, 1, 1, 2, 1, 1, 2, 1) длина периода равна 3, а сам период — (1, 2, 1),
задача по заданному массиву найти длину его периода.
Подскажите хотя бы алгоритм, как в заданном ниже вручную массиве, можно выявить последовательность и ее длину.
Код:
import java.util.Scanner;
public class Solution {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a = scan.nextInt();
}
}
}
Есть идея реализовать так :
Возьмем вот массив 121121121, В массиве ищем след. единицу, после 1ой и проверяем, идет ли после нее второй элемент ( =2). Если нет, то ищем следующую единицу и проверяем еще раз. Так же для проверки берем и 3ий элемент. Но проблема в том, что элементов последовательности, может быть в данном случае 1,2,3,6. Получается каждый раз искать число целых делителей длинны массива?
В общем я путаюсь и реализовать не получается)
Using the undocumented "Periodic" padding as the third argument of PadRight:
ClearAll[fpF, fpF2]
fpF = Block[{i = 1}, While[i < Length@# &&
PadRight[#[[;; i]], Length@#, "Periodic"] != #, i++]; i] &;
fpF2 = Block[{i = 1}, While[i < Length@# &&
PadRight[#[[;; i]], Length@#, "Periodic"] != #, i++]; {i, #[[;; i]]}] &;
Examples: Using tc from @ubpdqn’s answer:
tc = {{19, 6, 19, 6, 19, 6, 19, 6, 19, 6, 19, 6},
{73, 7, 4, 73, 7, 4, 73, 7, 4, 73, 7, 4, 73, 7},
{73, 7, 4, 7, 2, 6, 7, 2, 7, 73, 9, 17, 7, 7},
{6, 3, 6, 3, 3, 6, 3, 6, 3, 3, 6, 3, 6, 3, 3, 6, 3, 6, 3, 3},
{6, 1, 6, 2, 6, 3, 6, 1, 6, 2, 6, 3, 6, 1, 6, 2},
{1, 1, 1},
{1, 2, 1, 2, 1}};
fpF /@ tc
(* {2, 3, 14, 5, 6, 1, 2} *)
{#, ## & @@ fpF2@#} & /@ tc // Grid[#, Dividers -> All] &
(* or {#,fpF @ #, #[[;;fpF @ #]]}&/@tc //Grid *)
If a complete periodic pattern were sought, we could search for periods less than or equal to half the Length of the input list:
ClearAll[fpFa, fpFb]
fpFa = Block[{i = 1, n = Length@#}, While[i < 1 + n/2 &&
PadRight[#[[;; i]], n, "Periodic"] != #, i++]; i = If[i < 1 + n/2, i, n]] &;
fpFb = Block[{i = 1, n = Length@#}, While[i < 1 + n/2 &&
PadRight[#[[;; i]], n, "Periodic"] != #, i++]; i = If[i < 1 + n/2, i, n];
{i, #[[;; i]]}] &;
|
0 / 0 / 0 Регистрация: 02.01.2014 Сообщений: 11 |
|
|
1 |
|
Найти период сгенерированных определенным образом чисел06.03.2014, 21:07. Показов 10393. Ответов 19
Допустим я генерирую числа определенным способом(Митчелла и Мура, Линейный конгруэнтный метод и т.д).
0 |
|
294 / 265 / 48 Регистрация: 09.04.2013 Сообщений: 1,037 |
|
|
07.03.2014, 22:14 |
2 |
|
Примерный алгоритм: Саму проверку на повторы периода можно целиком позаимствовать из алгоритмов проверки равенства строк.
1 |
|
22 / 15 / 7 Регистрация: 27.10.2013 Сообщений: 95 |
|
|
08.03.2014, 23:10 |
3 |
|
Нужно вывести все числа, кроме тех, что относятся к повторяющимся? Каков критерий определения повторяющихся чисел? Могут по 2е цифры часто повторятся, по 3 и т.д. Повторяющиеся числа это самая длинная, из повторяющихся последовательностей чисел? Длина периода всегда одна и та же? Если немного уточните условия задачи, то выложу код на c#.
1 |
|
0 / 0 / 0 Регистрация: 02.01.2014 Сообщений: 11 |
|
|
10.03.2014, 22:48 [ТС] |
4 |
|
Нужно найти период последовательности псевдослучайных чисел.
0 |
|
294 / 265 / 48 Регистрация: 09.04.2013 Сообщений: 1,037 |
|
|
11.03.2014, 00:28 |
5 |
|
Xn=(a*Xn-1+c) mod(m);
-Как определить длину предпериода? a,c,m константы ? тогда из-за рекурсивности формулы получаем что для определения предпериода достаточно найти сам период, потом запустить генератор с начала и ждать любое число из периода, когда нашли – сделать шаг назад. Полученный порядковый номер числа и будет длинной пред периода.
-Как без запоминания всей последовательности найти период? – она ведь может быть гигантской А ведь и не надо её всю запоминать, нужно только найти период. Кстати, а не может ли быть математического описания когда появятся повторения ? Добавлено через 7 минут
2 |
|
831 / 639 / 101 Регистрация: 20.08.2013 Сообщений: 2,524 |
|
|
12.03.2014, 18:25 |
6 |
|
Допустим набор чисел сгенерирован линейным конгруэнтным методом. Тогда надо генерировать последовательность двумя счётчиками – один с единичным шагом, второй – с двойным. Когда получится одинаковое число, запомнить его и продолить генерировать до тех пор пока оно не повторится. Это позволяет найти период. Чтобы найти предпериод, начинаем генерировать сначала, но одним из счётчиков пролистываем начало, по длинне равное периоду, после чего считаем обоими счётчиками синхронно. Когда числа совпадут, предпериод найден.
1 |
|
Potanin 22 / 15 / 7 Регистрация: 27.10.2013 Сообщений: 95 |
||||
|
12.03.2014, 19:49 |
7 |
|||
|
Не уверен что правильно понял задания, но, если понял правильно, то этот алгоритм создает одну и ту же постоянно повторяющуюся последовательность чисел. То есть например 123123123123, тогда здесь периодом будет 123.
1 |
|
831 / 639 / 101 Регистрация: 20.08.2013 Сообщений: 2,524 |
|
|
14.03.2014, 11:46 |
8 |
|
Potanin, просто ужас…
0 |
|
294 / 265 / 48 Регистрация: 09.04.2013 Сообщений: 1,037 |
|
|
14.03.2014, 12:50 |
9 |
|
x = (a * x + c) * m; } Не умножить, а найти модуль от деления на m Не по теме: Про поиск в строке промолчу, ибо думаю что я недостаточно знаю этот ЯП, вдруг что-то не то подумаю… Но спинным мозгом чувствую что что-то не то
2 |
|
22 / 15 / 7 Регистрация: 27.10.2013 Сообщений: 95 |
|
|
14.03.2014, 16:02 |
10 |
|
Так тоже работает, хоть и поиздевался над алгоритмом)))) Если просто удвоенный счетчик использовать то могут быть проблемы с, например 11311341131134. Первые три цифры и последующие три может ошибочно посчитать за период. Если посмотреть удлиненную версию (для этого берется +10 но тут можно +1) то такой ошибки можно избежать.
1 |
|
831 / 639 / 101 Регистрация: 20.08.2013 Сообщений: 2,524 |
|
|
14.03.2014, 18:11 |
11 |
|
Так тоже работает, хоть и поиздевался над алгоритмом)))) Я не про сдвиг 10, а про саму реализацию. Использование строк подобным образом – это извращение.
Если просто удвоенный счетчик использовать то могут быть проблемы с, например 11311341131134. Я ответил на конкретный вопрос. Для всех последовательностей, где каждый последующий элемент определяется ровно одним предыдущим, этот способ верный, причём есть доказательство этого факта.
1 |
|
294 / 265 / 48 Регистрация: 09.04.2013 Сообщений: 1,037 |
|
|
16.03.2014, 02:21 |
12 |
|
) Если просто удвоенный счетчик использовать то могут быть проблемы с, например 11311341131134 У тебя изначально задание сохранять последовательность в одну и ту же строку без символов-разделителей или ты так сам себе выбрал? В обоих случаях это плохая задумка, тут нужно либо массив чисел, либо добавлять разделители между строковым представлением чисел.
0 |
|
22 / 15 / 7 Регистрация: 27.10.2013 Сообщений: 95 |
|
|
16.03.2014, 08:56 |
13 |
|
Последнее замечание не совсем понятно. В итоге выводятся сам период и его длина, а не вся строка. Или суть в том, что необходимо сохранить не последовательность цифр в str, а последовательность чисел, формирующих период? Тогда тут возникает проблема. Допустим у меня началась генерация и мы получаем: 1 2 3 4 5 (затем) 12 34 51 и какую тут последовательность чисел приписать к периоду во втором случае?
0 |
|
831 / 639 / 101 Регистрация: 20.08.2013 Сообщений: 2,524 |
|
|
16.03.2014, 12:40 |
14 |
|
Не надо вообще использовать строки.
0 |
|
294 / 265 / 48 Регистрация: 09.04.2013 Сообщений: 1,037 |
|
|
16.03.2014, 18:55 |
15 |
|
Последнее замечание не совсем понятно. Нужно работать с числами чтобы правильно находить период, а не цифрами в числах, поэтому и получается у вас, что “могут быть проблемы с, например 11311341131134”. Желательно отказаться от строк вообще и перейти на целочисленные массивы.
0 |
|
22 / 15 / 7 Регистрация: 27.10.2013 Сообщений: 95 |
|
|
16.03.2014, 19:18 |
16 |
|
Все еще не ясно как, если работать не с цифрами, а с числами, получать период целиком. В любом же случае, если, как я указывал выше, есть 1 2 3 4 5 и 12 34 51, чтобы во втором случае вычислить период необходимо от последнего числа отделить последнюю цифру. Или же соответствующие алгоритмы генерации чисел устроены таким образом, что данной проблемы не возникает?
0 |
|
831 / 639 / 101 Регистрация: 20.08.2013 Сообщений: 2,524 |
|
|
16.03.2014, 23:04 |
17 |
|
Или же соответствующие алгоритмы генерации чисел устроены таким образом, что данной проблемы не возникает? Нужно найти период в последовательности чисел, а не цифр.
1 |
|
22 / 15 / 7 Регистрация: 27.10.2013 Сообщений: 95 |
|
|
17.03.2014, 09:58 |
18 |
|
Но ведь по линейному конгруэнтному методу каждое последующее число больше предыдущего, в следствие чего повторение последовательности именно из чисел невозможно.
0 |
|
Qwertiy 831 / 639 / 101 Регистрация: 20.08.2013 Сообщений: 2,524 |
||||
|
17.03.2014, 13:26 |
19 |
|||
|
Но ведь по линейному конгруэнтному методу каждое последующее число больше предыдущего Неправда. Там же по модулю.
1 |
|
Potanin 22 / 15 / 7 Регистрация: 27.10.2013 Сообщений: 95 |
||||
|
17.03.2014, 13:54 |
20 |
|||
|
Неправда. Там же по модулю.
Не о том модуле подумал, разобрался, спасибо
0 |
|
IT_Exp Эксперт 87844 / 49110 / 22898 Регистрация: 17.06.2006 Сообщений: 92,604 |
17.03.2014, 13:54 |
|
20 |
Связь периода и бордера
| Теорема: |
|
Если у строки длины есть бордер длины , то у нее также имеется период длины . |
| Доказательство: |
|
Пусть дана строка . Напишем формально определение бордера длины строки : Сделаем замену : Получили определение периода длины . Но , значит у строки есть период длины . |
Свойства периода
| Теорема (о кратном периоде): |
|
Если у строки есть период длины , то у нее имеется также период длины , где . |
| Доказательство: |
|
Пусть длина строки равна , сама строка — . Доказательство будем вести индукцией по числу .
Утверждение доказано. |
Перед доказательством следующей теоремы проверим пару интуитивно понятных утверждений.
| Лемма (1): |
|
Пусть строка имеет периоды и , причём . Тогда суффикс и префикс длины имеют период . |
| Доказательство: |
|
Покажем истинность утверждения про префикс; с суффиксом доказательство аналогичное. Требуется показать: Исходя из того, что имеет период , выполнено Также имеет период и из ограничений на верно , поэтому |
| Лемма (2): |
|
Пусть строка имеет период , и существует подстрока такая, что и имеет период , где . Тогда имеет период . |
| Доказательство: |
|
Пусть , где . Требуется показать: . Зафиксируем и . Заметим, что поскольку , отрезок содержит по меньшей мере целых чисел, так что найдутся . С учётом можем написать [1]. Помимо того , а в таком случае верно и . Теперь воспользуемся следующим фактом: если строка имеет период , то (действительно, без ограничения общности можем сказать, что , и исходя из этого выстроить цепочку равенств ). В виду того, что имеет период , имеют место равенства и . Кроме того имеет период , потому верно . Тогда и . |
| Теорема (Фин и Вильф): |
|
Если у строки есть периоды и , где , то также является периодом этой строки. |
| Доказательство: |
|
Обозначим . Доказательство будем вести индукцией по . В случае видим что , что соответствует базе, в то время как при выполнено , так что .
|
См. также
- Основные определения, связанные со строками
Примечания
- ↑ Свойство сравнений (№8)
Источники информации
- Wikipedia — Substring
- Lothaire M. Algebraic Combinatorics on Words — Cambridge University Press, 2002. — с. 272. — ISBN 0-521-81220-8
Вот пример ответа на ваш вопрос с помощю php
$user_id = 57;
$array = [
['user_id' => 57, 'phone_code' => 104, 'date' => '2017-06-07 07:49:52'],
['user_id' => 43, 'phone_code' => 104, 'date' => '2017-06-07 08:57:41'],
['user_id' => 72, 'phone_code' => 104, 'date' => '2017-06-07 09:49:38'],
['user_id' => 57, 'phone_code' => 104, 'date' => '2017-06-07 11:08:34'],
['user_id' => 25, 'phone_code' => 104, 'date' => '2017-06-07 12:49:38'],
];
for($i=0;$i<count($array);$i++){
if($array[$i]['user_id'] == $user_id){
$phone_code = $array[$i]['phone_code'];
break;
}
}
$user_array = [];
for($i=0;$i<count($array);$i++){
if($array[$i]['phone_code'] == $phone_code && $array[$i]['user_id'] == $user_id && $array[$i+1]['user_id'] != $user_id){
$user_array[$i]['date'] = $array[$i]['date'].' - '.$array[$i+1]['date'];
}
}
print_r($user_array);
Но это не вариант, если у вас строки в таблице достигнут тысяч.
Для этого надоSQL запросом вывести только нужные строки.
Вот если тебе не составит труда создать вот такую таблицу то у тебя не будет проблем с выводом нужных строк.
CREATE TABLE `user_log` (
`id` int(11) NOT NULL,
`user_id` int(11) NOT NULL,
`prev_user_id` int(11) NOT NULL,
`phone_code` mediumint(9) DEFAULT NULL,
`date` datetime NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
INSERT INTO `user_log` (`id`, `user_id`, `prev_user_id`, `phone_code`, `date`) VALUES
(1853, 57, 52, 104, '2017-06-07 07:49:52'),
(1863, 43, 57, 104, '2017-06-07 08:57:41'),
(1866, 72, 43, 104, '2017-06-07 09:49:38'),
(1867, 57, 72, 104, '2017-06-07 11:08:34'),
(1868, 25, 57, 104, '2017-06-07 12:49:38');
И тут уже совсем простой запрос даст тебе то что нужно.
SELECT * FROM `user_log` WHERE `user_id` = 57 OR `prev_user_id` = 57;
И на последок для того что бы на больших количествах строк у тебя запрос не медлил можешь поставить на колонках user_id и prev_user_idиндексы.
