Я могу САМ решить безопасно ли мне находиться рядом с вором-рецидивистом "но это было давно и я прощен" или с нетвойнистом "меня посадили ни за что"
"Политические" судимости, имхо, правильнее вообще не упоминать в справке. Понятно что тот же нетвойнист, в отличии от уголовника, никакой опасности не представляет и для адекватных людей это скорее даже плюс, но вот нанимающий может оказаться с "пунктиком" в голове и только на основании этого отказать хорошему кандидату.
При наличии в ЯП из коробки комплексных чисел, перебирать соседние 4 клетки можно было бы с помощью умножения на i (мнимую единицу). Или на -i, чтобы в другую сторону.
О быстром и медленном указателях для этой задачи несколько раз писали на Хабре. Так же известно, что если стартовать два медленных указателя, один от начала списка, другой от места встречи fast и slow, то новая встреча будет как раз в узле, на который ссылается хвост. Доказательство этого факта внесло бы новизну в тему.
Пределы нужны, чтобы не уходить в бесконечные вычисления, если в рекурсивном типе забыли дописать условие остановки. Выбраны, скорее всего, каким-то опытным путем. Вот ПР, в котором они были окончательно установлены для обычной рекурсии и увеличены для хвостовой.
Утилиты со светчиками за пределами всяких тайпчелленджей практически не встречаются)
Надо заметить, что TExtractAllKeysTypeA поддерживает более глубокую рекурсию, чем TExtractAllKeysTypeB. У первого 48, у второго 32. Первый можно улучшить до 96, убрав рекурсивный вызов из конкатенации наружу:
Код
type TExtractAllKeysTypeA1<O, P extends string = '', K extends keyof O = keyof O> = K extends string
? O[K] extends string
? `${P}${K}`
: TExtractAllKeysTypeA1<O[K], `${P}${K}.`>
: never;
Но это не всегда хвостовая рекурсия (последнее действие тут может быть объединение дистрибутивных результатов, если их больше одного).
Хвостовая позволит увеличить глубину рекурсии до 1000:
Код
type GetNext<D, T> = D extends [infer P extends string, infer O]
? keyof O extends infer K extends keyof O
? K extends string
? O[K] extends T
? O[K] extends string
? `${P}${K}`
: [`${P}${K}.`, O[K]]
: never
: never
: never
: never;
type TailRec<D, R = never> = [D] extends [never]
? R
: TailRec<GetNext<D, object>, R | GetNext<D, string>>;
type TExtractAllKeysTypeC<O> = TailRec<['', O]>;
Здесь never оказался в довольно свойственной для себя роли единичного элемента операции объединения - с него начинает накапливаться результат R в типе TailRec.
Ещё один забавный факт: keyof never = string | number | symbol. Откуда внутри пустого типа "столько всего"? Формально, never является подтипом любого объекта, потому в нем есть все возможные поля, какие могут быть в объетах.
Тут формально можно так разуметь. При R >= r, то у нас в плоскости ХУ есть круг радиуса r, с центром в т. (0, R), над осью Х, а тор получен вращением этого круга вокруг оси Х. И весь этот круг имеет положительную площадь, а весь тор - соответственно, положительный объем.
Если взять 0 < R < r, тогда часть круга оказывается ниже оси Х. Её площадь - "отрицательна", и своим вращением она вычерчивает в пространстве "отрицательный" объем, т.к. крутится в ту же сторону. Объем тора - сумма "отрицательной" и положительной компонент. Даша получает всё что выше R - там только положительное, а Саша - всё что ниже R, там положительное и "отрицательное".
Если R = 0, то по этой схеме выходит, что у Даши один шар, а у Саши - "минус один" шар.
Интересно так же, что если ответ не делить на Пи, то будет объем шара с радиусом r.
Такие задачи интереснее решать без интегралов, "простыми школьными рассуждениями". Выясним, насколько объем дашиной (синей) части больше, чем половина - это то же самое значение, как половина минус розовая часть.
Сначала докажем, что ответ не зависит от R. Сечение тора любой плоскостью, перпендикулярной его оси и удаленной от центра не более чем на r, дает область между окружностями радиусом (R-m) и (R+m). Легко посчитать через разность площадей кругов:
Площадь сей области S = 4*Пи*R*m
Площадь синей части Sb = Пи*m*m + 2*Пи*R*m
Разница D = Sb - S/2 = Пи*m*m
Итого, в каждом таком сечении разница не зависит от R. Значит, она и для всего объема не зависит от R.
Тогда если R уменьшить до нуля, то объем тора будет 0, а синяя часть будет шаром с объемом 4Пи*r^3 / 3. Это и есть ответ.
Не, ну сам по себе бинпоиск разобран, тут без вопросов. Только реализовывать нужно именно как upperbound/lowerbound. Во-первых, потому что это задача в общем виде, а поиск элемента - частный случай. Во-вторых, на каждой итерации на одно сравнение меньше, в самих итераций - лишь на одну больше в среднем случае (у представленного здесь поиска элемента делается выход из цикла, если элемент нашелся, до полного сужения интервала, но в среднем случае это будет на предпоследней итерации). Иными словами, писать "поиск элемента" - то, как не надо делать.
Это пояснение автору, до чего именно я так душно докопался.
Решает (но не в js, там нет этого). Однако в общем случае перековка рекурсии в хвостовую точно такая же, как в цикл. И не имеет смысла, если в языке есть цикл.
Глубина стека - всего 16 элементов? Тут же в рекурсии в любой момент времени уменьшается или n, или m - значит, в любой момент времени глубина стека не более n+m.
Не уменьшается. ackermann(m - 1, ackermann(m, n - 1)) - здесь второй параметр может быть гораздо больше исходного n
Для ackermann(3, n) глубина рекурсии будет 2^(n+3)
"Политические" судимости, имхо, правильнее вообще не упоминать в справке. Понятно что тот же нетвойнист, в отличии от уголовника, никакой опасности не представляет и для адекватных людей это скорее даже плюс, но вот нанимающий может оказаться с "пунктиком" в голове и только на основании этого отказать хорошему кандидату.
По хорошему надо бы законодательно приравнять возраст к "медицинской тайне", чтобы работодатели и hr-щики не совали нос куда не следует.
При наличии в ЯП из коробки комплексных чисел, перебирать соседние 4 клетки можно было бы с помощью умножения на i (мнимую единицу). Или на -i, чтобы в другую сторону.
Крышка не проваливается в люк, видимо. Но тут надо знать диаметр люка и крышки.
О быстром и медленном указателях для этой задачи несколько раз писали на Хабре. Так же известно, что если стартовать два медленных указателя, один от начала списка, другой от места встречи fast и slow, то новая встреча будет как раз в узле, на который ссылается хвост. Доказательство этого факта внесло бы новизну в тему.
Пределы нужны, чтобы не уходить в бесконечные вычисления, если в рекурсивном типе забыли дописать условие остановки. Выбраны, скорее всего, каким-то опытным путем. Вот ПР, в котором они были окончательно установлены для обычной рекурсии и увеличены для хвостовой.
Утилиты со светчиками за пределами всяких тайпчелленджей практически не встречаются)
Надо заметить, что
TExtractAllKeysTypeAподдерживает более глубокую рекурсию, чемTExtractAllKeysTypeB. У первого 48, у второго 32. Первый можно улучшить до 96, убрав рекурсивный вызов из конкатенации наружу:Код
Но это не всегда хвостовая рекурсия (последнее действие тут может быть объединение дистрибутивных результатов, если их больше одного).
Хвостовая позволит увеличить глубину рекурсии до 1000:
Код
Здесь
neverоказался в довольно свойственной для себя роли единичного элемента операции объединения - с него начинает накапливаться результатRв типеTailRec.Наглядно заценить можно здесь.
Ещё один забавный факт:
keyof never = string | number | symbol. Откуда внутри пустого типа "столько всего"? Формально,neverявляется подтипом любого объекта, потому в нем есть все возможные поля, какие могут быть в объетах.Да, с нулевым R всё непросто)
Тут формально можно так разуметь. При R >= r, то у нас в плоскости ХУ есть круг радиуса r, с центром в т. (0, R), над осью Х, а тор получен вращением этого круга вокруг оси Х. И весь этот круг имеет положительную площадь, а весь тор - соответственно, положительный объем.
Если взять 0 < R < r, тогда часть круга оказывается ниже оси Х. Её площадь - "отрицательна", и своим вращением она вычерчивает в пространстве "отрицательный" объем, т.к. крутится в ту же сторону. Объем тора - сумма "отрицательной" и положительной компонент. Даша получает всё что выше R - там только положительное, а Саша - всё что ниже R, там положительное и "отрицательное".
Если R = 0, то по этой схеме выходит, что у Даши один шар, а у Саши - "минус один" шар.
Интересно так же, что если ответ не делить на Пи, то будет объем шара с радиусом r.
Такие задачи интереснее решать без интегралов, "простыми школьными рассуждениями". Выясним, насколько объем дашиной (синей) части больше, чем половина - это то же самое значение, как половина минус розовая часть.
Сначала докажем, что ответ не зависит от R. Сечение тора любой плоскостью, перпендикулярной его оси и удаленной от центра не более чем на r, дает область между окружностями радиусом (R-m) и (R+m). Легко посчитать через разность площадей кругов:
Площадь сей области S = 4*Пи*R*m
Площадь синей части Sb = Пи*m*m + 2*Пи*R*m
Разница D = Sb - S/2 = Пи*m*m
Итого, в каждом таком сечении разница не зависит от R. Значит, она и для всего объема не зависит от R.
Тогда если R уменьшить до нуля, то объем тора будет 0, а синяя часть будет шаром с объемом 4Пи*r^3 / 3. Это и есть ответ.
Вопрос по таблице сравнений (которая где-то вверху): а как у вас так вышло, что на мобиксе нельзя покрыть код линтерами и тестами?
А если вот так:
Так М и Ж примерно одинаковое количество. Значит, есть ещё один М, у которого 0, а в среднем получается 1.
По мнению властей, качество сильно ухудшается, если на компьютер пользователя может прийти что-то супротив официальной пропаганды.
Зеркальные стены (которые планируется добавить) напомнили вот такую задачу
Не, ну сам по себе бинпоиск разобран, тут без вопросов. Только реализовывать нужно именно как upperbound/lowerbound. Во-первых, потому что это задача в общем виде, а поиск элемента - частный случай. Во-вторых, на каждой итерации на одно сравнение меньше, в самих итераций - лишь на одну больше в среднем случае (у представленного здесь поиска элемента делается выход из цикла, если элемент нашелся, до полного сужения интервала, но в среднем случае это будет на предпоследней итерации). Иными словами, писать "поиск элемента" - то, как не надо делать.
Это пояснение автору, до чего именно я так душно докопался.
Написать кучу букв про бинпоиск и не упомянуть upperbound/lowerbound - зря время потратить.
Решает (но не в js, там нет этого). Однако в общем случае перековка рекурсии в хвостовую точно такая же, как в цикл. И не имеет смысла, если в языке есть цикл.
Не уменьшается.
ackermann(m - 1, ackermann(m, n - 1))- здесь второй параметр может быть гораздо больше исходного nДля
ackermann(3, n)глубина рекурсии будет 2^(n+3)У бумажных книг только один плюс: более приятный процесс чтения. Но это субъективно, конечно же.
Сам изредка тоже достаю свои первые книги по программированию - в сугубо ностальгических целях.
Всё то же самое.