• Как найти рекурсивным способом эйлеров путь в графе, из какой вершины начинать?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Эйлеров цикл существует в графе, только если входная степень каждой вершины равна ее выходной степени.

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

    Это элементарно доказать - путь в каждую вершину входит сколько-то раз и столько же раз выходит. Исключение - только начальная и конечная вершина, если они не совпадают.

    Соответственно, вам надо подсчитать степени всех вершин, проверить что все хорошо (максимум одна с in==out+1 и одна с in==out-1) и запустить или от любой или от той, у которой исходящих ребер больше.
    Ответ написан
    Комментировать
  • Какую структуру данных выбрать для подсчета элементов?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Вам нужен std::map или std::unordered_map. Самому писать структуру данных не надо.

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

    В качестве ключа используйте пару {Тип транспорта, номер маршрута}. В качестве значения - счетчик остановок.

    Еще вам нужен еще один map из тип транспорта-> std::set или std::unordered_set номеров маршрутов.

    Для построения структур один раз приходитесь по всем остановкам и увеличивайте счетчик в первой структуре. Добавляйте маршрут к транспорту во второй структуре.

    Для поиска ответа пройдитесь циклом по всем элементам set из второго map - это все маршруты. Смотрите в первом map'е сколько остановок у этого маршрута и выбирайте максимум.
    Ответ написан
    2 комментария
  • Не порекомендуете учебник по математическому моделированию?

    gbg
    @gbg
    Любые ответы на любые вопросы
    Самарский с Михайловым

    7q7yzgwbxdxjep5jhgnuqltodou.png
    По численным методам - Патанкар
    ylugpt4bg0tbigg9si6nu1nqsza.png
    Ответ написан
    Комментировать
  • Когда использовать ООП?

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

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


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

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Если это задача такая, то я предполагаю, что там надо удалить минимальное количество скобок, чтобы последовательность стала правильной. Можно только удалять скобки, потому что вместо любого добавления скобки, можно просто вторую пару удалять. Количество действий не изменится. Правда, в ваших примерах оно удалит все скобки.

    Тут можно решать динамическим программированием. Пусть F(l,r) - минимальное количество операций удаления, чтобы сделать из строки с l по r правильную скобочную последовательность.

    База - если l..r - пустая строка - ответ 0.
    Иначе надо рассматривать варианты, что будет с последним символом. Если в конце стоит открывающая скобка, то ее надо удалить - других вариантов нет: F(l,r) = 1+F(l,r-1).

    Если же там закрывающая скобка, то есть 2 варинта: или этот символ удаляем, или берем в ответ. В первом варианте ответ такой-же, как выше. Во втором - надо перебрать, а какой же символ в строке будет открывающей скобкой для данной. Пусть это символ i (там должна стоять открывающая скобка того же типа). Тогда ответ F(l,i-1)+F(i+1,r-1) - ведь части перед парой скобок и внутри их должны тоже быть правильными последовательностями.
    Из всех вариантов надо выбрать минимальный - это и будет ответ для текущего состояния.

    Если хотите восстанвливать саму последовательность, то надо при сохранении минимума еще и сохранять в отдельном двумерном массиве - какой именно из вариантов был выбран (дропнуть последний символ, или какой символ взять ему в пару).

    Ответ к задаче - F(1,n) - для всей строки.

    Это решение потребляет O(n^2) памяти и занимает O(n^3) времени.
    Ответ написан
    2 комментария
  • Как исправить скобочную последовательность?

    dollar
    @dollar
    Делай добро и бросай его в воду.
    Определить такую последовательность можно с помощью стека - это структура в памяти (обычный массив), куда вы должны будете складывать скобки по мере прохождения по текстовой строке со скобками. Если скобка открывающая, то скалываете её в стек. Если закрывающая, то вынимаете соответствующую открывающую скобку из стека. И если скобка не та (тип не совпал), или необходимо взять скобку из пустого стека, или в конце строки стек не опустел, то значит в строке присутствует ошибка.

    А вот автоматически исправлять ошибку - дело неблагодарное. Потому что текстовая строка с дефектом не содержит информации о том, какой она должна быть. Например, если ошибка в том, что скобка пропущена, то как узнать, в какое место нужно вставить недостающую скобку? Никак! Разве что ваша строка имеет определённый формат и всякие намёки на то, где это скобка может быть. Но даже в этом случае, скорее всего, будет неоднозначность.

    Например, строка из текста программы: x = 2 * 2 + 2);
    С помощью алгоритма выше вы можете узнать, что в скобочной последовательности допущена ошибка. Но есть целых три места, куда можно вставить открывающую скобку, чтобы строка стала валидной синтаксически. Если это Си-подобный язык, то четыре. Но даже если рассматривать более или менее разумные места для вставки, то их два, и всё равно не понятно, что именно будет исправлением ошибки.

    P.S. Дарю вам бонусный пример строки для медитации:
    /* [(]) */ y = (a[i] + 7); // }])
    Ответ написан
    2 комментария
  • Почему площадь криволинейной трапеции это разность первообразных?

    @LeoMay
    Студент
    Что такое интеграл? Если вспоминать еще школьное объяснение, то это "тупо" сумма всех прямоугольников, которые помещают внутрь площади, которые рисуют в каждом учебнике. Форма записи говорит "сумма каждого значения функции в каждой точке при бесконечно малом приращении", тобишь этот dx буквально значит бесконечно малый икс. Это, своего рода математически говорит "сдвигаем следующее значение, которое найдём, на чуть чуть". По сути, мы находим сумму всех высот линий, которые можно впихнуть под функцию.

    Почему именно работает формула Ньютона Лейбинца, советую посмотреть доказательство, разобрать по пальцам. Понять, что значит предел суммы.
    Попытался пояснить на пальцах, математически объяснение может быть некорректным, так что обязательно ищи доказательства всех формул, очень помогает
    Ответ написан
    2 комментария
  • Как посчитать позицию вектора?

    ProgrammerForever
    @ProgrammerForever
    Учитель, автоэлектрик, программист, музыкант
    Вам нужны полярные координаты

    Формулы для перевода:
    x = x0 + R*cos(phi)
    y = y0 + R*cos(pi/2 - phi) = y0 + R*sin(phi)

    Основаны на том, что проекция вектора на ось(или в общем случае - направление) - это длина вектора умноженная на угол между осью(или направлением) и вектором. Угол считается от направления до вектора против часовой. Если угол "неудобный" (больше 180 градусов, например) - то его всё равно нужно брать. Ну или брать меньший "удобный" угол и учитывать в формуле направление проекции - если направление проекции совпадает с положительным направлением оси - то ставим "+", если в противоположную сторону - то "-".
    Ответ написан
    Комментировать
  • Как возвести decimal в степень с плавающей точкой?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Вы что-то напутали.
    1.000001**2**19 тоже возвращает 1.689255227180379. Только что в консоли проверил.

    > costumePow(1.000001, 19)
    1.689255227180379
    > 1.000001**2**19
    1.689255227180379
    Ответ написан
    6 комментариев
  • Плох ли Angular DI?

    Xuxicheta
    @Xuxicheta Куратор тега Angular
    инженер
    Так он через токены и работает.
    Через класс это типа шорткат, когда объект функции-конструктора используется как объект токена, чтобы меньше кода писать. Это же js, тут классов то нет, они все first-class entity
    Ответ написан
    1 комментарий
  • Как работает сборщик мусор с колбеками Promise?

    bingo347
    @bingo347 Куратор тега JavaScript
    Crazy on performance...
    Сборщики мусора (далее GC) бывают разные, в том же v8 используется сразу 3 типа GC в зависимости от поколения объектов (упрощенно молодое, старое и сложные случаи), но в большинстве своем принцип работы сводится к просчету достижимости из некоторого корня в дереве объектов (например глобального объекта, но не только его). v8 не является исключением, и его GC содержит C++ api для создания таких корней. Из JS мы данным api можем воспользоваться лишь косвенно, через сущности языка предоставляемые либо самим v8 либо платформой (браузером, node.js, deno и т.д.)
    Чтоб было понятно давайте рассмотрим простой пример:
    const h = 'Hello world!';
    const n = 'nothing';
    setTimeout(() => {
      console.log(h);
    }, 1000);
    У нас есть строковые переменные h и n. Переменная n нигде больше не используется и ее память очистится при ближайшей работе GC. А вот переменная h оказалась в замыкании созданном стрелочной функцией. И хотя в JS мы не можем достучаться до h имея ссылку на эту функцию, сама функция все таки имеет ссылку на h, а значит h не может быть уничтожена пока не будет уничтожена сама функция. В терминах GC ссылка на h будет серой, то есть сама ссылка на h недоступна из корня напрямую, но сейчас мы проверяем объекты, которые на нее ссылаются и истина будет зависеть от них (подробнее можете погуглить "mark black white and gray memory in gc").
    Давайте посмотрим на саму стрелочную функцию, которая держит h в замыкании. Из кода видно, что мы ее передаем в функцию setTimeout, о которой известно, что это api предоставленное платформой (а значит вероятно какая-то часть написана на C++), а так же, что она асинхронная. Платформе реализующей setTimeout наша функция понадобится после асинхронного ожидания и никто платформе не сможет гарантировать, что во время этого ожидания не будет работы GC, поэтому ей ничего не остается, кроме как запросить у v8 создание нового корневого дерева объектов, в которое и будет положена ссылка на данную функцию.
    После же выполнения таймаута платформе больше не нужна наша функция, поэтому ссылка на нее будет удалена из дерева объектов. А так как других ссылок на функцию нет, и она больше не доступна ни из одного корня - GC удалит из памяти и функцию и строку связанную h, которая так же стала недоступна из корня.

    Посмотрим на пример из вопроса. У нас есть стрелочная функция, которая удерживает на себе инстанс компонента через this ссылку (так как стрелочные функции замыкают this). Саму функцию в памяти удерживает промис порожденный вызовом loader('url'), так как мы отдали её в метод then. Других ссылок на данную функцию нет, а значит и сама функция и ее замыкание (инстанс компонента) будут "жить" не менее "жизни" промиса.
    Скажем был отправлен запрос на сервер, но потом компонент в котором был объявлен промис и колбек был удален.
    И после удаления приходит ответ от сервера, и он выполнит колбек. Это значит что колбек остался в памяти со всеми переменными контекста
    Если других ссылок не осталось, то инстанс компонента будет удерживаться от очистки через промис.

    Теперь стоит разобраться с самим промисом. У него может быть 3 состояния - pending, resolved или rejected. После перехода в состояния resolved или rejected промис может выполнить сохраненные колбэки в ближайшем микротаске, а после он удалит на них ссылки из себя, в следствии чего, память удерживаемая замыканием колбэка может быть очищена (при отсутствии на нее других ссылок, достижимых из какого-либо корня).
    В состоянии pending промис может потенциально находится бесконечно долго, при этом ссылаясь на все колбэки переданные ему в методы then, catch или finally, а значит так же косвенно ссылаясь на их замыкания. И тут все зависит от того, кто ссылается на данный промис, и достижим ли он из корня. И да, промис вполне может быть удален из памяти так и не дождавшись своего завершения.
    интересное умозаключение
    Если Promise - это обещание, то в данном случае оно будет нарушено?


    В комментах к вопросу есть еще один интересный пример:
    function getSomething(){
      return new Promise((resolve, reject)=>{
        if(sys_condition){
           resolve();
        } 
      })
    }
    
    function testPromise(){
      let config = {....}
      getSomething().then(()=>{
         #use config
         goOn(...config)
      })
    }
    
    testPromise();
    У нас есть вызванная 1 раз функция testPromise, которая получает из функции getSomething промис, в который с помощью метода then сохраняет колбэк, удерживающий в замыкании переменную config. Сам промис она нигде не сохраняет, что здесь очень важно.
    В функции getSomething мы просто возвращаем промис созданный через его конструктор, который как мы уже знаем нигде больше не сохраняется. И на этом могло бы все и закончится, без вызова колбэка независимо ни от чего. Но конструктор промиса выполняет свой колбэк синхронно, а кроме того он передает в него 2 функции - resolve и reject, которые в своем замыкании ссылаются на только что созданный промис (а это уже 2 ссылки на него, хотя мы то его никуда не сохраняли). Переменная reject никак не используется, а значит спокойно может быть удалена после завершения колбэка. Переменная resolve просто вызывается как функция внутри условия, но более тоже никак не используется и никуда не сохраняется, а значит так же может быть удалена.
    В этом примере. если sys_condition = false и resolve не вызовется, это значит что создается утечка памяти
    Нет, утечки памяти не будет. Колбэк созданный в testPromise будет удален вместе с замыканием, так и не вызвавшись ни разу.
    Ответ написан
    3 комментария
  • Какие задачи решают на Rust, а какие на Golang?

    bingo347
    @bingo347
    Crazy on performance...
    Какие задачи решают на Rust
    любые. Rust - язык общего назначения, применимый к большинству возможных задач. Rust достаточно высокоуровневый для написания на нем прикладного ПО и компилируется в достаточно эффективный машинный код, для применения в ядрах ОС, драйверах или embedded разработке. Так же Rust на сегодня имеет самый маленький размер при компиляции в wasm, что критично для использования в web. Я честно не знаю такой сферы, к которой бы не подошел Rust.
    Единственной проблемой в применимости Rust я вижу недостаточную его распиаренность в РФ, что часто бывает самым важным критерием для "манагеров" и прочих людей принимающих решения о используемом стеке.
    а какие на Golang
    Golang тоже язык общего назначения, но имеющий ряд ограничений:
    - Крайне тяжелый рантайм не дает возможность использовать его в wasm, embedded или компонентах ядра.
    - Необходимость в сборке мусора опять таки ограничивает разработку для embedded или компонентов ядра.
    - Отказ от llvm в качестве бэкенда компилятора ограничивает число целевых платформ.
    Можно один заменить другим?
    Rust спокойно заменяет Golang в любой возможной на последнем задаче, наоборот же иногда имеем ряд ограничений.

    Вместо P.S.:
    Golang скорее всего окажется более быстрым для прототипирования и быстрого старта. Однако отсутствие полиморфизма в любом виде (утиная типизация не в счет) и ограниченность одной парадигмой структурного программирования делает этот язык крайне дорогим в поддержке. Так же этому (и быстрому прототипированию и дорогой поддержке кода) способствует лютая ненависть создателей языка к принципу DRY.
    Rust имеет такую редкую сегодня строгую типизацию, одним из нюансов которой являются концепции владения и заимствования (которые позволяют делать автоматическое управление памятью в compile time), что порождает с одной стороны высокий порог входа в технологию (что сглаживается человекопонятным выводом компилятора, если входящие умеют читать, что еще более редко встречается сегодня, чем строгая типизация), но так же удешевляет поддержку продукта длительное время. Так же надо понимать, что Rust не спасет от кривых рученок быдлокодеров (разве что они не смогут его освоить), так как при большом желании можно сделать и утечки памяти и дедлоки и гонки данных (хотя в Golang это все сделать на порядок проще).
    Ну и надо не забывать, что много где присутствует hype-driven-development и Golang распиарен, а Rust нет.
    Ответ написан
    3 комментария
  • Почему разрешается добавить значение в кортеж?

    bingo347
    @bingo347 Куратор тега TypeScript
    Crazy on performance...
    Потому что кортеж в ts это подтип массива, а система типов ts настолько убога, что через нее нельзя выразить, что у подтипа недоступны какие-то методы основного типа.
    qwe[2] = 77
    Тут просто сразу 2 ошибки типов:
    во-первых 77 нельзя присвоить типу undefined - так как [string, number] - это вполне себе сахар над типом
    {readonly length: 2; 0: string; 1: number} & Readonly<typeof Array.prototype>

    во-вторых 2 в индексе опять таки нельзя воткнуть в тип 'length' | 0 | 1 | keyof typeof Array.prototype
    Ответ написан
    Комментировать
  • Как получить набор точек на координатной плоскости?

    Xuxicheta
    @Xuxicheta
    инженер
    Однако ты своим вопросом заставил поломать голову
    Конечно, сам способ так считать координаты это полный изврат, однако такое поведение combineLatest на какое-то время сильно меня озадачило :)

    Но все оказалось довольно просто https://stackblitz.com/edit/tanks-field-without-gl...
    Найди отличие.
    Ответ написан
    5 комментариев
  • Стоит ли начинать заниматься программированием в 30+ если до этого не программировал?

    opium
    @opium
    Просто люблю качественно работать
    Вы так говорите как будто в 30 лет у вас нет рук и ног и вывалился глаз.
    Берите и делайте и меньше задавайте глупых вопросов на тостере.
    Ответ написан
    5 комментариев
  • Стоит ли начинать заниматься программированием в 30+ если до этого не программировал?

    @sprour
    Однозначно стоит. Это как конструктор собирать. начните с малого javabegin.ru
    Ответ написан
    Комментировать
  • Стоит ли начинать заниматься программированием в 30+ если до этого не программировал?

    Symphony
    @Symphony
    Как сказали выше, если ради материальной выгоды или статуса, то даже не начинайте, есть куча других профессий, где низкий порог вхождения и большой доход.
    Если приняли решение изучать, начните с Питона или Джавы, но только не с Пхп!
    Ответ написан
    8 комментариев
  • Стоит ли начинать заниматься программированием в 30+ если до этого не программировал?

    @vilgeforce
    Раздолбай и программист
    Если вы собираетесь заниматься программированием (вышиванием/выгулом собак/плеванием в потолок) только ради денег - не стоит. Тратить свое время и силы на то, что неинтересно (иначе как в связи с баблом) - плохая идея.
    Ответ написан
    3 комментария
  • Как запретить доступ к переменным js из консоли?

    Taraflex
    @Taraflex
    Ищу работу. Контакты в профиле.
    (function(){
    "use strict";
    
    //приватная переменная
    var a = 100500;
    
    })()
    Ответ написан
    Комментировать
  • Как запретить доступ к переменным js из консоли?

    DevMan
    @DevMan
    Не занимайтесь ерундой: консоль - не единственный способ увидеть ваш json.
    Ответ написан
    Комментировать