ермин «алгоритм», впервые употребленный в современном значении. Лейбницем (1646–1716), является латинизированной формой имени великого персидского математика Мухаммеда бен Муссы аль-Хорезми (ок. 783 – ок. 850). Его книга «Об индийском счете» в XII в. была переведена на латинский язык и пользовалась широкой популярностью не одно столетие. Имя автора европейцы произносили как Алгоритми (Algorithmi), и со временем так стали называть в Европе всю систему десятичной арифметики.
Научное определение алгоритма дал А. Чёрч в 1930 году. В наше время понятие алгоритма является одним из основополагающих понятий вычислительной математики и информатики.
Алгоритм — это точное и полное описание последовательности действий над заданными объектами, позволяющее получить конечный результат.
Можно сказать, что алгоритм решения какой-либо задачи — это последовательность шагов реализации (или нахождения) этого решения, а процесс построения алгоритма (алгоритмизация) — разложение задачи на элементарные действия или операции.
Область математики, известная как теория алгоритмов, посвящена исследованию свойств записи, области применения различных алгоритмов, а также созданию новых алгоритмов. Теория алгоритмов находит широкое применение в различных областях деятельности человека — в технике, производстве, медицине, образовании и т. д. Появление компьютера позволило решать чрезвычайно сложные, трудоемкие задачи.
Определение алгоритма для применения в области информатики нуждается в некотором уточнении. Во-первых, решение задач в информатике всегда связано с преобразованием информации, а значит, исходными данными и результатом работы алгоритма должна быть информация. Это может быть представлено в виде схемы.
Объяснение:
Принцип работы рекурсивный
Объяснение:
# В комментариях я использовал слово итерация в значении запуска новой функции с данными spos/ppos большими на 1 (аналогично с циклом for
# Ввод данных
s = input("Слово: ")
p = input("Шаблон: ")
# match возвращает True, если подстрока s, начинающаяся с позиции spos,
# соответствует шаблону (подстрока p, которая начинается
# с позиции ppos)
def match(spos, ppos):
if (spos == len(s)) or (ppos == len(p)):
return (spos == len(s) and ppos == len(p)) #когда все символы слова либо шаблона пройдены возвращается True, если и шаблон и слово пройдены полностью, в другом случае возвращается False
elif p[ppos] == '?':
return match(spos + 1, ppos + 1) #когда встречается ? начинается новая итерация
elif p[ppos] == '*': #проверка если подстрока - *
for i in range(spos, len(s)): #обход всех оставшихся символов слова
if match(i, ppos + 1):
return True #если дочерняя функция (вызванная выше) выдала True, цикл for заканчивается до выдавая True
else: #выполняется когда не встретилось */?
return (s[spos] == p[ppos]) and (match(spos + 1, ppos + 1))# проверка на равентсво соответствующих (по индексу) символов слова и шаблона и запуск новой функции (итерации)
if match(0, 0):
print('YES') #если результат функции True в консоль выводится 'YES', иначе 'NO'
else:
print('NO')