Пользователь пока ничего не рассказал о себе

Наибольший вклад в теги

Все теги (28)

Лучшие ответы пользователя

Все ответы (641)
  • Возможно ли решить данную задачу?

    @Mercury13
    Программист на «си с крестами» и не только
    1018 — это обычное 64-битное целое. long long в Си, long в Java, int64 в Delphi.

    Очевидно, задача переводная, спичка не только match (это слово у них очень многозначное), но и matchstick. Причём переводил то ли автомат, то ли редкий надмозг, пример неговорящий, и откровенно непонятно: то ли где находится число 11, то ли что на 11-й позиции. Будем решать 2-ю задачу: что на 11-й позиции.

    1. Определить количество разрядов (для этого хватает несложного цикла) и какой номер у данного числа среди N-значных чисел.
    2. А теперь находим, сколько есть N-значных чисел из M спичек. Рекуррентное соотношение:

    Q[N, M] = sum{k = 1..9} (Q[N−1, M−q(k)]), если N — найденная нами значность, но не 1-ца,
    Для остальных N формула та же, но суммирование 0…9.
    q(0) = 6, q(1) = 2, q(2) = 5, и т.д. — кол-во спичек в цифре.
    Граничное условие: Q[0, 0] = 1, Q[0, M] = 0 для остальных M.
    «Методом выкручивания рук» также примем, что для отрицательных M все Q равняются 0.

    Решаем рекуррентное соотношение динамическим программированием.
    3. А теперь самое интересное: воспользовавшись таблицей динамического программирования, находить цифру за цифрой, начиная со старшей.

    Например, у нас 15-е число. Первый шаг опустим, поверьте мне: это 4-е двузначное, начиная с нуля.
    2-й шаг.
    Q[1,2] = 1
    Q[1,3] = 1
    Q[1,4] = 1
    Q[1,5] = 3
    Q[1,6] = 3
    Q[1,7] = 1
    Q[2,4] = 1
    Q[2,5] = 2
    Q[2,6] не вычислял, главное — запредельно большое.

    Q[2,0]…Q[2,3] равняются нулю.
    Вычитаем Q[2,4] — получается 3.
    Вычитаем Q[2,5] — получается 1.
    Вычитаем Q[2,6] — не получается. Итого у нас шесть спичек, остаётся 1.

    3-й шаг, работаем по цифре.
    Ноль, Q[1, 6−6] = 0. Остаётся 1.
    Единица, Q[1, 6−2] = 1. Остаётся 0.
    Двойка, Q[1, 6−5] = 0. Остаётся 0.
    Тройка, Q[1, 6−5] = 0. Остаётся 0.
    Четвёрка, Q[1, 6−4] = 1. Не вычитается, остаётся 2 спички, 1 знак и номер 0. Записываем цифру 4.
    Ноль, Q[0, 2−5] = 0. Остаётся 0.
    Единица, Q[0, 2−2] = 1. Не вычитается, остаётся 0 спичек, 0 знаков и номер 0. Записываем цифру 1.

    Итого получили 41.
    Ответ написан
  • План подготовки для поступления в Яндекс ШАД?

    @Mercury13
    Программист на «си с крестами» и не только
    Алгоритмы. Немного олимпиадного программирования ОЧЕНЬ не помешает. Алгоритмы там предлагают несложные, но очень нетривиальные, надо чувствовать, как решить задачу. Элементы сложности алгоритмов. Две задачи из восьми гарантированно будут.

    Алгебра и дискретная математика. Первый курс, всё скопом, без доказательств. Линейные уравнения, квадратичные формы, матрицы, собственные векторы, жорданова форма, перестановки, графы, теория множеств, комбинаторика, алгебра логики…

    Интегралы (не слишком «злые», но приёмы «подстановка», «по частям» и «тригонометрический интеграл» всё же освоить стоит). Интеграл средней сложности — постоянный гость в ШАДý. Может быть и ещё одна задача из мутьанализа — но это как повезёт и задача будет гарантированно нетривиальная, но решающаяся на «том, что помнишь с института» — дифференцирование, ряды Тейлора, основы топологии, простейшие пределы, правило Лопиталя. Вспомни, как берутся простейшие двойные интегралы, может попасться, например, на теории вероятностей.

    ФКП. Самое начало. Аналитических функций и рядов Лорана точно не будет. А вот то, что в комплексном поле многочлен n-й степени имеет n корней, знать надо.

    Теория вероятностей. Непрерывные и дискретные вероятности. Нечто несложное, почти что на уровне кубиков и карт, но одна-две из восьми будет. Хотя статистика — важная часть ШАДа, на экзамене не требуют. И пекла типа белых шумов и интегралов Ито не будет. Хотя что-то типа дискретной марковской цепи — а вдруг, хотя знакомые мне три экзамена не было.

    Школьные олимпиадные задачи. Возможна одна.

    Итого.
    Две — алгоритмы.
    Одна-две — вероятность.
    Одна — интеграл.
    Две-три — что угодно из школьной математики, дискретной математики, матанализа, алгебры, ФКП…

    P.S. Очень хороший приём, который мне помог. Конечно, вам придётся держать скан какого-нибудь справочника или распечатку Википедии (это не возбраняется, но электроника запрещена — впрочем, калькулятора задачи не требуют). Печатайте на одной стороне, вторую — на черновик!
    Ответ написан
  • Может кто объяснить, что происходит при кликании ярлыка программы на физическом уровне?

    @Mercury13
    Программист на «си с крестами» и не только
    1. Мышь посылает команды «Я нажата» и «Я отпущена». Считаем, что мышь USB’шная — тогда диспетчер шины 125 раз в секунду даёт мыши таймслот, и она за это время посылает 8-байтовый пакет, и в нём есть поля «сдвиг по X, сдвиг по Y, нажатые кнопки». Сама ОС ведёт счёт координатам курсора мыши. Отображение курсора мыши — это отдельная функция графического драйвера (из-за требовательности к скорости).
    2. ОС из этих команд генерирует событие «Двойной щелчок по координатам (X, Y)» и посылает текущей программе (в данном случае — оболочке Windows, explorer.exe, он же Проводник).
    3. Рабочий стол — это сильно модифицированный ListView из comctl32.dll (если я правильно назвал эту библиотеку). Впрочем, событие «двойной щелчок» обрабатывается самим Проводником, и если какой-то элемент выделен, он говорит: запусти файл, библиотека shell32.dll, функция ShellExecute с глаголом «open».
    4. Библиотека оболочки shell32.dll имеет специальную ветвь кода для запуска ярлыков. Она разбирает файл ярлыка и вызывает более низкоуровневую функцию CreateProcess.
    5. Ядро Windows делает всё, что нужно, чтобы создать процесс, завести под него отдельное «пользовательское» адресное пространство, отдельный стек вызовов, потоки ввода-вывода и т.д. Сам EXE-файл и его библиотеки становятся частью системы подкачки Windows, и если какая-то страничка сегмента кода будет выброшена, она подгружается прямо из EXE/DLL. Разрешает динамические адреса, которые становятся известны только при загрузке программы (т.н. relocations). Процесс загрузки программы — дело сложное, с ним я незнаком.
    6. Считаем, что программа GUI’шная. Тогда при загрузке, как ни странно, ничего внешне не происходит (только трещит винт, подкачивая данные в оперативную память). Сама программа говорит WinAPI: мне нужно создать такое-то окно, с такими-то кнопками в заголовке, с отображением на панели задач.
    7. Система сама посылает окну события: «Я изменяю свой размер», «Я показываюсь», «Я перерисовываюсь». Программа может перехватить эти события и сделать по ним что-то своё. Если у окна есть неклиентская часть (заголовок, рамка), показывает их сама Windows.
    8. За перерисовку клиентской части окна (то есть того, что внутри рамки) отвечает одна из нескольких подсистем Windows. Наиболее распространённая — GDI (интерфейс графических устройств), хотя всё чаще используют библиотеки аппаратного ускорения — DirectX/OpenGL/Vulkan.
    9. Как только сработали события перерисовки — внутренние Windows и пользовательские — мы видим на экране окошко!
    Ответ написан
  • Когда ооп быстрее процедурного?

    @Mercury13
    Программист на «си с крестами» и не только
    ООП рассчитано не на скорость исполнения, а на скорость разработки. Как, впрочем, и многие другие современные технологии разработки. Всё, что ООП делает, можно реализовать и без ООП, и даже эффективнее. Стоит ли — другой вопрос.

    Какую задачу конкретно решает ООП? Обуздать сложность разработки программ, собранных из взаимодействующих компонентов. Вот от этого и пляшем: если программа не модульная (например, какой-нибудь сложный научный расчёт), ООП мало поможет. Также ООП не поможет, если стандартная реализация ООП недостаточно эффективна по процессору или по памяти — например, в мою бытность JavaMe’шником ООП не жаловали, поскольку памяти много ел, типичный мобильник имел от 215 до 800 килобайт доступной памяти. Также плохо будет работать там, где нет взаимодействия (на типичном PHP, который выдал страничку и исчез).

    Что на PHP можно реализовать объектно?
    • Поддержку каких-то протоколов (БД, почта, какая-нибудь внешняя веб-служба наподобие VK API или Mandrill).
    • Что-нибудь из предметной отрасли, что меняет своё состояние — например, генерация картинок, звуков, архивов, PDF…
    • Может, сделаешь какой-нибудь генератор страниц, который сначала собирает каркас страницы, а затем, в зависимости от настроек и целевого устройства, обращивает его HTML-кодом.
    Ответ написан

Лучшие вопросы пользователя

Все вопросы (88)