Один из способов решения этой проблемы рекурсивно основан на подсчете цифр. Для присутствующего di git x (с положительным счетчиком) проверьте, есть ли еще какое-нибудь y такое, что x + y равно указанной сумме (например, 10). Если y присутствует (имеет положительное число), вернуть 1 плюс рекурсивно вычисленное количество пар в оставшихся цифрах без x и y. Если нет, верните рекурсивно вычисленное количество пар в оставшихся цифрах без x. В базовом случае возвращается 0, когда не осталось цифр.
Вот пример реализации в Python. pair_present является логическим, но преобразуется в целое число при использовании в сумме (1 для True и 0 для False). num_pairs был написан как чистая функция, так что ее аргументы не подвергались деструктивному изменению.
from collections import Counter
def num_pairs(digits, total=10):
try:
x = next(digits.elements())
except StopIteration:
# base case: no digits
return 0
digits = digits - Counter({x: 1})
y = total - x
pair_present = digits[y] > 0
digits = digits - Counter({y: 1})
return pair_present + num_pairs(digits, total=total)
number = 734655
digits = Counter(int(c) for c in str(number))
print(num_pairs(digits)) # 3
Подобный подход мог бы работать непосредственно со строковым представлением числа, а не с подсчетом цифр. Для первого di git x в номере проверьте, есть ли еще какое-то y такое, что x + y равно указанной сумме (например, 10). Если присутствует y, вернуть 1 плюс рекурсивно вычисленное количество пар в оставшейся строке без x и y. Если нет, верните рекурсивно рассчитанное количество пар в оставшейся строке без x. Базовый случай возвращает 0, когда не осталось цифр.
Вот пример реализации в Python.
def num_pairs(string, total=10):
if len(string) == 0:
return 0
x = int(string[0])
string = string[1:] # remove x from string
y = total - x
pair_present = str(y) in string
if pair_present:
string = string.replace(str(y), '') # remove y from string
return pair_present + num_pairs(string, total=total)
number = 734655
print(num_pairs(str(number))) # 3
По сравнению с подходами, описанными выше, следующий итеративный подход имеет Преимущества, заключающиеся в том, что 1) в качестве входных данных используется само число, 2) предотвращается копирование объекта в более ранних решениях (использовавшихся ранее, чтобы избежать деструктивной модификации входных данных), и 3) по-видимому, более простой способ решения проблемы.
from collections import Counter
def num_pairs(number, total=10):
digits = Counter(int(c) for c in str(number))
output = 0
while True:
x = next(digits.elements(), None)
if x is None:
return output
digits[x] -= 1
y = total - x
if digits[y] > 0:
output += 1
digits[y] -= 1
print(num_pairs(734655)) # 3
Альтернативный способ рекурсивного решения проблемы - преобразовать предыдущую итеративную реализацию в ту, которая использует рекурсию вместо l oop, как показано в примере реализации Python ниже. Некоторые языки (например, Scheme) использовали бы здесь оптимизацию хвостового вызова, чтобы каждый рекурсивный вызов не использовал дополнительное пространство стека. Это не относится к Python.
from collections import Counter
def num_pairs(number, total=10, _state=None):
if _state is None:
_state = {
'digits': Counter(int(c) for c in str(number)),
'result': 0
}
digits = _state['digits']
x = next(digits.elements(), None)
if x is None:
return _state['result']
digits[x] -= 1
y = total - x
if digits[y] > 0:
_state['result'] += 1
digits[y] -= 1
return num_pairs(number, total, _state)
print(num_pairs(734655)) # 3
Кроме того, рекурсивное решение может использовать сортировку и двоичный поиск. Сначала отсортируйте цифры. Для первого di git x используйте двоичный поиск по другим цифрам, чтобы увидеть, есть ли y, такое, что x + y равно указанной сумме. Если присутствует y, вернуть 1 плюс рекурсивно вычисленное количество пар в оставшихся отсортированных цифрах. Если нет, верните рекурсивно вычисленное количество пар в оставшихся цифрах. В базовом случае возвращается 0, если не осталось цифр. Особый случай требуется для случая, когда x + y равно указанной сумме и x == y, чтобы предотвратить перерасчет. Вот пример реализации в Python.
from bisect import bisect_left
def num_pairs(digits, total=10, _sorted=False):
if len(digits) == 1:
return 0
if not _sorted:
digits = sorted(digits)
x = digits[0]
digits = digits[1:]
y = total - x
if x > y:
return 0
# Use binary search to check for y's location.
idx = bisect_left(digits, y)
pair_present = idx < len(digits) and digits[idx] == y
# If x + y == total and x == y, pop y to prevent over-counting.
if pair_present and x == y:
digits = digits[1:]
return pair_present + num_pairs(digits, total=total, _sorted=True)
number = 734655
print(num_pairs([int(c) for c in str(number)])) # 3