Pull to refresh
  • by relevance
  • by date
  • by rating

Три задачки

Entertaining tasks
Представляю вашему вниманию своеобразный блиц — три небольших задачки, начиная от самой баянистой и кончая той, которую вы даже в гугле не найдете =)

1. стена, кирпич, часы, вокзал…
(продолжите последовательность)

2. л, с, д…
(продолжите последовательность)

3. кра.се.т. — что это?
Внимание! Второе задание пока не решено!
Total votes 16: ↑10 and ↓6 +4
Views 700
Comments 31

Отгадайте последовательность

Lumber room
Хотел запостить в Занимательные задачки, но не хватает кармы. Поэтому напишу в своём блоге.

Угадайте, что считает следующая функция f, определённая на множестве натуральных чисел. Вот её первые 40 значений:
f(1) = 0
f(2) = +бесконечность (или неопределена)
f(3) = f(4) = 2
f(5) = f(6) =… = f(13) = 3
f(14) = f(15) =… = f(40) = 4

Если возникнут трудности, то потом дам некоторые подсказки.

Update. Подсказки не понадобились. В комментах уже есть ответ!
Total votes 22: ↑17 and ↓5 +12
Views 275
Comments 34

Открыть сейф

Entertaining tasks
Привет.

Хочу рассказать вам об одной задаче, которая занимает меня уже очень продолжительное время. Сразу хочу сказать, что я не знаю ее решения (чтобы не превращать топик в очередной топик зла). Также я не встречал задач, подобной этой, в интернете, хотя вполне допускаю, что первый же коммент будет со ссылкой на решение.

Читать дальше →
Total votes 22: ↑19 and ↓3 +16
Views 1.2K
Comments 36

Как Роберт Моррис на 8-ми битах до 10 000 считал

Programming *Java *Algorithms *


Как все знают с помощью n-бит, можно реализовать счетчик считающий до 2n-1, но если у вас очень ограниченные ресурсы, или вам просто хочется поэкспериментировать и объединить в одно целое последовательности, вероятности, рандом и увеличение счетчика, то прошу под кат.

Читать дальше →
Total votes 61: ↑52 and ↓9 +43
Views 36K
Comments 51

За один проход

Sport programming *Programming *Algorithms *
Среди задач по программированию часто попадаются такие: дана последовательность однотипных элементов (обычно это числа), требуется за один проход по ней найти какую-нибудь характеристику (среднее квадратическое отклонение, количество минимальных элементов, непрерывный участок с наибольшей суммой...) Дополнительное ограничение — последовательность может быть очень длинной, и в память не поместится. Других ограничений на элементы последовательности, обычно, не накладывается.
С этими задачами всё, более или менее, понятно: нужно найти то, что на мехмате МГУ называют «индуктивным расширением» искомой функции, и реализовать её вычисление. Если найти не удалось (требуемый объём памяти слишком велик), то задача не решается.
Но попадаются и другие задачи. В них есть дополнительные ограничения на элементы последовательности в совокупности, и эти ограничения приходится существенно использовать для решения (и проверять их не надо). Простейшая такая задача выглядит так:

Задача 1. В последовательности записаны целые числа от 1 до N в произвольном порядке, но одно из чисел пропущено (остальные встречаются ровно по одному разу). N заранее неизвестно. Определить пропущенное число

Решение очевидно: просматриваем числа, находим их количество K и сумму S. По условию, N=K+1, значит, сумма чисел от 1 до N будет равна (K+1)*(K+2)/2, и пропущенное число равно (K+1)*(K+2)/2-S. Если вы почему-то боитесь переполнений, то работайте с беззнаковыми числами (там переполнения не страшны — но будьте осторожны при вычислении (K+1)*(K+2)/2 :) ), или вместо суммы ищите XOR всех чисел.
Другие задачи
Total votes 73: ↑72 and ↓1 +71
Views 130K
Comments 55

Создаем произвольный порядок элементов в списке измерений и мер сводной таблицы Excel для табличной модели куба SSAS

Data Mining *Visual Studio *Microsoft SQL Server *Big Data *
Tutorial
Если вам приходилось иметь дело с кубом, в котором число мер и измерений over9000 и не хватает трех экранов, чтобы это уместить, то, наверняка, приходилось слышать и стоны пользователей, на тему неудобства работы с этим чудовищем. Ведь пользователи чаще всего работают с одними и теми же измерениями, без которых не обходится почти ни одна выборка. Однако из-за особенности экселя, любящего сортировать по алфавиту все элементы, находящиеся в области Поля сводной таблицы, эти наиболее востребованные объекты часто разбросаны по всему списку, вперемешку с остальными (редко используемыми) элементами.


Приходится десять раз скролить список вверх и вниз, пока пытаешься установить фильтр на трёх (Дата, Товар, Клиент) полях. Работать с этим каждый день никаких нервов не хватит.

Решение банальное и не новое — в начале имен измерений добавлять символ или цифру, влияя тем самым на порядок.

Но пользователи — это одна сторона медали, им такой подход удобен. А как же разработчики?
Ведь оно как должно быть: начинаешь писать в формуле имя измерения, а студия подсказки выдает, верно? Вот только в случае с допсимволами все это выглядит в коде, скажем так… не очень. В VS2017 уже сделали поиск по вхождению, а в предыдущих такого не было и приходилось писать Календарь не с буквы К, а с цифры 5, потому что 5 Календарь. Запросы в других программах приходится писать без подсказок и упомнить какая цифра у какого измерения или поля — тот еще квест.



Когда нужно изменить порядок, то, по сути, нужно переименовать таблицу или поле, а если это поле используется в формуле, то студия исправит и формулу. Когда формул десятки (а их всегда десятки), то в Git будет подсвечиваться половина модели, потому что студия реально все формулы исправила, в то время как я хотел только поменять поля местами в порядке сортировки. Запросы же в других источниках (за пределами студии) поломаются вообще. Крайне неудобно!

Но выход есть.
Читать дальше →
Total votes 11: ↑10 and ↓1 +9
Views 2.4K
Comments 0

Фрактал Герасимова. Обнаружил закономерность. Таблица Чёрного

Abnormal programming *Algorithms *Mathematics *
Sandbox
Я обнаружил эту закономерность, когда разглядывал пост пользователя xcont. Наткнувшись на эту публикацию, я обратил внимание на то что узоры повторяются не только при увеличении масштаба по числам Фибоначчи.



Мне стало интересно есть ли закономерность в этих узорах. Но имея только 2 параметра x и y, я решил что нужно обозначать что-то ещё, общее среди всех получаемых узоров. Тут я заметил что если взять первые 4 квадрата на поле, в любом случае мы получаем 3 варианта начала узора, если линия идёт:

вверх(↑)



вниз(↓)



или же не идёт*(-)

Читать дальше →
Total votes 31: ↑27 and ↓4 +23
Views 9.3K
Comments 11

Задачи из школьного учебника II

Entertaining tasks Programming *Mathematics *
Часть I
Часть II

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


При решении некоторых задач необходимо рассматривать диапазон, в пределах которого может находиться искомая величина.

Рассмотрим метод оценок при решении неравенств.

Предположим, что цена за одну единицу товара может колебаться в пределах от 5 до 10 RUB. Дать оценку сверху означает определить максимальное значение, которое может принимать искомая величина. Для двух единиц товара, цена за который не превышает 10 оценка сверху составит 10+10=20.

Рассмотрим задачу из задачника профильной направленности М.И. Башмакова
37. Известны оценки для переменных $ x $ и $ y: 0<x<5, 2<y<3.$

Дайте оценки сверху для следующих выражений:
1. $ 2x+3y $
2. $ xy $

5. $ \frac{ 1 }{y} $
6. $ \frac{ x }{y} $

8. $ x-y $
9. $ 3x-2y $

Указание к решению задач
Для оценки этих значений необходимо воспользоваться следующим свойством числовых неравенств:
Если $a<b$ и оба числа положительны, то $ -a>-b $
Если $a<b$ и оба числа положительны, то $ \frac{ 1 }{a}>\frac{ 1 }{b}$
При умножении членов неравенства на одно и то же положительное число смысл неравенства не меняется, при умножении членов неравенства на одно и то же отрицательное число смысл неравенства меняется на противоположный.
Доказательство (Элементарная математика).
Пусть $a>b$, тогда $a-b>0$. Если $m>0$, то $m(a-b)>0$, так как произведение положительных чисел положительно. Раскрыв скобки в левой части последнего неравенства, получим $am-bm>0$, т.е. $am>bm$. Аналогичным образом рассматривается случай $m<0$.
Точно такой же вывод можно сделать и относительно деления частей неравенства на какое-либо отличное от нуля число, так как деление на число $n \neq 0$ равносильно умножению на число $1/n$, а числа $n$ и $1/n$ имеют одинаковые знаки.


Читать дальше →
Total votes 17: ↑16 and ↓1 +15
Views 7.2K
Comments 1

Треугольник Паскаля vs цепочек типа «000…/111…» в бинарных рядах и нейронных сетях

Data Mining *Algorithms *Big Data *Mathematics *Open data *

Серия «Белый шум рисует черный квадрат»



История цикла этих публикаций начинается с того, что в книге Г.Секей «Парадоксы в теории вероятностей и математической статистике» (стр.43), было обнаружено следующее утверждение:


Рис. 1.

По анализу комментарий к первым публикациям (часть 1, часть 2) и последующими рассуждениями созрела идея представить эту теорему в более наглядном виде.

Большинству из участников сообщества знаком треугольник Паскаля, как следствие биноминального распределения вероятностей и многие сопутствующие законы. Для понимания механизма образования треугольника Паскаля развернем его детальнее, с развертыванием потоков его образования. В треугольнике Паскаля узлы формируются по соотношению 0 и 1, рисунок ниже.


Рис. 2.

Для понимания теоремы Эрдёша-Реньи составим аналогичную модель, но узлы будут формироваться из значений, в которых присутствуют наибольшие цепочки, состоящие последовательно из одинаковых значений. Кластеризации будет проводиться по следующему правилу: цепочки 01/10, к кластеру «1»; цепочки 00/11, к кластеру «2»; цепочки 000/111, к кластеру «3» и т.д. При этом разобьём пирамиду на две симметричные составляющие рисунок 3.


Рис. 3.

Первое что бросается в глаза это то, что все перемещения происходят из более низкого кластера в более высокий и наоборот быть не может. Это естественно, так как если цепочка размера j сложилась, то она уже не может исчезнуть.
Читать дальше →
Total votes 17: ↑17 and ↓0 +17
Views 4.2K
Comments 5

Какой следующий член…? — Ищем формулу для n-го члена последовательности, производящие функции и Z-преобразование

Wolfram Research corporate blog Entertaining tasks Programming *Algorithms *Mathematics *
Tutorial
Скачать файл с кодом и данные можно в оригинале поста в моем блоге

В языке Wolfram Language есть четыре совершенно потрясающие функции: FindSequenceFunction, RSolve, DifferenceRootReduce и FindFormula. В этой статье мы обсудим их возможности и поговорим о функциях, тесно с ними связанных — для поиска параметров линейной рекурсии FindLinearRecurrence (коэффициентов линейного рекуррентного уравнения), производящих функциях GeneratingFunction и Z-преобразовании ZTransform.

Первая функция — FindSequenceFunction — по последовательности чисел ищет выражение для её n-го члена не требуя вообще ничего более.

Hold @ FindSequenceFunction[{1, 1, 2, 3, 5, 8, 13}, n]



FindSequenceFunction[
{-2, 4Sqrt[Pi],
-16, 16Sqrt[Pi],
-128/3, 32Sqrt[Pi],
-1024/15, 128Sqrt[Pi]/3,
-8192/105, 128Sqrt[Pi]/3},
n]


Читать дальше →
Total votes 17: ↑17 and ↓0 +17
Views 4.5K
Comments 3

Что нужно знать об устройстве коллекций, основанных на хешировании

OTUS corporate blog Programming *Java *Algorithms *Industrial Programming *
Всем привет. На связи Владислав Родин. В настоящее время я являюсь руководителем курса «Архитектор высоких нагрузок» в OTUS, а также преподаю на курсах, посвященных архитектуре ПО.

Помимо преподавания, как вы могли заметить, я занимаюсь написанием авторского материала для блога OTUS на хабре и сегодняшнюю статью хочу посвятить запуску нового потока курса «Алгоритмы для разработчиков».





Введение


Хеш-таблицы (HashMap) наравне с динамическими массивами являются самыми популярными структурами данных, применяемыми в production'е. Очень часто можно услышать вопросы на собеседованиях касаемо их предназначения, особенностей их внутреннего устройства, а также связанных с ними алгоритмов. Данная структура данных является классической и встречается не только в Java, но и во многих других языках программирования.
Читать дальше →
Total votes 16: ↑14 and ↓2 +12
Views 7.8K
Comments 4

Последовательность и последствия

Abnormal programming *System Analysis and Design *Popular science

Последовательность действий важна.

Наш мир опутан многочисленными невидимыми связями, которые мы не ощущаем и, зачастую, не понимаем. И если сделать неверный шаг, результат будет…
Читать дальше →
Total votes 3: ↑0 and ↓3 -3
Views 1.2K
Comments 4

Генерация случайных чисел с помощью ДНК

ua-hosting.company corporate blog Information Security *Cryptography *Popular science Biotechnologies


Случайности. Для кого-то все, что происходит вокруг, это одна сплошная случайность. А кто-то утверждает, что случайностей не бывает. Философствовать и спорить на эту тему можно много часов, а выводов все равно будет множество. Перейдя от метафизических размышлений к более реальным, можно увидеть, что случайные числа нашли свое применение во многих аспектах нашей жизни: от игровых автоматов до систем кодирования информации. Процесс, во время которого создается последовательность случайных чисел/символов, которую нельзя предугадать, именуется генерацией случайных чисел (ГСЧ). За долгую историю человечества было создано немало методов ГСЧ. Одни достаточно просты и понятны: игральные кости, монеты (орел/решка), колода карт и т.д.

Другие же применяют куда более сложные физические процессы: к примеру, за счет высокочастотных движений электронов электрическое сопротивление провода не является постоянным, т.е. варьируется случайным образом. Измерив этот фоновый шум, можно получить последовательность случайных чисел. Но методики ГСЧ не ограничиваются исключительно физикой. Группа ученых из Швейцарской высшей технической школы Цюриха (или сокращенно ETHZ) создали новый метод генерации случайных чисел, основанный на синтезе ДНК. Как именно это было достигнуто, насколько случайны полученные число, и можно ли их предугадать? Ответы на эти вопросы ждут нас в докладе ученых. Поехали.
Читать дальше →
Total votes 19: ↑19 and ↓0 +19
Views 2.2K
Comments 2

Посмеяться над мемами, стать мемологом, найти связь между «Симпсонами» и «Риком и Морти»: итоги конкурса про мемы

FUNCORP corporate blog Reading room Conferences

На прошлой неделе прошла конференция по мобильной разработке Mobius 2021, на которой мы выступили с докладом про анализ данных в приложениях, а также предложили участникам поиграть в мем-квиз и Memology Game. Cуть последней — найти связь между мемами и выстроить их в единую логическую цепочку.

Под катом поделимся результатами, а также расскажем, как появилась идея, какие шишки набили при её создании, и что интересного для себя открыли.

Спойлер: в игре может быть бесконечно много решений, помимо тех, что задумали мы, и надеемся, что читатели Хабра помогут отыскать наиболее оригинальные варианты. Авторов самых на наш взгляд необычных решений наградим мерчем. Свои варианты оставляйте в комментариях к статье.

А еще предлагаем поучаствовать в разработке Memology 2.0 и дать обратную связь — что подкрутить, чтобы игра стала лучше/понятнее/интереснее/смешнее.

Читать далее
Total votes 49: ↑26 and ↓23 +3
Views 1.5K
Comments 5