Интересный вопрос!

[Lexa]

Мне сегодня в универе продложил препод задачу.
Есть одномерный массив из 1000 символов (любых, буквы, цифры) в любом порядке (могут повторятся). Надо взять первые 5 символов и проверить есть ли такие же комбинации где нить в массиве ещё.

Я ему предложыл 2 способа решения:
1. взять первые 5 символов и передвигать их на одну позицию сравнивая. Так сказать "перебрать массив"

2. Создать базу данных и занести все возможные варианты в базу. Ну и естественно сравнить с первой 5-ой.


Препод конечно одобрил мой ход мышления, НО попросил проверить какой способ быстрее! На любом языке, на мой выбор.

Так, допустим я все создал, загнал, проверил, нашол.

Ну и наконец вопрос: Как посчитать затраченное время на поиск сравнений?

Продемонстрирую на примере использования команд Блица.

Создаешь 2 переменные: time_start и time_end.
Далее так:

;присваиваешь первой переменной текущее время в миллисекундах:
time_start=Millisecs()

;...
;выполняется алгоритм
;...

;присваиваешь второй переменной текущее время в миллисекундах:
time_end=Millisecs()

;считаешь, сколько затрачено времени
result = time_end - time_start

[impersonalis]

Вот ещё примерчик
http://community.boolean.name/index.php?showtopic=122

[Lexa]

Огромный сенькс.
Вследующий раз сначало в поиск

[SubZer0]

Originally posted by Lexa@Oct 22 2005, 12:38 AM
Огромный сенькс.
Вследующий раз сначало в поиск

необязательно

[Jet]

Я ему предложыл 2 способа решения:
1. взять первые 5 символов и передвигать их на одну позицию сравнивая. Так сказать "перебрать массив"

2. Создать базу данных и занести все возможные варианты в базу. Ну и естественно сравнить с первой 5-ой.

а препод приколист у вас теория вероятности уже была или нет?

количество вариантов при втором методе решения:
4,02387260077093773543702433923e+2567 (число с 2567-ю нулями )
угадай, такая программа успеет выполниться за твою жизнь?
/на самом деле не знаю, можешь проверить. но в любом случае это очень долго. и тупо. и памяти сожрет... хм... представил? /

а препод приколист

наш препод мечтает составить таблицу md5hashей )
~255^16

[Lexa]

Он просто хотел показать что 2 способ быстрее и удобней (хотя я немного сомневаюсь)

[Jet]

Он просто хотел показать что 2 способ быстрее и удобней (хотя я немного сомневаюсь)

1-й способ лучше. я надеюсь, ты просто опечатался, а не невнимательно читал тему?

а не невнимательно читал тему?

логическое преобразование : "а внимательно читал тему?"

не + не = 0
не * не = 0

мат.лог. operation

[Lexa]

Это он (препод) сказал что 2-ой способ лучше. Я же считаю что 1-ый проще и лучше.

[Jet]

Это он (препод) сказал что 2-ой способ лучше. Я же считаю что 1-ый проще и лучше.

составить все варианты??? хм, если ты так упорно это повторяешь, будем тебе верить где такие преподы водятся? всегда Россия была креепка задним местом, но чтобы настолько... я бы с этим "преподом" на ящик пива поспорил сразу бы. или на "автомат" до конца курса только зассыт, гад

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

[cheaters-hater]

может я чего не понял, но найти надо повторяющуюся комбинацию из 5 символов. значит если символов 1000 то вариантов получится 1000-5= 995. и всего 4975 операция сравнения. ну 4995 если брать и с конца массива плавно переходить на начало (997-й, 998-й, 999-й, 1000-й, 1-й). а теперь можно еще взять и создать строковую переменную и в нее плюсовать 5 символов, которые нужно сравнить, чтобы повысить производительность. (это третий способ)

а если 5 символов которые нужно сравнивать с первыми 5 могут стоять не рядом, то тогда еще проще.

[Android]

Прошло всего ничего 4 года..