Pull to refresh
33
0

программист

Send message

Экскурсия в натуральные числа или Расширенная Гипотеза Коллатца, часть II

Level of difficultyMedium
Reading time3 min
Views3K

В предыдущей части мы с вами расширили всем известную гипотезу Коллатца.

Так, расширенная гипотеза Коллатца утверждает, что множество чисел x, для которых есть циклы, отличные от {1}, равно {5, 181}.

Поясню другими словами..

Читать далее

Расширенная гипотеза Коллатца, или проблема «nx+1» — часть I

Reading time3 min
Views3K

Расширенная гипотеза Коллатца, или проблема "nx+1"


Вероятно, все уже слышали про гипотезу "3х+1", или гипотезу Коллатца.


Правила очень простые. Берём любое число. Если оно нечётное, умножаем его на 3 и добавляем 1. Если оно чётное, делим на 2. Повторяем то же самое действие с результатом. Обязательно ли в конце мы получим 1?

Читать дальше →

Использование битовой арифметики для получения наилучших решений задач с LeetCode по скорости и памяти

Level of difficultyMedium
Reading time4 min
Views7.3K

Некоторое время назад, во время подготовки к интервью, я наткнулся на несколько забавных задач на сайте leetcode.com. Сами задачки не слишком сложны, но их решения довольно любопытны. Кроме того, задачки такого типа довольно часто попадаются на собеседованиях в крупных компаниях.

Читать далее

Битва за производительность: SparseMap vs GenerationsMap

Level of difficultyMedium
Reading time7 min
Views5.5K

Есть такая занимательная структура данных, описанная в статье Russ Cox — sparse map.


Она используется, например, в недрах компилятора Go. А ещё в некоторых пакетах его стандартной библиотеки.


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


Читать дальше →

В поисках Числа Бога

Level of difficultyHard
Reading time12 min
Views3K

Речь идет о головоломках по типу кубика Рубика (за подробностями - в первую статью серии).

Алгоритмом Бога на пазле (от англ. "puzzle" - головоломка) - это кратчайший путь от состояния А до В.

Антипод - самое запутанное состояние пазла (одно из множества).

Число Бога (далее ЧБ) - это (всё эквивалентные формулировки):

Найти Число Бога

Снятие с воинского учета. Дистанционно. Пакет документов

Level of difficultyEasy
Reading time6 min
Views55K

По состоянию на лето 2023, в военных комиссариатах разных регионов и даже районов одного города требования к пакету документов отличаются, запись через Госуслуги может не гарантировать прием, а без личного присутствия заявителя могут вообще не захотеть общаться. Информация ниже не является полным гайдом по снятию с учета, это шаблоны документов + рекомендации из практики.

Если вкратце, то рабочий кейс, это когда: (А) имеется основание для снятия: уже живете зарубежом полгода, либо имеется иностранный ВНЖ, (B) грамотно составлено заявление на снятие с учета и подписано вашей подписью, (C) в военкомат идет ваш представитель по доверенности, которая оформлена у российского нотариуса или в зарубежном консульстве РФ.

Ниже пояснения и документы. Делайте все красиво, грамотно, и тогда результат будет ?

Читать далее

Внезапно сложная задача на литкоде: Варианты покупки двух товаров

Level of difficultyHard
Reading time6 min
Views13K

Есть вот такая, вроде бы, простая задача на литкоде: Дано три числа total - сколько у вас есть денег, cost1, cost2 - цены двух товаров. Надо подсчитать, сколько всего существует различных способов купить сколько-то этих двух товаров, не выходя из бюджета (значение имеет только общее количество покупок). Иными словами, сколько существет целых неотрицательных пар (x, y), таких что x*cost1+y*cost2 <= total . Например, имея товары ценами {5, 10} и 20 денег на руках, есть 9 способов потратить деньги: 0, 5, 5+5, 5+5+5, 5+5+5+5, 10, 10+5, 10+5+5, 10+10.

Она там даже помечена как medium и вообще в одну строчку решается, но это если допускать безумно медленное решение за O(total / max(cost1, cost2)) , т.е линейное от входных чисел. А сможете ли вы решить ее сильно быстрее - за O(log(max(cost1, cost2))) ? В этом случае задачка становится вполне себе hard и требует много математики и аккуратности. Если интересно решение - добро пожаловать под кат. Буду рад любым альтернативным решениям. Может кто-то сможет додуматься до похожего решения проще.

Читать далее

Ищем простые числа до триллиона за тридцать минут

Reading time21 min
Views28K
image

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

Сегодня я хотел бы поделиться с вами различными вариантами реализации поиска простых чисел на языке C#, начиная с классических алгоритмов — решета Эратосфена, Сундарама и Аткина, и кончая различными оптимизациями (сегментация, факторизация). Особый упор я делал на простоту: самый быстрый из алгоритмов, который мне удалось получить, содержит 120 строк кода и ищет простые числа до триллиона меньше, чем за 30 минут, а до миллиарда — меньше, чем за секунду (это далеко от производительности лучших из существующих библиотек по поиску простых чисел, но эти библиотеки обычно содержат свыше 4000 строк кода).
В заключение мы применим самую быструю реализацию для поиска максимального расстояния между двумя соседними простыми числами до триллиона. Прежде чем заходить под кат, я предлагаю вам попытаться угадать ответ. Для сравнения, для простых чисел до 100 максимальное растояние равно 8 (между соседними простыми числами 89 и 97), а до тысячи — 20 (между 887 и 907).

Весь исходный код можно найти на гитхабе.
Читать дальше →

Game of Life с битовой магией, многопоточностью и на GPU

Reading time8 min
Views15K

Всем привет!


Недавняя статья на Хабре в очередной раз показала неостывающий интерес к игре «Жизнь» в частности и всевозможным оптимизациям в общем. Статья и комментарии к ней, особенно любопытство к вычислениям на GPU, вдохновили меня на то, чтобы поделиться своими изысканиями на данном поприще и, забегая вперёд, скажу, что повествование пойдёт о расчётах на GPU, битовой магии, многопоточности и огромных полях для игры «Жизнь», порядка миллиарда клеток.


Читать дальше →

Тетрис на битбордах: старые песни на новый лад

Reading time11 min
Views2.5K
image

Битборды (Bitboard) — специальные битовые структуры, позволяющие эффективно рассчитывать ходы в настольных играх. На хабре писали про применение битбордов к шахматам и даже к шашкам. Сегодня мы применим технику битбордов к несколько неожиданной, но всем знакомой игре – к тетрису. Результатом наших изысканий будет консольная игра, а также автоматический поиск лучших ходов (при заданной последовательности фигур), скорость которого как раз и обеспечивается эффектиностью битовых манипуляций. Заодно мы поддержим проигрывание найденных ходов в автоматическом режиме, чтобы в полной мере насладиться компьютерным интеллектом. В конце статьи дана ссылка на гитхаб с кодом игры на C#, а также коротенькое видео игры из 114 ходов, найденной компьютером поиском в глубину за пятнадцать минут.

Обычно битборд – это машинное слово, состоящее из нескольких байт, каждый бит которого соответствует одной клетке поля в игре. Так, в шахматах всего 64 клетки, что соответствует 8-байтному слову (ulong в C#), а в шашках – 32 (uint в C#). Любители тетриса наверняка помнят, что размер поля в стандартном тетрисе – 10 на 20 клеток, то есть, 200 бит, что не влезает ни в один числовой тип. Конечно, можно разбить поле на четыре части и использовать четыре восьмибайтных слова, или можно не мелочиться и использовать массив из двадцати двухбайтных слов, по одному слову на каждую линию поля; все реализации тетриса на битбордах, которые я нашел (в количестве одной штуки), так и делают. Но мы пойдем другим путем…
Читать дальше →

Как ускорить игру «Жизнь» в сто раз

Reading time17 min
Views52K
image

Сложно найти человека, не знакомого с игрой "Жизнь", придуманной английским математиком Джоном Конвеем еще в 1970 году, и до сих пор не теряющей своей популярности. Многие программисты писали свою реализацию этой игры, и еще одна вряд ли кого-то удивит. Однако эта игра является отличным примером, показывающим, насколько полезной может оказаться оптимизация вычислений, даже не меняющая асимтотическую сложность алгоритма. Мы начнем с простейшей реализации на c# и будем последовательно применять различные оптимизации, ускоряя работу программы.

Мы также улучшим алгоритм на JavaScript, ускорив его в 10 раз по сравнению с неоптимизированной версией.

В конце статьи дана ссылка на код, а также на online-реализацию игры с оптимизированным алгоритмом на JavaScript, выполняющим до двухсот итераций в секунду на поле размера 1920x1080 (Full HD), где вы можете убить время поиграть в эту замечательную игру.
Читать дальше →

База данных простых чисел до ста миллиардов на коленке

Reading time7 min
Views12K
image

Самый известный алгоритм для нахождения всех простых чисел, не больших заданного, – решето Эратосфена. Он замечательно работает для чисел до миллиардов, может быть, до десятков миллиардов, если аккуратно написан. Однако каждый, кто любит развлекаться с простыми числами, знает, что их всегда хочется иметь под рукой как можно больше. Как-то раз мне для решения одной задачи на хакерранке понадобилась in-memory база данных простых чисел до ста миллиардов. При максимальной оптимизации по памяти, если в решете Эратосфена представлять нечетные числа битовым массивом, его размер будет около 6 гигабайт, что в память моего ноутбука не влезало. Существует модификация алгоритма, гораздо менее требовательная по памяти (делящая исходный диапазон чисел на несколько кусков и обрабатывающая по одному куску за раз) – сегментированное решето Эратосфена, но она сложнее в реализации, и результат целиком в память все равно не влезет. Ниже предлагаю вашему вниманию алгоритм почти такой же простой, как и решето Эратосфена, но дающий двукратную оптимизацию по памяти (то есть, база данных простых чисел до ста миллиардов будет занимать около 3 гигабайт, что уже должно влезать в память стандартного ноутбука).
Читать дальше →

Перестановки. 9-й класс. Задача на четность

Reading time3 min
Views4.5K
image

Май выдался холодным, отопление отключили, а вычислительные (и обогревательные) мощности какие-никакие, а простаивают. Так почему бы не загрузить их чем-нибудь бесполезным, что и согреет, и развлечёт.

Но начну издалека. На днях попалась на глаза задачка для средней школы со следующей формулировкой: «Несколько последовательных натуральных чисел выписали в строку в таком порядке, что сумма каждых трёх подряд идущих чисел делится нацело на самое левое число этой тройки. Какое максимальное количество чисел могло быть выписано, если последнее число строки нечётно?»
Читать дальше →
2

Information

Rating
Does not participate
Registered
Activity