Алгоритм O (nlogn) - Найти три равномерно расположенных в двоичной строке

У меня вчера был этот вопрос на тесте Алгоритмов, и я не могу найти ответ. Это сводит меня с ума, потому что это стоило около 40 баллов. Я полагаю, что большинство класса не решило это правильно, потому что я не придумал решение за последние 24 часа.

Для произвольной двоичной строки длины n найдите три равномерно расположенные строки, если они существуют. Напишите алгоритм, который решает это за O (n * log (n)) время.

Таким образом, у строк, подобных этим, есть три "равномерно распределенных": 11100000, 0100100100.

редактировать: это случайное число, поэтому оно должно быть в состоянии работать для любого числа. Примеры, которые я привел, должны были проиллюстрировать «равномерно распределенное» свойство. Таким образом, 1001011 является действительным числом. С 1, 4 и 7 равными интервалами.

13.10.2009 14:15:32
Возможно ли следующее: 10011010000? У него есть три 1 (первая, вторая, четвертая), равномерно распределенные, но есть и дополнительные 1.
Anna 13.10.2009 14:27:02
Роберт, вам нужно, чтобы ваш профессор дал вам ответ на этот вопрос и разместил его здесь. Эта проблема толкает меня вверх по стене. Я могу понять, как это сделать в n ^ 2, но не в n * log (n).
James McMahon 14.10.2009 01:29:48
Хм, я тоже долго пытался это выяснить, пока не нашел хорошего ответа. Возможно, вы неправильно поняли вопрос? Например, если задается вопрос, найдите алгоритм, который выполняется в O (n log n), который определяет положение равномерно разнесенной последовательности интервалов k в гораздо большей последовательности, это можно легко сделать с помощью быстрого преобразования Фурье.
ldog 14.10.2009 02:47:49
если ваш проф дает решение, пожалуйста, опубликуйте его как ответ.
ldog 14.10.2009 02:49:14
Учитывая тот факт, что Клаус Рот получил Медаль Филдса 1958 года за (среди прочего) доказательство того, что для каждой плотности d> 0 существует натуральное число N, такое, что каждое подмножество {1, ..., N} по крайней мере с d * N элементов содержит арифметическую прогрессию длины 3, я не удивлен, что до сих пор никто не нашел убедительный алгоритм для задачи еще. Смотрите также en.wikipedia.org/wiki/Szemer%C3%A9di%27s_theorem
j.p. 16.10.2009 20:56:28
30 ОТВЕТОВ
РЕШЕНИЕ

В заключение! Следуя указаниям в ответе sdcvvc , мы имеем его: алгоритм O (n log n) для задачи! Это тоже просто после того, как вы это поймете. Те, кто догадался, БПФ были правы.

Проблема: нам дана двоичная строка Sдлины n , и мы хотим найти в ней три равномерно распределенные единицы. Например, Sможет быть 110110010, где n = 9. Оно равномерно расположено на 1 с в позициях 2, 5 и 8.

  1. Сканируйте Sслева направо и составьте список Lпозиций из 1. Для S=110110010вышеизложенного у нас есть список L = [1, 2, 4, 5, 8]. Этот шаг O (n). Теперь задача состоит в том, чтобы найти арифметическую прогрессию длины 3 в L, то есть найти отличные a, b, c в Lтаких, что ba = cb или, что эквивалентно, a + c = 2b . Для приведенного выше примера мы хотим найти прогрессию (2, 5, 8).

  2. Сделайте многочлен p с членами x k для каждого k в L. Для приведенного выше примера мы сделаем многочлен p (x) = (x + x 2 + x 4 + x 5 + x 8 ) . Этот шаг O (n).

  3. Найдите многочлен q= p 2 , используя быстрое преобразование Фурье . Для приведенного выше примера мы получаем полином q (x) = x 16 + 2x 13 + 2x 12 + 3x 10 + 4x 9 + x 8 + 2x 7 + 4x 6 + 2x 5 + x 4 + 2x 3 + x 2 . Этот шаг O (n log n).

  4. Игнорировать все слагаемые, кроме тех, которые соответствуют x 2k для некоторого k в L. Для приведенного выше примера мы получаем термины x 16 , 3x 10 , x 8 , x 4 , x 2 . Этот шаг O (n), если вы решите сделать это вообще.

Вот ключевой момент: коэффициент любого x 2b для b in L- это как раз количество пар (a, c) в Lтаких, что a + c = 2b . [CLRS, Ex. 30.1-7] Одна такая пара всегда (b, b) (поэтому коэффициент равен по крайней мере 1), но если существует какая-либо другая пара (a, c) , то коэффициент равен по крайней мере 3 из (a, c) ) и (с, а) . Для приведенного выше примера мы имеем коэффициент х 10, равный 3 именно из-за AP (2,5,8). (Эти коэффициенты х 2bвсегда будет нечетным числом по причинам, указанным выше. И все остальные коэффициенты в q всегда будут четными.)

Итак, алгоритм должен посмотреть на коэффициенты этих слагаемых x 2b и посмотреть, больше ли какой-либо из них, чем 1. Если их нет, то нет равномерно распределенных 1. Если это б в , Lдля которых коэффициент х больше 1, то мы знаем , что есть некоторая пара (а, с) - кроме (Ь, Ь) - для которых а + с = 2b . Чтобы найти фактическую пару, мы просто пробуем каждый a in L(соответствующий c будет 2b-a ) и видим, есть ли 1 в позиции 2b-a in S. Этот шаг O (n).

Вот и все, ребята.


Кто-то может спросить: нужно ли нам использовать БПФ? Многие ответы, такие как бета , flybywire и rsp , предполагают, что подход, который проверяет каждую пару из 1 и видит, есть ли 1 в «третьей» позиции, может работать в O (n log n), основываясь на интуиции что если слишком много единиц, мы легко найдем тройку, а если слишком мало единиц, проверка всех пар займет немного времени. К сожалению, в то время как эта интуиция является правильной и простым подходом является лучше , чем O (N 2 ), не намного лучше. Как и в ответе sdcvvc , мы можем взять «канторовоподобное множество» строк длиной n = 3 kс 1s в позициях, в которых в тройном представлении есть только 0s и 2s (no 1s). Такая строка имеет 2 k = n (log 2) / (log 3) ≈ n 0,63 единицы и не имеет равномерно распределенных 1 с, поэтому проверка всех пар будет порядка квадрата числа 1 с: 4 k ≈ n 1,26, что, к сожалению, асимптотически намного больше, чем (n log n). На самом деле, худший случай еще хуже: Лео Мозер в 1953 году построил (эффективно) такие строки, в которых n 1-c / √ (log n) 1s, но нет равномерно распределенных 1s, что означает, что на таких строках простая подход занял бы n (n 2-2c / √ (log n) )- только крошечное немного лучше , чем Q (п 2 ) , удивительно!


О максимальном числе 1 с в строке длины n без 3 равномерно распределенных (как мы видели выше, было не менее n 0,63 от простой конструкции типа Кантора и не менее n 1-c / √ (log n) с Конструкция Мозера) - это OEIS A003002 . Его также можно рассчитать непосредственно из OEIS A065825 как k, так что A065825 (k) ≤ n <A065825 (k + 1). Я написал программу, чтобы найти их, и оказалось, что жадный алгоритм не дает самую длинную такую ​​строку. Например, для n = 9 мы можем получить 5 1 с (110100011), но жадный дает только 4 (110110000), для n= 26 можно получить 11 1s (11001010001000010110001101) , но жадный дает только 8 (+11011000011011000000000000), а для п = 74 , мы можем получить 22 1s (11000010110001000001011010001000000000000000010001011010000010001101000011) , но жадный дает только 16 (11011000011011000000000000011011000011011000000000000000000000000000000000). Они соглашаются в довольно многих местах до 50 (например, все от 38 до 50), хотя. Как говорится в ссылках OEIS, кажется, что Ярослав Вроблевский заинтересован в этом вопросе, и он поддерживает веб-сайт об этих не усредняющих наборах . Точные цифры известны только до 194 года.

127
23.05.2017 12:26:29
Очень хорошо. Впечатляет. Кажется, немного ожидая, что кто-то придумает это в тесте.
hughdbrown 18.10.2009 20:15:07
Ну, шаг 1, перевод проблемы в поиске точки доступа, прост. Шаг 3, что многочлены могут быть умножены за O (n log n) времени, это просто факт. Реальный трюк и то, что делает проблему трудной, это идея думать о 11011 как о многочлене с коэффициентами [1,1,0,1,1] и т. Д. Это умная и часто полезная идея, которая охватывает все путь обратно в Эйлер. [См. Удивительную книгу Уилфа « Генерирование функциональности » для современной экспозиции: math.upenn.edu/~wilf/DownldGF.html ]. Это зависит от того, подвергались ли учащиеся генерации функций в недавней памяти или нет. :-)
ShreevatsaR 19.10.2009 15:33:22
Извините, мой расчет совершенно неверен. Это должно быть 110110010 ^ 2 = 12124214302200100. Но идея стоит. Просто обратите внимание на положение 3.
Guillermo Phillips 19.10.2009 18:28:17
Очень впечатляюще. Это действительно круто видеть, что эта тема / вопрос собрались вместе и нашли решение. Я начинал думать, что это невозможно. Также этот профессор злой.
KingNestor 19.10.2009 19:45:13
@RexE: Если p имеет степень n-1 (имеет n членов), q = p ^ 2 имеет степень 2n-2 (имеет не более 2n-1 членов). Как ты получил n ^ 2? (Кроме того, умножение двух полиномов степени n за время O (n log n) с использованием БПФ является довольно стандартной операцией; пожалуйста, нажмите на ссылку в ответе или посмотрите статью в Википедии .)
ShreevatsaR 8.10.2010 07:36:29

Адаптация алгоритма Рабина-Карпа может быть возможной для вас. Его сложность равна 0 (n), поэтому он может вам помочь.

Посмотрите http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm

-2
13.10.2009 15:26:20
Рабин-Карп использует хеширование строк, чтобы найти точные подстроки, поэтому это не может помочь с проблемой.
Robert Parker 13.10.2009 15:48:51

Я подозреваю, что простой подход, который выглядит как O (n ^ 2), на самом деле даст что-то лучше, например, O (n ln (n)). Последовательности, требующие наибольшего времени для тестирования (для любого заданного n), - это те, которые не содержат трио, и это накладывает серьезные ограничения на число единиц, которые могут быть в последовательности.

Я выдвинул некоторые аргументы, размахивающие руками, но я не смог найти опрятного доказательства. Я собираюсь сделать удар в темноте: ответ - очень умная идея, которую профессор знал так долго, что это кажется очевидным, но это слишком сложно для студентов. (Или это, или вы проспали лекцию, которая покрывала это.)

6
13.10.2009 17:45:34
лол, нет, я не спала ни на каких лекциях. Я разговаривал с несколькими другими студентами, и никто не имел четкого представления о том, как ее решить. Большинство из них написали несколько слов о «разделяй и властвуй», чтобы получить частичный кредит.
Robert Parker 13.10.2009 19:05:11

Это казалось забавной проблемой, поэтому я решил попробовать свои силы в этом.

Я делаю предположение, что 111000001 найдет первые 3 и будет успешным. По сути, число нулей, следующих за 1, является важным, поскольку, согласно вашему определению, 0111000 совпадает с 111000. Как только вы найдете два случая 1, следующий найденный 1 завершает трилогию.

Вот это в Python:

def find_three(bstring):
    print bstring
    dict = {}
    lastone = -1
    zerocount = 0
    for i in range(len(bstring)):
        if bstring[i] == '1':
            print i, ': 1'
            if lastone != -1:
                if(zerocount in dict):
                    dict[zerocount].append(lastone)
                    if len(dict[zerocount]) == 2:
                        dict[zerocount].append(i)
                        return True, dict
                else:
                    dict[zerocount] = [lastone]
            lastone = i
            zerocount = 0
        else:
            zerocount = zerocount + 1
    #this is really just book keeping, as we have failed at this point
    if lastone != -1:
        if(zerocount in dict):
            dict[zerocount].append(lastone)
        else:
            dict[zerocount] = [lastone]
    return False, dict

Это первая попытка, так что я уверен, что это можно написать более понятным способом. Пожалуйста, перечислите случаи, когда этот метод не работает внизу.

0
13.10.2009 23:53:05
@ рекурсивные, они не расположены равномерно.
James McMahon 14.10.2009 00:18:29
Что вы подразумеваете под равномерно распределенными? Посмотрите на индексы 0, 3 и 6. Все, и с двумя, разделяющими каждый.
recursive 14.10.2009 00:22:34
О, я понимаю, как я понял, нули были включены только в интервал.
James McMahon 14.10.2009 00:28:04
Вопрос упоминает «1001011», на котором это не работает. Был более ранний (теперь удаленный) ответ, опубликованный сразу после вопроса, который решил ту же (другую) проблему, что и этот. :-)
ShreevatsaR 14.10.2009 00:33:02
Я смотрел на это сегодня на работе, и я не понимал, что имел в виду Роб со своим редактированием. Я отредактировал вопрос для ясности. Я должен был знать, что что-то упустил, когда мне было легко с этим.
James McMahon 14.10.2009 00:38:49

Пока не смог найти решение :(, но есть некоторые идеи.

Что если мы начнем с обратной задачи: построим последовательность с максимальным числом 1 с и БЕЗ любых равномерно распределенных трио. Если вы можете доказать, что максимальное число 1 равно o (n), то вы можете улучшить свою оценку, выполняя итерацию только по списку только 1.

2
14.10.2009 09:32:58
Ну, число 1 определенно ограничено сверху O (n). Это не может быть O (n ** 2), верно - число 1 растет быстрее, чем данные? Важный вопрос заключается в том, является ли верхний предел ниже этого.
hughdbrown 16.10.2009 22:10:54
Я использовал маленький o, а не большой
Olexiy 16.10.2009 23:05:32

Для простого типа задачи (т.е. вы ищете три «1» с единственным (то есть нулем или более) «0» между ними), это довольно просто: вы можете просто разбить последовательность на каждое «1» и искать две смежные подпоследовательности, имеющие такой же длины (вторая подпоследовательность, конечно, не последняя). Очевидно, это можно сделать за O (n) раз.

Для более сложной версии (т. Е. Вы ищете индекс i и разрыв g > 0 такой, что s[i]==s[i+g]==s[i+2*g]=="1"), я не уверен, существует ли решение O (n log n) , поскольку возможно, что O (n²) триплетов, имеющих это свойство (представьте себе строку из всех, таких триплетов приблизительно n / 2 ). Конечно, вы ищете только один из них, но я не знаю, как его найти ...

1
14.10.2009 09:49:07
Да, мы обсуждаем более сложную версию проблемы. Тем не менее, решение n * log (n) может быть возможным.
Olexiy 14.10.2009 11:34:45
на самом деле n выберите 3, что составляет O (n ^ 3) возможных троек, я думаю, что когда вы сказали примерно n ^
ldog 14.10.2009 16:41:24
@gmatt: n выбрать 2 достаточно; если мы фиксируем две единицы, определяется позиция третьей, и это постоянное время, чтобы увидеть, есть ли 1 в этой позиции или нет.
ShreevatsaR 14.10.2009 19:35:09
@ ShreevatsaR: да, верно, я думаю, я думал о безусловном случае.
ldog 14.10.2009 21:50:54
@gmatt: на самом деле, мы ищем кортежи (i, g), как определено выше, с ограничениями 0 <= i <(n-3) и 0 <g <(ni-1) / 2, отсюда и оценка n ^
MartinStettner 15.10.2009 09:40:44

Может ли это быть решением? Я не уверен, что это O (nlogn), но, на мой взгляд, это лучше, чем O (n²), потому что единственный способ не найти тройку - это распределение простых чисел.

Есть место для улучшения, второй найденный 1 может быть следующим первым 1. Также нет проверки ошибок.

#include <iostream>

#include <string>

int findIt(std::string toCheck) {
    for (int i=0; i<toCheck.length(); i++) {
        if (toCheck[i]=='1') {
            std::cout << i << ": " << toCheck[i];
            for (int j = i+1; j<toCheck.length(); j++) {
                if (toCheck[j]=='1' && toCheck[(i+2*(j-i))] == '1') {
                    std::cout << ", " << j << ":" << toCheck[j] << ", " << (i+2*(j-i)) << ":" << toCheck[(i+2*(j-i))] << "    found" << std::endl;
                    return 0;
                }
            }
        }
    }
    return -1;
}

int main (int agrc, char* args[]) {
    std::string toCheck("1001011");
    findIt(toCheck);
    std::cin.get();
    return 0;
}
-3
14.10.2009 10:48:15
Технически это O (n ^ 2). В среднем внутренний цикл будет повторять более половины n при каждом запуске. Так что это можно записать как O (n * (n / 2)), и это можно упростить до O (n ^ 2)
Robert Parker 14.10.2009 11:31:22
Хм, похоже ты прав. Это не простая проблема, просто найти все 1 занимает O (n), не так много места для дальнейшего поиска / сравнения со сложностью O (logn).
DaClown 14.10.2009 11:55:08

Одна из проблем заключается в том, чтобы думать о факторах и изменениях.

При сдвиге вы сравниваете строку единиц и нулей со сдвинутой версией самого себя. Затем вы берете соответствующие. Возьмите этот пример, сдвинутый на два:

1010101010
  1010101010
------------
001010101000

Результирующие 1 (побитовые AND) должны представлять все те 1, которые равномерно разделены двумя. Тот же пример сдвинут на три:

1010101010
   1010101010
-------------
0000000000000

В этом случае нет 1, которые равномерно распределены на три.

Так что это говорит вам? Хорошо, что вам нужно только проверить сдвиги, которые являются простыми числами. Например, скажем, у вас есть два 1, которые шесть друг от друга. Вам нужно будет только проверить «две» смены и «три» смены (поскольку они делят шесть). Например:

10000010 
  10000010 (Shift by two)
    10000010
      10000010 (We have a match)

10000010
   10000010 (Shift by three)
      10000010 (We have a match)

Таким образом, единственные сдвиги, которые вам когда-либо нужно проверять, это 2,3,5,7,11,13 и т. Д. До простого, ближайшего к квадратному корню размера строки цифр.

Почти решен?

Я думаю, что я ближе к решению. В принципе:

  1. Сканирование строки на 1. Для каждой 1 ноты это остаток после взятия модуля его положения. Модуль составляет от 1 до половины размера струны. Это потому, что максимально возможный размер разделения составляет половину строки. Это сделано в O (n ^ 2). НО. Необходимо проверять только простые модули, поэтому O (n ^ 2 / log (n))
  2. Сначала отсортируйте список модулей / остатков в порядке наибольшего модуля, это можно сделать за время O (n * log (n)).
  3. Ищите три последовательных модуля / остатка, которые являются одинаковыми.
  4. Каким-то образом восстановить положение тех!

Я думаю, что самый большой ключ к ответу - это то, что самые быстрые алгоритмы сортировки - это O (n * log (n)).

НЕПРАВИЛЬНО

Шаг 1 не так, как указал коллега. Если бы у нас были единицы в позициях 2, 12 и 102. Тогда, взяв модуль 10, они все имели бы одинаковые остатки, и все же не были бы одинаково разнесены! Сожалею.

0
15.10.2009 15:42:14
Это интересный подход, дайте нам знать, если вы найдете полное решение.
James McMahon 14.10.2009 15:37:53
сдвиг на число k O (n) раз, а затем O (n) проверок за смену дает алгоритм O (n ^ 2), даже если вы сдвигались на одно число. Ваш алгоритм должен сдвинуться более чем на одно число.
ldog 14.10.2009 16:48:02

Это можно решить за линейное время O (n)

  1. начать с начала и ждать первого 1
  2. Начните считать нули.
  3. Когда вы нажмете 1 магазин количество подсчитанных нулей (действительное число также 0) NumberOfZeros -> PrevZeros
  4. Начните считать нули.
  5. Когда вы нажимаете 1, проверьте NumberOfZeros == PrevZeros

    Если верный счетчик возврата

    еще NumberOfZeros -> prev_zeros и перейти к 4

-7
14.10.2009 15:25:25
@ralu, это то, что я сделал в своем ответе. Проблема намного сложнее, потому что 1 также может быть разделителем.
James McMahon 14.10.2009 15:21:26
я не думал об этом, но если бы весь стекопоток не взломал это за 2 дня, как бы кто-нибудь решил эту проблему за 1 час во время экзамена?
Luka Rahne 15.10.2009 21:17:52
Лучшая идея, о которой я могу подумать сейчас, - это использовать свойство, согласно которому их не более чем n / ln (n) (фи-функция от простой плотности), если решения не существует. Это означает, что это может быть решено за n ^ 2 / log (n) раз.
Luka Rahne 15.10.2009 21:25:57
Это может быть легко решено в n log (n), если можно доказать, что худшая плотность k log (n) в долгосрочной перспективе.
Luka Rahne 15.10.2009 21:39:55

Забавный вопрос, но как только вы поймете, что фактический шаблон между двумя единицами не имеет значения, алгоритм становится:

  • сканирование искать '1'
  • начиная со следующего сканирования позиции для другого '1' (до конца массива минус расстояние от текущего первого '1', иначе 3-й '1' был бы вне границ)
  • если в позиции 2 '1' плюс расстояние до первого 1 'третий' 1 'найден, мы имеем равные пробелы.

В коде, JTest fashion, (обратите внимание, этот код написан не для того, чтобы быть наиболее эффективным, и я добавил несколько println, чтобы увидеть, что происходит.)

import java.util.Random;

import junit.framework.TestCase;

public class AlgorithmTest extends TestCase {

 /**
  * Constructor for GetNumberTest.
  *
  * @param name The test's name.
  */
 public AlgorithmTest(String name) {
  super(name);
 }

 /**
  * @see TestCase#setUp()
  */
 protected void setUp() throws Exception {
  super.setUp();
 }

 /**
  * @see TestCase#tearDown()
  */
 protected void tearDown() throws Exception {
  super.tearDown();
 }

 /**
  * Tests the algorithm.
  */
 public void testEvenlySpacedOnes() {

  assertFalse(isEvenlySpaced(1));
  assertFalse(isEvenlySpaced(0x058003));
  assertTrue(isEvenlySpaced(0x07001));
  assertTrue(isEvenlySpaced(0x01007));
  assertTrue(isEvenlySpaced(0x101010));

  // some fun tests
  Random random = new Random();

  isEvenlySpaced(random.nextLong());
  isEvenlySpaced(random.nextLong());
  isEvenlySpaced(random.nextLong());
 }

 /**
  * @param testBits
  */
 private boolean isEvenlySpaced(long testBits) {
  String testString = Long.toBinaryString(testBits);
  char[] ones = testString.toCharArray();
  final char ONE = '1';

  for (int n = 0; n < ones.length - 1; n++) {

   if (ONE == ones[n]) {
    for (int m = n + 1; m < ones.length - m + n; m++) {

     if (ONE == ones[m] && ONE == ones[m + m - n]) {
      System.out.println(" IS evenly spaced: " + testBits + '=' + testString);
      System.out.println("               at: " + n + ", " + m + ", " + (m + m - n));
      return true;
     }
    }
   }
  }

  System.out.println("NOT evenly spaced: " + testBits + '=' + testString);
  return false;
 }
}
1
14.10.2009 16:05:35
Если я не ошибаюсь, это O (n²), потому что внешний цикл выполняется n раз, а внутренний цикл в среднем n / 2 раза.
StriplingWarrior 14.10.2009 16:38:09
Внешний цикл выполняется n раз, а внутренний цикл в среднем n / 4, но запускается только с позиций, следующих за «1». Чтобы приблизиться к поведению n ^ 2, число «1» должно быть большим, что приводит к истинному результату на ранней стадии, тем самым останавливая обработку. Поэтому поведение n ^ 2 никогда не произойдет. Как определить O на основе известных свойств данных ускользает от меня в данный момент.
rsp 14.10.2009 19:09:44
К сожалению, речь идет не о среднем реальном времени выполнения, а скорее о теоретическом времени выполнения Big O. И ваш подход O (n²) (такой же, как мой, потому что ваш подход такой же, как мой)
DaClown 15.10.2009 07:01:20
Я говорил не о среднем поведении, а о максимальном поведении. Я не удивлюсь, если это доказуемо, что максимальная энтропия, которая не проходит тест, содержит log n '1 в строке.
rsp 15.10.2009 09:10:45
Что если вы обновите индекс во внешнем цикле индексом первого 1, найденного во внутреннем цикле, т. Е. Если (ones [m] == ONE) {n = m}? Это помогает большой O?
steamer25 15.10.2009 20:14:06

Я предполагаю, что причина этого nlog (n) заключается в следующем:

  • Чтобы найти 1, который является началом триплета, вам нужно проверить (n-2) символов. Если вы не нашли его к этому моменту, вы не сможете (символы n-1 и n не могут запустить триплет) (O (n))
  • Чтобы найти второй 1, являющийся частью триплета (начатый первым), вам нужно проверить m / 2 (m = nx, где x - смещение первых 1) символов. Это потому, что если вы не нашли вторую 1 к тому времени, когда вы на полпути от первой к концу, вы не будете ... так как третья 1 должна быть точно на том же расстоянии, что и вторая. (O (журнал (п)))
  • Это O (1), чтобы найти последние 1, так как вы знаете индекс, по которому они должны быть к тому времени, когда вы найдете первое и второе.

Итак, у вас есть n, log (n) и 1 ... O (nlogn)

Редактировать: Ой, мой плохой. В моем мозгу было установлено, что n / 2 было logn ... чего, очевидно, нет (удвоение числа элементов по-прежнему удваивает число итераций во внутреннем цикле). Это все еще на п ^ 2, не решая проблему. Ну, по крайней мере, я должен написать код :)


Реализация в Tcl

proc get-triplet {input} {
    for {set first 0} {$first < [string length $input]-2} {incr first} {
        if {[string index $input $first] != 1} {
            continue
        }
        set start [expr {$first + 1}]
        set end [expr {1+ $first + (([string length $input] - $first) /2)}]
        for {set second $start} {$second < $end} {incr second} {
            if {[string index $input $second] != 1} {
                continue
            }
            set last [expr {($second - $first) + $second}]
            if {[string index $input $last] == 1} {
                return [list $first $second $last]
            }
        }
    }
    return {}
}

get-triplet 10101      ;# 0 2 4
get-triplet 10111      ;# 0 2 4
get-triplet 11100000   ;# 0 1 2
get-triplet 0100100100 ;# 1 4 7
0
14.10.2009 18:45:43

Я думал о подходе «разделяй и властвуй», который может сработать.

Во-первых, при предварительной обработке вам нужно вставить все числа, меньшие половины вашего размера ввода ( n / 3), в список.

Учитывая строку: 0000010101000100(обратите внимание, что этот конкретный пример действителен)

Вставьте все простые числа (и 1) от 1 до (16/2) в список: {1, 2, 3, 4, 5, 6, 7}

Затем разделите его пополам:

100000101 01000100

Продолжайте делать это, пока не доберетесь до строк размера 1. Для всех строк размера один с 1 в них добавьте индекс строки в список возможностей; в противном случае верните -1 в случае ошибки.

Вам также нужно будет вернуть список возможных расстояний, связанных с каждым начальным индексом. (Начните с списка, который вы сделали выше, и убирайте числа по ходу дела). Здесь пустой список означает, что вы имеете дело только с одним 1, и поэтому в этой точке возможен любой пробел; в противном случае список включает в себя интервалы, которые должны быть исключены.

Итак, продолжаем с примером выше:

1000 0101 0100 0100

10 00 01 01 01 00 01 00

1 0 0 0 0 1 0 1 0 1 0 0 0 1 0 0

На первом шаге объединения у нас теперь восемь наборов из двух. Во-первых, у нас есть возможность множества, но мы узнаем, что интервал на 1 невозможен из-за присутствия другого нуля. Таким образом, мы возвращаем 0 (для индекса) и {2,3,4,5,7} за то, что интервал на 1 невозможен. Во втором у нас ничего нет и поэтому возвращаем -1. В третьем случае мы имеем совпадение без пропусков в индексе 5, поэтому вернем 5, {1,2,3,4,5,7}. В четвертой паре мы возвращаем 7, {1,2,3,4,5,7}. В пятом верните 9, {1,2,3,4,5,7}. В шестой верните -1. В седьмом верните 13, {1,2,3,4,5,7}. В восьмом верните -1.

Объединяя снова в четыре набора по четыре, мы имеем:

1000: Return (0, {4,5,6,7}) 0101: Return (5, {2,3,4,5,6,7}), (7, {1,2,3,4,5,6 , 7}) 0100: Возврат (9, {3,4,5,6,7}) 0100: Возврат (13, {3,4,5,6,7})

Объединение в наборы из восьми:

10000101: Return (0, {5,7}), (5, {2,3,4,5,6,7}), (7, {1,2,3,4,5,6,7}) 01000100: Возврат (9, {4,7}), (13, {3,4,5,6,7})

Объединение в набор из шестнадцати:

10000101 01000100

По мере нашего продвижения, мы продолжаем проверять все возможности до сих пор. До этого шага мы оставили вещи, которые выходили за пределы конца строки, но теперь мы можем проверить все возможности.

По сути, мы проверяем первые 1 с интервалами 5 и 7 и обнаруживаем, что они не совпадают с 1. (Обратите внимание, что каждая проверка является ПОСТОЯННОЙ, а не линейным временем) Затем мы проверяем вторую (индекс 5) с интервалами 2, 3, 4, 5, 6 и 7 - или мы бы это сделали, но мы можем остановиться на 2, так как это на самом деле совпадает.

Уф! Это довольно длинный алгоритм.

Я не знаю 100%, если это O (n log n) из-за последнего шага, но, насколько я могу судить , все, что там есть, определенно O (n log n) . Я вернусь к этому позже и попытаюсь уточнить последний шаг.

РЕДАКТИРОВАТЬ: изменил мой ответ, чтобы отразить комментарий Велбога. Извините за ошибку. Я также напишу немного псевдокода позже, когда у меня будет немного больше времени, чтобы расшифровать то, что я написал снова. ;-)

1
15.10.2009 01:48:42
Я не следую вашему алгоритму, но +1 за попытку алгоритма, который фактически пытается быть O (n log n)
ldog 14.10.2009 18:20:33
Спасибо. Я постараюсь объяснить это лучше, когда у меня будет больше времени (возможно, напишу какой-нибудь псевдокод или что-то в этом роде).
Platinum Azure 14.10.2009 19:08:11
Почему вы только смотрите на пробелы возможностей простых чисел? Как бы вы предложили сопоставить строку как 100010001? Если я правильно понимаю ваш подход, он не сможет соответствовать, потому что правильный ответ (0,{4})невозможно вычислить. Учитывая, что вам нужны не простые числа в вашем списке, я думаю, что легко придумать патологические строки, которые раздувают списки возможностей, которые вам нужно проверить выше O (n log (n)), я думаю.
Welbog 14.10.2009 21:47:22
ругается Ну, я изначально собирался сделать кратные, но я вроде изменил мой ответ на полпути через и не получил изменить все. Сожалею. Скоро исправим
Platinum Azure 15.10.2009 01:43:14
Я не думаю, что это O (n log n). На первом этапе объединения вы рассматриваете (n / 2) наборов, каждый из которых, возможно, возвращает набор из O (n) возможных интервалов. К сожалению, это одно делает это O (n ^ 2).
MartinStettner 15.10.2009 09:39:56

Я думаю, что нашел способ решения проблемы, но я не могу построить формальное доказательство. Решение, которое я принял, написано на Java и использует счетчик 'n' для подсчета количества обращений к списку / массиву. Так что n должно быть меньше или равно stringLength * log (stringLength), если это правильно. Я пробовал это для чисел от 0 до 2 ^ 22, и это работает.

Он начинается с перебора входной строки и составления списка всех индексов, которые содержат единицу. Это просто O (n).

Затем из списка индексов он выбирает firstIndex и secondIndex, который больше первого. Эти два индекса должны содержать индексы, потому что они находятся в списке индексов. Оттуда может быть рассчитан третий индекс. Если inputString [thirdIndex] равен 1, то он останавливается.

public static int testString(String input){
//n is the number of array/list accesses in the algorithm
int n=0;

//Put the indices of all the ones into a list, O(n)
ArrayList<Integer> ones = new ArrayList<Integer>();
for(int i=0;i<input.length();i++){
    if(input.charAt(i)=='1'){
        ones.add(i);
    }
}

//If less than three ones in list, just stop
if(ones.size()<3){
    return n;
}

int firstIndex, secondIndex, thirdIndex;
for(int x=0;x<ones.size()-2;x++){
    n++;
    firstIndex = ones.get(x);

    for(int y=x+1; y<ones.size()-1; y++){
        n++;
        secondIndex = ones.get(y);
        thirdIndex = secondIndex*2 - firstIndex;

        if(thirdIndex >= input.length()){
            break;
        }

        n++;
        if(input.charAt(thirdIndex) == '1'){
            //This case is satisfied if it has found three evenly spaced ones
            //System.out.println("This one => " + input);
            return n;
        }
    }
}

return n;

}

дополнительное примечание: счетчик n не увеличивается, когда он перебирает входную строку для построения списка индексов. Эта операция O (n), поэтому она не повлияет на сложность алгоритма.

0
14.10.2009 18:57:22
Кажется, у вас все еще есть две вложенные петли O (n), что делает его O (n ^ 2)
RHSeeger 14.10.2009 19:09:11
Массив индексов не совпадает с размером входной строки. Это мешает мне написать реальное доказательство или доказать, что оно неверно. Я подозреваю, что есть некая математическая идея, которая делает эту работу.
Robert Parker 14.10.2009 19:19:38
Я думаю, уловка этой проблемы заключается в том, что, несмотря на то, что ваш алгоритм - O (n ^ 2), наихудший возможный случай строки, которую вы можете получить, приведет только к O (nlogn) итерациям, в противном случае вы найдете решение, используя ваш алгоритм.
z - 14.10.2009 20:21:21
тестирование до 2 ^ 22 на самом деле не проверяет его сложность. 2 ^ 22 имеет только 22 бита, что означает, что ваше N равно 22. Попробуйте это для нескольких значений, где N составляет несколько миллионов.
Peter Recore 15.10.2009 19:40:55
Попробуйте этот алгоритм с одной из максимальных «плохих» строк, указанных в ответе yx, и вы обнаружите, что это O(n^2)алгоритм.
Welbog 16.10.2009 12:17:31

Это не решение, а мысль, похожая на то, о чем думал Алексей

Я играл с созданием последовательностей с максимальным количеством единиц, и все они довольно интересны, я получил до 125 цифр, и вот первые 3 числа, которые он нашел, пытаясь вставить как можно больше «1» битов:

  • 11011000011011000000000000001101100001101100000000000000000000000000000000000000000110110000110110000000000000011011000011011
  • 10110100010110100000000000010110100010110100000000000000000000000000000000000000000101101000101101000000000000101101000101101
  • 10011001010011001000000000010011001010011001000000000000000000000000000000000000010011001010011001000000000010011001010011001

Обратите внимание, что все они фракталы (не слишком удивительно, учитывая ограничения). Может быть что-то в размышлении задом наперед, возможно, если строка не является фракталом с характеристикой, то она должна иметь повторяющийся узор?

Спасибо бета за лучший термин для описания этих чисел.

Обновление: Увы, похоже, что шаблон ломается при запуске с достаточно большой начальной строки, например: 10000000000001:

100000000000011
10000000000001101
100000000000011011
10000000000001101100001
100000000000011011000011
10000000000001101100001101
100000000000011011000011010000000001
100000000000011011000011010000000001001
1000000000000110110000110100000000010011
1000000000000110110000110100000000010011001
10000000000001101100001101000000000100110010000000001
10000000000001101100001101000000000100110010000000001000001
1000000000000110110000110100000000010011001000000000100000100000000000001
10000000000001101100001101000000000100110010000000001000001000000000000011
1000000000000110110000110100000000010011001000000000100000100000000000001101
100000000000011011000011010000000001001100100000000010000010000000000000110100001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001100100000000100100000000000010000000010000100000100100010010000010000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000110000010000000000000000000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001100100000000100100000000000010000000010000100000100100010010000010000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000110000010000000000000000000001001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001000000000000000000000100100000000000000000000000000000000000011
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001000000000000000000000100100000000000000000000000000000000000011001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001001000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001000000000000000000000100100000000000000000000000000000000000011001000000000000000000000010010000010000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001100100000000100100000000000010000000010000100000100100010010000010000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000110000010000000000000000000001001000000000000000000000000000000000000110010000000000000000000000100100000100000011
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001001000001000000110000000000001
8
23.05.2017 12:26:29
Святой * @ !!, это фракталы! Если это так, это ставит верхнюю границу числа 1, и это меньше, чем O (n).
Beta 15.10.2009 18:38:45
фракталы, это гораздо лучший термин для их описания. Спасибо
z - 15.10.2009 18:51:39
Интересно, что эти паттерны очень похожи на троичный набор Кантора ( en.wikipedia.org/wiki/Cantor_set ). Если это так, то пропорция должна стремиться к нулю ...
flybywire 15.10.2009 20:25:12
Очевидно ли, что последовательности с максимальным числом 1 с без троек имеют прямое отношение к наихудшему времени выполнения алгоритма? Вполне возможно, что у вас могут быть строки с множеством единиц, но в которых тройки встречаются очень поздно, поскольку эти единицы находятся в позициях, которые проверяются поздно вашим алгоритмом.
ShreevatsaR 16.10.2009 12:28:18
Мой анализ числа единиц в строках по сравнению с их общим размером, кажется, показывает, что существует линейная зависимость между числом единиц и размером строки, что наводит меня на мысль, что нет счастливой верхней границы, которая позволяет нам сказать, что количество единиц в строке будет не более log (n) для данной строки. Таким образом, решения, имеющие дело только с позициями единиц, а не всей строки, тоже будут O (n ^ 2). Или, точнее, O (n + m ^ 2), где m - количество единиц в строке, n - размер строки, а m - big-theta (n).
Welbog 16.10.2009 14:52:19

Здесь я приведу приблизительное предположение и позволю тем, кто лучше разбирается в сложности, помочь мне понять, как мой алгоритм работает в O-нотации.

  1. заданная двоичная строка 0000010101000100 (как пример)
  2. обрезать голову и хвост нулей -> 00000 101010001 00
  3. мы получаем 101010001 из предыдущего расчета
  4. проверить, является ли средний бит единицей, если истина, то найдены правильные три равных "единицы" (только если число битов нечетно нумеровано)
  5. соответственно, если оставшееся количество битов даже пронумеровано, голова и хвост «один» не могут быть частью равномерно расположенного «одного»,
  6. мы используем 1010100001 в качестве примера (с дополнительным нулем, чтобы стать четным урожаем), в этом случае нам нужно снова обрезать, затем становится -> 10101 00001
  7. мы получаем 10101 из предыдущего расчета и проверяем средний бит, и мы снова нашли равномерно распределенный бит

Я не знаю, как рассчитать сложность для этого, кто-нибудь может помочь?

редактировать: добавить код, чтобы проиллюстрировать мою идею

edit2: попытался скомпилировать мой код и обнаружил некоторые серьезные ошибки, исправлено

char *binaryStr = "0000010101000100";

int main() {
   int head, tail, pos;
   head = 0;
   tail = strlen(binaryStr)-1;
   if( (pos = find3even(head, tail)) >=0 )
      printf("found it at position %d\n", pos);
   return 0;
}

int find3even(int head, int tail) {
   int pos = 0;
   if(head >= tail) return -1;
   while(binaryStr[head] == '0') 
      if(head<tail) head++;
   while(binaryStr[tail] == '0') 
      if(head<tail) tail--;
   if(head >= tail) return -1;
   if( (tail-head)%2 == 0 && //true if odd numbered
       (binaryStr[head + (tail-head)/2] == '1') ) { 
         return head;
   }else {
      if( (pos = find3even(head, tail-1)) >=0 )
         return pos;
      if( (pos = find3even(head+1, tail)) >=0 )
         return pos;
   }
   return -1;
}
1
15.10.2009 05:26:44
@ рекурсивный Я думаю, что это сработает, когда он достигнет вызова find3even (head + 1, tail), который затем обрежет его до 111 при head = 4, не могли бы вы проверить еще раз?
andycjw 15.10.2009 03:51:01
@recursive, пожалуйста, проверьте код, который я добавил, чтобы лучше объяснить псевдокод, который я создал ранее, который не очень строг и
andycjw 15.10.2009 03:53:29
Это nlogn - для n битов мы ожидаем приблизительно logn итераций, проверяющих n * c битов, где C - константа.
Ron Warholic 15.10.2009 19:36:24
Да, это похоже на 111001 и 100111 как самые простые случаи. Равномерно расположенные единицы не должны быть в центре среднего бита.
Dean J 15.10.2009 19:53:20
Он правильно обрабатывает эти случаи, 111001 имеет четное количество битов, поэтому он сразу разделяется на 111 и 001. Поскольку 111 имеет нечетное количество битов, а средний бит равен единице, он успешно возвращается.
Ron Warholic 15.10.2009 20:06:11

Я думаю, что этот алгоритм имеет сложность O (n log n) (C ++, DevStudio 2k5). Теперь я не знаю деталей того, как анализировать алгоритм, чтобы определить его сложность, поэтому я добавил в код некоторую информацию для сбора метрик. Код подсчитывает количество тестов, выполненных на последовательности 1 и 0 для любого заданного ввода (надеюсь, я не сделал шарики алгоритма). Мы можем сравнить фактическое количество тестов со значением O и посмотреть, есть ли корреляция.

#include <iostream>
using namespace std;

bool HasEvenBits (string &sequence, int &num_compares)
{
  bool
    has_even_bits = false;

  num_compares = 0;

  for (unsigned i = 1 ; i <= (sequence.length () - 1) / 2 ; ++i)
  {
    for (unsigned j = 0 ; j < sequence.length () - 2 * i ; ++j)
    {
      ++num_compares;
      if (sequence [j] == '1' && sequence [j + i] == '1' && sequence [j + i * 2] == '1')
      {
        has_even_bits = true;
        // we could 'break' here, but I want to know the worst case scenario so keep going to the end
      }
    }
  }

  return has_even_bits;
}

int main ()
{
  int
    count;

  string
    input = "111";

  for (int i = 3 ; i < 32 ; ++i)
  {
    HasEvenBits (input, count);
    cout << i << ", " << count << endl;
    input += "0";
  }
}

Эта программа выводит количество тестов для каждой строки длиной до 32 символов. Вот результаты:

 n  Tests  n log (n)
=====================
 3     1     1.43
 4     2     2.41
 5     4     3.49
 6     6     4.67
 7     9     5.92
 8    12     7.22
 9    16     8.59
10    20    10.00
11    25    11.46
12    30    12.95
13    36    14.48
14    42    16.05
15    49    17.64
16    56    19.27
17    64    20.92
18    72    22.59
19    81    24.30
20    90    26.02
21   100    27.77
22   110    29.53
23   121    31.32
24   132    33.13
25   144    34.95
26   156    36.79
27   169    38.65
28   182    40.52
29   196    42.41
30   210    44.31
31   225    46.23

Я также добавил значения 'n log n'. Нанесите их на график с помощью выбранного графического инструмента, чтобы увидеть корреляцию между двумя результатами. Распространяется ли этот анализ на все значения n? Я не знаю.

-3
3.07.2012 13:40:12
Это не идеальное соотношение, я согласен. Однако кривая ближе к n log n, чем к n ^ 2.
Skizz 15.10.2009 14:16:11
Попробуйте накачать размер ввода до миллиона или более. При небольших входах кривая часто выглядит аналогично кривым алгоритмов, которые, очевидно, лучше, когда размер входа накачан.
Nick Larsen 15.10.2009 18:29:57
Двойной цикл for с внутренним, ограниченным внешним, создает треугольную форму, которая по-прежнему имеет сложность O (n ^ 2). Подумайте обо всем (i, j) так, что i в [0, n] и j в [0, n-2 * i], у вас есть треугольник, а площадь треугольника имеет квадратичную тенденцию.
Matthieu M. 16.10.2009 14:30:34
Чтобы быть точным, Тесты = (n ^ 2-2n) / 4 для четного n; очевидно квадратичный.
Grandpa 16.10.2009 19:49:19

Я придумал что-то вроде этого:

def IsSymetric(number):
    number = number.strip('0')

    if len(number) < 3:
        return False
    if len(number) % 2 == 0:
        return IsSymetric(number[1:]) or IsSymetric(number[0:len(number)-2])
    else:
        if number[len(number)//2] == '1':
            return True
        return IsSymetric(number[:(len(number)//2)]) or IsSymetric(number[len(number)//2+1:])
    return False

Это вдохновлено andycjw.

  1. Обрезать нули.
  2. Если даже, тогда проверьте две подстроки 0 - (len-2) (пропустить последний символ) и из 1 - (len-1) (пропустить первый символ)
  3. Если нет, то даже если средний символ равен единице, мы добьемся успеха. Еще разделите строку в середине без элемента середины и проверьте обе части.

Что касается сложности, то это может быть O (nlogn), так как в каждой рекурсии мы делим на два.

Надеюсь, поможет.

1
15.10.2009 14:54:21
Похоже, вы конвертируете проблему с N элементами в 2 задачи с N-1 элементами. Разделение его пополам означало бы преобразование его в 2 задачи с N / 2 элементами.
RHSeeger 15.10.2009 21:41:02
Это относится только к четным длинам. Таким образом, если len равно 8, алгоритм создает строки длиной: 7, 7, 3, 3, 3, 3. Высота дерева рекурсии равна 3, что равно lg (8).
Beku 15.10.2009 22:15:20

Это может помочь ....

Эта проблема сводится к следующему:

Для заданной последовательности натуральных чисел найдите смежную подпоследовательность, разделенную на префикс и суффикс, такой, чтобы сумма префикса подпоследовательности была равна сумме суффикса подпоследовательности.

Например, для данной последовательности [ 3, 5, 1, 3, 6, 5, 2, 2, 3, 5, 6, 4 ]мы найдем подпоследовательность [ 3, 6, 5, 2, 2]с префиксом [ 3, 6 ]с префиксной суммой 9и с суффиксом [ 5, 2, 2 ]с суффиксной суммой 9.

Сокращение заключается в следующем:

Учитывая последовательность нулей и единиц и начиная с самого левого, продолжайте двигаться вправо. Каждый раз, когда встречается другой, запишите количество ходов с момента предыдущего и добавьте это число в результирующую последовательность.

Например, учитывая последовательность [ 0, 1, 1, 0, 0, 1, 0, 0, 0, 1 0 ], мы бы нашли сокращение [ 1, 3, 4]. Из этого сокращения мы вычисляем смежную подпоследовательность [ 1, 3, 4], префикс [ 1, 3]с суммой 4и суффикс [ 4 ]с суммой 4.

Это сокращение может быть вычислено в O(n).

К сожалению, я не уверен, куда идти отсюда.

2
15.10.2009 20:49:08
Это более компактная запись, но она не поможет справиться со сложностью времени. Множество префиксных разделов изоморфно поиску всех пар во всех случаях «1», то есть O (n ^ 2).
p00ya 16.10.2009 08:12:06
Очевидно, существуют алгоритмы, работающие с непрерывными суммами подпоследовательностей. К сожалению, похоже, что все они имеют дело с поиском смежной подпоследовательности с максимальной суммой в O (n).
yfeldblum 16.10.2009 11:10:19
@ p00ya это не правильно. Используя этот алгоритм, временная скопляемость зависит от верхнего предела числа ложных, который по предположению на сгенерированной строке Кантора равен ((3/2) ^ (log (n) / log (3))), и сложность пространства становится такой, но сложность времени становится этой, умноженной на n. Проверьте мой второй ответ. (не отрицательный): D
Luka Rahne 17.10.2009 02:07:45
@ralu: вы полагаете, что сгенерированные Кантором строки - наихудший случай, что неверно. Для записи, количество пар, безусловно, O (n ^ 2); но я предполагаю, что я действительно имел в виду, что это была большая Омега (n ^ 2), что неверно, учитывая эти результаты (особенно см. ссылку NrootN), предлагая более низкую оценку в парах большой Омеги (n ^ (2 / 1,52) )) доказательством или большой омегой (n ^ (4/3)) предположением.
p00ya 19.10.2009 06:48:11

Предположение:

Просто неправильно, говоря о log (n) числе верхнего предела единиц

РЕДАКТИРОВАТЬ:

Теперь я обнаружил, что используя числа Кантора (если они верны), плотность на множестве равна (2/3) ^ Log_3 (n) (что за странная функция), и я согласен, плотность log (n) / n слишком высокая.

Если это верхний предел, существует алгоритм, который решает эту проблему по крайней мере за O (n * (3/2) ^ (log (n) / log (3))) сложность времени и O ((3/2) ^ ( log (n) / log (3))) сложность пространства. (проверьте ответ юстиции для algorhitm)

Это все еще намного лучше, чем O (n ^ 2)

Эта функция ((3/2) ^ (log (n) / log (3))) действительно выглядит как n * log (n) на первый взгляд.

Как я получил эту формулу?

Наложение числа Кантора на строку.
Предположим, что длина строки равна 3 ^ p == n
На каждом шаге генерации строки Кантора вы сохраняете 2/3 преобладающего числа единиц. Примените это р раз.

Это значит (n * ((2/3) ^ p)) -> (((3 ^ p)) * ((2/3) ^ p)) оставшихся и после упрощения 2 ^ p. Это означает 2 ^ p единиц в 3 ^ p строке -> (3/2) ^ p единиц. Подставьте p = log (n) / log (3) и получите
((3/2) ^ (log (n) / log (3)))

0
17.10.2009 02:42:03
False: набор Кантора имеет плотность n ^ log_3 (2).
sdcvvc 16.10.2009 14:35:29

При сканировании 1 с, добавьте их позиции в список. При добавлении второй и последующих 1-ых, сравните их до сих пор с каждой позицией в списке. Интервал равен currentOne (в центре) - previousOne (слева). Правый бит - currentOne + интервал. Если это 1, конец.

Список из них растет обратно пропорционально расстоянию между ними. Проще говоря, если у вас много нулей между 1 (как в худшем случае), ваш список известных 1 будет расти довольно медленно.

using System;
using System.Collections.Generic;

namespace spacedOnes
{
    class Program
    {
        static int[] _bits = new int[8] {128, 64, 32, 16, 8, 4, 2, 1};

        static void Main(string[] args)
        {
            var bytes = new byte[4];
            var r = new Random();
            r.NextBytes(bytes);
            foreach (var b in bytes) {
                Console.Write(getByteString(b));
            }
            Console.WriteLine();
            var bitCount = bytes.Length * 8;
            var done = false;
            var onePositions = new List<int>();
            for (var i = 0; i < bitCount; i++)
            {
                if (isOne(bytes, i)) {
                    if (onePositions.Count > 0) {
                        foreach (var knownOne in onePositions) {
                            var spacing = i - knownOne;
                            var k = i + spacing;
                            if (k < bitCount && isOne(bytes, k)) {
                                Console.WriteLine("^".PadLeft(knownOne + 1) + "^".PadLeft(spacing) + "^".PadLeft(spacing));
                                done = true;
                                break;
                            }
                        }
                    }
                    if (done) {
                        break;
                    }
                    onePositions.Add(i);
                }
            }
            Console.ReadKey();
        }

        static String getByteString(byte b) {
            var s = new char[8];
            for (var i=0; i<s.Length; i++) {
                s[i] = ((b & _bits[i]) > 0 ? '1' : '0');
            }
            return new String(s);
        }

        static bool isOne(byte[] bytes, int i)
        {
            var byteIndex = i / 8;
            var bitIndex = i % 8;
            return (bytes[byteIndex] & _bits[bitIndex]) > 0;
        }
    }
}
0
16.10.2009 22:20:41

Вот несколько мыслей, которые, несмотря на все мои старания, похоже, не закутаются в поклон. Тем не менее, они могут быть полезной отправной точкой для чьего-либо анализа.

Рассмотрим предложенное решение следующим образом. Это тот подход, который предложили несколько человек, включая меня в предыдущей версии этого ответа. :)

  1. Обрезать ведущие и конечные нули.
  2. Сканирование строки в поисках 1.
  3. Когда 1 найден:
    1. Предположим, что это середина 1 решения.
    2. Для каждого предыдущего 1 используйте его сохраненную позицию, чтобы вычислить ожидаемую позицию финальной 1.
    3. Если вычисленная позиция находится после конца строки, она не может быть частью решения, поэтому удалите эту позицию из списка кандидатов.
    4. Проверьте решение.
  4. Если решение не найдено, добавьте текущий 1 в список кандидатов.
  5. Повторяйте, пока не будет найдено больше 1.

Теперь рассмотрим строки входных строк, подобные приведенным ниже, которые не будут иметь решения:

101
101001
1010010001
101001000100001
101001000100001000001

В общем, это конкатенация k строк вида j 0, за которыми следует 1 для j от нуля до k-1.

k=2  101
k=3  101001
k=4  1010010001
k=5  101001000100001
k=6  101001000100001000001

Обратите внимание, что длины подстрок равны 1, 2, 3 и т. Д. Таким образом, размер задачи n имеет подстроки длиной от 1 до k такие, что n = k (k + 1) / 2.

k=2  n= 3  101
k=3  n= 6  101001
k=4  n=10  1010010001
k=5  n=15  101001000100001
k=6  n=21  101001000100001000001

Обратите внимание, что k также отслеживает количество единиц, которые мы должны рассмотреть. Помните, что каждый раз, когда мы видим 1, нам нужно учитывать все 1, увиденные до сих пор. Поэтому, когда мы видим вторую 1, мы рассматриваем только первую, когда мы видим третью 1, мы пересматриваем первые две, когда мы видим четвертую 1, нам нужно пересматривать первые три, и так далее. К концу алгоритма мы рассмотрели k (k-1) / 2 пары единиц. Назовите это р.

k=2  n= 3  p= 1  101
k=3  n= 6  p= 3  101001
k=4  n=10  p= 6  1010010001
k=5  n=15  p=10  101001000100001
k=6  n=21  p=15  101001000100001000001

Соотношение между n и p таково, что n = p + k.

Процесс прохождения строки занимает O (n) времени. Каждый раз, когда встречается 1, выполняется максимум (k-1) сравнений. Поскольку n = k (k + 1) / 2, n> k ** 2, то sqrt (n)> k. Это дает нам O (n sqrt (n)) или O (n ** 3/2). Тем не менее, обратите внимание, что это не может быть очень жесткой границей, потому что число сравнений идет от 1 до максимум k, это не k за все время. Но я не уверен, как объяснить это в математике.

Это все еще не O (n log (n)). Кроме того, я не могу доказать, что эти данные являются худшими, хотя я подозреваю, что это так. Я думаю, что более плотная упаковка 1 в передней части приводит к еще более редкой упаковке в конце.

Поскольку кто-то может все еще найти это полезным, вот мой код для этого решения на Perl:

#!/usr/bin/perl

# read input as first argument
my $s = $ARGV[0];

# validate the input
$s =~ /^[01]+$/ or die "invalid input string\n";

# strip leading and trailing 0's
$s =~ s/^0+//;
$s =~ s/0+$//;

# prime the position list with the first '1' at position 0
my @p = (0);

# start at position 1, which is the second character
my $i = 1;

print "the string is $s\n\n";

while ($i < length($s)) {
   if (substr($s, $i, 1) eq '1') {
      print "found '1' at position $i\n";
      my @t = ();
      # assuming this is the middle '1', go through the positions
      # of all the prior '1's and check whether there's another '1'
      # in the correct position after this '1' to make a solution
      while (scalar @p) {
         # $p is the position of the prior '1'
         my $p = shift @p;
         # $j is the corresponding position for the following '1'
         my $j = 2 * $i - $p;
         # if $j is off the end of the string then we don't need to
         # check $p anymore
         next if ($j >= length($s));
         print "checking positions $p, $i, $j\n";
         if (substr($s, $j, 1) eq '1') {
            print "\nsolution found at positions $p, $i, $j\n";
            exit 0;
         }
         # if $j isn't off the end of the string, keep $p for next time
         push @t, $p;
      }
      @p = @t;
      # add this '1' to the list of '1' positions
      push @p, $i;
   }
   $i++;
}

print "\nno solution found\n";
0
16.10.2009 16:07:11
Ваша «нерешительная» последовательность неверна; индекс каждого 1 представляет собой последовательность треугольных чисел 1, 3, 6, 10, 15 ... и т. д. и включает в себя числа 6, 36 и 66, которые образуют арифметическую прогрессию.
Jason S 17.10.2009 13:26:16

Ваша проблема называется СРЕДНЯЯ в этой статье (1999):

Задача является 3SUM-сложной, если есть подквадратичная редукция из задачи 3SUM: При заданном множестве A из n целых чисел существуют ли такие элементы a, b, c в A, что a + b + c = 0? Не известно, является ли AVERAGE 3SUM-сложным. Однако существует простое линейное сокращение времени от AVERAGE до 3SUM, описание которого мы опускаем.

Википедия :

Когда целые числа находятся в диапазоне [-u ... u], 3SUM может быть решена за время O (n + u lg u) путем представления S в качестве битового вектора и выполнения свертки с использованием FFT.

Этого достаточно, чтобы решить вашу проблему :).

Что очень важно, так это то, что O (n log n) - это сложность с точки зрения количества нулей и единиц, а не количества единиц (которые могут быть заданы в виде массива, как [1,5,9,15]). Проверить, имеет ли набор арифметическую прогрессию, слагаемое числа 1, сложно, и согласно этой статье на 1999 год не известен более быстрый алгоритм, чем O (n 2 ), и предполагается, что он не существует. Все, кто не принимает это во внимание, пытаются решить открытую проблему.

Другая интересная информация, в основном неактуальная:

Нижняя граница:

Легкой нижней границей является канторовоподобное множество (числа 1..3 ^ n-1, не содержащие 1 в их троичном расширении) - его плотность равна n ^ (log_3 2) (около 0,631). Поэтому любой проверки, если набор не слишком большой, а затем проверка всех пар недостаточно, чтобы получить O (n log n). Вы должны исследовать последовательность умнее. Более нижняя граница указана здесь - это п 1-с / (журнал (п)) ^ (1/2) . Это означает, что набор Кантора не является оптимальным.

Верхняя граница - мой старый алгоритм:

Известно, что для больших n подмножество {1,2, ..., n}, не содержащее арифметической прогрессии, имеет не более n / (log n) ^ (1/20) элементов. Статья « О тройках в арифметической прогрессии» доказывает больше: набор не может содержать более n * 2 28 * (log log n / log n) 1/2 элементов. Таким образом, вы можете проверить, достигнута ли эта граница, а если нет, наивно проверить пары. Это алгоритм O (n 2 * log log n / log n), более быстрый, чем O (n 2 ). К сожалению, «На тройках ...» есть на Springer - но первая страница доступна, и экспозиция Бена Грина доступна здесь , страница 28, теорема 24.

Кстати, газеты принадлежат 1999 году - в тот же год, что и первый, о котором я упоминал, поэтому, вероятно, в первом не упоминается этот результат.

35
17.10.2009 08:26:14
Отличный ответ, первый, который говорит что-то определенное об этой проблеме. Таким образом, канторовоподобное множество имеет n ^ 0,63 1 с, что означает, что алгоритм «проверить все пары 1 с» равен по меньшей мере n ^ 1,26 (log n log n) в худшем случае. Нижняя граница, указанная в статье Семереди (кстати, статья Мозера, которую он цитирует, доступна здесь: books.google.com/books?id=Cvtwu5vVZF4C&pg=PA245 ), по-видимому, фактически подразумевает n ^ (2-o (1)), но мы должны быть немного осторожнее, потому что там у нас есть числа, взятые из {1, ..., n}, но здесь это сумма чисел в последовательности, которая равна n.
ShreevatsaR 18.10.2009 08:31:53
Э-э, что именно представляет собой двоичная последовательность типа Кантора, в которой содержится n ^ (log_3 2) 1, а не три равномерно распределенные 1?
ShreevatsaR 18.10.2009 08:46:13
Пример: 101000101000000000101000101. Его длина составляет 3 ^ n, и имеет 2 ^ n (так что плотность n ^ 0,63). Если вы запишите места 1 в двоичном виде, это будет {0,2,20,22,200,202,220,222}. Другой возможный способ думать об этом - взять последовательность единиц и непрерывно удалять «средние», как в обычной конструкции набора Кантора: 111111111 -> 111000111 -> 101000101. Причина, по которой он не содержит арифметическую прогрессию: if x , y, z образовали единицу, тогда y = (x + z) / 2 и x и z различаются в некотором месте расширения. Возьмите самый важный. Скажем, x имеет 0, а z имеет 2. Тогда у должно быть 1 там. противоречие.
sdcvvc 18.10.2009 09:40:15
Опять отличное исследование! Я продолжил работу над документом 3SUM 2008 года, и в нем упоминалось упражнение CLRS. 30.1-7, после просмотра которого я получил ответ - алгоритм O (n log n) на самом деле довольно прост! (Просто возводя в квадрат полиномиальную / производящую функцию.) Я разместил ответ ниже. (Теперь я не могу
ShreevatsaR 18.10.2009 16:36:58
Таким образом, ответ на его экзаменационный вопрос был что-то вроде: «Эта проблема сводится к сложной задаче 3-SUM, а сложная 3-SUM не имеет субквадратичного решения, поэтому эта задача не может быть решена в O (n logn). " Да?
hughdbrown 18.10.2009 18:57:19

Хорошо, я собираюсь сделать еще один удар по проблеме. Я думаю, что могу доказать алгоритм O (n log (n)), который похож на те, которые уже обсуждались, используя сбалансированное двоичное дерево для хранения расстояний между единицами. Этот подход был вдохновлен наблюдением Джастиса о сокращении проблемы до списка расстояний между единицами.

Можем ли мы отсканировать входную строку, чтобы построить сбалансированное двоичное дерево вокруг позиции 1, чтобы каждый узел сохранял позицию 1, а каждое ребро обозначалось расстоянием до смежной 1 для каждого дочернего узла. Например:

10010001 gives the following tree

      3
     / \
  2 /   \ 3
   /     \
  0       7

Это можно сделать в O (n log (n)), поскольку для строки размера n каждая вставка принимает O (log (n)) в худшем случае.

Тогда проблема заключается в поиске дерева, чтобы определить, есть ли в каком-либо узле путь от этого узла до левого потомка, который имеет то же расстояние, что и путь через правый потомок. Это может быть сделано рекурсивно на каждом поддереве. При объединении двух поддеревьев в поиске мы должны сравнить расстояния от путей в левом поддереве с расстояниями от путей в правом. Поскольку число путей в поддереве будет пропорционально log (n), а количество узлов равно n, я считаю, что это можно сделать за O (n log (n)).

Я что-то пропустил?

1
16.10.2009 18:44:09
«Так как число путей в поддереве будет пропорционально log (n)», почему не n? Вообще это перспективный подход.
sdcvvc 16.10.2009 18:50:38
@sdcwc: это пропорционально log (n), а не n, потому что в сбалансированном дереве каждое поддерево имеет половину узлов, а количество путей к корню поддерева такое же, как количество узлов в поддереве (исключая корень).
Jeremy Bourque 16.10.2009 19:08:40

Редакция: 2009-10-17 23:00

Я запустил это на больших числах (например, строки 20 миллионов), и теперь я считаю, что этот алгоритм не O (n logn). Несмотря на это, это достаточно классная реализация и содержит ряд оптимизаций, которые делают ее действительно быстрой. Он оценивает все расположения двоичных строк 24 или менее цифр менее чем за 25 секунд.

Я обновил код, чтобы включить 0 <= L < M < U <= X-1наблюдение, сделанное ранее сегодня.


оригинал

По сути, это похоже на другой вопрос, на который я ответил . Этот код также просматривал три значения в серии и определял, удовлетворяет ли триплет условию. Вот код C #, адаптированный из этого:

using System;
using System.Collections.Generic;

namespace StackOverflow1560523
{
    class Program
    {
        public struct Pair<T>
        {
            public T Low, High;
        }
        static bool FindCandidate(int candidate, 
            List<int> arr, 
            List<int> pool, 
            Pair<int> pair, 
            ref int iterations)
        {
            int lower = pair.Low, upper = pair.High;
            while ((lower >= 0) && (upper < pool.Count))
            {
                int lowRange = candidate - arr[pool[lower]];
                int highRange = arr[pool[upper]] - candidate;
                iterations++;
                if (lowRange < highRange)
                    lower -= 1;
                else if (lowRange > highRange)
                    upper += 1;
                else
                    return true;
            }
            return false;
        }
        static List<int> BuildOnesArray(string s)
        {
            List<int> arr = new List<int>();
            for (int i = 0; i < s.Length; i++)
                if (s[i] == '1')
                    arr.Add(i);
            return arr;
        }
        static void BuildIndexes(List<int> arr, 
            ref List<int> even, ref List<int> odd, 
            ref List<Pair<int>> evenIndex, ref List<Pair<int>> oddIndex)
        {
            for (int i = 0; i < arr.Count; i++)
            {
                bool isEven = (arr[i] & 1) == 0;
                if (isEven)
                {
                    evenIndex.Add(new Pair<int> {Low=even.Count-1, High=even.Count+1});
                    oddIndex.Add(new Pair<int> {Low=odd.Count-1, High=odd.Count});
                    even.Add(i);
                }
                else
                {
                    oddIndex.Add(new Pair<int> {Low=odd.Count-1, High=odd.Count+1});
                    evenIndex.Add(new Pair<int> {Low=even.Count-1, High=even.Count});
                    odd.Add(i);
                }
            }
        }

        static int FindSpacedOnes(string s)
        {
            // List of indexes of 1s in the string
            List<int> arr = BuildOnesArray(s);
            //if (s.Length < 3)
            //    return 0;

            //  List of indexes to odd indexes in arr
            List<int> odd = new List<int>(), even = new List<int>();

            //  evenIndex has indexes into arr to bracket even numbers
            //  oddIndex has indexes into arr to bracket odd numbers
            List<Pair<int>> evenIndex = new List<Pair<int>>(), 
                oddIndex = new List<Pair<int>>(); 
            BuildIndexes(arr, 
                ref even, ref odd, 
                ref evenIndex, ref oddIndex);

            int iterations = 0;
            for (int i = 1; i < arr.Count-1; i++)
            {
                int target = arr[i];
                bool found = FindCandidate(target, arr, odd, oddIndex[i], ref iterations) || 
                    FindCandidate(target, arr, even, evenIndex[i], ref iterations);
                if (found)
                    return iterations;
            }
            return iterations;
        }
        static IEnumerable<string> PowerSet(int n)
        {
            for (long i = (1L << (n-1)); i < (1L << n); i++)
            {
                yield return Convert.ToString(i, 2).PadLeft(n, '0');
            }
        }
        static void Main(string[] args)
        {
            for (int i = 5; i < 64; i++)
            {
                int c = 0;
                string hardest_string = "";
                foreach (string s in PowerSet(i))
                {
                    int cost = find_spaced_ones(s);
                    if (cost > c)
                    {
                        hardest_string = s;
                        c = cost;
                        Console.Write("{0} {1} {2}\r", i, c, hardest_string);
                    }
                }
                Console.WriteLine("{0} {1} {2}", i, c, hardest_string);
            }
        }
    }
}

Принципиальные различия:

  1. Исчерпывающий поиск решений
    Этот код генерирует мощный набор данных, чтобы найти самый сложный вход для решения этого алгоритма.
  2. Все решения по сравнению с трудными для решения
    Код предыдущего вопроса сгенерировал все решения с использованием генератора Python. Этот код просто отображает самое сложное для каждой длины шаблона.
  3. Алгоритм оценки
    Этот код проверяет расстояние от среднего элемента до его левого и правого края. Код Python проверял, была ли сумма выше или ниже 0.
  4. Сходимость по кандидату
    Текущий код работает от середины к краю, чтобы найти кандидата. Код в предыдущей задаче работал от краев к середине. Это последнее изменение дает значительное улучшение производительности.
  5. Использование четных и нечетных пулов
    На основании наблюдений в конце этой записи код ищет пары четных чисел пар нечетных чисел, чтобы найти L и U, сохраняя M фиксированным. Это уменьшает количество поисков путем предварительного вычисления информации. Соответственно, код использует два уровня косвенности в основном цикле FindCandidate и требует двух вызовов FindCandidate для каждого среднего элемента: один раз для четных чисел и один раз для нечетных.

Общая идея состоит в том, чтобы работать с индексами, а не с необработанным представлением данных. Вычисление массива, в котором появляются единицы, позволяет алгоритму работать во времени, пропорциональном количеству единиц в данных, а не во времени, пропорциональном длине данных. Это стандартное преобразование: создайте структуру данных, которая позволит быстрее работать, сохраняя при этом эквивалентность задачи.

Результаты устарели: удалены.


Изменить: 2009-10-16 18:48

На данных yx, которым доверяют другие ответы как репрезентативные данные для вычисления, я получаю эти результаты ... Я удалил их. Они устарели.

Я хотел бы отметить, что эти данные не самые сложные для моего алгоритма, поэтому я считаю, что предположение о том, что фракталы yx труднее всего решить, ошибочно. Я ожидаю, что наихудший случай для конкретного алгоритма будет зависеть от самого алгоритма и вряд ли будет согласован для разных алгоритмов.


Изменить: 2009-10-17 13:30

Дальнейшие наблюдения по этому вопросу.

Сначала преобразуйте строку из 0 и 1 в массив индексов для каждой позиции 1. Скажем, длина этого массива A равна X. Тогда цель состоит в том, чтобы найти

0 <= L < M < U <= X-1

такой, что

A[M] - A[L] = A[U] - A[M]

или

2*A[M] = A[L] + A[U]

Поскольку A [L] и A [U] суммируются с четным числом, они не могут быть (четными, нечетными) или (нечетными, четными). Поиск совпадения можно улучшить, разбив A [] на нечетные и четные пулы и ища совпадения на A [M] в пулах нечетных и четных кандидатов по очереди.

Однако это скорее оптимизация производительности, чем алгоритмическое улучшение. Количество сравнений должно уменьшиться, но порядок алгоритма должен быть таким же.


Изменить 2009-10-18 00:45

Еще одна оптимизация происходит со мной в том же духе, что и разделение кандидатов на четных и нечетных. Поскольку три индекса нужно добавить к кратному 3 (a, a + x, a + 2x - mod 3 равно 0, независимо от a и x), вы можете разделить L, M и U на их значения mod 3 :

M  L  U
0  0  0
   1  2
   2  1
1  0  2
   1  1
   2  0
2  0  1
   1  0
   2  2

На самом деле, вы можете объединить это с четным / нечетным наблюдением и разделить их на значения мод 6:

M  L  U
0  0  0
   1  5
   2  4
   3  3
   4  2
   5  1

и так далее. Это обеспечило бы дальнейшую оптимизацию производительности, но не алгоритмическое ускорение.

3
23.05.2017 11:55:13

Я думал, что добавлю один комментарий, прежде чем публиковать 22-е наивное решение проблемы. Для наивного решения нам не нужно показывать, что число 1 в строке не более O (log (n)), а скорее всего O (sqrt (n * log (n))).

Решение:

def solve(Str):
    indexes=[]
    #O(n) setup
    for i in range(len(Str)):
        if Str[i]=='1':
            indexes.append(i)

    #O((number of 1's)^2) processing
    for i in range(len(indexes)):
        for j in range(i+1, len(indexes)):
                            indexDiff = indexes[j] - indexes[i]
            k=indexes[j] + indexDiff
            if k<len(Str) and Str[k]=='1':
                return True
    return False

По сути, это немного похоже на идею и реализацию flybywire, хотя и смотрит вперед, а не назад.

Жадный струнный строитель:

#assumes final char hasn't been added, and would be a 1 
def lastCharMakesSolvable(Str):
    endIndex=len(Str)
    j=endIndex-1
    while j-(endIndex-j) >= 0:
        k=j-(endIndex-j)
        if k >= 0 and Str[k]=='1' and Str[j]=='1':
            return True
        j=j-1
    return False



def expandString(StartString=''):
    if lastCharMakesSolvable(StartString):
        return StartString + '0'
    return StartString + '1'

n=1
BaseStr=""
lastCount=0
while n<1000000:
    BaseStr=expandString(BaseStr)
    count=BaseStr.count('1')
    if count != lastCount:
        print(len(BaseStr), count)
    lastCount=count
    n=n+1

(В свою защиту, я все еще нахожусь в стадии понимания "учить питона")

Кроме того, потенциально полезный вывод из жадного построения строк, есть довольно последовательный скачок после попадания степени 2 в число 1 ... которого я не хотел ждать, чтобы засвидетельствовать попадание в 2096.

strlength   # of 1's
    1    1
    2    2
    4    3
    5    4
   10    5
   14    8
   28    9
   41    16
   82    17
  122    32
  244    33
  365    64
  730    65
 1094    128
 2188    129
 3281    256
 6562    257
 9842    512
19684    513
29525    1024
0
16.10.2009 23:06:26

Я постараюсь представить математический подход. Это скорее начало, чем конец, поэтому любая помощь, комментарии или даже противоречия будут высоко оценены. Однако, если такой подход доказан - алгоритм представляет собой простой поиск в строке.

  1. Для фиксированного числа пробелов kи строки Sпоиск k-пространственного триплета занимает O(n)- мы просто проверяем каждое 0<=i<=(n-2k)if S[i]==S[i+k]==S[i+2k]. Тест проходит, O(1)и мы делаем это n-kраз, где kесть константа, поэтому она принимает O(n-k)=O(n).

  2. Давайте предположим, что существует обратная пропорция между числом 1's' и максимальным пространством, которое мы должны искать. То есть, если их много 1, должен быть триплет, и он должен быть достаточно плотным; Если их всего несколько 1, триплет (если есть) может быть довольно разреженным. Другими словами, я могу доказать, что если мне достаточно 1, такой триплет должен существовать - и чем больше 1у меня, тем более плотный триплет должен быть найден. Это может быть объяснено принципом Pigeonhole - Надеюсь уточнить это позже.

  3. Скажем, есть верхняя граница kвозможного количества пробелов, которые мне нужно искать. Теперь для каждого 1расположенного в S[i]нам нужно проверить 1в S[i-1]и S[i+1], S[i-2]и S[i+2], ..., S[i-k]и S[i+k]. Это требуется O((k^2-k)/2)=O(k^2)для каждого 1в S- из-за формулы суммирования серии Гаусса . Обратите внимание, что это отличается от раздела 1 - я имею kв качестве верхней границы для числа пробелов, а не как постоянный пробел.

Нам нужно доказать O(n*log(n)). То есть нам нужно показать, что k*(number of 1's)пропорционально log(n).

Если мы можем сделать это, алгоритм тривиален - для каждого 1в Sчей индекс i, просто искать 1«S с каждой стороны до расстояния k. Если два были найдены на одном расстоянии, верните iи k. Снова, сложная часть должна была бы найти kи доказать правильность.

Буду очень признателен за ваши комментарии здесь - я пытался найти связь между kчислом и числом 1на моей доске, но пока безуспешно.

0
16.10.2009 23:50:21

Ниже приведено решение. Там и там могут быть небольшие ошибки, но идея здравая.

Изменить: это не п * журнал (п)

КОД ПСЕВДО:

foreach character in the string
  if the character equals 1 {         
     if length cache > 0 { //we can skip the first one
        foreach location in the cache { //last in first out kind of order
           if ((currentlocation + (currentlocation - location)) < length string)
              if (string[(currentlocation + (currentlocation - location))] equals 1)
                 return found evenly spaced string
           else
              break;
        }
     }
     remember the location of this character in a some sort of cache.
  }

return didn't find evenly spaced string

Код C #:

public static Boolean FindThreeEvenlySpacedOnes(String str) {
    List<int> cache = new List<int>();

    for (var x = 0; x < str.Length; x++) {
        if (str[x] == '1') {
            if (cache.Count > 0) {
                for (var i = cache.Count - 1; i > 0; i--) {
                    if ((x + (x - cache[i])) >= str.Length)
                        break;

                    if (str[(x + (x - cache[i]))] == '1')
                        return true;                            
                }
            }
            cache.Add(x);                    
        }
    }

    return false;
}

Как это работает:

iteration 1:
x
|
101101001
// the location of this 1 is stored in the cache

iteration 2:
 x
 | 
101101001

iteration 3:
a x b 
| | | 
101101001
//we retrieve location a out of the cache and then based on a 
//we calculate b and check if te string contains a 1 on location b

//and of course we store x in the cache because it's a 1

iteration 4:
  axb  
  |||  
101101001

a  x  b  
|  |  |  
101101001


iteration 5:
    x  
    |  
101101001

iteration 6:
   a x b 
   | | | 
101101001

  a  x  b 
  |  |  | 
101101001
//return found evenly spaced string
0
17.10.2009 18:09:49
Ваш алгоритм работает, но вам нужно доказать, что он меньше O (n ^ 2). Тривиальный анализ приводит вас к O (n ^ 2). Для каждого 1 вы проходите все 1, которые были до него. Делаем функцию сложности 1 + 2 + 3 + ... + (k / 2-1) = O (k ^ 2) [где k - число 1 с].
Anna 17.10.2009 13:49:23
Я проверил, и действительно, худший сценарий без решения больше, чем O (n * log (n))
Niek H. 17.10.2009 18:08:56

Как насчет простого решения O (n) с пространством O (n ^ 2)? (Используется предположение, что все побитовые операторы работают в O (1).)

Алгоритм в основном работает в четыре этапа:

Этап 1: для каждого бита в вашем исходном числе выясните, как далеко они находятся, но примите во внимание только одно направление. (Я рассмотрел все биты в направлении младшего значащего бита.)

Этап 2: обратный порядок битов на входе;

Этап 3: повторите шаг 1 на обратном входе.

Стадия 4: Сравните результаты Стадии 1 и Стадии 3. Если какие-либо биты находятся на одинаковом расстоянии выше И ниже, у нас должен быть удар.

Имейте в виду, что ни один шаг в вышеприведенном алгоритме не занимает больше времени, чем O (n). ^ _ ^

В качестве дополнительного преимущества этот алгоритм найдет ВСЕ одинаково расположенные из КАЖДОГО числа. Так, например, если вы получите результат «0x0005», то в равном расстоянии 1 и 3 единицы

Я действительно не пытался оптимизировать код ниже, но это компилируемый код C #, который, кажется, работает.

using System;

namespace ThreeNumbers
{
    class Program
    {
        const int uint32Length = 32;

        static void Main(string[] args)
        {
            Console.Write("Please enter your integer: ");
            uint input = UInt32.Parse(Console.ReadLine());

            uint[] distancesLower = Distances(input);
            uint[] distancesHigher = Distances(Reverse(input));

            PrintHits(input, distancesLower, distancesHigher);
        }

        /// <summary>
        /// Returns an array showing how far the ones away from each bit in the input.  Only 
        /// considers ones at lower signifcant bits.  Index 0 represents the least significant bit 
        /// in the input.  Index 1 represents the second least significant bit in the input and so 
        /// on.  If a one is 3 away from the bit in question, then the third least significant bit 
        /// of the value will be sit.
        /// 
        /// As programed this algorithm needs: O(n) time, and O(n*log(n)) space.  
        /// (Where n is the number of bits in the input.)
        /// </summary>
        public static uint[] Distances(uint input)
        {
            uint[] distanceToOnes = new uint[uint32Length];
            uint result = 0;

            //Sets how far each bit is from other ones. Going in the direction of LSB to MSB
            for (uint bitIndex = 1, arrayIndex = 0; bitIndex != 0; bitIndex <<= 1, ++arrayIndex)
            {
                distanceToOnes[arrayIndex] = result;
                result <<= 1;

                if ((input & bitIndex) != 0)
                {
                    result |= 1;
                }
            }

            return distanceToOnes;
        }

        /// <summary>
        /// Reverses the bits in the input.
        /// 
        /// As programmed this algorithm needs O(n) time and O(n) space.  
        /// (Where n is the number of bits in the input.)
        /// </summary>
        /// <param name="input"></param>
        /// <returns></returns>
        public static uint Reverse(uint input)
        {
            uint reversedInput = 0;
            for (uint bitIndex = 1; bitIndex != 0; bitIndex <<= 1)
            {
                reversedInput <<= 1;
                reversedInput |= (uint)((input & bitIndex) != 0 ? 1 : 0);
            }

            return reversedInput;
        }

        /// <summary>
        /// Goes through each bit in the input, to check if there are any bits equally far away in 
        /// the distancesLower and distancesHigher
        /// </summary>
        public static void PrintHits(uint input, uint[] distancesLower, uint[] distancesHigher)
        {
            const int offset = uint32Length - 1;

            for (uint bitIndex = 1, arrayIndex = 0; bitIndex != 0; bitIndex <<= 1, ++arrayIndex)
            {
                //hits checks if any bits are equally spaced away from our current value
                bool isBitSet = (input & bitIndex) != 0;
                uint hits = distancesLower[arrayIndex] & distancesHigher[offset - arrayIndex];

                if (isBitSet && (hits != 0))
                {
                    Console.WriteLine(String.Format("The {0}-th LSB has hits 0x{1:x4} away", arrayIndex + 1, hits));
                }
            }
        }
    }
}

Кто-то, вероятно, прокомментирует, что для любого достаточно большого числа побитовые операции не могут быть выполнены в O (1). Ты был бы прав. Тем не менее, я бы предположил, что каждое решение, которое использует сложение, вычитание, умножение или деление (что не может быть сделано путем сдвига) также будет иметь эту проблему.

0
17.10.2009 10:25:59

Очевидно, что нам нужно по крайней мере проверять связки триплетов одновременно, поэтому нам нужно как-то сжать проверки. У меня есть алгоритм-кандидат, но анализ сложности времени выходит за рамки моих возможностей * временной порог.

Постройте дерево, в котором у каждого узла есть три дочерних элемента, и каждый узел содержит общее количество единиц на своих листьях. Создайте связанный список на 1, а также. Назначьте каждому узлу разрешенную стоимость, пропорциональную диапазону, который он охватывает. Пока время, которое мы проводим в каждом узле, находится в пределах бюджета, у нас будет алгоритм O (n lg n).

-

Начните с корня. Если квадрат из общего числа 1 ниже, чем его разрешенная стоимость, примените наивный алгоритм. В противном случае рециркулировать на своих детей.

Теперь мы либо вернулись в рамках бюджета, либо знаем, что в одном из дочерних элементов нет действительных триплетов. Поэтому мы должны проверить триузлы между узлами.

Теперь все становится невероятно грязным. По сути, мы хотим использовать потенциальные наборы детей, ограничивая диапазон. Как только диапазон достаточно ограничен, чтобы наивный алгоритм работал в рамках бюджета, вы делаете это. Наслаждайтесь этим, потому что я гарантирую, что это будет утомительно. Там как десяток дел.

-

Причина, по которой я думаю, что алгоритм будет работать, состоит в том, что последовательности без действительных триплетов, кажется, чередуются между группами 1 и партиями 0. Он эффективно разделяет близлежащее пространство поиска, и дерево имитирует это разделение.

Время выполнения алгоритма совсем не очевидно. Он опирается на нетривиальные свойства последовательности. Если 1 действительно редки, то наивный алгоритм будет работать в рамках бюджета. Если 1 плотные, то совпадение должно быть найдено сразу. Но если плотность «просто правильная» (например, около ~ n ^ 0,63, чего можно добиться, установив все биты в позиции без цифры «2» в базе 3), я не знаю, будет ли это работать. Вы должны доказать, что эффект расщепления достаточно силен.

0
17.10.2009 18:22:39

Никакого теоретического ответа здесь нет, но я написал быструю Java-программу для изучения поведения во время выполнения в зависимости от k и n, где n - общая длина бита, а k - число единиц. Я с несколькими из ответчиков, которые говорят, что «обычный» алгоритм, который проверяет все пары позиций битов и ищет 3-й бит, даже если для него потребуется O (k ^ 2) в худшем случае, в реальность, потому что в худшем случае нужны разреженные цепочки битов, это O (n ln n).

В любом случае, вот программа, ниже. Это программа в стиле Монте-Карло, которая запускает большое количество испытаний NTRIALS для константы n и случайным образом генерирует наборы битов для диапазона значений k, используя процессы Бернулли с ограничениями плотности единиц, которые могут быть заданы, и записывает время выполнения. обнаружение или невозможность найти триплет из равномерно распределенных единиц, время измеряется в шагах, а не во времени ЦП. Я запустил его для n = 64, 256, 1024, 4096, 16384 * (все еще выполняется), сначала тестовый прогон с 500000 испытаний, чтобы увидеть, какие значения k занимают самое продолжительное время работы, затем другой тест с 5000000 тестами с суженными- сосредоточиться на плотности, чтобы увидеть, как эти значения выглядят. Самые длинные времена пробега случаются с очень разреженной плотностью (например, для n = 4096 пики времени пробега находятся в диапазоне k = 16-64, с небольшим пиком для среднего времени пробега при 4212 шагах при k = 31, максимальное время работы достигло 5101 шагов при k = 58). Похоже, что для шага O (k ^ 2) в худшем случае потребовалось бы чрезвычайно большое значение N, чтобы стать больше шага O (n), когда вы сканируете цепочку битов, чтобы найти индексы позиции 1.

package com.example.math;

import java.io.PrintStream;
import java.util.BitSet;
import java.util.Random;

public class EvenlySpacedOnesTest {
    static public class StatisticalSummary
    {
        private int n=0;
        private double min=Double.POSITIVE_INFINITY;
        private double max=Double.NEGATIVE_INFINITY;
        private double mean=0;
        private double S=0;

        public StatisticalSummary() {}
        public void add(double x) {
            min = Math.min(min, x);
            max = Math.max(max, x);
            ++n;
            double newMean = mean + (x-mean)/n;
            S += (x-newMean)*(x-mean);
            // this algorithm for mean,std dev based on Knuth TAOCP vol 2
            mean = newMean;
        }
        public double getMax() { return (n>0)?max:Double.NaN; }
        public double getMin() { return (n>0)?min:Double.NaN; }
        public int getCount() { return n; }
        public double getMean() { return (n>0)?mean:Double.NaN; }
        public double getStdDev() { return (n>0)?Math.sqrt(S/n):Double.NaN; } 
        // some may quibble and use n-1 for sample std dev vs population std dev    
        public static void printOut(PrintStream ps, StatisticalSummary[] statistics) {
            for (int i = 0; i < statistics.length; ++i)
            {
                StatisticalSummary summary = statistics[i];
                ps.printf("%d\t%d\t%.0f\t%.0f\t%.5f\t%.5f\n",
                        i,
                        summary.getCount(),
                        summary.getMin(),
                        summary.getMax(),
                        summary.getMean(),
                        summary.getStdDev());
            }
        }
    }

    public interface RandomBernoulliProcess // see http://en.wikipedia.org/wiki/Bernoulli_process
    {
        public void setProbability(double d);
        public boolean getNextBoolean();
    }

    static public class Bernoulli implements RandomBernoulliProcess
    {
        final private Random r = new Random();
        private double p = 0.5;
        public boolean getNextBoolean() { return r.nextDouble() < p; }
        public void setProbability(double d) { p = d; }
    }   
    static public class TestResult {
        final public int k;
        final public int nsteps;
        public TestResult(int k, int nsteps) { this.k=k; this.nsteps=nsteps; } 
    }

    ////////////
    final private int n;
    final private int ntrials;
    final private double pmin;
    final private double pmax;
    final private Random random = new Random();
    final private Bernoulli bernoulli = new Bernoulli();
    final private BitSet bits;
    public EvenlySpacedOnesTest(int n, int ntrials, double pmin, double pmax) {
        this.n=n; this.ntrials=ntrials; this.pmin=pmin; this.pmax=pmax;
        this.bits = new BitSet(n);
    }

    /*
     * generate random bit string
     */
    private int generateBits()
    {
        int k = 0; // # of 1's
        for (int i = 0; i < n; ++i)
        {
            boolean b = bernoulli.getNextBoolean();
            this.bits.set(i, b);
            if (b) ++k;
        }
        return k;
    }

    private int findEvenlySpacedOnes(int k, int[] pos) 
    {
        int[] bitPosition = new int[k];
        for (int i = 0, j = 0; i < n; ++i)
        {
            if (this.bits.get(i))
            {
                bitPosition[j++] = i;
            }
        }
        int nsteps = n; // first, it takes N operations to find the bit positions.
        boolean found = false;
        if (k >= 3) // don't bother doing anything if there are less than 3 ones. :(
        {       
            int lastBitSetPosition = bitPosition[k-1];
            for (int j1 = 0; !found && j1 < k; ++j1)
            {
                pos[0] = bitPosition[j1];
                for (int j2 = j1+1; !found && j2 < k; ++j2)
                {
                    pos[1] = bitPosition[j2];

                    ++nsteps;
                    pos[2] = 2*pos[1]-pos[0];
                    // calculate 3rd bit index that might be set;
                    // the other two indices point to bits that are set
                    if (pos[2] > lastBitSetPosition)
                        break;
                    // loop inner loop until we go out of bounds

                    found = this.bits.get(pos[2]);
                    // we're done if we find a third 1!
                }
            }
        }
        if (!found)
            pos[0]=-1;
        return nsteps;
    }

    /*
     * run an algorithm that finds evenly spaced ones and returns # of steps.
     */
    public TestResult run()
    {
        bernoulli.setProbability(pmin + (pmax-pmin)*random.nextDouble());
        // probability of bernoulli process is randomly distributed between pmin and pmax

        // generate bit string.
        int k = generateBits();
        int[] pos = new int[3];
        int nsteps = findEvenlySpacedOnes(k, pos);
        return new TestResult(k, nsteps); 
    }

    public static void main(String[] args)
    {
        int n;
        int ntrials;
        double pmin = 0, pmax = 1;
        try {
            n = Integer.parseInt(args[0]);
            ntrials = Integer.parseInt(args[1]);
            if (args.length >= 3)
                pmin = Double.parseDouble(args[2]);
            if (args.length >= 4)
                pmax = Double.parseDouble(args[3]);
        }
        catch (Exception e)
        {
            System.out.println("usage: EvenlySpacedOnesTest N NTRIALS [pmin [pmax]]");
            System.exit(0);
            return; // make the compiler happy
        }

        final StatisticalSummary[] statistics;
        statistics=new StatisticalSummary[n+1];
        for (int i = 0; i <= n; ++i)
        {
            statistics[i] = new StatisticalSummary();
        }

        EvenlySpacedOnesTest test = new EvenlySpacedOnesTest(n, ntrials, pmin, pmax);
        int printInterval=100000;
        int nextPrint = printInterval;
        for (int i = 0; i < ntrials; ++i)
        {
            TestResult result = test.run();
            statistics[result.k].add(result.nsteps);
            if (i == nextPrint)
            {
                System.err.println(i);
                nextPrint += printInterval;
            }
        }
        StatisticalSummary.printOut(System.out, statistics);
    }
}
0
18.10.2009 15:26:01