forum.boolean.name - Интересный вопрос!

forum.boolean.name (http://forum.boolean.name/index.php)

- Алгоритмика (http://forum.boolean.name/forumdisplay.php?f=21)

- - Интересный вопрос! (http://forum.boolean.name/showthread.php?t=235)

Lexa	22.10.2005 01:50

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

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

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

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

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

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

alcosholik

22.10.2005 02:06

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

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

Код:

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

time_start=Millisecs()



;...

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

;...



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

time_end=Millisecs()



;считаешь, сколько затрачено времени

result = time_end - time_start

impersonalis

22.10.2005 02:18

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

Lexa	22.10.2005 02:38

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

:@ :@

SubZer0

22.10.2005 04:00

Цитата:

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

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

Jet	22.10.2005 13:30

Цитата:

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

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

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

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

jimon

22.10.2005 14:45

Цитата:

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

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

Lexa	22.10.2005 14:51

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

Jet	22.10.2005 22:35

Цитата:

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

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

jimon

22.10.2005 22:59

Цитата:

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

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

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

мат.лог. operation :)

Lexa	25.10.2005 00:27

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

Jet	25.10.2005 01:05

Цитата:

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

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

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

cheaters-hater

21.06.2009 14:58

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

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

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

Android

21.06.2009 15:45

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

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

Часовой пояс GMT +4, время: 15:30.