Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Последние темы форума

Показать новые сообщения »

Почтовая рассылка

Подписчиков: 11853
Последний выпуск: 19.06.2015

период массива, повторяющаяся последовательность

75K
05 октября 2011 года
gluk-12
2 / / 05.10.2011
Господа, задача слушающая.
Мне даже немного стыдно, но увы - я не могу придумать решение.
Периодом массива 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. Получается каждый раз искать число целых делителей длинны массива?
В общем я путаюсь и реализовать не получается)
76K
06 октября 2011 года
Lasur
2 / / 06.10.2011
Код:
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;
    }
}


Первое что пришло в голову, так что скорее всего можно быстрее;
Если что непонятно по коду - спрашивай
75K
06 октября 2011 года
gluk-12
2 / / 05.10.2011
А можно поподробнее о !isSimilar(sub, Arrays.copyOfRange(array, k*sub.length, (k+1)*sub.length))) ? Интуитивно понимаю, что тут ссылка на метод, описанный ниже, но вот логика работы не ясна.
И как мне указать ссылку в public static int[] getCycle(int[] array) на уже существующий массив, заданный способом выше?
76K
06 октября 2011 года
Lasur
2 / / 06.10.2011
1)Метод IsSimilar получает два массива int -ов и проверяет на совпадение их поэлементно (я не проверяю их на совпадение длин, так как в конкретно моем примере длины его параметров всегда совпадают). Таким образом здесь
 
Код:
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;
я проверяю ляжет ли полученный мной массив в массив у которого мы ищем цикл сколько-то раз. Если в какой-то момент массивы не совпали - он не период, а значит я возвращая false.

2)Ты получил массив int[] а, теперь просто передай его в метод getCycle - получиш массив, который будет его периодом. Возьмеш длину .length массива - получиш длину периода.
 
Код:
ArrayCycle.getCycle(a).length
97K
16 августа 2016 года
qquser
1 / / 16.08.2016
Код:
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;
                }

            }
        }
    }

Знаете кого-то, кто может ответить? Поделитесь с ним ссылкой.

Ваш ответ

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог