Алгоритмы и аспекты

Есть особая магия в головоломках, обладающих большим комбинаторным потенциалом. В то же время, именно в рутинных операциях полностью раскрывается потенциал ЭВМ. Соединяясь в рамках одной задачи, эти два тезиса будоражат как предстоящее путешествие: что-то из приключенческих фильмов с подбором шифров и разгадыванием кодов.

Сегодня я поведаю вам очередную историю о том, как причудливо влияют сегодняшние решения на далекое будущее.

В минувший день рождения, в качестве подарка я получил набор Apitor SuperBot, позволяющий создавать и программировать простых роботов. Титульная (но не единственная) модель, изображение которой даже вынесено на упаковку - джип. Вообще, джип в «базовой комплектации» не предусматривает подключение сенсоров и представляет собой одну из моделей для ручного управления с телефона. Тем не менее, как нарочно, модель …

Продолжая стенания о повсеместном употреблении жаргонизма «десятичное число», вместо терминологически верного «число, записанное в десятичной системе счисления», я взял, да и провёл конвертацию числа, записанного римскими цифрами, в число, представленное в шестнадцатеричной системе счисления.

Чем отличается ссылка от указателя? Когда использовать то или другое? На первый взгляд, оба инструмента делают одно и то же, приводя к избыточности и без того сложного языка.
"Масла в огонь" подливает амперсанд, который уже встречался и в роли битового И (бинарный ), и в роли логического И (бинарный ), и в роли взятия адреса (унарный префиксный ). Впрочем, последнее кажется логичным: ссылка ведь использует адрес объекта на который ссылается... но ведь для хранения адреса используется указатель?

При переходе на Си/Си++ с других языков - имеющих более конкретную область применения, и потому скрывающих за ненадобностью от программиста тонкости диспетчеризации памяти - неминуемо возникает вопрос о необходимости выбирать способ создания объекта (переменной, экземпляра класса) в памяти: автоматический объект («на стеке»), объект в динамически выделяемой памяти («в куче»), статический объект. Особого шарма добавляют сочетания типа «статически созданный указатель на динамическую память».

С момента прошлой заметки по данной теме прошло много времени, но интерес к изложенному в ней не утихал. Разобравшись с основной проблемой (как, собственно, реализовать дифференцирование) читатели стали задавать вопросы о двух приведённых в тексте формулах. На этих формулах построен весь вывод, но сами они не выводятся, а сопровождены комментарием о простоте их получения при должной внимательности. Настало время.

Процесс объяснения машине (которая понимала только целые числа) того, как надо работать с дробными числами, помог выработать абстрактное синтаксическое восприятие арифметических операций. Да, простейшая машина лишена понимания смысловой нагрузки информации, вводимой в неё, и процессов, которые в ней (машине) протекают. Тем не менее, иногда очень кстати бывает включить "режим калькулятора" и просто начать шпарить примеры один за другим.

Возможно, в процессе чтения чужого исходного кода, Вы натыкались на конструкции проверки равенства переменной самой себе. Не спешите ужасаться абсурдности проверки и попытке создать видимость большого объёма кода.

Стандарт IEEE 754, среди прочего, описывает особое состояние числа с плавающей запятой...

Вернёмся к старой теме генерации стандартного шума из равномерного, и рассмотрим вопрос: откуда берётся константа (т.н. "магическое число") 12 в формуле дисперсии?

В процессе ответа на первый вопрос, рассмотрим алгоритм получения формул дисперсии и математического ожидания для непрерывных случайных величин, на примере равномерного распределения.

Вычислить площадь четырёхугольника, изображённого на рисунке слева.
Ограничения: учащийся ещё не знает формулу площади трапеции, треугольника и любых фигур, кроме прямоугольника.

Вычислить площадь четырёхугольника, изображённого на рисунке слева.
Ограничения: Требуется решить задачу изощрённым формальным способом. На этот раз, учащийся забудет даже формулу площади прямоугольника.

Выделите коричневым цветом утолщённую горизонталь, соединяющую точки с абсолютной высотой 175 м. Через сколько метров проведены утолщённые горизонтали, если на плане показана только одна из них - 175 м.

Предложите свои варианты ответа.

Недавно на форуме была поднята тема производительности (времени выполнения) функций работы со строками. Автор вопроса интересуется поведением функции в зависимости от аргументов, передаваемых в неё. Сведений о внутреннем устройстве функции нет - сделать аналитическую оценку затруднительно. Подобное тестирование кажется тривиальным, но имеет некоторые тонкости, могущие кардинально исказить результат.

Несколько лет назад, мне продемонстрировали следующий занятный баг. Интерфейс разрабатываемого приложения корректно рисовался, пока запущенный на этом же компьютере музыкальный плеер "молчал". Стоило снять воспроизведение с паузы - картинка в "нашем" приложении начинала мерцать. Не спасало ни сворачивание окна плеера, ни отключение визуальных эффектов воспроизведения музыки, ни выбор другой композиции (кто бы сомневался). При этом оба приложения никак друг с другом не были связаны (как это кажется на первый взгляд). Вот это детектив!

Я уже как-то поднимал вопрос о генерации истинно случайных чисел "на коленке" (тут). Конечно, определить меру случайности в последовательности чисел можно огромным числом способов, поэтому конкретизируем: речь идёт о генерации, в основе которой не лежат арифметические методы.
Так вот: вопрос-то я поднимал, но в разговорах, время от времени, наталкиваюсь, с одной стороны - на непонимание собеседниками аспектов генерации, с другой - на интерес к игральным костям, с диапазоном выходных значений отличным от [1;6]. Данное обстоятельство подтолкнуло меня сделать небольшой обзор генераторов, имеющихся в продаже которые я сумел приобрести.

На первый взгляд ничего непонятно: оператор дифференцирования применяется к матрицам, некоторые из которых ещё и транспонированы, дифференцирование происходит по вектору и т.п.
Но не стоит паниковать!
Сперва опишем общие правила дифференцирования при работе с подобными объектами.

Сколько часов в сутках? Двадцать четыре? 24₁₀? XXIV? 18₁₆?
Число, само по себе - некая абстракция, характеризующая некоторую величину: количество яблок на столе, сумму в кошельке, и т.п.

При реализации некоторых задач, Вам может потребоваться обеспечить выборку двух случайных объектов из множества, при этом объекты должны быть обязательно разными. Например, Вы хотите перемешать массив перестановками элементов, но не желаете тратить процессорное время на вырожденные перестановки вида v[j]⇄v[j]. Или Вы индицируете активность системы, случайным образом меняя выбранный элемент - выбор одного и того же элемента два раза подряд недопустим.

В каком логическом/иерархическом/etc отношении находятся Метод Монте-Карло и Закон больших чисел?

При моделировании различных возмущений и шумов реального мира, Вы рано или поздно сталкиваетесь с необходимостью программно генерировать шум, значения амплитуд которого распределены нормально. Ну а конкретнее: почти всегда выбирается так называемое "стандартное нормальное распределение".

Небольшой опрос показал, что большинство людей не видит необходимости иметь на инженерном калькуляторе клавишу генерации квазислучайного числа. Действительно, окружающий мир полон случайностей (их подлинную детерминированность или стохастичность оставим на откуп философам): от чего бы не взять в руки монетку или игральную кость? Но что делать, когда необходимо большее число состояний, чем может породить выбранный генератор? Большинство людей довольно быстро придумывает неправильное решение и довольствуется им.

В данной заметке я опишу алгоритм расчёта параметров траектории движения тела, брошенного под углом к горизонту и движущегося в постоянном гравитационном поле. Проблема всплывает то тут, то там: при кодировании визуализации (например, в игре "Морской бой"), при выборе искусственным интеллектом параметров стрельбы и т.п.

Сегодня я хотел бы обсудить вопрос расстановки (не оптимальной, а произвольной) кораблей перед боем. Слева вы видите пример результата работы рассматриваемого далее алгоритма: корабли в форме букв «Б», «А», «Н» расставлены на игровом поле с несколькими запрещёнными к использованию клетками (помечены зелёным цветом).

Доброго времени суток, уважаемые! Так случилось, что вопросом программирования более-менее адекватного ИИ для игры "морской бой" я озадачился где-то в конце 2004 года. Быть может я, не имея должных руководств под рукой, изобретал тогда велосипед, но и в последствии, мне попадались потрясающие своей честностью алгоритмы: стрелять наобум, время от времени подглядывая у игрока расположение кораблей, для выравнивания баланса. В последствии я несколько раз улучшал алгоритм. По последним статьям на Хабре можно судить, что тема актуальна, к тому же - мне есть что добавить к написанному другими пользователями.
Итак, цель моей заметки: реализация оптимальной одной из стратегий атаки на корабли соперника, причём не только первое попадание, но и последующее "сопровождение ко дну". Отмечу, что корабли в моей реализации - почти (об этом ниже) произвольной формы.