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();
}
}
}
период массива, повторяющаяся последовательность
Господа, задача слушающая.
Мне даже немного стыдно, но увы - я не могу придумать решение.
Периодом массива 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),
задача по заданному массиву найти длину его периода.
Подскажите хотя бы алгоритм, как в заданном ниже вручную массиве, можно выявить последовательность и ее длину.
Есть идея реализовать так :
Возьмем вот массив 121121121, В массиве ищем след. единицу, после 1ой и проверяем, идет ли после нее второй элемент ( =2). Если нет, то ищем следующую единицу и проверяем еще раз. Так же для проверки берем и 3ий элемент. Но проблема в том, что элементов последовательности, может быть в данном случае 1,2,3,6. Получается каждый раз искать число целых делителей длинны массива?
В общем я путаюсь и реализовать не получается)
Мне даже немного стыдно, но увы - я не могу придумать решение.
Периодом массива 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),
задача по заданному массиву найти длину его периода.
Подскажите хотя бы алгоритм, как в заданном ниже вручную массиве, можно выявить последовательность и ее длину.
Код:
Есть идея реализовать так :
Возьмем вот массив 121121121, В массиве ищем след. единицу, после 1ой и проверяем, идет ли после нее второй элемент ( =2). Если нет, то ищем следующую единицу и проверяем еще раз. Так же для проверки берем и 3ий элемент. Но проблема в том, что элементов последовательности, может быть в данном случае 1,2,3,6. Получается каждый раз искать число целых делителей длинны массива?
В общем я путаюсь и реализовать не получается)
Код:
import java.util.Arrays;
class ArrayCycle
{
public static int[] getCycle(int[] array)
{
for (int i=1; i<array.length-1; i++){
if (array.length%i!=0)
break;
int[] sub = Arrays.copyOfRange(array, 0, i);
if (check(array, sub))
return sub;
}
return array;
}
private static boolean check(int[] array, int[] sub)
{
if (array.length%sub.length!=0)
return false;
for (int k=1; k<array.length/sub.length; k++)
if (!isSimilar(sub, Arrays.copyOfRange(array, k*sub.length, (k+1)*sub.length)))
return false;
return true;
}
private static boolean isSimilar(int[] x, int[] y)
{
for (int i=0; i<x.length; i++)
if (x != y)
return false;
return true;
}
}
class ArrayCycle
{
public static int[] getCycle(int[] array)
{
for (int i=1; i<array.length-1; i++){
if (array.length%i!=0)
break;
int[] sub = Arrays.copyOfRange(array, 0, i);
if (check(array, sub))
return sub;
}
return array;
}
private static boolean check(int[] array, int[] sub)
{
if (array.length%sub.length!=0)
return false;
for (int k=1; k<array.length/sub.length; k++)
if (!isSimilar(sub, Arrays.copyOfRange(array, k*sub.length, (k+1)*sub.length)))
return false;
return true;
}
private static boolean isSimilar(int[] x, int[] y)
{
for (int i=0; i<x.length; i++)
if (x != y)
return false;
return true;
}
}
Первое что пришло в голову, так что скорее всего можно быстрее;
Если что непонятно по коду - спрашивай
А можно поподробнее о !isSimilar(sub, Arrays.copyOfRange(array, k*sub.length, (k+1)*sub.length))) ? Интуитивно понимаю, что тут ссылка на метод, описанный ниже, но вот логика работы не ясна.
И как мне указать ссылку в public static int[] getCycle(int[] array) на уже существующий массив, заданный способом выше?
И как мне указать ссылку в public static int[] getCycle(int[] array) на уже существующий массив, заданный способом выше?
1)Метод IsSimilar получает два массива int -ов и проверяет на совпадение их поэлементно (я не проверяю их на совпадение длин, так как в конкретно моем примере длины его параметров всегда совпадают). Таким образом здесь
я проверяю ляжет ли полученный мной массив в массив у которого мы ищем цикл сколько-то раз. Если в какой-то момент массивы не совпали - он не период, а значит я возвращая false.
2)Ты получил массив int[] а, теперь просто передай его в метод getCycle - получиш массив, который будет его периодом. Возьмеш длину .length массива - получиш длину периода.
Код:
for (int k=1; k<array.length/sub.length; k++)
if (!isSimilar(sub, Arrays.copyOfRange(array, k*sub.length, (k+1)*sub.length)))
return false;
if (!isSimilar(sub, Arrays.copyOfRange(array, k*sub.length, (k+1)*sub.length)))
return false;
2)Ты получил массив int[] а, теперь просто передай его в метод getCycle - получиш массив, который будет его периодом. Возьмеш длину .length массива - получиш длину периода.
Код:
ArrayCycle.getCycle(a).length
Код:
using System;
using System.Text.RegularExpressions;
class Program
{
static void Main(string[] args)
{
int n = 9;
string text = "1 2 1 1 2 1 1 2 1" + " ";
for (var i = 1; i <= n; i++)
{
var match = Regex.Match(text, @"(\d+\s){0," + i + "}").ToString();
if (string.IsNullOrEmpty(text.Replace(match, "")))
{
Console.WriteLine(i);
return;
}
}
}
}
using System.Text.RegularExpressions;
class Program
{
static void Main(string[] args)
{
int n = 9;
string text = "1 2 1 1 2 1 1 2 1" + " ";
for (var i = 1; i <= n; i++)
{
var match = Regex.Match(text, @"(\d+\s){0," + i + "}").ToString();
if (string.IsNullOrEmpty(text.Replace(match, "")))
{
Console.WriteLine(i);
return;
}
}
}
}