Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Варпаховский Ф.Л. Элементы теории алгоритмов
 
djvu / html
 

равно ftfc нулю или нет, сможем заключить, делится п на р или нет.
Рассмотрим этот пример более детально. Отметим прежде всего, что поставленная «общая» задача включает в себя бесконечное (счетное) множество «частных» задач. Так, если число р фиксировано, например положено р=23, то можно говорить о следующих частных задачах: делится ли 0 на 23 (задача 1), делится ли 1 на 23 (задача 2), делится ли 2 на 23 (задача 3) и т. д. Приведенное выше правило одинаково пригодно для решения любой из этих задач, и решение каждой из них получается по данному правилу после проведения конечного числа операций (шагов). В нашем случае шаги эти включают в себя операции вычитания и сравнения чисел по их величине. Эти операции, в свою очередь, могут быть «разложены» на более простые операции также с конечным числом шагов. Вопрос о том, какие же операции следует считать наиболее простыми, не поддающимися дальнейшему разложению, мы сейчас оставляем в стороне, довольствуясь уверенностью в «конечности» каждой из применяемых здесь операций.
Следующее важное замечание относится к вопросу «кодирования» условий частных задач и их решений. Именно, речь идет о возможности задания такого алфавита А с буквами #i, , . . , as, словами которого можно было бы выразить как условия всех частных задач, так и их решения (т. е. ответы к задачам), причем по кодирующему слову соответствующее условие или ответ должны восстанавливаться однозначно. Оказывается, что в рассмотренном случае такой алфавит возможен — достаточно даже просто однобуквенного алфавита, скажем алфавита А^ состоящего из единственной буквы |:Л = = {|} (в алфавите ЛА возможны только слова 11 ... |,
ч*^s
состоящие из k последовательных «палочек», которые мы будем называть словами длины k\ в частности, пустое слово называется словом длины нуль). Закодируем, например, ответ делится словом |, ответ не делится — пустым словом, а условие частной задачи, в которой требуется определив, делится ли число k на р, — словом длины k.
Упражнение 1. Вывести из данного примера правило (конечную процедуру) для решения следующей за-

 

1 2 3 4 5 6 7 8 9 10 20


Математика