Алгоритмы сортировки. Их не много, но и не мало. Есть часто используемые, есть никому не нужные. Я решил произвести обзор этих алгоритмов, чтоб освежить и свою память, и память хабрапользователей. И начнём с редкоиспользуемого алгоритма Gnome Sort(гномья сортировка).
Читать полностью »
Метка «Алгоритмы» - 13
Алгоритмы сортировки. Gnome Sort на Си
2012-08-23 в 14:08, admin, рубрики: c++, Алгоритмы, алгоритмы сортировки, Программирование, С++, Си, сортировка, метки: Алгоритмы, алгоритмы сортировки, Программирование, С++, Си, сортировкаКак правильно искать в Google
2012-08-14 в 21:19, admin, рубрики: api, Google, Google API, Алгоритмы, операторы, поиск, метки: Google, Алгоритмы, операторы, поиск Наверняка нет человека, который хотя бы раз слышал о таком замечательном поисковике, как Google. Полагаю, вам не раз приходилось его использовать, когда вы хотел что-нибудь узнать. Вот только находили ли вы то, чего хотели? Если вы так же часто как и я ищете ответы в Google, я думаю, вам будет полезна эта статья, потому что она расчитана сделать ваш поиск более быстрым и эффективным. Итак, для начала немного истории…
Читать полностью »
Раз дощечка, два дощечка — будет лесенка…
2012-08-13 в 19:49, admin, рубрики: Алгоритмы, задачи, фибоначчи, метки: Алгоритмы, задачи, фибоначчиИменно о лесенках хотелось бы немного поговорить. Есть такая относительно распространенная задача с программистских собеседований:
Вы поднимаетесь по лестнице. На каждом шаге вы можете подняться либо на 1 ступеньку, либо на 2. Всего лестница имеет n ступенек. Сколькими разными способами вы можете дойти до конце лестницы?
Задача не сильно сложная, но имеющая пару интересных моментов относительно минимально возможной сложности решения и демонстрирующая «штуки, которые интересно знать».
Кэш фукция
2012-08-09 в 9:55, admin, рубрики: c++, Алгоритмы, кэш, Песочница, Программирование, метки: c++, Алгоритмы, кэш, ПрограммированиеДобрый день, читатели. В процессе изучения С++ столкнулся с такой вот (достаточно интересной) задачей (а точнее по рекомендации товарища) — написание Кэш функции (не Хэш).Читать полностью »
Ассоциативные запоминающие устройства
2012-08-04 в 11:53, admin, рубрики: Алгоритмы, память, метки: Алгоритмы, памятьКогда говорят о запоминающих устройствах, большинство людей вспоминают о накопителях на магнитных дисках (HDD) и о памяти с произвольным доступом (ОЗУ). Уверен, большинство читающих этот пост, знает о множестве фундаментальных различий между устройствами этих классов. Но на самом деле у этих устройств есть и кое-что общее: и в оперативной памяти, и на жёстких дисках поиск информации выполняется по её адресу. Программистам такой подход кажется если не единственно возможным, то уж точно самым логичным, но к счастью реальный мир не ограничивается исключительно программными абстракциями. В этой статье мы рассмотрим запоминающие устройства с доступом по содержанию.Читать полностью »
Используем быстрое возведение матриц в степень для написания очень быстрого интерпретатора простого языка программирования
2012-08-01 в 16:57, admin, рубрики: Алгоритмы, интерпретаторы, Компиляторы, матрицы, Песочница, метки: Алгоритмы, интерпретаторы, матрицыНедавно на хабре появилась неплохая статья про вычисление N-ного числа фибоначи за O(log N) арифметических операций. Разумный вопрос, всплывший в комментариях, был: «зачем это может пригодиться на практике». Само по себе вычисление N-ого числа фибоначи может и не очень интересно, однако подход с матрицами, использованный в статье, на практике может применяться для гораздо более широкого круга задач.
В ходе этой статьи мы разберем как написать интерпретатор, который может выполнять простые операции (присвоение, сложение, вычитание и урезанное умножение) над ограниченным количеством переменных с вложенными циклами с произвольным количеством итераций за доли секунды (конечно, если промежуточные значения при вычислениях будут оставаться в разумных пределах). Например, вот такой код, поданный на вход интерпретатору:
loop 1000000000
loop 1000000000
loop 1000000000
a += 1
b += a
end
end
end
end
Незамедлительно выведет a = 1000000000000000000000000000, b = 500000000000000000000000000500000000000000000000000000, несмотря на то, что если бы программа выполнялась наивно, интерпретатору необходимо было бы выполнить октиллион операций.
Читать полностью »
Почему компьютерное зрение очень мало используется на практике
2012-07-30 в 13:00, admin, рубрики: Алгоритмы, Компьютерное зрение, машинное зрение, Песочница, Программирование, проектирование, Проектирование и рефакторинг, метки: Алгоритмы, Компьютерное зрение, машинное зрение, Программирование, проектированиеНа самом деле правильнее было бы назвать «машинное зрение», но так я думаю понятнее будет, если кто не знает то это не охранное видеонаблюдение, а распознавание или измерение чего либо c помощью камер. Существует много задач и областей, где компьютерное зрение было бы очень востребовано и могло бы использоваться повсеместно, но на практике оно используется очень редко.
Я реализовал несколько проектов в этой области для решения разных задач, конкретно это вычисление и подсчет площадей, контроль качества продукции, причем разной и в разных отраслях таких как: фигурная порезка и раскрой листов ДСП, ДВП, МДФ, измерение площадей шкурок животных на производства изделий из кожи и др.
Задача вычисления площади может показаться довольно сложной. Если подходить строго математически, то да, например, посчитать площадь квадрата или прямоугольника очень просто умножаем длину на ширину и готово, если треугольника чуть сложнее, а вот других криволинейных фигур может быть очень сложно.
Мой алгоритм подсчета площади настолько прост, что его можно реализовать без всяких библиотек и т.п. буквально в десять строк кода, по сути это простейший детектор движения только с калибровкой камеры. Камера жестко фиксируется над местом, куда подается продукция, делается снимок фона (без продукции), например, белый стол, цвета пикселей загоняются в массив. Далее на стол подается или ложится образец, например какая-то коробка. Далее делается второй снимок с коробкой, цвета второго кадра пишутся в другой массив и затем сравниваются значения цветов, количество отличающихся пикселей суммируется. Затем этот образец измеряется рулеткой, вводится в программу его площадь и вычисляется площадь одного пикселя, т.е. площадь делится на число пикселей. Вот и вся калибровка. Далее достаточно подавать любую продукцию, любого размера и формы, определятся число изменившихся пикселей, и умножается на площадь одного пикселя, найденного при калибровке, надеюсь все понятно. Причем продукция может двигаться, например, на конвейере, площадь будет измеряться правильно, нужно только захват Читать полностью »
Вычислительная геометрия, или как я стал заниматься олимпиадным программированием. Часть 2
2012-07-23 в 17:03, admin, рубрики: Алгоритмы, вычислительная геометрия, метки: Алгоритмы, вычислительная геометрияВступление
Это вторая часть моей статьи посвящена вычислительной геометрии. Думаю, эта статья будет интереснее предыдущей, поскольку задачки будут чуть сложнее.
Начнем с взаимного расположения точки относительно прямой, луча и отрезка.
Читать полностью »
Вычислительная геометрия, или как я стал заниматься олимпиадным программированием.Часть 1
2012-07-14 в 20:46, admin, рубрики: Алгоритмы, вычислительная геометрия, метки: Алгоритмы, вычислительная геометрияЗдравствуйте, уважаемые читатели! Это моя вторая статья, и мне хотелось бы поговорить о вычислительной геометрии.
Немного истории
Я являюсь студентом уже 4 курса математического факультета, и до того как я начал заниматься программированием, я считал себя математиком на 100 процентов.
В конце первого курса мой преподаватель по информатике, который занимается олимпиадным программированием, обратил на меня внимание. Им как раз не хватало одного математика в команду. Так потихоньку меня начали приучать к олимпиадному программированию. Скажу честно, для меня это было очень сложно: для человека, который узнал слово Delphi на первом курсе. Однако мой преподаватель оказался очень грамотным специалистом и нашел хороший подход ко мне. Он начал давать мне математические задачи, который я сначала решал чисто математически, а уже потом писал код (с грехом пополам).
Мне очень нравится подход моего преподавателя: «разберись с этой темой, а потом расскажи нам, да так чтоб мы все поняли».
Итак, первой на самом деле важной задачей, с которой мне поручили разобраться, было именно вычислительная геометрия, необходимо было разобраться в типичных задач этого раздела информатики. И я решил подойти к этой задаче со всей ответственностью.
Я помню, как долго мучился с этими задачами, чтобы они прошли все тесты на сайте informatics.mccme. Зато теперь я очень рад, что прошел через все испытания и знаю, что же такое задачи вычислительной геометрии.
Читать полностью »
Об обратной польской нотации(записи) на Хабре уже рассказывали . Как известно вся сила ОПН в постфиксной записи математического выражения. О том как преобразовать привычную для нас инфиксную запись в постфиксную детально рассмотрено в статье выше, на Википедии и даже приведена реализация на Ассемблере. Но вот о том как провернуть обратное действие я статей не нашел.