Производящие функции и умножение рядов
Сначала простой пример: мы хотим знать, сколько существует способов получить 20 центов из пяти центов и десяти центов.
Вы когда-нибудь задумывались, можете ли вы выполнять математические операции и писать алгоритмы для всего, что вы изучаете на уроках математики в колледже, в коде Python? Бьюсь об заклад, ты сможешь. Выбросьте устаревший калькулятор и прекратите поиск более мощных онлайн-калькуляторов. Как насчет того, чтобы написать свою собственную программу. Давайте проведем дискретную математику.
Ценники: N = x⁰ + x⁵ + x¹⁰ + x¹⁵ + x²⁰ (Возьмите монету 0, 1, 2, 3 или 4 раза)
Даймы: D = x⁰ + x¹⁰ + x²⁰ (Возьмите десять центов 0, 1 или 2 раз)
Теперь просто умножьте элемент серии на элемент.
Комбинации монет: (x⁰ + x⁵ + x¹⁰ + x¹⁵ + x²⁰) * (x⁰ + x¹⁰ + x²) =
x⁰ * (x⁰ + x¹⁰ + x²⁰) +
x⁵ (* x⁰ + x¹⁰ + x²⁰) +
x¹⁰ * (x⁰ + x¹⁰ + x²⁰) +
x¹⁵ (* x⁰ + x¹⁰ + x²⁰) +
x²⁰ (* x⁰ + x¹⁰ + x²⁰)
= x⁰ + x⁵ + 2x¹⁰ + 2x¹⁵ + 3x²⁰
Таким образом, мы знаем, что существует 3 различных комбинации монет, поэтому мы получаем 20 центов. 2 дайма, 1 дайм и 2 никеля или 4 никеля. Выглядит правильно!
Примечание: (Одна комбинация для 0 и 5 центов, 2 для 10 и 15 центов)
1. Сначала мы импортируем numpy
import numpy as np
2. Затем мы составляем списки для всех типов монет
Python не может напрямую работать с степенными рядами, такими как x¹, x², x³…, но не беспокойтесь, вместо этого мы просто кодируем ряд как список 1, 2, 3…
(1 + 2 = 3 аналогично к x¹ + x² = x³)
cents = list(range(0,101,1)) # [0,1,2,3 ...,100] nickels = list(range(0,105,5)) # [0,5,10,15 ...,100] dimes = list(range(0,110,10)) # [0,10,20,30 ...,100] quarters = list(range(0,125,25)) # [0,25,50,75,100] coins = [cents,nickels,dimes,quarters]
3. Написание функции для умножения рядов: это сложно.
Не самое красивое решение, но оно работает хорошо. (Это просто умножение ряда сверху, добавляя степени и отслеживая счет)
def series_multiplication(powers):
powers = [np.array(p) for p in powers]
current_counts = np.ones(len(powers[0]))
current_powers = powers[0]
#current_counter = counters[0]
for p in powers[1:]:
# multiply each element from the first series with each element in the other series
powers_to_add = []
for e in p:
power_mult = [] #list(current_powers + e)
for cp,cc in list(zip(current_powers, current_counts)):
elements_to_add = [cp+e]*int(cc)
power_mult.extend(elements_to_add) # append each multiplied cp element cc times
powers_to_add.extend(power_mult)
current_powers, current_counts = np.unique(powers_to_add,return_counts=True)
return list(zip(current_powers, current_counts))
Полученные результаты
Теперь, когда у нас есть 1 доллар каждого типа монет (100 центов, 20 никелей, 10 десятицентовиков, 4 четверти), мы получаем счет для каждой комбинации от 1 цента до 400 центов. (Вывод закорочен, чтобы было удобнее читать)
Есть 242 способа обменять 1 доллар!
series_multiplication(coins) Output: [(0, 1), (1, 1), (2, 1), (3, 1), (4, 1), (5, 2), ... (10, 4), ... (20, 9), ... (100, 242), ... (400, 1)]
Спасибо моему профессору Дону Арапура из Университета Пердью за столь хорошее объяснение концепции производящих функций.
Если вы цените усилия, которые я вложил в эту статью, и хотите увидеть больше, пожалуйста, 👏 эту историю и рассмотрите возможность подписки на мою учетную запись.
Некоторые из моих других статей, которые могут вас заинтересовать
Подписывайтесь на меня на Medium, чтобы не пропустить новые сообщения об искусственном интеллекте, машинном обучении, математике и предпринимательстве! Кристоф Остертаг
