Все сервисы Хабра

Сообщество IT-специалистов

Ответы на любые вопросы об IT

Профессиональное развитие в IT

Удаленная работа для IT-специалистов

Войти на сайт
  • Все вопросы
  • Все теги
  • Пользователи

Хабр Q&A — вопросы и ответы для IT-специалистов

Получайте ответы на вопросы по любой теме из области IT от специалистов в этой теме.

Узнать больше
другие проекты хабра
  • Хабр
  • Карьера
  • Фриланс
Задать вопрос
Mrrl

Mrrl

Заводчик кардиганов
  • 220
    вклад
  • 0
    вопросов
  • 299
    ответов
  • 36%
    решений
Комментарии
  • Информация
  • Ответы
  • Вопросы
  • Комментарии
  • Подписки
  • Нравится
  • Достижения
  • Стоит ли читать WEB-программисту книгу "Д.Е Кнут искусство программирования"?

    Mrrl
    Mrrl @Mrrl
    Alexander: Этот пример - примерно 4-й курс мехмата (моя дочка сейчас готовится к экзамену - там очень похожая тематика). Конечно, просто понять формулы и приёмы можно и в 11 классе, но чтобы они вошли в общую картину мира, надо знать гораздо больше.
    Написано более трёх лет назад
  • Как разбить множество на три подмножества с одинаковой суммой элементов?

    Mrrl
    Mrrl @Mrrl
    volyihin: В знаке закодировано направление, с которого мы пришли в клетку (a,b): если в ней +x, то пришли с клетки (a-x,b) - и элемент x принадлежит первому множеству, а если -x - то пришли с (a,b-x), и элемент x принадлежит второму множеству.
    Написано более трёх лет назад
  • Как разбить множество на три подмножества с одинаковой суммой элементов?

    Mrrl
    Mrrl @Mrrl
    Владимир Петриго: Это даст выигрыш в 2 раза. При больших n (и не очень больших значениях) этого не хватит.
    Написано более трёх лет назад
  • Как разбить множество на три подмножества с одинаковой суммой элементов?

    Mrrl
    Mrrl @Mrrl
    Вики утверждает, что достаточно O(n*m^2) памяти, где m - наибольшее число, а n - длина последовательности. Это заметно меньше, чем O(S^2). Интересно, как.
    Написано более трёх лет назад
  • Как разбить множество на три подмножества с одинаковой суммой элементов?

    Mrrl
    Mrrl @Mrrl
    Владимир Петриго: Да, если на обратном пути проверять именно возможность прохода по последнему элементу, то не заблудимся. Будет ли проще решение? Возможно, будет. Хотя и незначительно.
    А если последовательность содержит меньше 40 элементов, то можно сделать наоборот - завести массив UInt64[S/3+1,S/3+1], и сразу накапливать в его посещённых элементах разбиение на подмножества - в троичной системе. Тогда идти назад не придётся, в последней клетке будет сразу готов ответ.
    Написано более трёх лет назад
  • Как определить координаты тела, если оно движется по эллипсу?

    Mrrl
    Mrrl @Mrrl
    Японский Городовой: Действительно, там же "текущее положение планет"! Большие планеты у нас движутся по окружности, а далёкие карликовые за время существования программы сдвинутся так мало, что этим можно пренебречь, достаточно оставить их в положении на какой-нибудь 2020 год.
    Написано более трёх лет назад
  • Как разбить множество на три подмножества с одинаковой суммой элементов?

    Mrrl
    Mrrl @Mrrl
    Ашот Такиев: Если получится восстановить, то хорошо. Но всё зависит от того, что именно вы храните в массиве. Если это, допустим, история заполнения достижимых ячеек (sum(S1),sum(S2)), то при обратном поиске есть опасность пойти по ложному пути.
    Массив обратных ссылок - самый дешёвый и надёжный вариант. И его можно делать не дополнительным, а единственным (ссылки нет - клетка пока недостижима).
    Написано более трёх лет назад
  • Как найти максимальное значение без ?/switch/if?

    Mrrl
    Mrrl @Mrrl
    Осталось написать abs без условных операторов :)
    Написано более трёх лет назад
  • Как разбить множество на три подмножества с одинаковой суммой элементов?

    Mrrl
    Mrrl @Mrrl
    Антон Федорян:
    x = [8, 6, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3]
    IndexError: list index out of range
    Написано более трёх лет назад
  • Как разбить множество на три подмножества с одинаковой суммой элементов?

    Mrrl
    Mrrl @Mrrl
    Вы решили задачу о рюкзаке за O(N)? Поздравляю.
    И что она сделает с таким массивом: [3, 2, 2, 3, 2, 6] ?
    Написано более трёх лет назад
  • Как найти максимальное значение без ?/switch/if?

    Mrrl
    Mrrl @Mrrl
    Антон: Так он ведь не отсортирован! 65 идёт после 98.
    Написано более трёх лет назад
  • Что не так с алгоритмом для поиска наибольшей неубывающей подпоследовательности?

    Mrrl
    Mrrl @Mrrl
    Ашот Такиев: В начале d={-1,-1,-1,...} - ни одной последовательности у нас нет.
    Приходит элемент с индексом 0, равный 1. Он образует последовательность длины 1, предыдущего элемента у него нет. Поэтому у нас есть последовательность длины 1, кончающаяся на элементе с индексом 0 (d[1]=0), и prev[0]=-1.
    Приходит элемент с индексом 1, равный 2. Последовательность длины 1 из него делать неэффективно (поскольку у нас уже есть последовательность с меньшим последним элементом), но мы можем добавить его к имеющейся последовательности, и получить последовательность длины 2: d[2]=1, prev[1]=0 (элемент с индексом 1 идёт после элемента с индексом 0).
    Аналогично обрабатываем 7,8 и 9: d[3]=2, prev[2]=1; d[4]=3, prev[3]=2; d[5]=4,prev[4]=3.
    Приходит 5 (элемент с индексом 5). Его мы можем вставить после двойки, получив лучшую последовательность длины 3: d[3]=5, prev[5]=1. Дальше получится d[4]=6, prev[6]=5 и d[3]=7, prev[7]=1.
    Чтобы построить по массивам d и prev ответ, надо ещё поработать. Начать с элемента d[5]=4 (самая длинная последовательность), потом взять prev[4]=3, prev[3]=2, prev[2]=1, prev[1]=0, prev[0]=-1. Это (кроме последнего числа) индексы ответа, записанные в обратном порядке. Берём элементы исходного массива по этим индексам: 1,2,3,8,9 - они и дадут ответ.
    Написано более трёх лет назад
  • Как найти разницу двух чисел в массиве рекурсивно?

    Mrrl
    Mrrl @Mrrl
    Похоже, что без Find1 можно обойтись, вызвав сразу Find2(0,n-1,0,n-1).
    Фактически, мы здесь проверяем некоторое свойство для двух отрезков, для чего делим один из отрезков пополам, и сопоставляем каждую половину с другим отрезком. Может быть, задача не очень удачна, но этот приём надо знать. Например, это решение легко обобщается на двумерный случай (найти два таких числа в массиве, монотонном по обеим координатам). С указателями вы там намучаетесь.
    Написано более трёх лет назад
  • Как найти разницу двух чисел в массиве рекурсивно?

    Mrrl
    Mrrl @Mrrl
    ifqthenp: Удачи. Конечно, рекурсия в сочетании с побочными эффектами может озадачить проверяющего. Но здесь такой подход делает код и проще, и эффективнее.
    Написано более трёх лет назад
  • Как найти разницу двух чисел в массиве рекурсивно?

    Mrrl
    Mrrl @Mrrl
    Для второй задачи - то же, но убираете проверки A[q]-A[p] < M и им подобные, оставляете только ==M.
    Написано более трёх лет назад
  • Как найти разницу двух чисел в массиве рекурсивно?

    Mrrl
    Mrrl @Mrrl
    ifqthenp: Да, рекурсия здесь слегка не по делу, задача проще без неё (в обоих случаях). Для второй достаточно отсортировать массив и свести задачу к первой (O(n*log n)). Вот если массив портить нельзя, а дополнительная память разрешается не более O(log(n)) - тут надо думать.
    Написано более трёх лет назад
  • Как решить задачу об огурцах?

    Mrrl
    Mrrl @Mrrl
    И что он сделает для такого поля (стоимость парника - 2 клетки)?
    * * * . *
    . . . . *
    * . . . *
    * . . . .
    * . * * *
    Написано более трёх лет назад
  • Как решить задачу об огурцах?

    Mrrl
    Mrrl @Mrrl
    Например. Пусть посадка такая:
    * . .
    * * .
    * . *
    . * *

    стоимость парника - 3 дополнительных клетки.
    Идём снизу. Конфигурацию будем задавать отрезками пересечения линии с парниками. Например, [1,2],[3] - линия пересекла два парника, один занял первые две клетки, другой - третью.
    В начале у нас парников нет, штраф нулевой.
    В первой строке мы можем построить такие конфигурации:
    (A1): [1,2],[3] - штраф=9 (два парника и 3 клетки)
    (A2): [1,2,3] - штраф=6
    (A3): [2],[3] - штраф=8
    (A4): [2,3] - штраф=5.
    В следующей строке возможны конфигурации
    (B1): [1],[2],[3] - штраф=14 (из A3)
    (B2): [1],[3] - штраф=13 (из A3 или А4)
    (B3): [1,2],[3] - штраф=12 (из A1)
    (B4): [1],[2,3] - штраф=11 (из A4)
    (B5): [1,2,3] - штраф=9 (из A2)
    B1 может получиться только из A3 (продлили парник [2]), остальные конфигурации - из любой другой.
    Строка 3:
    (C1): [1],[2],[3] - штраф=17 (из B1)
    (C2): [1],[2] - штраф=16 (из B1 или B4)
    (C3): [1],[2,3] - штраф=14 (из B4)
    (C4): [1,2],[3] - штраф=15 (из B3)
    (C5): [1,2] - штраф=14 (из B3 или B5)
    (C6): [1,2,3] - штраф=12 (из B5)
    Последняя строка:
    (D1): [1],[2],[3] - штраф=20 (из C1)
    (D2): [1],[2] - штраф=18 (из C2)
    (D3): [1],[2,3] - штраф=17 (из C3)
    (D4): [1,2],[3] - штраф=18 (из C4)
    (D5): [1,2] - штраф=16 (из C5)
    (D6): [1,2,3] - штраф=15 (из C6)
    (D7): [1] - штраф=15 (из C3)
    (D8): [1],[3] - штраф=19 (из С1 или С3).
    Таким образом, получаем две оптимальных конфигурации: либо один парник на всю площадь, либо два парника - один в левом ряду, другой в двух правых.
    Написано более трёх лет назад
  • Как спроецировать фигуру на плоскость?

    Mrrl
    Mrrl @Mrrl
    Strollager: Для плоскости z=0 - да. В этом случае x'=x, y'=y. Если бы вы проектировали на плоскость x+y+z=1, можно было бы взять О=(0,0,1), X=(1,-1,0)/sqrt(2), Y=(1,1,-2)/sqrt(6), и формулы для x', y' были бы сложнее.
    Написано более трёх лет назад
  • В чем проблема в типах данных при поиске факториала?

    Mrrl
    Mrrl @Mrrl
    А что это за компилятор? С 16-битным int и действующим long double? Неужели Borland?
    И до какого числа надо считать факториал? Переход к каждому новому типу (short - long - double - int64) увеличит порог примерно на 3-5 чисел, так что в общем случае потребуется длинная арифметика.
    Написано более трёх лет назад
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • Следующие →
Самые активные сегодня
  • vabka
    Василий Банников
    • 9 ответов
    • 0 вопросов
  • sasmoney
    sasmoney
    • 9 ответов
    • 0 вопросов
  • Drno
    • 5 ответов
    • 0 вопросов
  • GNUBack
    • 5 ответов
    • 0 вопросов
  • nedosekinstanislav
    Stanislav
    • 4 ответа
    • 0 вопросов
  • Sanes
    Sanes
    • 4 ответа
    • 0 вопросов
  • © Habr
  • О сервисе
  • Правила
  • Обратная связь
  • Блог

Войдите на сайт

Чтобы задать вопрос и получить на него квалифицированный ответ.
Войти через центр авторизации