Ответы пользователя по тегу Алгоритмы
  • Где научиться алгоритмам?

    Astrohas
    @Astrohas
    Python/Django Developer
    Кормен . Алгоритмы вводный курс (ну или Т. Кормен - Алгоритмы. Построение и анализ)
    Дасгупта С., Пападимитриу Х., Вазирани У. - Алгоритмы - 2014 хорош в паре с курсом лекций от Lektorium.
    Ответ написан
    Комментировать
  • Какой алгоритм эффективнее ищет минимум?

    Astrohas
    @Astrohas
    Python/Django Developer
    первый O(N)
    второй N*log(n) * C
    для поиска одного минимума хорош первый
    а для множественного поиска хорош второй в паре с банальным бинарным поиском
    Ответ написан
    Комментировать
  • Как найти наибольшую поседовательность за O(n)?

    Astrohas
    @Astrohas
    Python/Django Developer
    https://www.youtube.com/watch?v=t2DpD9GnhfU гуровиц объясняет более внятно.
    Просто берете стандартный алгоритм, при n-ом итеме проверяете его разницу в значениях и если разница равно 1 то только тогда увеличиваете счетчик.
    Ответ написан
    2 комментария
  • Есть ли книга алгоритмы в примерах и задачах?

    Astrohas
    @Astrohas
    Python/Django Developer
    поищите видеoкурсы на intuit.ru
    Ответ написан
    Комментировать
  • Как найти сумму чисел массива, которых равна определенному числу?

    Astrohas
    @Astrohas
    Python/Django Developer
    Тут товарищ рекурсия нужна
    CIRCLES = [
        [7, 2, 3, 5, 16, 50, 25, 40],
        [2, 5, 10, 30, 25, 3, 10, 25],
        [25, 10, 2, 10, 5, 2, 10, 5],
        [7, 2, 3, 20, 3, 7, 2, 5],
        [2, 20, 1, 7, 25, 1, 25],
        [3]
    ]
    condidats = [0,0,0,0,0,0]
          
    R  = [];
    function get_sum(s, ind){
        if (ind >= CIRCLES.length) {
            if (s == 136) {
               alert(condidats)
             }
         }
        else {
          for (let i in CIRCLES[ind] ){
          	item =  CIRCLES[ind][i];
            condidats[ind] = item;
            get_sum(s+item, ind+1);
          }
        }
    }
    
    get_sum(0, 0)


    думаю псевдокод понятен
    упд: исправил
    вот и js говнокод
    https://jsfiddle.net/m1nsra5d/4/
    Ответ написан
    2 комментария
  • Как сделать обход в глубину на основе файловой системы?

    Astrohas
    @Astrohas
    Python/Django Developer
    Лучше всего использовать что-то типа os.walk
    А для того чтобы получить словарь можно использовать следующее:
    import os
    from functools import reduce
    
    def get_struct(rootdir):
    
        dir = {}
        rootdir = rootdir.rstrip(os.sep)
        start = rootdir.rfind(os.sep) + 1
        for path, dirs, files in os.walk(rootdir):
            folders = path[start:].split(os.sep)
            subdir = dict.fromkeys(files)
            parent = reduce(dict.get, folders[:-1], dir)
            parent[folders[-1]] = subdir
        return dir

    вывод:
    >>>pprint.pprint(get_struct("/home/hasan/Загрузки"), indent=4)
    {   'Загрузки': {   '.directory': None,
                        'CS15Setup.exe': None,
                        'CrossOver 16.2.5': {   'Crack': {   'winewrapper.exe.so': None},
                                                'CrossOver 16.2.5.md5': None,
                                                'crossover-16.2.5-1.rpm': None,
                                                'crossover_16.2.5-1.deb': None,
                                                'install-crossover-16.2.5.bin': None},
                        'Effective_Python_proglib.pdf.crdownload': None,
                        'Grokaem_algoritmy_Illyustrirovannoe_posobie_dlya_pr.rar': None,
                        'Hodyachij.zamok.2004.DUAL.BDRip.XviD.AC3.-HQCLUB.avi': None,
                        'IDM-6.28.17': {   'IDM-6.28.17.exe': None,
                                           'Тихая установка.cmd': None},
                        'IDM-6.28.17.zip': None,
                        'IMG_20171002_102640.jpg': None,
                        'IMG_20171002_102653.jpg': None,
                        'IMG_20171006_213030.jpg': None,
                        'IMG_20171009_185922.jpg': None,
                        'IMG_20171009_185934.jpg': None,
                        'IMG_20171009_205812.jpg': None,
                        'IMG_20171009_210242.jpg': None,
                        'IMG_20171009_210311.jpg': None,
                        'IMG_20171009_210355.jpg': None,
                        'Postroenie_sistem_mashinnogo_obuchenia_na_yazyke_Python.zip': None,
                        'SIMS3_Repack.iso': None,
                        'TORRENT': {},
                        '[rutor.is]Hodyachij.zamok.2004.DUAL.BDRip.XviD.AC3.-HQCLU.torrent': None,
                        '[rutor.is]SIMS3_Repack.torrent': None,
                        '[rutor.is]Teoriya.Bolshogo.Vzriva.(5.sezon.01-24.serii.iz.torrent': None,
                        '[rutor.is]The Big Bang Theory.s05.torrent': None,
                        '[rutor.is]Zakljate._Nashi_dni_The_Crucifixion_2017_WEB-DL.torrent': None,
                        'payeer_mastercard_ru.pdf': None,
                        'risovach.ru.jpg': None,
                        'selecttv_latest_07_09_2017.apk': None,
                        'st_7972_1b.jpg': None,
                        'thenightmarebeforechristmas19933d720pblurayx264ytsag-english-110597': {   'The Nightmare Before Christmas en.srt': None},
                        'thenightmarebeforechristmas19933d720pblurayx264ytsag-english-110597.zip': None,
                        'Не подтвержден 741176.crdownload': None,
                        'Силен Д., Мейсман А. - Основы Data Science и Big Data. Python и наука о данных - 2017.PDF': None}}
    Ответ написан
  • Литература для изучения "Алгоритмов и структуры даных"?

    Astrohas
    @Astrohas
    Python/Django Developer
    Кормен алгоритмы вводный курс
    Дасгупта, Пападимитрий - Алгоритмы
    Ответ написан
    Комментировать
  • Где можно сделать красивые блок-схемы алгоритма?

    Astrohas
    @Astrohas
    Python/Django Developer
    Google Drive + Draw.io
    Ответ написан
    Комментировать
  • Хорошие сборники задач по теории алгоритмов?

    Astrohas
    @Astrohas
    Python/Django Developer
    Дасгупта Пападимитриу Вазирини - Алгоритмы
    Кормен, Лайзерсон, Штайн - Алгоритмы построение и анализ

    Скиена Стивенс - Алгоритмы. Руководство по разработке
    Порублев и Ставровский - Алгоритмы и программы. Решение олимпиадных задач
    Меньшиков - Олимпиадные задачи по программированию
    И еще ACMP.Ru, topcoder и codeforces
    Знания вы можете также черпать из википедии, e-maxx.ru , algolist.manual.ru и курсам от Интуит (хоть и там школьники, но вещи довольно таки не школьные), а также лекции Куликова из CSC или Лекториума.
    Upd: Кстати забыл сказать что курс Куликова идет по книге Дасгупты, так что желательно одновременно начать чтение этой книги и просмотра этого курса
    Ответ написан
    5 комментариев
  • Как вычислить пересекаются ли много многоугольников?

    Astrohas
    @Astrohas
    Python/Django Developer
    Если в вкратце - то вам нужно хранить в какой то структуре все отрезки (стороны) каждого многоугольника в виде пар (x1, y1 , x2, y2), а также координаты краев. Затем При добавлении вам нужно сравнивать многоугольник которого хотите добавить со всеми многоугольниками. Суть сравнения в проверки пересечения отрезков. Т.Е. сравниваем отрезки друг с другом. Общее время для сравнение двух многоугольников N^M, где N и M - количество отрезков многоугольников. Для того чтобы не тратить ресурсов для сравнения многоугольников которые не могут быть пересекать друг друга, сначала сравнивайте координаты краев.
    UPD:
    Как отметил Сергей Соколов нужно проверят возможность вхождения одной фигуры в другую. Для этого вдобавок нужно например проверять вхождение точки одного многоугольника в другую. Тоже NM операций.
    Ответ написан
    5 комментариев
  • Как осуществить анализ схожести строк и проверить на плагиат?

    Astrohas
    @Astrohas Автор вопроса
    Python/Django Developer
    Решение следующее.
    В подачу для начало даются тексты. Тексты канонизируются, разделяются на шинглы. Затем в таблицу базы данных (например Shingles) добавляются их контрольные суммы . Кроме этого добавляются форигном айди для текста, и позиция шингла. Когда нужно сравнить какойто текст на плагиат из базы, сравниваются контрольные суммы хешов. Сравнение текста на 20 000слов занимает около .5 секунды. Конечно же контрольные суммы и шинглы нового текста затем добавляются в базу.
    Ответ написан
    Комментировать