0 и 1, Нужно узнать есть ли одинаковые цифры. |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
0 и 1, Нужно узнать есть ли одинаковые цифры. |
mihas |
Сообщение
#1
|
Гость |
ЗДравствуйте ребята программеры! Вот на днях мне препод дал задачу (сказал, что с какой то олимпиады). Условие таково:
Вводится строка из 0 и 1 (причем строка должна быть не более 1000 000 символов). Затем вводится начальная позиция (min) и конечная позиция(max). Вот и требуется узнать есть ли между заданными позициями (включая их самих) одинаковые числа, т.е. только 0 или только 1. С первого взгляда задача очень проста, но там есть одно условие: нужно, чтобы программа выполнялась не более двух секунд. Т.е. нужно придумать очень быстрый алгоритм проверки в заданном интервале. У меня же пока что получается 10 секундная прога, помогите сделать 2 секундную. Заранее благодарен. P.S.: я сделал прогу проверкой в лоб, т.е. берется начальный элемент (т.е. st[min], где st - это мой массив из 0 и1) строки и затем проверяется с каждым элементом до конечного (т.е. до st[max]) |
BlackShadow |
Сообщение
#2
|
Гость |
Я бы посоветовал удваивать интервал. Т. е. сначала сравнить первые 2 байта, затем первые две пары байт затем по 4 и т. д. При грамотной реализации может дать ускорение... Но это оптимизация скорее на уровне асма...
|
zx1024 |
Сообщение
#3
|
Пионер Группа: Пользователи Сообщений: 119 Пол: Мужской Репутация: 0 |
Все зависит от вида хранения данных (побитово или нет).
От прохода от min до max никуда не деться. Не хочется никого обижать, но может быть цикл прохода не оптимизирован ИМЕННО по времени. |
xds |
Сообщение
#4
|
N337 Группа: Пользователи Сообщений: 737 Пол: Мужской Репутация: 26 |
Я попробовал такой "предельно тупой" код:
Код program _0or1; var f: Text; c, c0: Char; Min, Max, i: LongInt; begin Assign(f, 'input.txt'); Reset(f); Readln(f, Min, Max); for i := 1 to Min do Read(f, c0); for i := 1 to Max - Min do begin Read(f, c); if c <> c0 then begin Writeln('Нет'); Close(f); Exit; end; end; Close(f); Writeln('Да'); end. Будучи откомпилирован на BP 7.0 и запущен на AMD K6-2 300 MHz он справляется с самым сложным случаем (1000000 проверок) за ~0.5 с. Компиляция с помощью FP дает примерно такой же результат. А может предельно тупой я сам: не смог разобраться в условии задачи... -------------------- The idiots are winning.
|
Atos |
Сообщение
#5
|
Прогрессор Группа: Пользователи Сообщений: 602 Пол: Мужской Реальное имя: Михаил Репутация: 9 |
Я бы посоветовал открывать файл не как текстовой, а как нетипизированный с длиной записи 1, а потом реализовать идею BlackShadow. Тогда существенное ускорение для больших строк даст BlockRead.
|
xds |
Сообщение
#6
|
N337 Группа: Пользователи Сообщений: 737 Пол: Мужской Репутация: 26 |
Кстати, Text использует буферизацию по умолчанию, правда размер буфера небольшой (128 байт). Несомненно, BlockRead с буфером разумного размера (4-16 Кб) даст некоторый прирост скорости чтения. Тем не менее, приведенный выше пример кода наводит на мысли, что программа легко укладывается в поставленные временные рамки даже при чуть менее чем "неразумной" реализации (под "неразумными" способами я подразумеваю что-то вроде "var f: File of Char", "BlockRead(f, c, 1)" )
-------------------- The idiots are winning.
|
BlackShadow |
Сообщение
#7
|
Гость |
Я уже где-то кому-то говорил, что оптимальный размер буфера совпадает с размером кластера диска, с которым происходит работа...
|
pascal65536 |
Сообщение
#8
|
Пионер Группа: Пользователи Сообщений: 62 Пол: Мужской Репутация: 1 |
А если хранить каждый 0 или 1 в массиве, пофигу каком.
Для заданного диапазона сосчитать сумму элементов массива. Если будет 0 тогда только 0 записаны, Если сумма равна числу элементов тогда только 1. |
BlackShadow |
Сообщение
#9
|
Гость |
Вот только счётчик в таком случае надо 4-ёх байтный брать. А то вдруг там сумма ровно в 256 или 65536 выйдет...
|
Текстовая версия | 20.04.2024 16:27 |