Я написал рекурсивную функцию, чтобы найти no. экземпляров подстроки в родительской строке. То, как я поддерживаю подсчет, заключается в объявлении/инициализации count как глобальной переменной вне области функции. Проблема в том, что это даст мне правильные результаты только при первом запуске функции, потому что после этого count!= 0 для начала. И если у меня есть внутри функции, чем каждый раз, когда она вызывается рекурсивно, она будет установлена в 0.
count=0
def countSubStringMatchRecursive(target,key):
index=find(target,key)
global count
targetstring=target
if index>=0:
count=count+1
target=target[index+len(key):]
countSubStringMatchRecursive(target,key)
else :
pass
return "No. of instances of", key, 'in', targetstring, 'is', count
Примечание. Я ищу решение для функции recursive специально, у меня есть итеративная функция, которая работает нормально.
EDIT: Спасибо всем, это было частью домашней работы, поэтому я использовал только строковый модуль
Один из способов изменения кода - использовать локальную функцию следующим образом:
def countSubStringMatchRecursive(target,key):
def countit(target,key,count):
index=find(target,key)
if index>=0:
target=target[index+len(key):]
count += countit(target,key,count) + 1
return count
return "No. of instances of", key, 'in', target, 'is', countit(target,key,0)
Ваша рекурсивная функция имеет производительность O (n ^ 2), поскольку она копирует оставшееся содержимое строки каждый раз, когда находит совпадение. Это медленнее, чем итерационное решение O (n) и без необходимости.
Вы можете легко переписать его быстрее и в то же время упростить код и расширить его функциональность, передав начальный индекс для поиска в качестве необязательного параметра для функции:
def countSubStringMatchRecursive(target, key, start_index = 0):
index = target.find(key, start_index)
if index >= 0:
return countSubStringMatchRecursive(target, key, index + len(key)) + 1
return 0
target_string = 'an apple and a banana'
key = 'an'
count = countSubStringMatchRecursive(target_string, key)
print "Number of instances of %r in %r is %d" % (key, target_string, count)
Вывод:
Number of instances of 'an' in 'an apple and a banana' is 4
Обновление. Если вы действительно хотите использовать функцию поиска строкового модуля, вы можете сделать это, просто изменив одну строку:
index = find(target, key, start_index)
Здесь что-то похожее на Грега Хьюглилла. Однако вместо этого мы переходим по текущему счету каждый раз, когда вызываем функцию, а затем возвращаем счет, когда больше нет совпадений. Хотя я подозреваю, что это не имеет никакого отношения к Python, на языках, реализующих рекурсию хвостового вызова, это позволяет каждый последующий вызов do_count оптимизироваться в стеке вызовов. Это означает, что каждый вызов do_count не приводит к росту стека вызовов.
def count_sub_strings(target, key):
def do_count(target, key, count):
index = target.find(key)
if index >= 0:
target = target[index + len(key):]
return do_count(target, key, count + 1)
else:
return count
return "No. of instances of %s in %s is %s" % (key, target, do_count(target, key, 0))
Просто одно примечание: все представленные решения (от исходного Q до всего As) решают проблему, отличную от специально сформулированной (я предполагаю, что ошибка в конкретном заявлении о проблеме, но стоит исправить, если это так;-). Рассмотрим:
>>> 'banana'.count('ana')
1
>>> sum('banana'[x:x+3]=='ana' for x in range(len('banana')))
2
первое выражение подсчитывает неперекрывающиеся вхождения 'ana' в 'banana'; второй - подсчет всех вхождений - есть два вхождения во всех, по индексам 1 и 3 в "банане", и они перекрываются. Поэтому, учитывая оператор проблемы, я цитирую:
найдите no. случаев подстрока в родительской строке.
без упоминания о "неперекрывающемся", кажется, что необходимо учитывать совпадающие вхождения. Конечно, это легко исправить, как только вы заметили - вам просто нужно продвигаться на 1 каждый раз, вместо того чтобы продвигаться на len(key), что заставляет вас пропускать перекрывающиеся вхождения.
Итак, например:
import string
def countit(target, key, startfrom=0):
where = string.find(target, key, startfrom)
if where < 0: return 0
return 1 + countit(target, key, where+1)
print countit('banana', 'ana')
печатает 2, подсчитывая оба (перекрывающиеся) вхождения.
Я делаю этот курс на OpenCourseware, это здорово. В любом случае, это то, что я сделал. Я принял вдохновение от адама выше.
def countSubStringMatchRecursive(target, key, counter = 0):
if find(target,key) == 0:
countSubStringMatchRecursive(target[1:], key, counter + 1)
elif find(target,key) > 0:
countSubStringMatchRecursive(target[1:], key, counter)
elif find(target,key) == -1:
print counter
Принимая во внимание перекрывающиеся вхождения и поддерживая исходное определение из MIT, это более простой и компактный код, который я могу получить.
код:
from string import *
def countSubStringMatchRecursive(target, key):
index = find(target, key)
if index > -1:
return countSubStringMatchRecursive(target[index + 1:], key) + 1
return 0
def test(target, key):
instances = countSubStringMatchRecursive(target, key)
if instances == 0:
print "No instance of %r in %r" % (key, target)
else:
print "Number of instances of %r in %r: %d" % (key, target, instances)
test("atgacatgcacaagtatgcat","ggcc")
test("atgacatgcacaagtatgcat","atgc")
test("banana", "ana")
выход:
Нет экземпляра 'ggcc' в 'atgacatgcacaagtatgcat'
Число экземпляров 'atgc' в 'atgacatgcacaagtatgcat': 2
Число экземпляров "ana" в "банане": 2
def countSubStringMatchRecursive(target,key):
index = string.find(target, key)
if index == -1:
return 0
else:
return 1 + countSubStringMatchRecursive(target[index+len(key):],key)
Как насчет этого?
def count_it(target, key):
index = target.find(key)
if index >= 0:
return 1 + count_it(target[index+len(key):], key)
else:
return 0
print count_it("aaa bbb aaa ccc aaa", "aaa")
Вывод:
3
Не непроверено...
код:
def countSubStringMatchRecursive(target, key, count=0):
#### index = find(target, key) # HUH?
index = target.find(key)
if index >= 0:
count += 1
target = target[index+len(key):]
count = countSubStringMatchRecursive(target, key, count)
return count
for test in ['', 'bar', 'foo', 'foofoo', 'foo foo foo fo']:
print countSubStringMatchRecursive(test, 'foo'), test.count(key), repr(test)
выход:
0 0 ''
0 0 'bar'
1 1 'foo'
2 2 'foofoo'
3 3 'foo foo foo fo'
Я предполагаю, что это просто развлечение или домашнее задание... рекурсивная функция должна быть медленнее, чем соответствующее итеративное решение Python, которое будет, естественно, медленнее, чем использование target.count(key)... поэтому я не потрудился с фиксацией всех проблемы с вашей версией... но прочитайте PEP-008: -)
Комментарии к строковому модулю
Вы прокомментировали, что вы опустили from string import find. Какую версию Python вы используете? Какова последняя дата обновления для книги или учебника, которое вы используете?
С самого начала строкового модуля (он будет на вашем компьютере как <your Python install directory>/Lib/string.py, я цитирую версию 2.6):
"" Коллекция строковых операций (большинство из них больше не используется).
Внимание: большая часть кода, который вы видите здесь, обычно не используется в настоящее время. Начиная с Python 1.6, многие из этих функций реализованы как методы на стандартном строковом объекте. Они использовались встроенный модуль называется strop, но strop теперь устарел сам.
и т.д. ""
и вот этот код файла для функции find (лишенный комментариев):
def find(s, *args):
return s.find(*args)
поэтому использование string.find(target, key) вместо target.find(key) является отходами.
Другим способом может быть третий необязательный параметр в функции countSubStringMatchRecursive, называемый счетчиком, изначально установленным на 0. Таким образом, вы можете отслеживать счет. Это может привести к тому, что переменная count станет внешней, что может быть нежелательно, но поскольку она не хуже вашей глобальной переменной, я не думаю, что это будет проблемой в вашем случае.
Вам также придется изменить код, чтобы последний рекурсивный вызов был вызовом, который возвращает оператор return во внешний мир. См. Этот пример (непроверенный):
def countSubStringMatchRecursive(target, key, count = 0):
index = find(target, key)
targetstring = target
if index >= 0:
count += 1
target = target[index+len(key):]
countSubStringMatchRecursive(target, key, count)
else:
return "No. of instances of", key, 'in', targetstring, 'is', count
Изменить: я понял, что вам понадобится четвертый параметр, чтобы сохранить исходную строку, перемещающуюся вдоль рекурсии. Это, вероятно, менее оптимальное решение, и я бы рекомендовал использовать решение Greg Hewgill. Он имеет четкое разделение между взаимодействием с внешним и "бизнес-логикой", что делает код более многоразовым!
steps = 0
def addPersistence(number, steps):
steps += 1
if len(str(number))==1:
print(str(number) + "\nDone---------------------------------------------------")
print("TOTAL STEPS " + str(steps-1))
digits = [int(i) for i in str(number)]
result = 0
for j in digits:
result += j
if len(str(number)) != 1:
print(number)
addPersistence(result, steps)
Это пример, скопированный из одного из моих проектов. Эта функция предназначена для добавления к постоянству числа (который добавляет цифры числа и повторяет его до тех пор, пока число не становится равным 1), но, безусловно, его можно использовать повторно, и вы можете использовать свою функцию следующим образом (это код Python 3)., если вы хотите изменить его на Python 2, он все равно будет работать):
count=0
def countSubStringMatchRecursive(target,key,count):
index=find(target,key)
targetstring=target
if index>=0:
count+=1
target=target[index+len(key):]
countSubStringMatchRecursive(target,key,count)
else :
pass
print("STEPS: "+str(count))
Вы можете заметить, что мой код немного отличается. Почему? Ответ заключается в том, что количество шагов, которое требуется для того, чтобы число достигло 1 с помощью этой функции, заключается в том, что последний вызов не включен в мою функцию, поскольку это дублирование вызова перед этим.