Задать вопрос
Ответы пользователя по тегу Python
  • Расширенный алгоритм Евклида с усеченными остатками?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Идея этого усечения в том, что если вы ищите gcd(a, b), то можно также искать gcd(a,a-b). Вот эта замена b' = a-b у вас в коде и происходит.

    Вы там поддерживаете инвариант x_i*a+y_i*b = r_i

    Сответсвтенно, вам надо пересчитать x_cur и у_cur вместе с изменением r_cur.

    У вас есть x_prev*a+y_prev*b = r_prev и x_cur*a+y_cur*b = r_cur. Вам надо составить линейную комбинацию r_prev - r_cur. Ну вычтите одно уравнение из другого и все.

    Соответственно вам надо сделать вот это при применении вашего усечения:
    x_cur = x_prev - x_cur
    y_cur = y_prev - y_cur
    Ответ написан
  • Почему в Python последовательность append-ов суммируется в O(n), а не в O(n logn)?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    а общее число перераспределений для n добавлений уменьшается как O(logn). Почему тогда в таком случае для n последовательности append-ов общая сложность равна O(n), а не O(n logn)?


    Потому что эти распределения разного размера. Первое - совсем маленькое. Второе чуть больше и т.д. Чтобы суммарно было O(n Log n), каждое из них должно быть пропорционально n.

    1+4+10+⋯≤O(n)


    Вот это и есть ответ. Первые слагаемые маленькие. Получается геометрическая прогрессия, которая дает линейную сумму от n.
    Ответ написан
    Комментировать
  • Бинарный поиск. Правильно ли работает?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    if i == middle - 1 or i >= 5 and len(list) <= 4:
                return -1


    Вот эта часть вызвает вопросы. Отладочный код остался?

    Проблема в вашем коде, что он виснет, если числа в массиве вообще нет. Условие должно быть не про равенство, а про то, что у вас отрезок пуст (или длины 1) - надо сравнивать first и last.

    Обычно middle не поддерживают между итерациями цикла, а просто считают внутри. Между итерациями переходят только first и last.

    А так, да, бинпоиск - это весьма простой алгоритм.
    Ответ написан
    1 комментарий
  • Доработка алгоритмической задачи JAVA. Требуется помощь >?

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

    Есть более хитрое решение за линию. Вот два самых крайних забора, они могут быть вариантом ответа. В противном случае можно выкинуть из рассмотрения кротчайший из них: если он и есть в максимальном ответе, то можно сдвинуть вторую границу на другой крайний отрезок и ответ не ухудшится.

    Поэтому решение будет из двух указателей - левого и правого. Пока они не сошлись, считайте площадь, сравнивайте ее с текущим ответом, а потом двигайте указатель на меньшее число в сторону второго.
    Ответ написан
    8 комментариев
  • Как проходить список и одновременно удалять элементы, в том числе впереди курсора?

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

    Еще можноиспользовать обычный list, только вы итерируйтесь циклом while и используйте индексы:
    i = 0
    while i < len(arr):
      x = arr[i]
      j = i+1
      while j < len(arr):
        if ShouldDelete(arr[j], arr[i]):
          del a[j]


    Это будет в n раз медленнее, к сожалению. Можно наверно слайсами сделать быстрее:

    arr[i+1:] = y for y in arr[i+1:] if not ShouldDelete(x, arr[i])


    Я не питонист и возможно ошибку допустил. И мне этот код не кажктся очень понятным, но возможно это истиный путь для питона.

    А так, в общем случае, идет двойная итерация с пометками элементов на удаление.

    Какого-то названия этот прием не имеет, ибо это костыль для конкретных реализаций контейнеров.
    Ответ написан
    Комментировать
  • Как найти количество помеченных связных графов?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Формула включения-исключения. Берете все графы, где хотя бы одна вершина соединена со всеми (их n*2^(n-2)*(n-1)), вычитаете все графы, где хотя бы две вершины соеденины со всеми (2 раза, ведь они 2 раза подсчитались), прибавляете графы, где хотя бы 3 вершины соеденины со всеми (3 раза)... И т.д.

    Графов, где хотя бы k вершин имеют степень n-1 - C(n, k)*2^{(n-k-1)(n-k)/2}: тут можно выбрать k вершин и для каждого ребра из оставшихся n-k вершин есть 2 варианта - оно или есть, или нет.

    Это будет за O(n log n) решение, если пердподсчитать все факториалы и обратные к им по модулю в задаче. Ну, или O(n^2), если считать сочетания через треугольник паскаля.

    Ражеванное объяснение:

    Сложно подсчитать количество графов где ровно 1 вершина такая полная. Но легко подсчитать те, где k или более таких. Мы их такие зафиксируем и нарисуем от них все ребра. А все оставшиеся ребра в графе могут быть любыми. Во-первых, можно выбрать эти k вершин - поэтому у нас есть множитель C[n,k]. Оставшиеся, незафиксированные ребра идут между любыми двумя оставшимся n-k вершин. Их (n-k)(n-k-1)/2. И каждое может быть или проведено или нет.

    Поэтому всего таких графов, с не менее k вершин: F(k)=C[n,k]*2^{(n-k)(n-k-1)/2}.

    Теперь, как подсчитать графы ровно с 1 вершиной? Можно взять F(1). Но мы насчитали много лишнего, Графы с 2мя такими вершинами мы в F(1) подсчитали 2 раза. Поэтому вычтем 2F(2). Теперь графы ровно с 3 вершинами мы подсчитали 3 раза в F(1) и 3 раза в каждом F(2). Поэтому пока мы их насчитали 3-2*3 = -3 раза. Поэтому прибавим 3F(3). И далее, получится, что графы ровно с 4-мя вершинами мы подсчитали 4 раза (4-2*6+3*4). И т.д.
    Ответ написан
    6 комментариев
  • Как решить ошибку argument of type ‘float’ is not iterable в Python?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Чтобы проверить, что число a делиться на b, надо проверить, что остаток от деления равен 0: a % b == 0

    У вас же там происходит деление на 4 и 6, которое возвращает дробные числа, они же float.
    Ответ написан
    Комментировать
  • Как вывести минимальный элемент из динамической библиотеки?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    jidomasson, Вот и проблема (код из комментариев к вопросу):

    second_element = ctypes.c_int(A[1])
    begin = ctypes.pointer(second_element)
    
    last_element = ctypes.c_int(A[size - 1])
    end = ctypes.pointer(last_element)


    Тут вы, похоже, созадете новые объекты типа c_int и присваиваете им значения второго и последнего элементов массива. А потом указатели на них передаете в функцию. Функция ожидает указатели на элементы массива, а получает указатели на какие-то 2 никак не связанные между собой переменные. Поэтому она блуждает по левой памяти и просиходит что угодно. Хоть падение, хоть зависание.

    Вам надо брать указатели от A[0] и A[size-1] нарпямую.
    Ответ написан
  • Как показать зависимость скорости от O(nlogn)?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Можно, только надо числа брать побольше. Скажем, 100000 и 1000000. Для полносты картины можно взять несколько точек. Еще возьмите, например, 5000000 и 10000000.

    Но вообще сложность алгоритма обычно доказывают логически. Типа, у вас там n операций с кучей, каждая операция ограничена O(log n) - потому что она проходит по бинарному дереву с менее чем n листьями, а значит, высотой менее log n.
    Ответ написан
  • В чем причина ошибки IndentationError: unexpected unindent?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    IndentationError: unexpected unindent
    означает, что форматирование файла кривое. Скорее всего, табы вместо пробелов или наоборот в 22 строке. При форматировании не то вставили. Выглядеть оно может правильно, но питону важно, чтобы все было идентично.

    В питоне количество пробелов/табов в начале строки управляет вложенностью конструкций.
    Имеет значение не только количество табов/пробелов в начале строки, а их точная последовательность.

    Поэтому рекомендуется во всем файле использоваать или только табы, или только пробелы.
    Ответ написан
    Комментировать
  • Как построить граф по его граням?

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

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

    Ваша попытка использовать обобщенный оптимизатор похоже не работает, потому что у вас функция не дифферинцируема в нулях x из-за abs.
    Ответ написан
    Комментировать
  • Возникает ошибка, но не знаю какая?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Посмотрите на ограничения в задаче. Введите вашей программе максимальный тест: 15 монеток и сумму примерно в 1000000000. Ваша программа попробует съесть дюжину гигабайт памяти и упадет.
    Ответ написан
  • Почему 3 секунд не хватает для выполнения кода?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    У вас решениe за O(n^3), ибо у вас там 2 вложенных цикла до n, а внутри еще и постоянно вызываются min/max, которые проходятся по всему массиву.

    Ограничения же в задаче n<10^5. С такими ограничениями максимум O(n log n) решение уложится в 3 секунды.

    Подумайте, как его можно изменить, чтобы работало сильно быстрее? Подсказка: сначала вы берете 1 минимальный элемент, потом 2 самых маленьких, потом 3, и т.д. На второй итерации вам уже как бы не надо искать минимум- вы его уже знаете. Вас интересуют только оставшиеся числа. На третьей итерации у вас уже 2 числа раньше найдены. Надо как-то переиспользовать предыдущие вычисления.

    Что можно сделать с входным массивом, чтобы можно было получать несколько самых маленьких элементов быстро? Помните, что вам надо уложиться в O(n log n).
    Ответ написан
    Комментировать
  • Как сделать, что бы скрипт искал только фиксированное количество слагаемых?

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

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

    Более хитрые и быстрые варианты: динамическое программирование типа задачи о рюкзаке, где вы считаете количество способов набрать такую-то сумму стольки-то слагаемыми из стольки-то первых чисел. А потом используя это в рекурсивном переборе можно отрубать его тупиковые ветви: если ДП говорит, что там 0 наборов, то можно туда не идти в рекурсии. Или, если вам не сами наборы, а из количество нужно, то даже рекурсивного перебора не надо. Но это работает, только если target не очень большое.

    Второй более быстрый вариант: получить хоть бы и вашим перебором все варианты собрать все суммы среди первых n/2 чисел и отдельно среди оставшихся. Их надо распихать по разным массивам, в зависимости от количества слагаемых. Отсортировать по сумме. Потом перебрать, сколько чисел берем из первой половины, тогда понятно, сколько берем из второй. А потом двумя указателями, идущими навстречу в этих двух упорядоченных массивах можно за один проход найти все способы скомбинировать пару чисел из двух массивов, дающую искомую сумму.
    Ответ написан
  • Удалить из ряда элементы ,как?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Например, вот так:
    def GenerateAll(source, rep):
      for comb in itertools.combinations(range(len(source)), len(source)-len(rep)):
        s = list()
        prev = 0
        for (i, j) in enumerate(comb):
          s.append(source[j]);
        yield "".join(s)


    Обратите внимание, перебираем не сочетания из удаляемых позиций, а из 22 оставляемых (кстати, у вас числа не бьются, 48+22 = 60 != 64). Тут порядок в ответе будет обратный (первая строка будет "xxxxxx...xxxx12..." а не "12..xxx..xx". Если нужен тот же порядок, то будет чуть сложнее:
    def GenerateAll(source, rep):
      for comb in itertools.combinations(range(len(source)), len(rep)):
        s = list()
        prev = 0
        last = 0
        for (i, j) in enumerate(comb):
          while (last < j):
              s.append(source[last]);
              last += 1
          last += 1
        while (last < len(source)):
              s.append(source[last]);
              last += 1
        yield "".join(s)


    Это не самое питонистое решение, возможно в какой-то библиотеке уже есть готовая функция, которая вырезает из строки символы по индексам.
    Ответ написан
    1 комментарий
  • Как убрать time.sleep() или чем его заменить а автотестах?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Все индивидуально. Чего этот sleep в коде ждет?
    Может, тут он ждет отклика от сервера, и там действительно надо 200мс ждать. И просто заменой time sleep на что-то вы ничего не исправите. Или это анимация чего-то на экране, и тут можно в 0 все убирать.

    Но вообще гуглите simulated time python.
    Посмотрите, может simpy вам тут поможет.
    Ответ написан
    1 комментарий
  • Логика игры "Пятнашки" на Python?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Надо, чтобы "четность" перестановки совпадала с четностью финального поля (1).
    Занумеруйте все 16 позиций слева направо сверху вниз.
    чтобы подсчитать четность, рассматривайте каждую пару заполненных позиций (15\*14/2=105 пар) - если числа идут не в том порядке (большее число на позиции с меньшим номером) - то прибавьте 1 к ответу. В конце возьмите ответ по модулю 2. Это и будет четность перестановки.

    Чтобы получить поле, которое можно собрать, сгенерируйте любую перестановку (случайно перемешайте 15 чисел), а потом посчитайте ee четность. Если четность плохая, то поменйте местами любые 2 соседних элемента (выберите случайно, или меняйте первые 2 всегда - на вероятности всех возможных полей это не влияет).

    Edit: Но вы это почти все итак знатете, ибо функция is_solvable в вашем коде как раз инверсии уже считает.
    Значит, Но вы знаете, что плохое поле от хорошего отличается лишь четностью, значит, если поле плохое - меняйте местами 2 соседних по порядку элемента. Например верхний левый со вторым в верхней строке.
    Ответ написан
    Комментировать
  • Как правильно реализовать алгоритм Дейкстры в Python с применением ООП?

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

    Я бы действительно не вводил сущность ребро. И просто в вершинах хранил список соседних вершин (оно еще называется список смежности). Так экономнее, быстрее и проще.

    В вашем подходе, чтобы получить соседнюю вершину надо взять ребро и посмотреть, какая их двух вершин не та изначальная. Или можно хранить только ориентированные ребра и все неориентированные придется раздваивать.
    Ответ написан
    Комментировать
  • Почему мой код считается медленным?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Ваш алгоритм работает за O(n^2). Вы для каждого числа в массиве считатете, сколько раз оно туда входит проходя по массиву через nums.count(i). Оптимальное же решение работает O(n). Надо в хеш-таблице подсчитать, сколько раз каждое число встречается, потом через алгоритм QuickSelect выбрать k-ый c конца элемент.

    Ну, или можно за O(n log n) отсортировать массив и потом за один проход подсчитать сколько раз каждое число встречается. Дальше можно второй раз отсортировать по количеству вхождений и выдать k-ый элемент. Это решение тоже пройдет.
    Ответ написан