Решение задач с анаграммами натолкнуло на мысль:
Сколько останется слов, если удалить все анаграммы и сабанграммы из словаря русского языка
В найденном словаре больше 1,5 млн слов в различных формах
Можно сравнить каждое слово с каждым, но для 1,5 млн записей это долго и неоптимально.
В мире с бесконечной памятью можно сгенерировать подстроки всех перестановок каждого слова и проверить наш словарь на них
Но есть ли решение получше?
Читать полностью »
Я много лет читаю курсы по комбинаторике и графам для студентов-математиков и computer scientists (как это по-русски, компьютерных научников?), раньше в Академическом университете, а теперь в СПбГУ. Программа у нас построена так, что эти темы проходят как часть «теоретической информатики» (другие темы в ней — алгоритмы, сложность, языки и грамматики). Не могу сказать, насколько это оправдано метафизически или исторически: всё же комбинаторные объекты (графы, системы множеств, перестановки, клетчатые фигуры и др.) начали изучали задолго до появления компьютеров, и сейчас последние хотя и важная, но далеко не единственная причина интереса к ним. Но так посмотреть на самых спецов по комбинаторике и по theoretical computer science — это удивительно часто одни и те же люди: Ловас, Алон, Семереди, Разборов и далее. Наверно, есть на то свои причины. На моих уроках часто очень нетривиальные решения сложных задач предлагают чемпионы олимпиадного программирования (их перечислять не буду, кому любопытно посмотрите топ codeforces.) В общем, думаю, что некоторые вещи из комбинаторики могут быть интересны сообществу. Говорите, если что так или не так.
Читать полностью »
В этой статье я хочу немного рассказать о самом лучшем в мире курсе по программированию.
С 2013 года наша небольшая команда занимается переводом и адаптацией англоязычных видеокурсов. За это время мы перевели и адаптировали свыше 150 часов материала. Перед тем как приступать к работе, мы анализировали материалы нескольких обучающих онлайн-школ, и выбирали, на наш педагогический взгляд, самую лучшую, которая максимально доступно, структурированно и кратко подаёт обучающий материал. В результате чего нам приходилось просматривать по несколько курсов касающихся одной и той же тематики, а после выбирать тот, который наиболее качественный и доступный для понимания новичкам.
Как оказалось, действительно качественных курсов и преподавателей не так уж и много. В русскоязычном обучающем пространстве достаточно часто встречаются пересъёмки или адаптация зарубежных курсов, которые пользуются популярностью у американских или европейских специалистов.
Остистая сосна
Несколько лет назад после ужина в День благодарения, проходившего в доме моих родителей в Вермонте, молния ударила в клён, стоявший у нас во дворе. Мы услышали ужасный треск, и темнота за окном кухни на какой-то миг сменилась ярким светом. И только весной мы смогли уже точно удостовериться в том, что дерево погибло.
Этот клён был молодым, его ствол по диаметру не превышал десертной тарелки. Если бы его жизнь не оборвалась в результате катастрофы, он мог бы прожить 300 лет. Но у деревьев смерть в результате несчастного случая встречается удивительно часто. Иногда это происходит из-за грубой людской ошибки, как когда в 2012 году во Флориде болотный кипарис возрастом более 3500 лет был уничтожен в результате намеренного поджога. Чаще беда приходит в виде плохой погоды – засухи, ветра, пожаров или заморозков. И, конечно, деревья подвержены влиянию паразитов и болезней; такая напасть, как грибок, может заметно укоротить время жизни дерева. Но те деревья, которым удалось избежать подобных врагов, способны жить невероятно долго.
Читать полностью »
Когда вам нужен один объект, вы создаёте один объект. Когда нужно несколько объектов, тогда есть несколько вариантов на выбор. Я видел, как многие новички в коде пишут что-то типа такого:
// Таблица рекордов
int score1 = 0;
int score2 = 0;
int score3 = 0;
int score4 = 0;
int score5 = 0;Это даёт нам значение пяти рекордов. Этот способ неплохо работает, пока вам не потребуется пятьдесят или сто объектов. Вместо создания отдельных объектов можно использовать массив.
// Таблица рекордов
const int NUM_HIGH_SCORES = 5;
int highScore[NUM_HIGH_SCORES] = {0};Будет создан буфер из 5 элементов, вот такой:
Заметьте, что индекс массива начинается с нуля. Если в массиве пять элементов, то они будут иметь индексы от нуля до четырёх.
Читать полностью »
Привет!
* На самом деле не совсем так. При разработке информационной системы, частью которой является различная обработка конструкторско-технологической документации, у меня возникла проблема, которую вкратце можно описать следующим образом. Сегодня мы имеем один состав изделия, за день приходит несколько изменений по различным частям этого изделия и к вечеру уже неясно, что же изменилось? Изделия порой могут иметь более 10 000 элементов в составе, элементы не уникальны, а реальность такова, что изменения по составу могут активно приходить, хотя изделие уже почти готово. Непонимание объема изменений усложняет планирование.
Состав изделия можно представить в виде древовидного графа. Не найдя подходящего способа сравнения двух графов, я решил написать свой велосипед.
Читать полностью »
В этой статье мы поговорим о том, как создать билборд-текстуру растительности в Unreal Engine 4. Такая растительность – это простой многократно размноженный четырехугольник, все копии которого всегда повернуты к камере. Я постараюсь привести доводы в пользу такого подхода, расскажу о потенциальных недостатках и отдельно затрону вопрос производительности.
Дерево – частный случай графа. Деревья широко применяются в программировании. Дерево – это связный граф без циклов. Дерево называется помеченным, если каждой вершине соответствует уникальная метка. Обычно это число.
Добрый день, уважаемые читатели.
Сегодняшняя статья будет посвящена сравнению моделей работы с иерархическими данными в PostgreSQL, через Django приложение. В статья я специально не использую чистую реализацию в базе данных, т. к. меня интересует именно производительность в среде, приближенной к боевой.
Однажды, около пяти лет назад, Фрэнк Нолво, немногословный коренастый шкипер с верховий реки Сепик, на севере Папуа – Новой Гвинеи, проснулся и отправился в город. У 42-хлетнего Нолво было девять детей. Он работал над пристройкой к дому, и ему требовались стройматериалы.
Если вы живёте в верховьях Сепик, вы не можете просто сходить в магазин. Нолво вышел из своей деревни Кагиру рано утром. Как и у других групп домов с пальмовыми крышами по реке, в Кагиру нет электричества, мобильной связи и дороги, соединяющей её с другими местами. Даже по стандартам Папуа – Новой Гвинеи, регион считается слишком жарким, бедным и сложным для проживания. Во время дождя наступает наводнение. Во время засухи ручьи пересыхают, и люди со своими каноэ оказываются в ловушке. Чтобы дойти куда-нибудь, нужно идти несколько дней. По безжалостным географическим причинам экономическое развитие в верховьях Сепик буксовало тысячи лет. А ещё там очень, очень много крокодилов.
Целый день проведя на воде, Нолво достиг Амбунти, большой деревни с населением в 2000 человек, где он переночевал. Следующим утром он двинулся дальше. Нолво считался среди местных процветающим и влиятельным человеком. Кроме лодки, у него была должность председателя района, в который входят 30 деревень, включая Кагиру. Но и для него путешествие было серьёзным предприятием. Одного горючего пришлось израсходовать на почти на 1000 кина [около 20 000 руб]. К обеду второго дня Нолво пришвартовал лодку и сел на грузовик, направлявшийся в Вевак, столицу провинции. Это и была цель его поездки, находившаяся в четырёх часах езды от берега. Именно на рынке в Веваке, покупая материалы, Нолво встретился с ещё одним главой района в верховьях Сепик, Дэвидом Салио, пригласившим его на встречу в местном отеле, посвящённую торговле квотами на выбросы CO2.
Читать полностью »
