|
|
|
|
Канал Игры Мечты: «Алгоритмы - кирпичики Игры Мечты» |
|
|
|
Krom
 455 EGP
  
Рейтинг канала: 1(3)
Репутация: 159
Сообщения: 1988
Откуда: Горы Урала
Зарегистрирован: 19.07.2005
  |
|
"- А кто этот молодой юноша? Он тоже генеральный инспектор? Эзра, - Костя повернулся к голубоглазому, - пусть Владимир Сергеевич держит ось, а мальчику ты дай чем-нибудь полезно поиграть. Лучше всего поставь его к своему экрану, пусть он посмотрит, как большие дяди делают бах." ("Стажёры", А. и Б. Стругацкие.)
Даже самые великие свершения начинаются с малого. Предлагаю полезно поиграться, с прицелом на делание в будущем "бах". Может быть, даже в виде Игры Мечты.
Вот, например, простенькая задачка:
1) Имеется практика продажи билетов на городской и пригородный транспорт. Билеты имеют серийный номер из шести цифр. Счастливым называется билет, у которого сумма цифр первой триады совпадает с суммой цифр второй триады. Сколько существует билетов со счастливыми номерами? Ответ привести в виде алгоритма, результатом работы которого было бы искомое число. Алгоритм должен работать менее двух секунд на машинах класса х486.
_________________
Не спешите меня. |
|
|
|
AlexD
 383 EGP
Рейтинг канала: 2(10)
Репутация: 82
Сообщения: 1084
Откуда: Тюмень, Россия
Зарегистрирован: 25.04.2003
 |
|
Прикольно.  Сразу школу вспомнил, это была первая задачка, на которой меня поймал мой учитель информатики.  Вторая была про поиск минимального элемента в массиве. 
_________________
тетрагидрометаноптерина макарена
метилентетрагидрофолата макарена
ЭЭЭЭЭ МАКАРЕНА |
|
|
|
Krom
455 EGP
Рейтинг канала: 1(3)
Репутация: 159
Сообщения: 1988
Откуда: Горы Урала
Зарегистрирован: 19.07.2005
|
|
AlexD:
Напиши ту задачку, если она такая же простенькая. Потом и посложнее возьмём, например, АСМ-ные.
_________________
Не спешите меня. |
|
|
|
AlexD
383 EGP
Рейтинг канала: 2(10)
Репутация: 82
Сообщения: 1084
Откуда: Тюмень, Россия
Зарегистрирован: 25.04.2003
|
|
Там суть подлова была не в сложности задачи, а в реализации алгоритма. Вернее сначала была задача про поиск максимального элемента. Я ему тогда сказал: "Берем переменную, делаем ее нулем, а потом перебираем массив, если число в массиве больше переменной, то запоминаем и идем дальше..." А он мне и говорит, а если надо найти минимальный, то какой значение первым поставим в переменную? Самое большое? А это какое? Максимальное которое влезает в байт (если массив из байтов)? А если числа в массиве будут отрицательные числа?
И вот тут я "подвис"...  И вправду, а какое значение ставить стартовое???
_________________
тетрагидрометаноптерина макарена
метилентетрагидрофолата макарена
ЭЭЭЭЭ МАКАРЕНА |
|
|
|
Krom
455 EGP
Рейтинг канала: 1(3)
Репутация: 159
Сообщения: 1988
Откуда: Горы Урала
Зарегистрирован: 19.07.2005
|
|
Да, сложный вопрос!
Нам повеселее задачку дали: максимальное надо было выбирать из окна в десять тысяч элементов в миллионном массиве, причём на каждом шаге окно сдвигалось на один элемент. Давалось пять секунд времени.
_________________
Не спешите меня. |
|
|
|
AlexD
383 EGP
Рейтинг канала: 2(10)
Репутация: 82
Сообщения: 1084
Откуда: Тюмень, Россия
Зарегистрирован: 25.04.2003
|
|
Кышмар!  Это на каких пентиумах?  Не-е-е, мы тогда на своих 386х только в Lotus гоняли или в Vorona... да DOS изучали... А програмили мы в основном дома на Z80, на асме... Пытались даже что-то вроде сетевой Элиты сделать... через порт принтера...
_________________
тетрагидрометаноптерина макарена
метилентетрагидрофолата макарена
ЭЭЭЭЭ МАКАРЕНА |
|
|
|
Shirson
1605 EGP
   
Рейтинг канала: 7(626)
Репутация: 219
Сообщения: 16511
Откуда: 79°W 44°N
Зарегистрирован: 29.01.2002
|
|
| AlexD : |
|
И вот тут я "подвис"... И вправду, а какое значение ставить стартовое???
|
Первый элемент массива, вестимо. В задаче с максимальным числом - тоже самое.
_________________
У меня бисера не доxеpа. |
|
|
|
Shirson
1605 EGP
Рейтинг канала: 7(626)
Репутация: 219
Сообщения: 16511
Откуда: 79°W 44°N
Зарегистрирован: 29.01.2002
|
|
| Krom : |
Да, сложный вопрос!
Нам повеселее задачку дали: максимальное надо было выбирать из окна в десять тысяч элементов в миллионном массиве, причём на каждом шаге окно сдвигалось на один элемент. Давалось пять секунд времени.
|
На каждом шаге чего? Цикла перебора окна или как?
_________________
У меня бисера не доxеpа. |
|
|
|
Krom
455 EGP
Рейтинг канала: 1(3)
Репутация: 159
Сообщения: 1988
Откуда: Горы Урала
Зарегистрирован: 19.07.2005
|
|
Тогда и эту задачку напишу.
2) Вот почти точная копия той самой задачки
_________________
Не спешите меня. |
|
|
|
Damien
|
|
| AlexD : |
|
Вторая была про поиск минимального элемента в массиве.
|
Отсортировать массив по возростанию/убыванию и выбрать первый жлемент!  Быстрые алгоритмы сортировки науке известны. 
| Krom : |
|
я билет, у которого сумма цифр первой триады совпадает с суммой цифр второй триады.
|
Первый напрашивающийся ответ, естественно - цикл с миллионом итераций. Что-то мне подсказывает, что не этого от меня ожидают. Посему я начал размышлять.
Сперва я подумал, что однозначно подходят числа, где вторая триада = первой. Таких чисел ровно 1000. Ну хорошо. Потом мне подумалось, что сюда-же подходят все пермутации первой триады. Ну да ладно. В любом справочнике по комбинаторике будет формула подсчета числа пермутаций. И что дальше?
Короче, в итоге мне придумался такой вот алгоритм, к комбинаторке не имеющий никакого отношения.
Производим цикл с тысячей итераций. На каждой итерации производим вложенный цикл из десяти итераций. Внутри цикла вычисляем значение переменной дельта=первая цыфра числа-счетчик цикла. После чего производим еще один вложенный цикл снова из десяти итераций, где выполняем следующие действия: дельта += вторая цифра числа-счетчик этого цикла. Ну и в итоге если третья цифра числа - дельта находится в пределах 0..9 то увеличить счетчик результата на один
В итоге я так посчитал, получается всего 1000х10х10 = 100 000 итераций цикла. Прирост производительности в 10 раз. Меньше, чем я ожидал Но тем не менее. Щас попробую реализовать этот алгоритм на Питоне, посмотрим как он работает...
|
|
|
|
Dark Archon
231 EGP
 
Репутация: 56
Сообщения: 389
Откуда: Moscow Federation
Зарегистрирован: 27.05.2004
|
|
Почитал задачу (довольно мутно изложенную), проанализировал сэмпл и пришел к такому выводу: sequence делится на subsequences по М (первое число), причем каждый следующий subsequence сдвигается относительно предыдущего не на М а всего на 1. Это имелось в виду?
| Damien : |
| AlexD : |
|
Вторая была про поиск минимального элемента в массиве.
|
Отсортировать массив по возростанию/убыванию и выбрать первый жлемент! Быстрые алгоритмы сортировки науке известны.
|
Шутку понял... смешно... (ц) Гоблин.
По твоему O(N*logn(N)) быстрее чем O(N)?
| Damien : |
|
Производим цикл с тысячей итераций. На каждой итерации производим вложенный цикл из десяти ...... В итоге я так посчитал, получается всего 1000х10х10 = 100 000 итераций цикла.
|
Зачем делать 100000 итераций, когда можно сделать их 1000, а дальше воспользоваться формулами комбинаторики? Правда понадобится вспомогательный массив размером 9+9+9=27 байт. (Последнее предложение считать подсказкой ).
Если подумать, то возможно можно и проще, но мне думать лень после тяжелой рабочей недели.
_________________
o
_/0\_
< > КУ! |
|
|
|
Shirson
1605 EGP
Рейтинг канала: 7(626)
Репутация: 219
Сообщения: 16511
Откуда: 79°W 44°N
Зарегистрирован: 29.01.2002
|
|
| Damien : |
|
Отсортировать массив по возростанию/убыванию и выбрать первый жлемент! Быстрые алгоритмы сортировки науке известны.
|
Это называется надев лыжи и стоя в гамаке 
Простой перебор массива даёт более быстрый и менее хлопотный результат, чем сортировка массива.
_________________
У меня бисера не доxеpа. |
|
|
|
Krom
455 EGP
Рейтинг канала: 1(3)
Репутация: 159
Сообщения: 1988
Откуда: Горы Урала
Зарегистрирован: 19.07.2005
|
|
Думаю, что Dark Archon'у за первую задачку можно поставить "зачёт", хотя намёки на решение ещё не есть решение И комбинаторные алгоритмы там вообще-то не используются Но это уже спойлер.
Шутка насчёт сортировки навела на мысль - завтра попробую рассказать, как определять временные затраты алгоритма (или, как говорят, его сложность О() )
Насчёт второй задачки кто-нибудь что-нибудь придумал?
_________________
Не спешите меня. |
|
|
|
Shirson
1605 EGP
Рейтинг канала: 7(626)
Репутация: 219
Сообщения: 16511
Откуда: 79°W 44°N
Зарегистрирован: 29.01.2002
|
|
А тут чего-то в голове мелькнуло...
| Код: |
Делать выборку в первом срезе окна, на предмет наибольшего числа. (НЧ)
Запоминать само число И его индекс.
При сдвиге проверять, вышло ли указанное число из выборки (индекс есть)
НЕТ - проверять пришедшее число на предмет его большести НЧ.
НЕТ - гоу ту сдвиг.
ДА - Запоминать пришедшее число как НЧ
ДА - Делать выборку НЧ перебором. ГоуТу сдвиг. |
Сыро, впринципе. Надо подумать, как исключить переборы, при выходе НЧ из выборки. Может "прогноз" хранить, на несколько чисел, меньших НЧ по убыванию.
_________________
У меня бисера не доxеpа. |
|
|
|
Krom
455 EGP
Рейтинг канала: 1(3)
Репутация: 159
Сообщения: 1988
Откуда: Горы Урала
Зарегистрирован: 19.07.2005
|
|
Shirson:
Тепло!
_________________
Не спешите меня. |
|
|
|
Shirson
1605 EGP
Рейтинг канала: 7(626)
Репутация: 219
Сообщения: 16511
Откуда: 79°W 44°N
Зарегистрирован: 29.01.2002
|
|
Ладно, может еще чего в голове мелькнёт
_________________
У меня бисера не доxеpа. |
|
|
|
Krom
455 EGP
Рейтинг канала: 1(3)
Репутация: 159
Сообщения: 1988
Откуда: Горы Урала
Зарегистрирован: 19.07.2005
|
|
А вот ещё задачка на предсказание(для понимания некоторых особенностей ИИ):
Над алфавитом (a,b) действуют следующие правила:
1) bXbY => XYbb
2) XabYbZ => XbYabaZ, X,Y,Z - п.п.ф.
правильно построенной формулой (п.п.ф.) будем считать любое, возможно пустое, слово. Например, aabba, baba, bbbbb суть п.п.ф. исчисления.
Аксиомой исчисления является слово abb;
Выводима ли в данном исчислении формула aa...abb [(a^14)bb]? На раздумья одна минута. (Но не больше двух! )
_________________
Не спешите меня. |
|
|
|
Dark Archon
231 EGP
Репутация: 56
Сообщения: 389
Откуда: Moscow Federation
Зарегистрирован: 27.05.2004
|
|
Значит вторую задачу я понял правильно.
Shirson, грамотный алгоритм. Это первое что приходит в голову. Во всяком случае в мою пришло тоже.
Возиться с сохранением НЧ (наибольшего числа) по убыванию - не стоит. Это надо будет сохранять сортированный массив и соблюдать сортировку при добавлении/выбрасывании числа из него. Это только увеличит сложность алгоритма. Кроме того, не надо забывать что данные даются не в качестве массива, а потоком , т.е. для повторного прохода, в целях нахождения нового НЧ, нужно будет сохранять текущее окно потока.
У меня другая мысля булькнула в вареных мозгах:
Что мешает вести вместо одного НЧ - М таких НЧ, по одному на каждый "срез окна", пересекающихся и соответственно проверяемых одновременно? В таком случае не надо будет ни сохранять значения измерений из потока, ни чего либо сортировать. Каждое значение будет взято единожды, но сравнено с М числами. Сложность получается O(N*M), когда worst, best и optimal case равны.
Н счет алфавита: a^14 - это что? "a" вроде буква алфавита, а не переменная/неизвестное, что в таком случае значит возведение буквы в степень? Или я чего не догнал?
_________________
o
_/0\_
< > КУ! |
|
|
|
Krom
455 EGP
Рейтинг канала: 1(3)
Репутация: 159
Сообщения: 1988
Откуда: Горы Урала
Зарегистрирован: 19.07.2005
|
|
Dark Archon:
Уточни, пожалуйста, насчёт множества НЧ и пересекающихся окон, я что-то не совсем вник.
А "возведение в степень" - это просто упрощение записи, указание того, сколько букв а в том ряду.
_________________
Не спешите меня. |
|
|
|
Krom
455 EGP
Рейтинг канала: 1(3)
Репутация: 159
Сообщения: 1988
Откуда: Горы Урала
Зарегистрирован: 19.07.2005
|
|
Статья про определение сложности алгоритма.
Если читать лень, то вкратце: сложность алгоритма определяется количеством его обращений к(или операций над) исходным данным, либо данным, построенным из исходных. Например, поиск минимального элемента массива требует проверки каждого элемента массива один раз - это означает сложность О(n), где n - число элементов массива. Метод сортировки "пузырёк" сравнивает все элементы сортируемого массива попарно, а так как пар элементов в массиве длины n будет n^2, то и сложность алгоритма равна O(n^2). Некоторые особо сложные задачи имеют решения в виде алгоритмов со сложностью не меньше O(n^3*log n), обычно это означает немалую нагрузку на процессор. Рабоче-крестьянские решения задач часто приводят к сложности вида O(2^n), что уже не лезет ни в какие ворота.
Если программа имеет участки различной сложности, то общей сложностью будет максимальная из сложностей участков. Например, если по задаче нужно выбрать минимальный элемент массива (сложность участка О(n)), а затем отсортировать элементы слева от него по возрастанию методом "пузырька" (сложность участка О(n^2)), то суммарная сложность алгоритма будет О(n^2).
Очевидно, что чем сложнее алгоритм, тем больше будут временные затраты на его работу. Более того, тем быстрее растут временные затраты с ростом количества входных данных. И если количество входных данных в общем случае уменьшить нельзя, то сложность программы, а значит и нагрузку на процессор, можно уменьшить, выбрав более эффективный алгоритм.
_________________
Не спешите меня. |
|
|
|
|
|
|
|
|
Канал Игры Мечты: «Алгоритмы - кирпичики Игры Мечты» |
|
|
