Category: Математика

18
Май
2022

Разложения arctan в ряд Тейлoра UNIX C

Разложение функции в ряд тейлера работает не стандартно в диапозонах выше -1 <= and >= 1
В википедии дан ряд тейлера и описание работы в области определения от минус бесконечности до плюс бесконечности, хотя по факту работает как и a…

04
Май
2022

С помощью какого модуля или какой возможности я могу строить графики заданных функций на Декартовой системе координат?

Я хочу построить(нарисовать графически) спираль Фибоначчи и другие функции на Декартовой плоскости.
Как я могу это сделать и как работать с графиками функций в Python?

20
Апр
2022

Method Math max() Сломает мою логику , когда в input первый цифр <0> то не получается больше вводить

Посмотрите в onInput пжл , логика такая что можно вводить максимум 12 цифры, потому что когда type-number то maxLength не работает и пришлось так написать, сейчас проблема в том что когда первый цифр 0 то я больше не могу вводить а если не…

15
Апр
2022

Как решить функцию? С\С++

программу с
использованием оператора цикла for для вычисления и вывода на
экран в точках xi=a+ih, i=0,1,2…,n, h=(b-a)/n промежутка [a,b]
значений функции y=f(x), указанной в варианте задания. Также программа должна определять наибольшее…

09
Апр
2022

Определение тренда графика

Пытался нагуглить, но так и не нашел решения
Я хочу определить, является ли тренд восходящим или нисходящим. Я вызываю апи binance и получаю оттуда 1000 свечей на дневном таймфремей. Каким образом я могу определить, что последние
10 (30, 2…

08
Апр
2022

Огромные числа в огромных степенях

Чтобы быстро возвести в степень, я подумал, что можно просто возвести в степень в программе, но не думал что числа будут настолько огромными.
Чтобы программа не занимала бесконечное количество памяти, я подумал записывать числа так: 1,0Е5 …

05
Апр
2022

PHP подсчитать процент роста цены за 24 часа

Помогите решить задачу. В бд каждый час записываются данные price, datetime.
Нужно подсчитать % роста цены за сутки. Каждый час значение price может подниматься или опускаться. % роста может быть больше 100%. Спасибо

05
Апр
2022

PHP подсчитать процент роста цены за 24 часа

Помогите решить задачу. В бд каждый час записываются данные price, datetime.
Нужно подсчитать % роста цены за сутки. Каждый час значение price может подниматься или опускаться. % роста может быть больше 100%. Спасибо

04
Апр
2022

алгоритм метод деления отрезка пополам

Напишите функцию реализующую алгоритм поиска минимума функции методом деления отрезка пополам. С помощью функции найдите максимальное значение функции f(x) с точностью 10−3.
у меня проблема с функцией V(как ее можно реализовать в этом алго…

23
Мар
2022

Как правильно хранить числа с плавающей точкой в базе данных SQLite3

пишу небольшое скрипт на Python к которому подкручена база данных SQLite3
Я записываю в базу данных числа с плавающей точкой ( или без неё ), чтобы потом вывести сумму этих чисел, но проблема в том что если в базе данных если число с двумя…

15
Мар
2022

Криптоалгоритм без передачи ключа. Как найти вторые ключи α и β?

Есть задача – Пусть абоненты А и В выбрали простое число р=23 и каждый их них независимо от другого выбрал числа a=5 и b=7 соответственно.
Пусть абонент А отправляет сообщение m=17 абоненту В.

Найти вторые ключи α и β.
Вычислить значения …

14
Мар
2022

Как извлечь из списка цифры и мат. оператор и совершить математическое действие?

Я совсем недавно начал изучать Python и столкнулся вот с такой задачей:
дан список из математических операторов и цифр
[‘//’, ‘456732’, ‘432’, ‘*’, ‘6847’, ’13’, ‘+’, ‘2345’, ‘9876’] (ну там дальше много…)
необходимо совершить над ними м…

05
Мар
2022

Метод Хаусхолдера (отражений)

Возникла проблема при решении СЛАУ методом отражений.
По существу весь алгоритм должен приводить систему уравнений Ax = b в эквивалентную ей систему уравнений, такую что в матричной записи эта система имела бы вид Rx = b’, где R – верхнетр…

03
Мар
2022

Математика 5 класса в Python в 10 строк

Есть программа в 10 строк, которая вычисляет все возможные ac в D=b^2-4ac
Вопрос собственно в том, возможно ли сделать, что бы результат выдавался отсортированным по n2 а не по n1?
Если что, хотя очевидно после запуска:

n1 = b^2

n2 = D

01
Мар
2022

🐶🌷 Задача: где фиалки, пес Вениамин?

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

25
Фев
2022

⬆️➡️ Задача о передвижении персонажа игры

Для персонажа в игре предусмотрено два направления движения: вперед и направо. Какую фигуру будет описывать траектория движения героя по заданной команде: правильный треугольник, ломаная линия, правильный шестиугольник или правильный девят…

24
Фев
2022

🧊 Фундаментальные структуры данных: массивы и связанные списки с реализацией на Python

В этой части материала мы рассмотрим массивы и связанные списки, а также теорию, которая стоит за ними и выполним реализацию этих структур на языке Python.

Массивы

Массивы – одна из самых фундаментальных структур данных в информатике. Они встроены во все языки программирования, даже такие низкоуровневые, как C или Assembler. Массивы представляют собой группу элементов одного типа, которые расположены на непрерывном участке памяти компьютера. Например, [5, 8, -1] или ['a', 'b', 'c'].

Поскольку элементы массива стоят рядом друг с другом, мы можем получить доступ к любому их индексу. Например, к первому, третьему или последнему элементу за время O(1).


В таких языках, как C и Java, требуется заранее указывать размер массива и тип данных. Структура списка в Python позволяет обойти эти требования, сохраняя данные в виде указателей на местоположение элементов в памяти, автоматически изменяя размер массива, когда место заканчивается. Элементам памяти не обязательно находиться рядом друг с другом.

Реализация

Основные ограничения, с которыми мы сталкиваемся при создании массивов на языке Python:

  1. После выделения места для массива мы не можем получить больше, не создав новый массив.
  2. Все значения в массиве должны быть одного типа.

Мы можем реализовать в Python очень простой класс Array, который имитирует основную функциональность массивов в языках более низкого уровня.

        from typing import Any

class Array:
    def __init__(self, n: int, dtype: Any):
        self.vals = [None] * n
        self.dtype = dtype

    def get(self, i: int) -> Any:
        """
        Возвращает значение как индекс i
        """
        return self.vals[i]

    def put(self, i: int, val: Any) -> None:
        """
        Обновляем массив как индекс i с val. Val должно быть одного типа с self.dtype
        """
        if not isinstance(val, self.dtype):
            raise ValueError(f"val явл {type(val)}; должно быть {self.dtype}")

        self.vals[i] = val
    

Давайте рассмотрим, какие способы реализации класса Array мы можем использовать. Создадим экземпляр. Подтвердим, что первый индекс пустой. Заполним слот символом char, а затем вернем его. Наши предыдущие действия подтвердили, что массив отвергает non-char (несимвольные) значения. Код не самый лучший, но рабочий:

        arr = Array(10, str)

arr.get(0)       # None
arr.put(0, 'a')  # None
arr.get(0)       # 'a'

arr.put(1, 5)    
# ValueError: val is <class 'int'>; must be <class 'str'>
    

Пример

В процессе работы с массивами вы, скорее всего, захотите использовать встроенный список Python, или массив NumPy, а не созданный нами класс Array. Однако, в целях использования массива, который не меняет размер, необходимо разобраться с Leetcode LC 1089: Duplicate Zeros (Дублирование нулей). Цель данных действий – продублировать все нули в массиве, изменяя его на месте таким образом, чтобы элементы двигались вниз и исчезали, а не увеличивали размер массива или создавали новый.

        def duplicate_zeros(arr: list) -> None:
    """
    Дублируем все нули в массиве, оставляя его первоначальную     длину. Например, [1, 0, 2, 3] -> [1, 0, 0, 2]
    """
    i = 0

    while i < len(arr):
        if arr[i] == 0:
            arr.insert(i, 0)   # Вставляем 0 как индекс i
            arr.pop()          # Убираем последний элемент
            i += 1
        i += 1
    

В итоге мы итеративно перемещаемся по списку, пока не найдем ноль. Затем вставляем еще один ноль и исключаем последний элемент для сохранения размера массива.

Обратите внимание: в данном случае важно использовать цикла while, а не for, так как мы изменяем массив по мере его прохождения. Тщательный контроль над индексом i позволяет нам пропустить вставленный ноль, чтобы избежать двойного счета.

Больше полезных материалов вы найдете на нашем телеграм-канале «Библиотека питониста»

Связанные списки

Связанные списки – еще одна ключевая структура данных в информатике. Как и массивы, связный список – это группа значений. Однако, в отличие от массивов, значения в связанном списке не обязательно должны быть одного типа, и нам не нужно заранее определять размер списка.

Основным элементом связанного списка является узел, который содержит некоторые данные и указатель на любое место в памяти.

Ниже представлен связанный список со значениями [1, 'a', 0.3]. Обратите внимание на различие размеров элементов. Мы видим четыре байта для целых и плавающих чисел, один байт для символов. Каждый узел имеет четырехбайтовый указатель, расстояние между узлами различно, последний из них содержит нулевой указатель, который указывает в пространство.


Отсутствие ограничений на типы данных и длину делает связанные списки привлекательными. Однако эта гибкость создает некоторые проблемы. Программе доступен только верх списка, а это значит, что для поиска любого другого узла нам придется пройти весь список. Другими словами, мы лишаемся O(1) поиска для любого элемента, кроме первого узла. Если вы запрашиваете 100-й элемент, то для его получения потребуется 100 шагов: схема O(n).

Можно сделать связанные списки более универсальными. Для этого необходимо добавить указатели на предыдущие узлы и раскрыть конец списка, или сделать его кольцевым. В целом, выбор связанных списков вместо массивов является платой за удобство.

Реализация

Чтобы создать связанный список в Python, начнем с определения узла. Необходимы только две части: данные, которые хранит узел и указатель на следующий узел в списке. Добавим метод __repr__ для того, чтобы было легче увидеть содержание узла.

        class ListNode:
    def __init__(self, val=None, next=None):
        self.val = val
        self.next = next

    def __repr__(self):
        return f"ListNode со значением {self.val}"
    

Далее попробуем использовать класс ListNode. Важно отметить, что вершина списка – это наша переменная head. Необходимо итеративно добавлять .next для доступа к более глубоким узлам, поскольку мы не можем ввести индекс типа [1] или [2], чтобы добраться до них.

        head = ListNode(5)
head.next = ListNode('abc')
head.next.next = ListNode(4.815162342)

print(head)            # ListNode со значением 5
print(head.next)       # ListNode со значением abc
print(head.next.next)  # ListNode со значением 4.815162342
    

Для того чтобы было легче добавить узел как в конец, так и в начало списка, напишем функции:

        def add_to_end(head: ListNode, val: Any) -> None:
    ptr = head
    while ptr.next:
        ptr = ptr.next
    ptr.next = ListNode(val)

def add_to_front(head: ListNode, val: Any) -> ListNode:
    node = ListNode(val)
    node.next = head
    return node
    

В add_to_end создаем переменную ptr (указатель). Она начинается с head и обходит список, пока не достигнет последнего узла, атрибутом .next которого является нулевой указатель. Далее, устанавливаем значение .next этого узла в новый ListNode. Внутри функции не нужно ничего возвращать, чтобы изменение вступило в силу.

В add_to_front мы создаем новый head, устанавливаем указатель .next в вершину существующего связанного списка. Вручную обновляем head вне данной функции с помощью нового узла. В противном случае, head по-прежнему будет указывать на старый head.

        # Создает и расширяет список
head = ListNode(5)
add_to_end(head, 'abc')
add_to_end(head, 4.815162342)

# Вывод
print(head)            # ListNode со значением 5
print(head.next)       # ListNode со значением abc
print(head.next.next)  # ListNode со значением 4.815162342

# Пытаемся обновить head
add_to_front(head, 0)  
print(head)            # ListNode со значением 5

# Корректное обновление head
head = add_to_front(head, 0)
print(head)            # ListNode со значением 0
    

Пример

Один из частых вопросов, который возникает во время работы со связными списками – возврат среднего узла. Так как обычно существует только начало списка, нет возможности заранее узнать его длину. Исходя из этого, может показаться, что нам придется обойти список дважды: один раз, чтобы узнать его длину, а второй, чтобы пройти половину пути.

Ранее мы использовали указатель, чтобы обойти список по одному узлу за раз, пока не дойдем конца.

На самом деле существует способ найти середину списка за один проход.

Что если у нас будет два указателя? Первый из них будет перемещаться по одному узлу за подход, а второй – по два. В тот момент, когда быстрый указатель достигнет конца списка, наш первоначальный указатель окажется только в середине.

Исходя из написанного выше, мы ответим на LC 876: Середина связанного списка (Middle of the Linked List) следующим образом:

        def find_middle(head: ListNode) -> ListNode:
    """
    Return middle node of linked list. If even number of nodes,
    returns the second middle node.
    """
    # Смотрим на медленную и быструю точки
    slow = head
    fast = head.next

    # Прогоняем список через цикл
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow 

    

В данном случае при работе с Leetcode, мы убеждаемся, что head.next – правильный вариант.

        # Список: A -> B -> C -> D -> E
# Середина: C

# Начало с head: неправильно
# Slow: A -> B -> C -> D  ==> Середина: D
# Fast: A -> C -> E -> null

# Начало с head.next: правильно
# Slow: A -> B -> C       ==> Середина: C
# Fast: B -> D -> null
    

LC 141. Linked List Cycle: Цикл связанного списка – пример использования медленных и быстрых указателей. Наша цель определить, есть ли в списке цикл, который возникает, когда следующий указатель узла показывает на более ранний узел в списке.

Проблема в том, что проход списка через цикл будет бесконечным.

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

Более простой подход заключается в использовании двух указателей.

В данном случае невозможно использование while fast и fast.next, так как эти методы имеют значение False только при достижении конца списка. Вместо этого, подставим slow и fast на первый и второй узлы. Будем перемещать их по списку с разной скоростью, пока они не совпадут. В конце списка вернем False. Если два указателя будут показывать на один и тот же узел, вернем True.

        def has_cycle(head: ListNode) -> bool:
    """
    Определяем где связанный список имеет цикл
    """
    slow = head
    fast = head.next

    while slow != fast:

        # Находим конец списка
        if not (fast or fast.next):
            return False

        slow = slow.next
        fast = fast.next.next

    return True
    
***

Мы узнали, что такое массивы и связанные списки. Это важная составляющая структур данных, которая используется во всех языках программирования.

В следующей части материала приступим к изучению деревьев и графов.

Материалы по теме

22
Фев
2022

🙈🙉🙊 Василий и свежие сплетни: что на самом деле произошло сегодня во дворе?

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

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

Ангелина Ивановна:

– Что произошло сегодня?! Да я своими глазами видела, как окно Виталию разбили! Он так ругался потом… Но вот точно что знаю – не камнем разбили, не камнем!

Мария Павловна:

– Ну что? Окно Виталию разбили камнем, огромным таким. Сама видела, как камень пролетел. Это точно не футбольный мяч был. Вообще, так потом все спокойно было во дворе, ведь Виталий даже не ругался ни на кого.

Жанна Макаровна:

– Какое окно разбили? Никто ничего не разбивал. Только слышала, как Виталий ругался из окна. Да и все.

Если учитывать, что каждая из женщин в своем повествовании солгала только один раз, что на самом деле происходило сегодня во дворе?

Решение:

Больше полезных материалов вы найдете на нашем телеграм-канале «Библиотека программиста»

***

Материалы по теме

22
Фев
2022

Нужно определить принадлежат ли точки окружности

Даны координаты точки i = [0, 1]
Радиус круга r = 3
я написал функцию
def get_result(i, r):
return (i[0]** 2 and i[1]** 2 < r** 2)

ожидаемое значение теста должно быть – True (точки принадлежат кругу)
но фактическое значение выдает…

21
Фев
2022

⚽ Зенит, Спартак или Локомотив: какую команду выбрал каждый из учеников?

Три ученика решили принять участие в спортивных соревнованиях. Для начала каждому из учеников необходимо было вступить в одну из трех команд: ABC, CAB или BCA. Но при подаче заявки на вступление в команду ребята немного повздорили.