|
Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения |
22.10.2005, 01:50
|
#1
|
ПроЭктировщик
Регистрация: 10.10.2005
Сообщений: 102
Написано 2 полезных сообщений (для 2 пользователей)
|
Мне сегодня в универе продложил препод задачу.
Есть одномерный массив из 1000 символов (любых, буквы, цифры) в любом порядке (могут повторятся). Надо взять первые 5 символов и проверить есть ли такие же комбинации где нить в массиве ещё.
Я ему предложыл 2 способа решения:
1. взять первые 5 символов и передвигать их на одну позицию сравнивая. Так сказать "перебрать массив"
2. Создать базу данных и занести все возможные варианты в базу. Ну и естественно сравнить с первой 5-ой.
Препод конечно одобрил мой ход мышления, НО попросил проверить какой способ быстрее! На любом языке, на мой выбор.
Так, допустим я все создал, загнал, проверил, нашол.
Ну и наконец вопрос: Как посчитать затраченное время на поиск сравнений?
|
(Offline)
|
|
22.10.2005, 02:06
|
#2
|
|
Продемонстрирую на примере использования команд Блица.
Создаешь 2 переменные: time_start и time_end.
Далее так:
;присваиваешь первой переменной текущее время в миллисекундах:
time_start=Millisecs()
;...
;выполняется алгоритм
;...
;присваиваешь второй переменной текущее время в миллисекундах:
time_end=Millisecs()
;считаешь, сколько затрачено времени
result = time_end - time_start
|
|
|
22.10.2005, 02:18
|
#3
|
Зануда с интернетом
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений (для 20,935 пользователей)
|
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
|
(Offline)
|
|
22.10.2005, 02:38
|
#4
|
ПроЭктировщик
Регистрация: 10.10.2005
Сообщений: 102
Написано 2 полезных сообщений (для 2 пользователей)
|
Огромный сенькс.
Вследующий раз сначало в поиск
|
(Offline)
|
|
22.10.2005, 04:00
|
#5
|
Администратор
Регистрация: 03.09.2005
Сообщений: 2,408
Написано 301 полезных сообщений (для 996 пользователей)
|
Originally posted by Lexa@Oct 22 2005, 12:38 AM
Огромный сенькс.
Вследующий раз сначало в поиск
|
необязательно
__________________
Как минимум я помог многим (с)
|
(Offline)
|
|
22.10.2005, 13:30
|
#6
|
ПроЭктировщик
Регистрация: 04.09.2005
Сообщений: 139
Написано одно полезное сообщение
|
Я ему предложыл 2 способа решения:
1. взять первые 5 символов и передвигать их на одну позицию сравнивая. Так сказать "перебрать массив"
2. Создать базу данных и занести все возможные варианты в базу. Ну и естественно сравнить с первой 5-ой.
|
а препод приколист у вас теория вероятности уже была или нет?
количество вариантов при втором методе решения:
4,02387260077093773543702433923e+2567 (число с 2567-ю нулями )
угадай, такая программа успеет выполниться за твою жизнь?
/на самом деле не знаю, можешь проверить. но в любом случае это очень долго. и тупо. и памяти сожрет... хм... представил? /
|
(Offline)
|
|
22.10.2005, 14:45
|
#7
|
|
наш препод мечтает составить таблицу md5hashей )
~255^16
|
|
|
Сообщение было полезно следующим пользователям:
|
|
22.10.2005, 14:51
|
#8
|
ПроЭктировщик
Регистрация: 10.10.2005
Сообщений: 102
Написано 2 полезных сообщений (для 2 пользователей)
|
Он просто хотел показать что 2 способ быстрее и удобней (хотя я немного сомневаюсь)
|
(Offline)
|
|
22.10.2005, 22:35
|
#9
|
ПроЭктировщик
Регистрация: 04.09.2005
Сообщений: 139
Написано одно полезное сообщение
|
Он просто хотел показать что 2 способ быстрее и удобней (хотя я немного сомневаюсь)
|
1-й способ лучше. я надеюсь, ты просто опечатался, а не невнимательно читал тему?
|
(Offline)
|
|
22.10.2005, 22:59
|
#10
|
|
а не невнимательно читал тему?
|
логическое преобразование : "а внимательно читал тему?"
не + не = 0
не * не = 0
мат.лог. operation
|
|
|
25.10.2005, 00:27
|
#11
|
ПроЭктировщик
Регистрация: 10.10.2005
Сообщений: 102
Написано 2 полезных сообщений (для 2 пользователей)
|
Это он (препод) сказал что 2-ой способ лучше. Я же считаю что 1-ый проще и лучше.
|
(Offline)
|
|
25.10.2005, 01:05
|
#12
|
ПроЭктировщик
Регистрация: 04.09.2005
Сообщений: 139
Написано одно полезное сообщение
|
Это он (препод) сказал что 2-ой способ лучше. Я же считаю что 1-ый проще и лучше.
|
составить все варианты??? хм, если ты так упорно это повторяешь, будем тебе верить где такие преподы водятся? всегда Россия была креепка задним местом, но чтобы настолько... я бы с этим "преподом" на ящик пива поспорил сразу бы. или на "автомат" до конца курса только зассыт, гад
PS. хотя по зрелому размышлению я не исключаю того варианта, что вы друг друга просто не поняли. ибо составлять все возможные комбинации 1000 символов - это одно (нафиг надо), а составлять комбинации из 5 символов и потом их двигать - это другое.
|
(Offline)
|
|
21.06.2009, 14:58
|
#13
|
Оператор ЭВМ
Регистрация: 09.10.2007
Сообщений: 45
Написано 8 полезных сообщений (для 16 пользователей)
|
Ответ: Интересный вопрос!
может я чего не понял, но найти надо повторяющуюся комбинацию из 5 символов. значит если символов 1000 то вариантов получится 1000-5= 995. и всего 4975 операция сравнения. ну 4995 если брать и с конца массива плавно переходить на начало (997-й, 998-й, 999-й, 1000-й, 1-й). а теперь можно еще взять и создать строковую переменную и в нее плюсовать 5 символов, которые нужно сравнить, чтобы повысить производительность. (это третий способ)
а если 5 символов которые нужно сравнивать с первыми 5 могут стоять не рядом, то тогда еще проще.
|
(Offline)
|
|
21.06.2009, 15:45
|
#14
|
Бывалый
Регистрация: 29.03.2007
Сообщений: 662
Написано 199 полезных сообщений (для 448 пользователей)
|
Ответ: Интересный вопрос!
Прошло всего ничего 4 года..
|
(Offline)
|
|
Эти 7 пользователя(ей) сказали Спасибо Android за это полезное сообщение:
|
|
Ваши права в разделе
|
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения
HTML код Выкл.
|
|
|
Часовой пояс GMT +4, время: 16:50.
|