Работаю в Google, пишу на C++. Занимался олимпиадным программированием.

Достижения

Все достижения (12)

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

Все теги (111)

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

Все ответы (527)
  • Когда использовать ООП?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    ООП - это не только, когда вы берете какие-то сущности из предметной области и оборачиваете каждую в объект, который что-то умеет делать. Это больше подход к организации кода. Вы делите задачу на подзадачи, а данные на обособленные части, абстрагируете детали внутри объектов. Это позволяет снижать сложность архитектуры. Теоретически любую программу можно написать внутри одной огромной функции с кучей goto. Но так никто не делает, потому что это невозможно поддерживать и невероятно сложно написать. ООП - это логическое продолжение процедур. Теперь вы не только какие-то части программы абстрагируете в одном месте, но теперь еще и данные вмести с ними.

    Мне нужен объект, который будет хранить состояние/данные, и есть общие операции над этим состоянием?


    Вопрос: что значит нужен? Всегда можно взять глобальную переменную, написать функции, которые это состояние принимают и что-то с ним делают. Но довольно часто организация в виде объекта просто удобнее.
    Ответ написан
  • Как решить задачу на сложность алгоритмов ниже?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    г) не правильно подсчитано.

    Составьте уравнение. Вот есть у вас функция времени для n входных данных f(n) на компе B. На компе A время выполнения будет - f(n)/100, ведь он в 100 раз быстрее.

    Теперь обозначьте за x объем данных на компе A, который надо найти. Тогда у вас f(x)/100 = f(n). Подставьте нужную функцию вместо f() и найдите x. Спойлер, будет похоже, но не то, что у вас в вопросе указано.
    Ответ написан
  • Как получить всевозможные комбинации массива PHP?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Подсчитайте руками, сколько комбинаций для массива из 1,2,3,4 элементов? ответ будет 1,3,7,15 - степени двойки минус один. Подумайте, откуда это берется? Каждый элемент может или быть в ответе, или нет. 2 варианта. Премножаем все, получаем степень двойки. Но это учитывает варинат пустого ответа, поэтому один надо вычесть.

    Тут есть 2 подхода - рекурсивная функция перебора, которая или берет или пропускает текущий элемент. В конце, если хоть один элемент был взят - выводит текущий массив.

    Второй подход - перебирать битовую маску. Каждое число от 1 до 2^n будет в двоичной системе числения представлять какой-то вариант выбора разрядов. Поэтому можно прогнать цикл от 1 до 2^n, потом посмотреть на биты этого числа и брать соотвествтующие числа из массива.
    Ответ написан
  • Как быстро проверить, является ли некоторое огромное число (от 100 знаков) квадратом целого числа?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Можно попробовать вычислить корень быстрым алгоритмом. Но там сложно. Гуглите Karatsuba square root. Есть открытые реализации. Есть еще какой-то адский метод через быстрое преобразование Фурье, попробуйте погуглить и его.

    Более простой в реализации, но менее быстрый метод вычисления корня - бинарный поиск. Храните l, r, l^2, r^2 и lr. По этим числам можно вычислить m=(l+r)/2, m^2, m*l, m*r без длинных умножений, а только складывая длинные числа и деля на 2. Вам надо поддерживать, чтобы l^2 <= n <= r^2. Изначально можно сделать l=1, r=10^51 (или больше - половина длины входного числа + немного, чтобы точно квадрат был больше n), потом делить отрезок пополам и отбрасывать ненужную половину.

    Еще есть вероятностный метод через символ Лежандра/Якоби. Это будет самым быстрым методом.

    Это как смотреть на последнюю цифру. Квадраты могут давать там 0, 1, 4, 9, 6, 5. Но нет ни одного квадрата, который оканчивался бы на 2. Т.е. если число заканчивается на 2, то можно сразу говорить, что это не квадрат. Это мы взяли остаток от деления на 10 (последняя цифра) и посмотрели, какие из них хорошие. Вот символ Лежандра - это такая проверка для модуля по любому простому числу (а не 10).

    Если брать некоторое простое число p, то n может быть квадратом, только если символ Лежандра (n/p) - равен 1 или 0 (По научному: n - должно быть квадратичным вычетом).

    Если брать небольшие (<64-битные) простые числа, то можно за линию считать n%p и потом вычислять символ Лежандра (n%p/p) по алгоритму через символ Якоби за O(log(p)^2). Когда подсчитали символ Лежандра и если он -1, то n - точно не корень.

    Тут проблема в том, что это необходимый, но недостаточный критерий - если для какого-то p вы получили -1 - то это точно не квадрат. Но возможно можно подобрать такое число, что все ваши тесты дадут 1, а оно не квадрат. Поэтому надо брать много простых чисел. Скажем, 20. Желательно еще числа брать достаточно большими. Но их не надо искать каждый раз, можно захардкодить. Грубая прикидка говорит, что вероятность ошибки такого алгоритма 2^(-количество простых чисел).

    Т.е. берете много простых чисел. Считаете для каждого n%p выполняя деление большого числа на короткое (один проход по массиву цифр). Потом считаете символ Лежандра. Если получили где-то -1 - то точно не квадрат. Иначе - скорее всего квадрат.

    Можно совместить вероятностный тест и вычисление корня. Сначала проверьте парочку простых чисел на символ Лежандра для отсечения точно не квадратов. Еще проверку последней цифры можно сделать, это очень дешево. Если не отсеклись, то считайте корень. Так будет всегда работать правильно но будет быстрее работать в некоторых случаях.
    Ответ написан
  • Сколько существует путей и почему?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Количество сочетаний из 125 по 50. Или 125!/50!/75!
    Потому что он обязательно сделает 50 шагов вправо и 75 шагов вверх. В любом порядке. Т.е. всего 125 шагов из которых любые 50 - по горизонтали.
    Ответ написан