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


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

задачи кодируется словом 11 . . . |0| | . . . |, а ее реше-
^^••••^•••^.^^••••^^^^ ^^^•^^•^•^..лммм^^^^
124 44
ние — словом 1111, если число п кодировать с помощью слова алфавита Ai длины п.
Упражнение 3. Найти правило, которое для любого натурального числа п позволяет конечным способом определить, с каким показателем данное простое число р входит в разложение числа п на простые множители (если п не делится на р, то считается, что р входит в указанное разложение с показателем нуль).
Пример 3. Пусть задан какой-нибудь алфавит А = = {яь . . . „ as}, состоящий из 5^1 букв, и некоторое слово а в этом алфавите. Требуется указать конечную процедуру, позволяющую для любого слова р узнать, содержит ли оно в качестве своей связной части слово а («входит» ли слово а в слово Р).
Требуемая процедура получается из следующих соображений: связных частей слова р, имеющих столько же букв, сколько а, — конечное число. Поэтому потребуется только конечное число шагов для побуквенного сравнения всех таких частей с а, и в ходе этого сравнения мы либо обнаружим тождественность какой-нибудь такой части и слова а, либо убедимся, что все эти части отличны от а. Скажем, если Л = {|, +, а}, а=||+, Р=| + |аа|+, то требуется испытать на совпадение с а следующие части р: | + |, + |я, \аа, аа\, я]+. Ни одна из этих частей с а не совпадает, поэтому р не содержит а.
В этом примере условие каждой частной задачи можно кодировать словом р уже введенного алфавита, утвердительный ответ — словом |, отрицательный — словом 11 (ответ к задаче | + |яя[+ будет тогда 11).
Пример 4. Определим на множестве натуральных чисел следующую функцию f(n): если какая-нибудь цифра встречается в десятичном разложении числа я в точности п+1 раз подряд, то /(п) = 1, в противном случае f(n)=0. Требуется указать процедуру, позволяющую для каждого п вычислить в конечное число шагов f(n).
Ясно, что. эта задача принадлежит тому же типу, что и рассматривавшиеся ранее. В частности, условия и решения соответствующих частных задач могут быть закодированы словами конечного алфавита. Однако в настоящее время никакое решение указанной задачи неизвестно: с одной стороны, не обнаружено требуемой конечной

 

1 2 3 4 5 6 7 8 9 10 20


Математика