«Е.А. Роганов Основы информатики и программирования Учебное пособие для студентов программистских специальностей Москва 2001 ББК 22.18 УДК 519.6 Р59 Е.А. Роганов. Основы информатики и программирования: Учебное пособие ...»

public class InvArr { public static void main(String[] args) throws Exception { n = Xterm.inputInt("Введите длину массива n -> ");

Задача 6.2. Запишите предикат, утверждающий, что ни одно из следующих утверждений не является истинным: a < b, b < c и x = y.

Решение. Это задание тоже не является сложным. Вот несколько эквивалентных между собой решений: P1 = ((a < b) = F ) ((b < c) = F ) Так как обычно нужно предъявить максимально простой предикат, то будем считать ответом последний из них P3.

В ряде последующих задач нам придется иметь дело с массивами, поэтому договоримся о следующих обозначениях: будем обозначать вырезку из массива b[0..m 1], в которой содержатся все элементы данного массива с индексами от j до k включительно, символом b[j..k]. В случаях, когда j > k, k < 0 или j m, вырезка представляет из себя пустое множество.

Задача 6.3. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n > 0 все элементы вырезки b[j..k] являются нулевыми.

Решение. Используем квантор всеобщности: i j i < k + 1 b[i] = 0.

Задача 6.4. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n > 0 ни один из элементов вырезки b[j..k] не нулевой.

Решение. Переформулировав данное высказывание (все элементы вырезки не нулевые), запишем ответ в следующем виде: i j i< k + 1 b[i] = 0.

Задача перевода высказывания с естественного языка на язык предикатов не всегда является однозначной, но именно это и является одной из причин его использования. Вот пример.

Задача 6.5. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n > 0 некоторые из элементов вырезки b[j..k] нулевые.

Решение. Данное высказывание можно понимать двояко: оно может означать, что в вырезке существует хотя бы один нулевой элемент, а может значить и то, что в ней как минимум два нулевых элемента. Вот ответы для каждого из этих вариантов трактовки задачи: P 1 = i j i < 0) (b[m] = 0).

Вот аналогичные задачи из области математики.

Задача 6.6. Запишите предикат, который утверждает, что функция f : {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} является сюръективной и отрицание этого факта. Упростите получившиеся предикаты, если это возможно.

§6. Спецификация программ и преобразователь предикатов Решение. В соответствии с определением сюръективности имеем P = (y {1, 2, 3, 4, 5} x {1, 2, 3, 4, 5} y = f (x)). Построим отрицание и упростим его в соответствии с законами эквивалентности. !P = (!(y {1, 2, 3, 4, 5} x {1, 2, 3, 4, 5} y = f (x))) = (y {1, 2, 3, 4, 5} !(x {1, 2, 3, 4, 5} y = f (x))) = (y {1, 2, 3, 4, 5} x {1, 2, 3, 4, 5} !(y = f (x))) = (y {1, 2, 3, 4, 5} x {1, 2, 3, 4, 5} y = f (x)).

Задача 6.7. Запишите предикат, который утверждает, что функция f : {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} все элементы, не превосходящие трех, не увеличивает, и отрицание этого факта. Упростите получившиеся предикаты, если это возможно.

Решение. P = (x {1, 2, 3} f (x) x). Его отрицание можно упростить: !P =!(x {1, 2, 3} f (x) x) = (x {1, 2, 3} f (x) > x).

В текст программы зачастую полезно включать предикаты, которые позволяли бы человеку или компьютеру проверять корректность хода выполнения программы. В тех случаях, когда подобные утверждения предназначены только для человека, они оформляются в виде комментариев.

Часто, однако, полезно поручить проверку истинности предикатов в процессе выполнения программы непосредственно компьютеру. В различных языках программирования эта возможность реализована поразному. Например, в программах на языке C можно использовать макрос assert(P), который в случае ложности его аргумента (предиката P) немедленно прекращает выполнение программы, сообщая о причине этого.

Механизм работы с исключениями и оператор if позволяют легко реализовать аналогичную конструкцию в языке Java. Вот простейший пример.

Задача 6.8. Напишите программу, содержащую проверку истинности утверждения о положительности введенного с клавиатуры целого числа.

Текст программы.

public class Assert { public static void main(String[] args) throws Exception { int n = Xterm.inputInt("Введите n -> ");

Задача 6.13. Вычислите и упростите wp("if(true);", R) для произвольного предиката R.

Решение. wp("if(true);", R) = wp("if(true); else ;", R) = ((T wp(";", R))(F wp(";", R))) = ((F R)(T R)) = (RT ) = R.

Рассмотрим в заключение задачу на решение уравнения, связанного со слабейшим предусловием.

Задача 6.14. Найдите такое значение выражения x, включающее другие переменные, для которого спецификация {Q} S {R} становится тавтологией: {T } "a=a+1; b=x;" {b = a + 1}.

§6. Спецификация программ и преобразователь предикатов Решение. Вспомним, что имеет место эквивалентность {Q} S {R} = (Q wp(S, R)). Таким образом, нам необходимо подобрать такое x, для которого (T wp("a=a+1; b=x;", b = a + 1)) = T. Вычислим сначала слабейшее предусловие, входящее в этот предикат: wp("a=a+1; b=x;", b = a + 1) = wp("a=a+1;", wp("b=x;", b = a + 1)) = wp("a=a+1;", x = a + 1) = (x = a + 2).

Легко убедиться, однако, что мы получили неверный результат! И все дело в том, что переменная x зависит от a. Проведем вычисления повторно, заменив x на x(a): wp("a=a+1; b=x(a);", b = a + 1) = wp("a=a+1;", wp("b=x(a);", b = a + 1)) = wp("a=a+1;", x(a) = a + 1) = (x(a + 1) = a + 2).

Вернемся к исходной задаче. Нам нужно выяснить, при каких значениях x выражение (T (x(a + 1) = a + 2)) = T окажется тавтологией.

Упростим данное выражение: ((T (x(a + 1) = a + 2)) = T ) = (T (x(a + 1) = a + 2)) = (F (x(a + 1) = a + 2)) = (x(a + 1) = a + 2).

Теперь ответ очевиден: x(a) = a + 1 или просто x = a + 1.

7. Задачи для самостоятельного решения.

Задача 6.15. Запишите предикат, утверждающий, что самое большее одно из следующих утверждений истинно: a < b, b < c.

Задача 6.16. Запишите предикат, утверждающий, что следующие утверждения не являются истинными одновременно: a < b, b < c и x = y.

Задача 6.17. Запишите предикат, утверждающий следующее: когда x < y, y < z означает, что v = w, но если x y, то y < z не может выполняться; однако если v = w, то x < y.

Задача 6.18. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n > 0 все нули массива находятся в вырезке b[j..k].

Задача 6.19. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n > 0 некоторые нули массива находятся в вырезке b[j..k].

Задача 6.20. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n > 0 справедливо высказывание: неверно, что все нули массива находятся в вырезке b[j..k].

Задача 6.21. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n > 0 справедливо высказывание: неверно, что не все нули массива находятся в вырезке b[j..k].

Задача 6.22. Запишите предикат, который утверждает, что функция f : {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} является инъективной и отрицание этого факта. Упростите получившиеся предикаты, если это возможно.

88 Глава I. Введение в информатику и программирование Задача 6.23. Запишите предикат, который утверждает, что функция f : {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} является биективной и отрицание этого факта. Упростите получившиеся предикаты, если это возможно.

Задача 6.24. Запишите предикат, который утверждает, что функция f : {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} все существует единственный элемент x {1, 2, 3, 4, 5}, который функция f уменьшает, и отрицание этого факта. Не используйте при этом квантора !.

Задача 6.25. Основываясь на определении 6.4 и спецификации программы 6.1, докажите истинность эквивалентности {Q} S {R} = (Q wp(S, R)).

Задача 6.26. Основываясь на определении 6.4, докажите закон монотонности (Q R) (wp(S, Q) wp(S, R)).

Задача 6.27. Основываясь на определении 6.4, докажите закон дистрибутивности дизъюнкции wp(S, Q) wp(S, R) = wp(S, Q R).

Задача 6.28. Вычислите и упростите wp("i=i+1; j=j-1;", i · j = 0).

Задача 6.29. Вычислите и упростите wp("x=x+y;", x < 2y).

Задача 6.30. Вычислите и упростите wp("i=i+1; j=j+1;", i = j).

Задача 6.31. Вычислите и упростите wp("a=0; n=1;", a2 < n (a + 1)2 n).

Задача 6.32. Вычислите и упростите wp("s=s+b[i]; i=i+1;", 0 < Задача 6.33. Вычислите и упростите следующее слабейшее предусловие wp("if (a > b) a=a-b; else b=b-a;", a > 0 b > 0).

Задача 6.34. Найдите такое значение выражения x, включающее другие переменные, для которого спецификация {Q} S {R} становится тавтологией: {T } "b=x; a=a+1;" {b = a + 1}.

Задача 6.35. Найдите такое значение выражения x, включающее другие переменные, для которого спецификация {Q} S {R} становится тавтологией: {i = j} "i=i+1; j=x;" {i = j}.

Некоторые из сформулированных ниже задач уже были разобраны ранее, другие предложены для самостоятельного решения, решения третьих будут приведены в последующих главах. Часть из них войдет §7. Все задачи главы в список зачетных задач, умение справиться с которыми является необходимым условием успешного завершения изучения курса.

Бльшая часть задач позаимствована из различной литературы, среди которой хочется отметить книги [9] и [14].

1. Задачи на составление алгоритмов.

Задача 7.1. Придумайте алгоритм, вводящий натуральное число, большее единицы, который находит наименьший простой делитель этого числа.

Задача 7.2. Придумайте алгоритм, вводящий три целых числа и определяющий, есть ли среди введенных чисел одинаковые или нет.

Задача 7.3. Придумайте алгоритм, вводящий три целых числа, который находит второе по величине число, если оно существует.

Задача 7.4. Придумайте алгоритм, вводящий три целых числа, определяющий количество максимальных чисел среди введенных.

Задача 7.5. Придумайте алгоритм, вводящий действительное число, который рассматривает это число, как координаты точки на прямой, и находит расстояние от этой точки до отрезка [0, 1].

Задача 7.6. Придумайте алгоритм, находящий n-ое простое число.

2. Простейшие задачи на программирование.

Задача 7.7. Напишите программу, выводящую на экран строку текста Здравствуй, мир!.

Задача 7.8. Напишите программу, печатающую на экране красивое поздравление с новым учебным годом.

Задача 7.9. Напишите программу, вводящую имя пользователя (с применением метода inputChars), которая затем приветствует его.

Задача 7.10. Напишите программу, вводящую натуральное число, большее единицы, которая находит и печатает наименьший простой делитель этого числа.

Задача 7.11. Напишите программу, вводящую два целых числа a и b, печатающую их, затем обменивающую значения этих переменных (так, чтобы новое значение a стало равно старому значению b, и наоборот) и вновь их печатающую.

Задача 7.12. Напишите программу, вводящую два целых числа a и b, печатающую их, затем обменивающую значения этих переменных (так, 90 Глава I. Введение в информатику и программирование чтобы новое значение a стало равно старому значению b, и наоборот) и вновь их печатающую, которая не использовала бы иных переменных, кроме a и b.

Задача 7.13. Напишите программу, вводящую три целых числа, и печатающую максимальное из них.

Задача 7.14. Напишите программу, вводящую три целых числа, и печатающую количество максимальных среди введенных чисел.

Задача 7.15. Напишите программу, вводящую три целых числа, и печатающую Yes в том случае, если среди введенных чисел есть одинаковые, и No иначе.

Задача 7.16. Напишите программу, вводящую три целых числа, и печатающую второе по величине, если оно существует, и No иначе.

Задача 7.17. Напишите программу, вводящую действительное число, которая рассматривает это число, как координаты точки на прямой, и печатает расстояние от этой точки до отрезка [0, 1].

Задача 7.18. Напишите программу, вводящую три целых числа, и печатающую с использованием всех возможностей класса Xterm как сами числа, так и их среднее арифметическое.

Задача 7.19. Напишите программу, вводящую действительные коэффициенты a, b и c квадратного уравнения ax2 +bx+c = 0 с положительным дискриминантом, находящую оба корня этого уравнения.

Задача 7.20. Напишите программу, которая вводит три целых числа, и, рассматривая эти числа, как координаты точек на прямой, печатает расстояние между наиболее удаленными друг от друга.

Задача 7.21. Напишите программу, которая вводит действительные координаты (x, y) и (a, b) двух точек на плоскости, и печатает расстояние от точки M (x, y) до единичной окружности с центром в точке C(a, b).

Задача 7.22. Напишите программу, которая вводит действительные координаты (x, y) и (a, b) двух точек на плоскости, и печатает расстояние от точки M (x, y) до прямой OA, где O начало координат, а A(a, b) отличная от O точка.

Задача 7.23. Напишите программу, вводящую три целых числа a, b и c, печатающую мощность множества решений уравнения ax2 + bx + c = 0.

§7. Все задачи главы 3. Задачи на предикаты.

Задача 7.24. Докажите, что выражение ((a b) = (b a)) является предикатом.

Задача 7.25. Докажите, что выражение a a не предикат.

Задача 7.26. Докажите, что выражение ((e1 (e2 e3 )) = ((e1 e2 ) (e1 e3 ))) является предикатом.

Задача 7.27. Докажите, что выражение ((e1 (e2 e3 )) = ((e1 e2 )e3 )) является предикатом.

Задача 7.28. Докажите, что выражение ((a a) не предикат.

Задача 7.29. Докажите, что выражение ((a b)) не предикат.

Задача 7.30. Изобразите деревья вывода для каждого из законов эквивалентности (см. страницу 42).

Задача 7.31. Вычислите значения предикатов P1 = (x = 0 x/(y 2) = 0) и P2 = (x = 0 && x/(y 2) = 0) в состоянии s = {(x, 7), (y, 2)}.

Задача 7.32. Вычислите значения предиката P = (i 0 i 0)) (j j 2 k) в состоянии s = {(k, 0)}.

Задача 7.33. Вычислите значения предиката P = (!(x > y b)(b x > y))!(x > y b) в состоянии s = {(x, 3), (y, 2), (b, F )}.

Задача 7.34. Вычислите значения предиката P = (b (x > y)) ((b (x > y))||(!(x > y) !b)) в состоянии s = {(x, 2), (y, 3), (b, T )}.

Задача 7.35. Покажите, что все законы эквивалентности (см. стр. 42) являются тавтологиями.

Задача 7.36. Запишите предикат, утверждающий, что если i < j, а m > n, то u = v.

Задача 7.37. Запишите предикат, утверждающий, что самое большее одно из следующих утверждений истинно: a < b, b < c.

Задача 7.38. Запишите предикат, утверждающий, что ни одно из следующих утверждений не является истинным: a < b, b < c и x = y.

Задача 7.39. Запишите предикат, утверждающий, что следующие утверждения не являются истинными одновременно: a < b, b < c и x = y.

Задача 7.40. Запишите предикат, утверждающий следующее: когда x < y, y < z означает, что v = w, но если x y, то y < z не может выполняться; однако если v = w, то x < y.

92 Глава I. Введение в информатику и программирование Задача 7.41. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n > 0 все элементы вырезки b[j..k] являются нулевыми.

Задача 7.42. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n > 0 ни один из элементов вырезки b[j..k] не нулевой.

Задача 7.43. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n > 0 некоторые из элементов вырезки b[j..k] нулевые.

Задача 7.44. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n > 0 все нули массива находятся в вырезке b[j..k].

Задача 7.45. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n > 0 некоторые нули массива находятся в вырезке b[j..k].

Задача 7.46. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n > 0 справедливо высказывание: неверно, что все нули массива находятся в вырезке b[j..k].

Задача 7.47. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n > 0 справедливо высказывание: неверно, что не все нули массива находятся в вырезке b[j..k].

Задача 7.48. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n > 0 справедливо высказывание: если в b[0..n 1] есть нуль, то он есть и в вырезке b[j..k].

Задача 7.49. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n > 0 справедливо высказывание: если в вырезке b[j..k] есть два нуля, то j = 1.

Задача 7.50. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n > 0 справедливо высказывание: элементы в вырезке b[j..k] расположены в возрастающем порядке.

Задача 7.51. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n > 0 справедливо высказывание: j является степенью двойки, если j встречается в вырезке b[j..k].

Задача 7.52. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n > 0 справедливо высказывание: если b[1], b[2] и b[3] есть соответственно 3, 4 и 5, то j = 3.

Задача 7.53. Запишите предикат, который утверждает, что функция f : {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} является сюръективной и отрицание этого факта. Упростите получившиеся предикаты, если это возможно.

§7. Все задачи главы Задача 7.54. Запишите предикат, который утверждает, что функция f : {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} является инъективной и отрицание этого факта. Упростите получившиеся предикаты, если это возможно.

Задача 7.55. Запишите предикат, который утверждает, что функция f : {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} является биективной и отрицание этого факта. Упростите получившиеся предикаты, если это возможно.

Задача 7.56. Запишите предикат, который утверждает, что функция f : {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} все элементы, не превосходящие трех, не увеличивает, и отрицание этого факта. Упростите получившиеся предикаты, если это возможно.

Задача 7.57. Запишите предикат, который утверждает, что функция f : {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} все существует единственный элемент x {1, 2, 3, 4, 5}, который функция f уменьшает, и отрицание этого факта. Не используйте при этом квантора !.

Задача 7.58. Основываясь на определении 6.4 и спецификации программы 6.1, докажите истинность эквивалентности {Q} S {R} = (Q wp(S, R)).

Задача 7.59. Основываясь на определении 6.4, докажите закон монотонности (Q R) (wp(S, Q) wp(S, R)).

Задача 7.60. Основываясь на определении 6.4, докажите закон дистрибутивности дизъюнкции wp(S, Q) wp(S, R) = wp(S, Q R).

Задача 7.61. Вычислите и упростите wp("i=i+2; j=j-2;", i + j = 0).

Задача 7.62. Вычислите и упростите wp("i=i+1; j=j-1;", i · j = 0).

Задача 7.63. Вычислите и упростите wp("x=x+y;", x < 2y).

Задача 7.64. Вычислите и упростите wp("x=(x+y)*(x-y);", x + y 2 = 0).

Задача 7.65. Вычислите и упростите wp("i=i+1; j=j+1;", i = j).

Задача 7.66. Вычислите и упростите wp("x=a/b;", x2 0).

Задача 7.67. Вычислите и упростите wp("i=1; s=b[0];", 1 i< Задача 7.68. Вычислите и упростите wp("a=0; n=1;", a2 < n (a + 1)2 n).

Задача 7.69. Вычислите и упростите wp("s=s+b[i]; i=i+1;", 0 < 94 Глава I. Введение в информатику и программирование Задача 7.70. Вычислите и упростите wp("if(true);", R) для произвольного предиката R.

Задача 7.71. Вычислите и упростите следующее слабейшее предусловие wp("if (a > b) a=a-b; else b=b-a;", a > 0 b > 0).

Задача 7.72. Найдите такое значение выражения x, включающее другие переменные, для которого спецификация {Q} S {R} становится тавтологией: {T } "a=a+1; b=x;" {b = a + 1}.

Задача 7.73. Найдите такое значение выражения x, включающее другие переменные, для которого спецификация {Q} S {R} становится тавтологией: {T } "b=x; a=a+1;" {b = a + 1}.

Задача 7.74. Найдите такое значение выражения x, включающее другие переменные, для которого спецификация {Q} S {R} становится тавтологией: {i = j} "i=i+1; j=x;" {i = j}.

Задача 7.75. Найдите такое значение выражения x, включающее другие переменные, для которого спецификация {Q} S {R} становится тавтологией: {i = j} "j=x; i=i+1;" {i = j}.

Задача 7.76. Задача о банке с кофейными зернами. В банке имеется несколько черных и белых кофейных зерен. Следующий процесс надо повторять, пока это возможно:

– случайно выберите из банки два зерна и – если они одного цвета, отбросьте их, но положите в банку другое черное зерно (имеется достаточный запас черных зерен, чтобы делать это);

– если они разного цвета, поместите белое зерно обратно в банку и отбросьте черное зерно.

Выполнение этого процесса уменьшает количество зерен в банке на единицу. Повторение процесса должно прекратиться, когда в банке останется всего одно зерно, так как тогда нельзя уже выбрать два зерна. Можно ли что-то сказать о цвете оставшегося зерна, если известно, сколько вначале в банке было черных и белых зерен?

Задача 7.77. Замыкание кривой. Двое играют на листе клетчатой бумаги произвольной формы и размера в следующую игру. Игроки делают ходы поочередно и начинает игрок A. Ход игрока A состоит в том, что он соединяет горизонтальным или вертикальным отрезком два соседних узла решетки, проводя непрерывную линию по границе одного из квадратиков (клеточек) бумаги. Ход игрока B сводится к проведению пунктирной линии, обладающей теми же свойствами. Проводить линию по уже нарисованной противником нельзя.

§7. Все задачи главы Игрок A выигрывает, если ему удается получить полностью замкнутую кривую, состоящую из непрерывных линий. Если игрок A не сумеет получить замкнутую кривую, то считается, что победил игрок B. Существует ли стратегия, гарантирующая выигрыш на произвольной доске для одного из игроков?

4. Задачи на особенности представления чисел в ЭВМ.

Задача 7.78. Предъявите целое число x такое, что x + 1 < x.

Задача 7.79. Предъявите действительное (типа double) число x такое, что x + 1 = x, а (x · 2)/2 = x. Воспользуйтесь тем, что класс java.lang.Double определяет константу MAX_VALUE.

Задача 7.80. Предъявите такие действительные (типа double) числа a, b и c такие, что a + (b + c) = (a + b) + c.

Задача 7.81. Явно перечислите и изобразите на числовой прямой все точки множества RM, сделав следующие допущения: числа хранятся в нормализованной форме с плавающей точкой; для хранения как мантиссы, так и порядка числа отводится по три бита (из которых в обоих случаях один является знаковым); никаких особых значений нет.

Задача 7.82. Предъявите действительное (типа double) число x такое, что (x/2) · 2 = x. Воспользуйтесь тем, что класс java.lang.Double определяет константу MIN_VALUE.

Задача 7.83. Определите (приближенно) M ACHEP S (машинное эпсилон) для типов double и float. Машинным эпсилоном называется наибольшее число x данного типа, удовлетворяющее соотношению 1 + x = 1.

Задача 7.84. Предъявите последовательность чисел (типа float), при суммировании которой в прямом и обратном порядке результаты будут отличаться не менее, чем вдвое.

Задача 7.85. Напишите программу, вводящую действительные коэффициенты a, b и c квадратного уравнения ax2 + bx + c = 0 с положительным дискриминантом, находящую оба корня этого уравнения достаточно точно во всех случаях.

5. Задачи на рекурсию и итерацию.

Задача 7.86. Напишите рекурсивную программу, вычисляющую факториал введенного натурального числа.

Задача 7.87. Напишите рекурсивную программу, печатающую n-ое число Фибоначчи.

96 Глава I. Введение в информатику и программирование Задача 7.88. Напишите итерационную программу, вычисляющую факториал введенного натурального числа.

Задача 7.89. Напишите программу, печатающую n-ое число Фибоначчи, которая имела бы линейную сложность.

Задача 7.90. Напишите программу, печатающую n-ое число Фибоначчи, которая имела бы логарифмическую сложность.

Задача 7.91. Напишите программу, вычисляющую факториал введенного натурального числа, не использующую ни итерации, ни рекурсии (имеющую сложность (1)).

Указание. Воспользуйтесь тем, что факториал очень быстро растущая функция, а множество ZM ограничено, и поэтому любая программа, работающая с величинами типа int, способна вычислить факториал только очень небольших чисел.

Задача 7.92. Напишите программу, перемножающую два натуральных числа, которая не использует операции умножения.

Задача 7.93. Напишите программу, перемножающую два натуральных числа, которая не использует операции умножения, и имеет при этом логарифмическую сложность.

Указание. Можете попробовать разобраться в программе, решающей задачу 5.5. В ней выполняется более сложное действие квадратная матрица возводится в степень n за логарифмическое время.

Задача 7.94. Напишите программу, вводящую целое число a и натуральное n, вычисляющую и печатающую степень an без использования вызова функции возведения в степень.

Задача 7.95. Напишите программу (быстрое возведение в степень), возводящую целое число a в целую неотрицательную степень b без вызова функции возведения в степень с временнй сложностью (log b).

Задача 7.96. Напишите программу, печатающую сумму квадратов всех натуральных чисел от 1 до введенного натурального n, которая имела бы константную сложность, т.е. не использовала бы ни итерации, ни рекурсии.

Задача 7.97. Напишите программу, вводящую натуральное число, и печатающую Yes, если оно является простым и No иначе.

Задача 7.98. Напишите программу, печатающую n-ое простое число.

Задача 7.99. Напишите рекурсивную программу, печатающую биноk минальный коэффициент Cn для целых n и k, где 0 k n. Для неотриn цательных n и k имеют место следующие соотношения: Cn = Cn = 1, Cn+1 = Cn + Cn.

Задача 7.100. Напишите программу, печатающую старшую цифру в десятичной записи введенного натурального числа.

Задача 7.101. Напишите программу, печатающую количество цифр в десятичной записи введенного натурального числа.

Задача 7.102. Напишите программу, печатающую десятичную запись введенного натурального числа, использующую только операции печати цифр от 0 до 9.

Задача 7.103. Напишите программу, печатающую количество натуральных решений неравенства x2 + y 2 < n для введенного натурального числа n.

Задача 7.104. Напишите программу, вводящую натуральное число R, и печатающую количество точек с целочисленными координатами внутри замкнутого шара радиуса R с центром в начале координат.

Задача 7.105. Напишите программу, вводящую целые коэффициенты многочлена пятой степени в порядке убывания его степеней, и печатающую последовательность коэффициентов его куба.

Задача 7.106. Напишите программу, вводящую натуральное число x, и печатающую наиболее близкую к x простую дробь вида m/n со знаменателем n, не превосходящем 100.

Задача 7.107. Напишите программу, печатающую первые k пар простых чисел. Два числа a и b образуют пару простых чисел, если они оба простые и b = a + 2.

Задача 7.108. Напишите программу, находящую сумму сложность которой была бы линейной.

Задача 7.109. Напишите программу, находящую наибольший общий делитель gcd(X, Y ) двух натуральных чисел X и Y.

Задача 7.110. Напишите программу, печатающую квадраты всех целых чисел от нуля до введенного натурального n, не использующую операций умножения и имеющую линейную сложность.

98 Глава I. Введение в информатику и программирование Задача 7.111. Напишите программу, находящую количество счастливых билетов с шестизначными номерами. Билет называется счастливым, если сумма его первых трех цифр равна сумме трех последних.

6. Задачи на массивы.

Задача 7.112. Напишите программу, которая вводит с клавиатуры непустой массив целых чисел, печатает его, затем инвертирует (то есть меняет местами первый элемент с последним, второй с предпоследним и т.д.), и вновь печатает.

Задача 7.113. Напишите программу, печатающую максимальный элемент непустого массива.

Задача 7.114. Напишите программу, печатающую количество максимальных элементов непустого массива, в которой используется только один цикл.

Задача 7.115. Напишите программу, которая вводит с клавиатуры непустой массив целых чисел, печатает его, затем сортирует (то есть переставляет его элементы так, чтобы они располагались в неубывающем порядке), и вновь печатает.

Задача 7.116. Напишите программу, вводящую фразу русского языка (с использованием метода inputChars), которая определяет, является ли введенная фраза палиндромом.

Указание. Палиндром эта фраза, инвертирование которой не изменяет ее. При этом все пробелы во фразе игнорируются.

Задача 7.117. Напишите программу, печатающую количество нулевых элементов в заданном целочисленном массиве.

Задача 7.118. Напишите программу, которая вводит с клавиатуры непустой массив целых чисел, и печатает Yes, если массив симметричен, и No иначе.

Задача 7.119. Напишите программу, которая вводит с клавиатуры непустой массив целых чисел, циклически сдвигает элементы массива вправо на одну позицию, и печатает результат. Цикличность означает, что последний элемент массива становится самым первым его элементом.

Задача 7.120. Напишите программу, которая вводит с клавиатуры непустой массив целых чисел, циклически сдвигает элементы массива вправо на k позиций, и печатает результат. Число k вводится с клавиатуры, а сложность программы должна быть (n).

§7. Все задачи главы Задача 7.121. Напишите программу, которая вводит с клавиатуры непустой массив целых чисел, заменяет все элементы массива, кроме крайних, на полусумму соседей, и печатает результат.

Задача 7.122. Напишите программу (линейный поиск), определяющую первое вхождение заданного целого числа x в массив целых чисел, заведомо содержащий это число.

Задача 7.123. Напишите программу, которая вводит с клавиатуры два непустых массива целых чисел в диапазоне от нуля до девяти, и, считая эти массивы десятичным представлением двух чисел, печатает их разность.

Задача 7.124. Напишите программу, которая вводит с клавиатуры два непустых неубывающих массива целых чисел, и печатает те и только те элементы, которые встречаются хотя бы в одном из массивов (объединение множеств).

Задача 7.125. Напишите программу, которая вводит с клавиатуры два непустых неубывающих массива целых чисел, и печатает те и только те элементы, которые встречаются в обоих массивах (пересечение множеств).

Задача 7.126. Напишите программу, которая вводит с клавиатуры два непустых неубывающих массива целых чисел, и печатает те и только те элементы, которые входят только в один из массивов (симметрическая разность множеств).

Задача 7.127. Напишите программу, печатающую значение многочлена степени n 0 в заданной точке x0. Коэффициенты многочлена хранятся в массиве a в порядке убывания степеней и являются целыми числами, также как и значение x0. Величины n, x0 и элементы массива a изменять в программе нельзя.

Задача 7.128. Напишите программу (двоичный поиск), определяющую для упорядоченного по неубыванию массива целых чисел, содержащего число x, первое вхождение этого целого числа, которая имела бы логарифмическую сложность.

Указание. Воспользуйтесь методом деления пополам, известным из курса математического анализа.

Задача 7.129. Напишите программу, заносящую в массив первые натуральных чисел, делящихся на 13 или на 17, и печатающую его.

100 Глава I. Введение в информатику и программирование Задача 7.130. Напишите программу, которая в массиве целых чисел длины m + n, рассматриваемом как соединение двух его частей начала длины m и конца длины n, обменивает начало и конец, не используя дополнительных массивов.

Задача 7.131. Напишите программу, вводящую целые коэффициенты многочлена и находящую все его рациональные корни.

Указание. Воспользуйтесь теоремой Безу, согласно которой числиp тель p любого рационального корня многочлена x = является делителем свободного члена, а знаменатель q делителем старшего коэффициента.

Задача 7.132. Напишите программу, которая вводит с клавиатуры непустой массив целых чисел, и печатает число локальных максимумов (элемент является локальным максимумом, если он не имеет соседей, больших, чем он сам).

7. Задачи на последовательности.

Задача 7.133. Напишите программу, вводящую последовательность целых чисел, и печатающую количество ее максимальных элементов.

Задача 7.134. Напишите программу, вводящую последовательность целых чисел, и печатающую количество различных значений квадратов ее элементов.

Задача 7.135. Напишите программу, вводящую последовательность вещественных чисел, и печатающую среднее арифметическое ее элементов (для непустой последовательности).

Задача 7.136. Напишите программу, вводящую последовательность целых чисел, и печатающую максимальное число идущих подряд одинаковых элементов.

Задача 7.137. Напишите программу, вводящую последовательность целых чисел, и печатающую номера первого и последнего ее максимальных элементов.

Задача 7.138. Напишите программу, вводящую последовательность целых чисел, и печатающую номер первого элемента, равного нулю, и нуль при отсутствии такого элемента в последовательности.

Задача 7.139. Напишите программу, вводящую последовательность целых чисел, и печатающую число элементов, больших предыдущего (первый элемент последовательности тоже считается таким).

§7. Все задачи главы Задача 7.140. Напишите программу, вводящую последовательность целых чисел, и печатающую второй по величине ее элемент и No, если такого элемента нет.

Задача 7.141. Напишите программу, вводящую последовательность целых чисел, и печатающую три ее таких (не обязательно различных) элемента x, y и z, что xy = z, или No, если таких элементов нет.

Задача 7.142. Напишите программу, вводящую последовательность целых чисел, и печатающую максимальную длину монотонного участка ее элементов.

Задача 7.143. Напишите программу, вводящую последовательность из нулей и единиц, печатающую число групп из единиц, разделенных нулями.

Задача 7.144. Напишите программу, вводящую последовательность целых чисел, и печатающую количество вхождений в нее фрагмента 1, 2, 3, 4, 5, 6.

Задача 7.145. Напишите программу, вводящую последовательность целых чисел, и печатающую количество вхождений в нее фрагмента 1, 2, 1, 2, 1, 2.

Основная цель данной главы показать, как теория помогает практике. Красивые и эффективные алгоритмы решения многих непростых задач при правильном подходе к ним будут получаться как бы сами собой. Процесс создания программ при этом в значительной мере автоматизируется, а вместе с решением мы получаем еще и доказательство правильности построенных программ.

В качестве дополнительного источника информации к данной главе можно порекомендовать книги [4] и [9].

§ 1. Базисные схемы обработки информации Все задачи на написание программ можно разделить на следующие три группы.

1. Простейшие задачи. В этот класс задач мы отнесем линейные программы и программы с ветвлениями, которые не используют ни циклов, ни рекурсивных вызовов. Создание подобных программ обычно не вызывает серьезных проблем, а их правильность легко может быть проверена с помощью методов, изложенных в предыдущей главе.

2. Задачи на программирование в малом. Бльшая часть зао дач, которые уже были нами рассмотрены, относятся именно к этой категории. Кроме совсем простых к ней относятся и более сложные, при решении которых оправдано применение различных методов разработки программ типа проектирования сверху вниз.

Характеристическим свойством задач на программирование в малом является их простая сводимость к совокупности таких задач на обработку информации, для решения которых достаточно применения итерации или рекурсии.

3. Большие проекты. Почти все практические задачи относятся именно к этому классу. Для них даже аккуратная формулировка постановки задачи является проблемой. Решение подобных задач требует применения специальных методов, большая часть из которых выходит за рамки нашего курса.

#$¦'$¤'$¦¤$% @ 2¤8¤67¤6¤!#¤ '$¦#$$# Рис. 1. Базисные схемы обработки информации Объектно-ориентированное проектирование в значительной мере помогает справиться со сложностью подобных задач, позволяя свести их к решению многих значительно более простых. Проекты, которые мы рассмотрим в следующей главе, позволят проиллюстрировать это на практике.

Предложенное деление задач на группы является достаточно условным и некоторые из них могут быть отнесены как ко второй, так и к третьей. В данной главе мы сосредоточимся на методах решения наиболее простых задач из второй категории, программная реализация которых не превосходит 10–20 строк текста. Все подобные задачи можно рассматривать, как задачи на обработку информации, что и поясняет название классификации методов их решения схемы обработки информации, графическая иллюстрация взаимосвязи которых приведена на рисунке 1.

1. Рекурсия и итерация. Как определения этих двух базисных схем обработки информации, так и их взаимосвязь уже были рассмотрены нами ранее. Напомним самое главное.

Рекурсия это такой способ организации обработки данных, при котором программа вызывает сама себя непосредственно, либо с помощью других программ.

Итерация способ организации обработки данных, при котором определенные действия повторяются многократно, не приводя при этом к рекурсивным вызовам программ.

Любой алгоритм, реализованный в рекурсивной форме, может быть переписан в итерационном виде, и наоборот.

Некоторые особенности применения рекурсии уже были рассмотрены при решении задачи 5.1. Сейчас мы продолжим исследование данного §1. Базисные схемы обработки информации вопроса, уделяя особое внимание процессу построения программы и доказательству ее правильности. Рекурсивная программа обычно возникает, как результат вычисления рекурсивно определенной функции на множестве программных переменных, а доказательство ее правильности требует исследования двух вопросов:

1) всегда ли и почему программа заканчивает работу?

2) почему после окончания работы программы будет получен требуемый результат?

Рассмотрим следующую задачу.

Задача 1.1. Напишите рекурсивную программу, перемножающую два целых числа, одно из которых неотрицательно, без использования операции умножения. Точные пред- и постусловия требуемой программы, времення сложность которой не должна превосходить (log b), таковы:

Q = (a ZM b ZM b 0), R = (z = ab). Числа a и b в программе изменять нельзя.

Решение. Фиксировав a, рассмотрим функцию mula (b) : ZM ZM, задаваемую следующим рекурсивным определением:

mula (0) = 0, mula (b) = 2 · mula (b/2), когда b положительно и четно, mula (b) = mula (b 1) + a, когда b положительно и нечетно.

Программа, вычисляющая функцию mula, легко пишется в соответствии с ее определением. В целях эффективности деление пополам и умножение на два реализуются с помощью сдвигов.

Текст программы.

public class MulR { static int mul(int x, int y) { // Xterm.print(" Вызов mul(" + x + "," + y + ")\n");

Теперь можно написать программу, реализующую вычисление этой функции.

Текст программы.

public class PolVal { static int a[], x0;

static int p(int k) { public static void main(String[] args) throws Exception { int n = Xterm.inputInt("n -> ");

for (int i=0; i 0. На втором этапе конструируется тело цикла S, реализующее преобразование T : сначала обеспечивается уменьшение ограничивающей функции h, а затем сохранение инварианта I.

Геометрическая интерпретация данной схемы приведена на рисунке 3, где через XS0 обозначено множество, получающееся из XQ с помощью совокупности присваиваний S0.

Рассмотрим применение этой схемы для решения следующей задачи.

Задача 1.3. Напишите программу, перемножающую два целых числа, одно из которых неотрицательно, без использования операции умножения. Точные пред- и постусловия требуемой программы, времення а сложность которой не должна превосходить (log b), таковы: Q = (a личины a и b изменять не разрешается, следует использовать инвариант I = (y 0 z + xy = ab) и ограничивающую функция h = y.

Решение. Для написания программы надо сконструировать S0 (совокупность присваиваний, осуществляющих начальную инициализацию), условие продолжения e и тело цикла S.

Начальные присваивания должны сделать истинным инвариант (в случае истинности предусловия) и при этом быть максимально простыми Рис. 3. Проектирование цикла при помощи инварианта и легко находимыми. В данном случае достаточно быстро можно обнаружить, что хорошим кандидатом на роль S0 является следующая совокупность присваиваний "x=a;y=b;z=0;".

Условие продолжения цикла e нам уже по существу дано, так как очередная итерация цикла должна происходить только при h > 0. По этой причине логично предположить, что наша программа должна содержать оператор "while(y>0)S;", тело которого S пока неизвестно.

Мы обязаны обеспечить завершение цикла, следовательно величина y должна уменьшаться на каждой его итерации. Уменьшение y каждый раз на единицу заведомо не позволит получить достаточно эффективную программу. По этой причине необходимо уменьшать величину y более быстро. Хорошей мыслью является попытка делить величину y пополам тогда, когда это можно (при четных y). Легко оценить, что если бы деление пополам происходило на каждом шаге цикла, то количество его итераций было бы примерно равно log b. Это вполне согласуется с тем, что требуется в решаемой задаче.

Так как после итерации цикла инвариант должен остаться истинным, то уже зная, как меняется y, вычисляем, как следует изменять z (ибо по условию задачи мы не можем изменять a и b). В результате находим (либо в уме, либо формально вычисляя wp), что при четных y величину x следует удваивать, а при нечетных необходимо увеличивать значение переменной z на x.

Программа написана!

Текст программы.

public class MulI { §1. Базисные схемы обработки информации public static void main(String[] args) throws Exception { int a = Xterm.inputInt("a -> ");

int b = Xterm.inputInt("b -> ");

3. Схема вычисления инвариантной функции. Общая схема итерации значительно упрощается для случая вычисления значений инвариантных функций.

Определение 1.3. Пусть X некоторое множество, F : X Y заданная на нем функция, а P предикат такой, что P (x) = (F (x) легко вычислить). Обозначим через XP то подмножество множества X, где P (x) = T. Если существует преобразование T : X \ XP X такое, что x X \ XP F (T (x)) = F (x), то функция F называется T -инвариантной или просто инвариантной функцией.

Простейшим примером инвариантной функции является хорошо известная еще из средней школы функция f : R R, f (x) = sin x. Она является T -инвариантной относительно преобразования T : R R, T (x) = x + 2.

Наибольший общий делитель двух целых чисел (greatest common divisor, gcd(x, y) или просто НОД(x,y)) инвариантен относительно преобразования T : Z Z Z Z, задаваемого формулой T (x, y) = Доказательство этого факта, основанное на основной теореме арифметики о разложении числа на простые множители, является достаточно простым и оставляется читателю. Обратите только внимание на то, что функция gcd(x, y) не определена в точке (0, 0).

Для вычисления значения T -инвариантной функции F в точке x 0 X применяется следующая схема.

Схема вычисления инвариантной функции. Многократно выполняется преобразование T, дающее последовательность точек Рис. 4. Схема вычисления инвариантной функции x0, x1,... Если очередная точка xn попадaет в подмножество XP, то итерации завершаются. По определению инвариантной функции F (xn ) легко вычисляется и совпадает с искомым F (x0 ).

Рисунок 4 содержит графическую иллюстрацию этой схемы.

Схема вычисления инвариантной функции значительно облегчает проектирование программы "S0;while(e)S;S1;", так как нам изначально известны инвариант I = (F (x) = F (x0 )) и условие продолжения цикла e(x) =!P (x). Тело цикла S конструируется, как программная реализация известного преобразования T, а написание S1, вычисляющей F (x n ), не может представлять трудностей в силу самого определения инвариантной функции.

В качестве иллюстрации применения схемы вычисления инвариантной функции рассмотрим следующую задачу.

Задача 1.4. Напишите программу, находящую наибольший общий делитель gcd(x, y) двух целых неотрицательных чисел x и y, не равных одновременно нулю. Воспользуйтесь следующими свойствами наибольшего общего делителя (не забудьте научиться доказывать все эти свойства):

gcd(x, y) = gcd(x, y x) = gcd(x y, y), gcd(x, y) = gcd(x, y + x) = gcd(x + y, y), gcd(x, x) = x, gcd(x, y) = gcd(y, x), gcd(x, 0) = gcd(0, x) = x.

Решение. Если через Z+ обозначить множество всех неотрицательM ных целых чисел, представимых в ЭВМ, то X = Z+ Z+ \ {(0, 0)}, Y = §1. Базисные схемы обработки информации Z+, XP = {(x, y) X x = 0 y = 0}, F (x, y) = gcd(x, y). В качестве преобM разования T : X\XP X можно взять T (x, y) = Таким образом, нам известны инвариант I = (gcd(x, y) = gcd(x0, y0 )) и условие продолжения e = (x = 0 y = 0). Начальные присваивания S в данном случае не нужны, тело цикла S пишется по определению T, a программа S1, вычисляющая gcd(x, y) для (x, y) XP, реализуется с помощью справедливой для этих значений аргумента формулы gcd(x, y) = x + y.

Текст программы.

public class Gcd { public static void main(String[] args) throws Exception { Xterm.println(" " + (x+y));

Обратите внимание на тот факт, что в построенной программе не понадобилось наличие переменной, соответствующей значению инвариантной функции gcd(x, y).

Рассмотрим еще одну задачу.

Задача 1.5. Напишите программу, перемножающую два целых числа, одно из которых неотрицательно, без использования операции умножения. Точные пред- и постусловия требуемой программы, времення а сложность которой не должна превосходить (log b), таковы: Q = (a ZM b Z M b 0), R1 = (z = ab). При написании программы величины a и b изменять не разрешается. Воспользуйтесь тем, что функция F : ZM ZM ZM ZM, F (x, y, z) = z + xy является инвариантной относительно преобразования T : ZM ZM ZM ZM ZM ZM, задаваемого формулой T (x, y, z) = {(x, y, z) X : y = 0}. Функция F и преобразование T заданы в условии задачи.

Таким образом, нам известны инвариант I = (F (x, y, z) = F (a, b, 0)) и условие продолжения e = (y = 0). Начальные присваивания S0 очевидны ("x=a; y=b; z=0;"), тело цикла S пишется по определению T, a программа S1, вычисляющая F (x, y, z) для (x, y, z) XP, в данном случае вырождается в пустой оператор ";", так как для этих значений аргумента F (x, y, z) = z. В результате получаем уже знакомую нам программу.

Текст программы.

public class MulInv { public static void main(String[] args) throws Exception { int a = Xterm.inputInt("a -> ");

int b = Xterm.inputInt("b -> ");

4. Функции на пространстве последовательностей. Еще одной ситуацией, в которой общая схема итерации значительно упрощается, является задача вычисления индуктивных функций. Такие функции определены на последовательностях X элементов из некоторого алфавита X.

Напомним важнейшие из определений §3.

Алфавит X Символом алфавита X называют любой его элемент, а цепочкой над произвольную последовательность символов. Цепочки алфавитом часто называют также словами, фразами и предложениями. Пустая цепочка обозначается специальным символом, а множество всех цепочек над алфавитом X принято обозначать X.

Длиной || цепочки X называется количество входящих в нее символов. Множество всех цепочек длины не менее k обозначают через Xk. Справедлива следующая последовательность включений:

Операция : X X X конкатенации (или сцепления) двух цепочек определена следующем образом. Пусть 1 = a1 a2... an, 2 = §1. Базисные схемы обработки информации Рис. 5. Схема вычисления индуктивной функции Теперь можно дать определение индуктивной функции.

Определение 1.4. Функция f : X Y называется индуктивной, если f ( x) можно вычислить, зная f () и x, т.е. если G : Y X Y Одним из простейших примеров индуктивной функции является функция длина цепочки || : X Z+. Она индуктивна, так как для нее существует функция G : Z+ X Z+, определенная формулой G(y, x) = y + 1, удовлетворяющая предыдущему определению.

Для вычисления значения f () индуктивной функции f на цепочке = a1 a2... an применяется следующая схема.

Схема вычисления индуктивной функции. Рассматривается последовательность цепочек, a1, a1 a2,..., a1 a2... an =. Сначала вычисляется значение f () функции f на пустой цепочке, а затем используется отображение G, позволяющее найти значение функции f на удлиненной цепочке, что дает возможность последовательно определить все требуемые величины вплоть до f ().

На рисунке 5 приведена графическая иллюстрация схемы вычисления индуктивной функции.

Схема вычисления индуктивной функции напоминает метод доказательства по индукции. Аналогом базы индукции является вычисление f (), а индуктивному переходу соответствует вычисление функции f (x) на удлиненной цепочке x с использованием вычисленного на предыдущем шаге значения f ().

Схема вычисления индуктивной функции позволяет легко построить программу вида "S0;while(e)S;", получающую на каждой следующей итерации цикла очередной элемент ai цепочки (последовательности) = a1 a2... an, которая находит значение f (). Инвариантом данного цикла является I = (0 i n f = f (a1 a2... ai )), условием продолжения e = (i n), S0 должно вычислять f (), а S быть программной реализацией функции G.

Простым и полезным примером, иллюстрирующим схему вычисления индуктивной функции, является задача нахождения значения многочлена, заданного последовательностью его коэффициентов.

Задача 1.6. Напишите программу, определяющую значение в целой точке t многочлена, заданного последовательностью его целых коэффициентов (в порядке убывания степеней).

Заметим, что Pn (t) = a0 tn + a1 tn1 +...+ an1 t + an = t · Pn1 (t) + an, где Pn1 (t) = a0 tn1 + a1 tn2 +... + an1. Поэтому функция f : (ZM ) ZM, определенная, как f () = f (a0 a1... an ) = Pn (t), удовлетворяет соотношению f ( x) = t·f ()+x, что доказывает ее индуктивность. Отображение G : ZM ZM ZM действует по формуле G(y, x) = ty + x, а f () = 0, что приводит к следующей программе.

Текст программы.

public class Pol { public static void main(String[] args) throws Exception { int t = Xterm.inputInt("t -> ");

Этот эффективный метод вычисления значения многочлена в точке носит имя схемы Горнера.

Методы доказательства правильности программ, построенных с помощью схемы вычисления индуктивных функций, и обобщение этой схемы, позволяющее применять аналогичный подход для функций, не являющихся индуктивными, будут рассмотрены ниже в §3.

5. Задачи для самостоятельного решения. При решении задач на рекурсию необходимо обосновать как то, почему программа заканчивает §1. Базисные схемы обработки информации работу, так и то, почему после ее завершения будет получен требуемый результат.

При использовании схемы вычисления инвариантной функции необходимо указать множества X, Y и XP, функцию F и преобразование T (см. определение инвариантной функции) и объяснить программную реализацию преобразования T.

Задача 1.7. Напишите рекурсивную программу, печатающую значение производной многочлена степени n 0 в заданной точке x 0. Коэффициенты многочлена хранятся в массиве a в порядке убывания степеней и являются целыми числами, так же как и значение x0. Величины n, x0 и элементы массива a изменять в программе нельзя.

Указание. Пусть Pn (x) = a0 xn + a1 xn1 +... + an1 x + an. Продифференцируем по x равенство Pn (x) = x · Pn1 (x) + an и подставим затем x = x0. Мы получим следующие соотношения:

P0 (x0 ) = 0, Pn (x0 ) = x0 · Pn1 (x0 ) + Pn1 (x0 ).

Воспользовавшись ими и формулами P0 (x0 ) = a0, Pn (x0 ) = x0 · Pn1 (x0 ) + an, легко определить рекурсивную функцию неотрицательного целого аргумента g : ZM ZM ZM, g(n) = (Pn (x0 ), Pn (x0 )) для вычисления которой и пишется программа.

Задача 1.8. Напишите программу, возводящую целое число в целую неотрицательную степень. Точные пред- и постусловия требуемой проR = (z = ab ).

При написании программы величины a и b изменять не разрешается, следует использовать инвариант I = (y 0 z · xy = ab ) и ограничивающую функцию h = y.

Задача 1.9. Напишите программу, находящую наибольший общий делитель gcd(x, y) двух целых неотрицательных чисел x и y, не равных одновременно нулю. Воспользуйтесь следующим свойством наибольшего общего делителя (докажите его!):

gcd(x, y) = Здесь операция x%y позволяет найти остаток от деления x на y.

Задача 1.10. Напишите программу, возводящую целое число в целую неотрицательную степень. Точные пред- и постусловия требуемой программы таковы: Q = (a ZM b ZM a > 0 b 0), R1 = (z = ab ).

При написании программы величины a и b изменять не разрешается. Воспользуйтесь тем, что функция F : ZM ZM ZM ZM, F (x, y, z) = zxy является инвариантной относительно преобразования T : Z M ZM ZM ZM ZM ZM, задаваемого формулой T (x, y, z) = (x, y 1, xz).

Задача 1.11. Напишите программу, находящую наибольший общий делитель gcd(x, y) двух целых неотрицательных чисел x и y, не равных одновременно нулю. Программа должна иметь временню сложность поу рядка (log max(x, y)) и не использовать операций деления и нахождения остатка от деления (допустимо деление пополам, реализуемое с помощью операции сдвига). Воспользуйтесь следующими свойствами наибольшего общего делителя (докажите их!):

gcd(2x, 2y) = 2gcd(x, y), gcd(2x, 2y + 1) = gcd(x, 2y + 1).

Указание. Воспользуйтесь инвариантностью функции F (x, y, z) = z · gcd(x, y) относительно следующего преобразования T :

T (x, y, z) = (x, y/2, z), если x нeчетно, а y четно, Не забудьте доказать T -инвариантность функции F.

§ 2. Проектирование цикла при помощи инварианта В предыдущем параграфе мы уже познакомились с техникой проектирования цикла при помощи инварианта, позволяющей значительно упростить написание программ. Вопросы нахождения инвариантов циклов и доказательства правильности получающихся программ основная тематика данного параграфа.

1. Условия правильности цикла. Теоремой, на которой базируется схема проектирования цикла при помощи инварианта, является следующее утверждение, которое мы примем без доказательства. Его истинность может быть выведена из свойств преобразователя предикатов wp и определения оператора цикла 6.12.

Теорема 2.1. Если 1) {Q} "S0;" {I}, 2) {I e} "S;" {I}, 3) (I!e) R, 4) Ieh>0 и 5) {I e} "h1=h; S;" {h < h1}, §2. Проектирование цикла при помощи инварианта то спецификация программы {Q} "S0;while(e)S;" {R} является тавтологией.

Докажем с помощью этой теоремы правильность некоторых программ, построенных в предыдущем параграфе.

Текст программы.

public class MulI { public static void main(String[] args) throws Exception { int a = Xterm.inputInt("a -> ");

int b = Xterm.inputInt("b -> ");

2) Для того чтобы проверить, что предикат I e wp(S, I) является тавтологией, вычислим предварительно wp(S, I).

wp(S, I) = wp("if((y&1)==0){y/=2; x+=x;} else{y-=1; z+=x;}", y ((y нечетно (y 0 z + xy = ab)) (y четно (y 1 z + xy = ab))) = ((y нечетно y четно) (y нечетно (y 1 z + xy = ab)) (y четно (y (F ((z + xy = ab) (y нечетно y 1)) ((z + xy = ab) (y четно y 0)) ((z + xy = ab) (y Далее имеем (Ie wp(S, I)) = (!I!eI) = (!e(I!I)) = (!eT ) = T.

Получившийся предикат представляет собой дизъюнкцию четырех членов и, очевидно, истинен, если истинны первый или второй из этих членов. В противном случае y = 0, и предикат принимает вид (z = abz = ab) = T. Таким образом, (I!e R) тавтология.

5) Для проверки последнего условия найдем wp("h1=h; S;", h < h1) = wp("h1=y;", wp("if((y&1)==0){y/=2; x+=x;} else{y-=1; z+=x;}", y < h1)) = wp("h1=y;", (y четно wp("y/=2; x+=x;", y < h1)) (y нечетно wp("y-=1; z+=x;", y < h1))) = wp("h1=y;", (y нечетноy < y + 1)) = ((y нечетно y < 2 y) (y четно T )) = ((y нечетно y < Тогда имеем (I e wp("h1=h; S;", h < h1)) = (y < 0 z + xy = 0 y > 0)) = ((y < 0 z + xy = ab y нечетно) T ) = T, что завершает доказательство правильности написанной программы.

Докажем частично правильность еще одной построенной в предыдущем параграфе программы.

Текст программы.

public class Gcd { public static void main(String[] args) throws Exception { Xterm.println(" " + (x+y));

Если в качестве ограничивающей функции взять h = x · y, то правильность полученной программы легко может быть доказана. Обозначим через x0 и y0 начальные значения переменных x и y, удовлетворяющих предусловию Q = (x Z+ y Z+ (x, y) = (0, 0)). Заметим также, что постусловие программы в целом может быть записано в виде предиката R1 = (напечатан gcd(x, y)), а постусловием цикла является предикат 1) (Q wp(";", gcd(x, y) = gcd(x0, y0 ))) =!Q T = T.

2) Сохранение инварианта после выполнения тела цикла следует из T -инвариантности gcd(x, y). Формальную проверку проведите самостоятельно.

4) Формальное доказательство проведите самостоятельно.

5) Формальное доказательство проведите самостоятельно.

§2. Проектирование цикла при помощи инварианта 6) Для завершения доказательства правильности программы необходимо еще показать, что является тавтологией R wp("S1", R1). Так как формального определения операторов печати мы не рассматривали, будем считать, что предикат R1 = (z = gcd(x, y)), а S1 имеет вид "z=x+y;".

(R wp("S1", R1)) = ((x = 0 y = 0) (x + y = gcd(x, y))) = (!(x = 0 y = 0) (gcd(x, y) = x + y)).

Полученная дизъюнкция истинна, если ложно условие (x = 0 y = 0).

В противном случае один из аргументов функции gcd равен нулю и по соответствующему свойству наименьшего общего делителя истинным является второй дизъюнктивный член, что завершает доказательство правильности программы.

2. Теория воздушного шарика. До сих пор мы использовали для построения программ готовые, не ясно откуда взявшиеся инварианты. На практике, конечно, постановка задачи не включает в себя инвариант. Однако любая корректная постановка задачи содержит ее пред- и постусловия: {Q} "S0;while(e)S;" {R}, поэтому они и должны послужить основой для построения инварианта.

Теперь нужно понять, какой именно из двух предикатов Q и R более важен для построения инварианта. Приведем два аргумента в пользу постусловия R.

Первый таков: предусловие Q достаточно часто имеет вид T, что соответствует отсутствию ограничений на начальные условия, в которых должна правильно работать программа. Понятно, что в этом случае инвариант можно строить только исходя из постусловия R.

Второй аргумент: представим себе R в виде цели, которой должен достичь путник на местности, а Q в виде точки его начального расположения. Инвариант, который мы хотим построить, должен помочь путнику достичь нужной ему цели. Можно ли надеяться на это, полностью проигнорировав R?

Если не помнить постоянно о цели в процессе написания программы, то весьма маловероятно, что она все же окажется достигнутой. Из какой бы начальной точки путник не вышел, если у него нет цели, он до нее не доберется!

Именно по этой причине программирование называют целенаправленной деятельностью, а за основу для построения инварианта берут постусловие R.

Рассмотрим геометрическую иллюстрацию стоящей перед нами задачи, изобразив на множестве X всех значений программных переменных подмножества XS0 и XR, второе из которых задается постусловием R, а первое представляет собой множество, которое может быть получено из XQ после выполнения совокупности простых присваиваний S0. Искомому инварианту цикла I на рисунке 6 должно соответствовать какое-то неизвестное нам пока множество XI.

Существует весьма красивое описание того, что происходит с множеством переменных программы в процессе выполнения цикла, называемое теорией воздушного шарика. Рассмотрим последовательность предикатов P0, P1,..., Pn, описывающих множества переменных до начала цикла, после его первой итерации,..., после n-ой (последней) итерации.

Множества, определяемые этими предикатами, представляют последовательность вложенных друг в друга множеств, причем X P0 = XI, а XPn = XR. Удобно представлять себе эти множества как последовательные состояния изначально надутого воздушного шарика, из которого на каждой очередной итерации цикла выпускают немного воздуха.

Используя эту модель, можно сказать, что построение инварианта требует так надуть шарик, находящийся в состоянии XR, чтобы он стал содержать множество XS0. С математической точки зрения необходимо ослабить предикат R до такой степени, чтобы истинность этого ослабленного предиката (который и будет взят в качестве инварианта I) могла быть получена из истинного Q с помощью простых начальных присваиваний S0.

Итак, основным методом построения инварианта является ослабление постусловия оператора цикла. При этом часто удается получить и условие продолжения цикла (что по существу эквивалентно заданию ограничивающей функции), взяв в его качестве отрицание того предиката, которым мы ослабили постусловие.

§2. Проектирование цикла при помощи инварианта Реально применяются три первых из следующих ниже приведенных методов построения инварианта.

1) Устранение конъюнктивного члена. Предикат A B C можно ослабить до A C.

2) Замена константы переменной. Предикат (j 0 j < n x b[j]) может быть ослаблен до (0 i n) (j 0 j < i x b[j]), где i новая переменная.

3) Расширение области значений переменной. Предикат 5 i < 10 можно ослабить до 0 i < 10.

4) Добавление дизъюнктивного члена. Предикат A можно ослабить до A B, где B некоторый другой предикат.

Причина того, что четвертый метод не применяется, весьма проста он не содержит никаких рекомендаций по поводу того, как именно выбрать предикат B. Остальные методы построения инварианта цикла будут проиллюстрированы в последующих секциях данного параграфа в процессе решения различных задач.

3. Устранение конъюнктивного члена. Этот метод хорош тем, что взяв в качестве условия продолжения цикла устраненный конъюнктивный член, мы автоматически добиваемся истинности третьего пункта теоремы 2.1, гарантирующей правильность построенного цикла.

Рассмотрим в качестве примера следующую задачу.

Задача 2.1. Напишите программу, находящую приближенное значение квадратного корня a Z+ из заданного неотрицательного цеM лого числа n. Вот более точная формулировка пред- и постусловия:

написании программы величину n изменять нельзя.

Решение. Построим инвариант с помощью метода устранения конъюнктивного члена (a + 1)2 > n из постусловия: I = (a 0 a2 n).

В качестве условия продолжения цикла e может быть взято отрицание удаленного конъюнктивного члена: e = ((a + 1)2 n), что эквивалентно выбору ограничивающей функции h = n (a + 1)2 + 1. Истинность инварианта перед началом выполнения цикла легко устанавливается присваиванием "a=0;" и нам остается только понять, как реализовать тело цикла Для того чтобы цикл завершился, величина a должна увеличиваться. Простейший способ увеличивать a на единицу на каждой итерации цикла. Легко заметить, что это преобразование сохраняет инвариант, поэтому построение программы завершено. Первый вариант программы будет строго соответствовать ее спецификации.

Текст программы.

public class Sqrt { public static void main(String[] args) throws Exception { int n = Xterm.inputInt("n -> ");

Xterm.println("sqrt(" + n + ") = " + a);

Эту программу можно переписать в чуть более компактном виде:

Фрагмент программы (Sqrt2.java).

Докажем все пять условий ее правильности.

Полученный предикат заведомо истинен, если ложны I или e, в противном случае он легко упрощается: wp(S, I) = (a 1 (a + 1)2 n) = (T T ) = T. Истинность первого конъюнктивного члена вытекает из предположения о истинности I, а истинность второго из истинности e.

4) (I e h > 0) = (!I!eh > 0) = (!I (a+1)2 > nn(a+1)2 +1 > 5) wp("h1=h; S;", h < h1) = wp("h1=n-(a+1)*(а+1)+1;", wp("a+=1;", n (a + 1)2 + 1 < h1)) = wp("h1=n-(a+1)*(a+1)+1;", n (a + 2)2 + 1 < в предположении, что истинны I и e (так как из истинности I следует a 0).

Следовательно, (I e wp("h1=h; S;", h < h1)) = (I e T ) = (!I!e T ) = T.

Применим метод устранения конъюктивного члена для построения инварианта цикла при решении еще одной задачи.

Задача 2.2. Напишите программу (линейный поиск), определяющую первое вхождение заданного целого числа x в заданный массив b[0..m 1] целых чисел (m > 0). Известно, что x находится в массиве b. Значения элементов массива b и число x в программе изменять нельзя.

§2. Проектирование цикла при помощи инварианта Решение. Выпишем формально заданные нам пред- и постусловия:

5) wp("h1=h; S;", h < h1) = wp("h1=m-i;", wp("i+=1;", mi < h1)) = Следовательно, (I e wp("h1=h; S;", h < h1)) = (I e T ) = (!I!e T ) = T.

4. Замена константы переменной. В качестве первого примера использования этого метода построения инварианта рассмотрим простую задачу суммирования элементов массива.

Задача 2.3. Напишите программу, находящую сумму s элементов заданного целочисленного массива b[0..n 1], элементы которого и величину n изменять нельзя. Точные пред- и постусловия: Q = (n > 0), Решение. В постусловие входит константа n, которую мы можем заменить новой переменной i, меняющейся в диапазоне от 0 до n включительно. Таким образом, метод замены константы переменной приводит стве ограничивающей функции следует взять h = n i.

Истинности инварианта легко добиться обнулением величин i и s, поэтому искомая программа будет иметь вид "i=0;s=0;while(i ");

Данный предикат заведомо истинен, если истинен один из первых четырех его дизъюнктивных членов. В противном случае имеем 0 i < n и I = T, поэтому истинен пятый его дизъюнктивный член, следовательно предикат является тавтологией.

(i = n) = (R (i = n)).

Очевидно, что (I!e R).

5) wp("h1=h; S;", h < h1) = wp("h1=n-i;", wp("s+=b[i];i+=1;", n Следовательно, (I e wp("h1=h; S;", h < h1)) = (I e T ) = (!I!e T ) = T.

Построим более быструю программу нахождения приближенного значения квадратного корня.

Задача 2.4. Напишите программу, находящую приближенное значение квадратного корня a Z+ из заданного неотрицательного цеM лого числа n. Точные пред- и постусловия требуемой программы, времення сложность которой не должна превосходить (log n), таковы:

написании программы величину n изменять нельзя.

Решение. Построим инвариант с помощью метода замены константы a + 1 на переменную b. Из условия задачи вытекает, что a < b n + 1, следовательно инвариантом является предикат I = (a < b n + 1 a n < b2 ). Условие продолжения цикла легко получается из того факта, что предикат (I!e R) должен быть тавтологией e = (a + 1 = b), а это означает использование ограничивающей функции h = b a 1.

После присваиваний "a=0;b=n+1;" предикат I становится истинным, следовательно наша программа имеет вид "a=0;b=n+1;while(a+1!=b)S;" с неизвестным пока телом цикла S.

Для того чтобы цикл завершился, необходимо уменьшать h, что эквивалентно сближению чисел a и b. Уменьшение разности b a на единицу на каждой итерации цикла не позволит достичь требуемой в условии задачи эффективности программы. Нужная времення сложность может быть получена при использовании метода деления отрезка [a, b] пополам на каждой итерации и выборе той из половинок, на которой лежит искомое приближенное значение квадратного корня. Реализация данной идеи приводит к следующей программе.

Текст программы.

public class Sqrt3 { public static void main(String[] args) throws Exception { n = Xterm.inputInt("n -> ");

fi b = fi1 ), h = n i. Число n в программе изменять нельзя.

§2. Проектирование цикла при помощи инварианта Задача 2.7. Напишите программу, находящую частное q и остаток r от деления x на y, не использующую операций умножения и деления. При написании программы положите Q = (x ZM y ZM x 0 y > 0), Величины x и y в программе изменять не разрешается.

Задача 2.8. Напишите программу, находящую наибольший общий делитель gcd(X, Y ) двух целых положительных чисел X и Y, не использующую операций умножения и деления и не изменяющую величин X и Y.

При написании программы положите Q = (X ZM Y ZM X > 0Y > 0), R = (x = y = gcd(X, Y )), I = (0 < x 0 < y gcd(x, y) = gcd(X, Y )), h = x + y 2 · gcd(x, y).

Указание. Воспользуйтесь следующими свойствами наибольшего общего делителя двух чисел не равных одновременно нулю (не забудьте научиться доказывать все эти свойства):

gcd(x, y) = gcd(x, y x) = gcd(x y, y), gcd(x, y) = gcd(x, y + x) = gcd(x + y, y), gcd(x, x) = x, gcd(x, y) = gcd(y, x), gcd(x, 0) = gcd(0, x) = x.

Задача 2.9. Напишите программу, находящую приближенное значение квадратного корня a Z+ из заданного неотрицательного цеM лого числа n. Вот более точная формулировка пред- и постусловия:

При написании программы величину n изменять нельзя. Для построения инварианта удалите из постусловия конъюнктивный член a 2 n. Оцените временню сложность получившейся программы и сравните ее со сложностью программы, построенной в задаче 2.1.

Задача 2.10. Напишите программу, определяющую первое вхождение заданного целого числа x в заданный массив массивов b[0..m 1][0..n 1] целых чисел (m > 0, n > 0). Значения элементов массива b и числа x, m и n в программе изменять нельзя. В момент завершения должно быть либо b[i][j] = x, либо, если числа x в массиве нет, i = m. Точные преди постусловия требуемой программы таковы: Q = (m > 0 n > 0), R = ((0 i < m 0 j < n x = b[i][j]) (i = m x b[0..m 1][0..n 1])).

Указание. Используйте инвариант, утверждающий, что x не находится в уже проверенных строках b[0..i 1] и среди уже проверенных элементов b[i][0..j 1] текущей строки i. В качестве ограничивающей функции возьмите h = (m i) · n j + m i.

Задача 2.11. Напишите программу (бинарный или двоичный поиск), определяющую для упорядоченного по неубыванию массива b[0..n 1] целых чисел и заданного целого числа x позицию i, в которую может быть вставлено это число без нарушения упорядоченности массива. Точные пред- и постусловия требуемой программы, времення сложность коа торой не должна превосходить (log n), таковы: Q = (x ZM n При написании программы величины x, n и элементы массива b изменять не разрешается, для построения инварианта используйте метод замены константы переменной.

Задача 2.12. Напишите программу, печатающую факториал введенного неотрицательного целого числа, изменять которое нельзя. Для построения инварианта используйте метод замены константы переменной.

§ 3. Индуктивные функции на пространстве В первом параграфе данной главы мы уже познакомились с индуктивными функциями и даже рассмотрели простейшую программу, написанную с помощью применения схемы вычисления индуктивной функции программу вычисления значения многочлена (см. решение задачи 1.6).

К сожалению, подавляющее большинство функций на пространстве последовательностей индуктивными не являются, что требует дальнейшего развития теории.

Весьма подробное рассмотрение вопросов, связанных с индуктивными функциями, и большое число задач на их применение содержатся в книге [9].

1. Критерий индуктивности и стационарные значения. Напомним основное определение.

Функция f : X Y называется индуктивной, если f ( x) можно вычислить, зная f () и x, т.е. если G : Y X Y такое, что Доказательство индуктивности функции обычно проводят конструктивно, предъявляя требуемую функцию G. Именно она позволяет написать программу, реализующую схему вычисления индуктивной функции.

Для доказательства же того факта, что заданная функция не является индуктивной, применяют следующий критерий индуктивности (точнее его отрицание).

Теорема 3.1. Критерий индуктивности. f : X Y индуктивна a, b X x X f (a) = f (b) f (a x) = f (b x).

Теорема утверждает, что f индуктивна тогда и только тогда, когда из равенства значений f на последовательностях a и b следует равенство §3. Индуктивные функции на пространстве последовательностей значений f на любых одинаково удлиненных последовательностях a x и Доказательство. Необходимость сформулированного в критерии условия немедленно следует из определения индуктивности. Если f индуктивна, то a, b X x Xf (a x) = G(f (a), x) = G(f (b), x) = f (b x).

Для доказательства достаточности построим требуемое отображение это отображение формулой G(y, x) = Корректность этого определения вытекает из заданного в условии теоремы свойства функции f. В самом деле, пусть найдутся две различные цепочки a и b такие, что f (a) = f (b). Тогда можно гарантировать, что f (a x) = f (b x), что и доказывает корректность определения отображения G, ибо G(y, x) действительно не зависит от выбора конкретного прообраза элемента y.

отображения G, то теорема полностью доказана.

В качестве примера использования критерия индуктивности докажем, что функция f : Z Z количество максимальных элементов последовательности целых чисел не является индуктивной. Возьмем a = 1, b = 2, Схема вычисления индуктивной функции, приведенная на странице 113, может быть несколько упрощена при условии наличия у функции так называемых стационарных значений.

Определение 3.1. Значение y Y индуктивной функции f : X Y называется стационарным, если X x X f () = y f ( x) = y.

Так, например, для функции f : {0, 1} {T, F } все элементы цепочки равны нулю значение F является стационарным.

В том случае, если индуктивная функция определена только на X k для k > 0, ее вычисление может начинаться не с пустой, a с одноэлементной или даже более длинной цепочки. Это, однако, приводит к более сложной программе, чего можно иногда избежать, доопределяя исходную функцию.

Индуктивную функцию f : Z Z произведение элементов числовой последовательности можно доопределить с сохранением функции G следующим образом: f () = 1.

Для того чтобы расширить сферу применимости схемы вычисления индуктивной функции вводится понятие индуктивного расширения.

2. Индуктивные расширения.

Определение 3.2. Функция F : X Y называется индуктивным расширением функции f : X Y, если 1) F индуктивна, Рассмотрим функцию f : R R среднее арифметическое элементов последовательности, которая не является индуктивной. Тогда функция F : R R N, определенная по формуле F () = ((s(), n())), где = a1 a2... an, s() = ai, а n = ||, является индуктивным расширением исходной функции f, и (s, n) = s/n.

Для вычисления значения f () не являющейся индуктивной функции f на цепочке применяется следующая обобщенная схема.

Обобщенная схема вычисления индуктивной функции.

Строится индуктивное расширение F исходной функции, которое позволяет ценой увеличения запоминаемой информации о цепочке (в F () информации больше, чем в f ()) применить схему вычисления индуктивной функции к F (), а затем просто найти f () = (F ()).

Пусть F1 : X Y1 и F2 : X Y2 два индуктивных расширения функции f : X Y. Будем говорить, что F1 F2, если : Y1 Y такое, что X F2 () = (F1 ()).

Определение 3.3. Минимальным индуктивным расширением функции f : X Y называется индуктивное расширение F : X Y такое, что 2) для любого индуктивного расширения F функции f выполнено F F.

Минимальные индуктивные расширения хороши тем, что уменьшают количество дополнительной информации, которая должна быть запомнена на каждом шаге для обеспечения возможности перевычисления функции на удлиненной цепочке.

Для любой функции на пространстве последовательностей существует и единственно (в определенном смысле), ее минимальное индуктивное расширение. Доказательство этого факта проведем в два этапа, сначала убедившись в единственности расширения.

Теорема 3.2. Минимальное индуктивное расширение любой функции f : X Y единственно с точностью до изоморфизма.

§3. Индуктивные функции на пространстве последовательностей Доказательство. Пусть для функции f : X Y существуют два минимальных индуктивных расширения F1 : X Y1 и F2 : X Y2.

Тогда в силу их минимальности имеем F1 (X ) = Y1 и F2 (X ) = Y2.

X F2 () = p12 (F1 ()). С другой стороны, F2 F1 и p21 : Y2 Y1 такое, что X F1 () = p21 (F2 ()). Для доказательства теоремы нужно показать, что отображения p12 и p21 биективны. Рассмотрим композиции этих отображений p12 p21 и p21 p12 и докажем, что они являются тождественными отображениями множеств Y2 и Y1 соответственно (из этого и следует биективность отображений p12 и p21 ).

Возьмем произвольный элемент y1 Y1. Из сюръективности F1 следует, что найдется цепочка X, такая что F1 () = y1 и поэтому y1 y1 = F1 () = p21 (F2 ()) = p21 (p12 (F1 ())) = p21 (p12 (y1 )) = (p21 p12 )(y1 ).

Полученное равенство показывает, что p21 p12 = IdY1 тождественное отображение. Рассматривая произвольный элемент y2 Y2, аналогично получаем, что p12 p21 = IdY2, что и завершает доказательство теореe мы.

3. Критерий минимальности. Перед тем, как сформулировать критерий минимальности, докажем существование минимального индуктивного расширения.

Теорема 3.3. Минимальное индуктивное расширение для любой функции f : X Y существует.

Доказательство. Для доказательства теоремы построим в три этапа каноническое минимальное индуктивное расширение F : X Y заданной функции f.

Первый этап. Рассмотрим на множестве цепочек X бинарное отношение, задаваемое формулой a b ( X f (a ) = f (b )), и покажем, что 1) отношение эквивалентности на X ;

Рефлексивность, симметричность и транзитивность отношения вытекают соответственно из рефлексивности, симметричности и транзитивности отношения равенства.

взяв в качестве цепочки, фигурирующей в определении отношения, = x 1, убеждаемся в истинности второго свойства.

Свойство 3) немедленно следует из определения отношения, если в качестве взять пустую цепочку.

Второй этап. Построим пространство Y и отображение F : X Y.

В качестве Y возьмем фактормножество (множество классов эквивалентности) X /, что можно сделать в силу свойства 1). Договоримся обозначать класс эквивалентности, содержащий цепочку через [] и определим отображение F : X Y формулой F () = [].

Переписав свойство 2) в эквивалентном виде a, b X x X F (a) = F (b) F (a x) = F (b x), из критерия индуктивности заключаем, что отображение F индуктивно.

Покажем, что F является индуктивным расширением исходной функции f : X Y. Определим проекцию : Y Y формулой ([]) = f ().

Корректность этого определения следует из свойства 3) если две цепочки 1 и 2 принадлежат одному классу эквивалентности, то значение функции f на них совпадает. Так как f () = (F ()) для произвольной цепочки X, то F действительно является индуктивным расширением отображения f.

Третий этап. Нам осталось показать, что построенное каноническое индуктивное расширение является минимальным.

Сюръективность F следует непосредственно из его построения, ибо каждый класс эквивалентности [] не пуст.

Предположим далее, что существует F : X Y иное индуктивное расширение исходной функции f, тогда для завершения доказательства теоремы нам необходимо показать, что F F.

из прообразов элемента y при отображении F. Проверим корректность данного определения.

Пусть F (1 ) = F (2 ) = y. Тогда в силу индуктивности F для произвольной цепочки справедливо равенство F (1 ) = F (2 ), а так как F индуктивное расширение функции f, то и f (1 ) = f (2 ).

Полученное равенство может быть переписано в виде [1 ] = [2 ], показывающем корректность определения проекции p.

Равенство F () = [] = p(F ()) для произвольной цепочки X показывает, что F F. Теорема полностью доказана.

Построенное в процессе доказательства этой теоремы каноническое индуктивное расширение позволяет убедиться в истинности следующего критерия минимальности.

Теорема 3.4. Критерий минимальности. Индуктивное расширение F : X Y функции f : X Y минимально ((F (X ) = §3. Индуктивные функции на пространстве последовательностей Доказательство. Необходимость первого условия критерия следует непосредственно из определения минимальности. Второе условие выполнено по построению для канонического минимального индуктивного расширения F : X Y, а так как по теореме единственности отображения F и F изоморфны, то и для F.

Для доказательства достаточности рассмотрим каноническое минимальное индуктивное расширение F : X Y и покажем, что оно изоморфно нашему F : X Y. В силу минимальности F существует отображение p : Y Y, такое что F () = p(F ()) для произвольной цепочки X. Критерий будет доказан, если мы покажем, что отображение p биекция.

Сюръективность p вытекает из сюръективности F и F, а инъективность доказывается следующим рассуждением. Рассмотрим различные u и v из Y и, воспользовавшись сюръективностью F, найдем цепочки a и b из X такие, что F (a) = u, а F (b) = v. Так как F (a) = F (b), то в силу данного нам условия a b, что эквивалентно неравенству F (a) = F (b).

Следовательно, отображение p различные u и v преобразует в различные же p(u) = F (a) и p(v) = F (b), что и требовалось доказать.

Докажем, что функция F : R R N, определенная по формуле ляется минимальным индуктивным расширением для f : R R сред- нее арифметическое элементов последовательности. Для доказательства сюръективности функции F предъявим прообраз произвольного элемента (s, n) R N. Им будет цепочка из n элементов, первый из которых равен s, а остальные нулевые. Для того чтобы проверить второе условие критерия минимальности, необходимо убедиться в том, что F (b) = (s2, n2 ) и либо s1 = s2, либо n1 = n2. Если для пустой цепочки = верно, что f (a ) = f (b ), то все доказано. Иначе имеем s1 /n1 = f (a) = f (b) = s2 /n2. Возьмем теперь в качестве одноэлементную цепочку 0. Предположив, что для нее f (a ) = f (b ), из системы s1 /(n1 + 1) = s2 /(n2 + 1) получим s1 = s2, n1 = n2, что противоречит предположению. Это завершает доказательство минимальности F.

Минимальные индуктивные расширения обладают тем достоинством, что позволяют свести к минимуму ту дополнительную информацию, которая необходима для индуктивного перевычисления исходной функции.

Иначе это свойство может быть сформулировано следующим образом.

Теорема 3.5. Для произвольной функции f на пространстве последовательностей существует единственный с точностью до изоморфизма однопроходный алгоритм с минимальной емкостной сложностью.

4. Применение теории индуктивных функций. В качестве первого примера рассмотрим уже встречавшуюся нам ранее задачу.

Задача 3.1. Напишите программу, вводящую последовательность целых чисел, и печатающую количество ее максимальных элементов.

x). Из отрицания критерия индуктивности заключаем, что f не является индуктивной.

Для построения ее индуктивного расширения F применим стандартный прием. Попробуем выразить значение функции f (x) на удлиненной цепочке через ее значение f () на исходной и элемент x. Известно, что это невозможно сделать (f не является индуктивной), но наша цель понять какой именно информации не хватает и, добавив ее, образовать функцию f1. Рассмотрим теперь функцию F1 = (f, f1). В том случае, если она индуктивна, требуемое расширение построено. Иначе повторим предыдущие действия и попытаемся выразить f ( x) и f1 ( x) через f (), f1 () и x с использованием дополнительной информации f2 (). Получаем следующего кандидата на роль индуктивного расширения функцию F2 = (f, f1, f2 ). При необходимости данный процесс может быть продолжен и далее, а его завершение гарантируется теоремой о существовании индуктивного расширения. В данном случае имеем f () = 0, f ( x) = f () + 1, если x = max(), Мы видим, что в качестве f1 следует взять функцию max, вычисляющую максимальное значение элементов цепочки. Тогда для F = (f, f 1 ) получаем F ( x) = (f () + 1, f1 ()) если x = f1 (), §3. Индуктивные функции на пространстве последовательностей Эта функция, однако, не определена на пустой цепочке, поэтому F = (f, f1 ) : (ZM ) Z+ ZM также определена только на (ZM ). ВосM пользовавшись тем, что диапазон представления целых чисел на ЭВМ ограничен, в данном случае можно доопределить F с сохранением функции перевычисления следующим образом: f1 () = Integer.MIN_VALUE (2147483648 для языка Java). Действительно, если принять, что максимальным элементом пустой цепочки является минимально представимое на ЭВМ целое число, то F () = (0, Integer.MIN_VALUE), а функция G : Z+ ZM M Z+ ZM определяется формулой G((y1, y2 ), x) = (y1 + 1, y2 ) если x = y2, Отображение : Z+ ZM Z+ тривиально: (y1, y2 ) = y1.

Докажем, что построенное нами расширение F не является минимальным. Для этого достаточно предъявить значение (y1, y2 ) Z+ ZM, коM торое не принимается ни на одной цепочке. Таковым будет, например, (0, 1). Докажите самостоятельно, что если вместо пространства Z + ZM рассмотреть ((NM ZM ) {0, Integer.MIN_VALUE}), то построенное нами расширение окажется минимальным.

Теперь можно написать программу, реализующую построенный алгоритм.

Текст программы.

public class NumMaxSeq2 { public static void main(String[] args) { int y1 = 0, y2 = Integer.MIN_VALUE;

Любая ошибка при вводе рассматривается здесь, как завершение последовательности чисел. Имена переменных, имеющихся в программе, совпадают с использованными при построении алгоритма, вычисление F () выполняется с помощью команд "int y1=0, y2=Integer.MIN_VALUE;", функция G реализована при помощи оператора if-else, в котором опущен случай x < y2 (так как тогда не нужно изменять ни y1, ни y2 ), а применение отображения сводится к печати только значения y1 из вычисленных y1 и y2.

Следующая задача нам тоже уже знакома.

Задача 3.2. Напишите программу, определяющую номер f первого элемента, равного x0, в последовательности целых чисел. В том случае, если число x0 в последовательности не встречается, положите f равным нулю.

следовательно f не является индуктивной.

Построим ее индуктивное расширение F. Заметим, что f () = 0, Следовательно, в качестве F () можно взять пару (f (), ||), где функция F : (ZM ) Z+ Z+. Эта функция уже индуктивна, так как F () = (0, 0), а преобразование G : Z+ Z+ ZM Z+ Z+ имеет вид G((y1, y2 ), x) = Заметим, что все значения функции f, отличные от нуля, являются стационарными, в то время как функция F не имеет стационарных значений. Ясно, что отображение : Z+ Z+ Z+ имеет вид (y1, y2 ) = y1.

Построенное нами расширение не является минимальным, так как значение (1, 0) не может быть принято функцией F ни на одной цепочке.

Вот программа, не использующая наличия стационарных значений.

Текст программы.

public class First1{ public static void main(String[] args) throws Exception { int x0 = Xterm.inputInt("x0 ->");

§3. Индуктивные функции на пространстве последовательностей Имена программных переменных совпадают с использованными при построении алгоритма, вычисление F () выполняется с помощью команд "int y1=0, y2=0;", реализация функции G очевидна, а применение отображения сводится к печати только значения y1.

Программа, использующая наличие у функции f стационарных значений, может выдавать ответ сразу же, как только одно из таких значений будет достигнуто.

Текст программы.

public class First2 { public static void main(String[] args) throws Exception { int x0 = Xterm.inputInt("x0 -> ");

} catch(Exception e){ Xterm.println("\nn = " + y1);

По достижению конца вводимой последовательности эта программа не выполняет никаких специальных действий (оператор ";" в блоке "catch"). В этой ситуации, как и в случае принятия функцией f любого из стационарных значений (y1 = 0), управление просто передается на оператор печати.

Решим еще одну задачу.

Задача 3.3. Напишите программу, вводящую последовательность вещественных чисел, и печатающую среднее арифметическое ее элементов (для непустой последовательности).

Решение. По условию задачи f : X1 Y, где X = Y = RM. Если x = 6, a = 0, b = 00 (цепочка из двух нулей), то f (a) = f (b) = 0, но f (a x) = 3 = 2 = f (b x), следовательно f не является индуктивной.

Построим ее индуктивное расширение F. Обозначив через S() сумS( x) пару (f (), ||). Для F : (RM ) RM Z+, где F () = (f (), ||), преобразование G : RM Z+ RM RM Z+ задается формулой G((y1, y2 ), x) = Проектируемая программа будет проще, если мы сможем продолжить F на (RM ) с сохранением G. Попробуем подобрать подходящую пару (y1, y2 ) такую, чтобы F () = (y1, y2 ) и x RM F ( x) = F (x) = G((y1, y2 ), x). Так как y2 = 0, то из последнего равенства получаем F (x) = (x, 1) = (x, 1) = G((y1, 0), x), что справедливо при всех y1 R. Следовательно, можно положить, например, F () = (0, 0). Теперь F : (RM ) RM Z+. Отображение : RM Z+ RM тривиально:

(y1, y2 ) = y1, а построенное нами расширение не является минимальным, так как значение (1, 0) функцией F не принимается.

Текст программы.

public class AverSeq{ public static void main(String[] args) { } catch(Exception e) { Рассмотрим задачу несколько другого типа.

§3. Индуктивные функции на пространстве последовательностей Задача 3.4. Напишите программу, определяющую количество вхождений образца abcd в последовательность символов.

Решение. Пусть X множество всех символов, тогда функция но f (1 x) = 1 = 0 = f (2 x), следовательно f не является индуктивной.

Заметив, что f () = 0, будем строить ее индуктивное расширение.

Введем дополнительную функцию f1 () : X {T, F }, которая будет истинна только тогда, когда кончается на abc, и рассмотрим функцию F1 = (f, f1 ).Для нее имеем F1 () = (0, F ), Необходимо ввести еще одну дополнительную функцию f2 () : X {T, F }, которая будет истинна только тогда, когда кончается на ab. Терассмотреть F2 = (f, f1, f2 ). Для нее имеем F2 () = (0, F, F ), перь можно Так как нам опять не удалось выразить F2 ( x) только через F2 () и x, придется рассмотреть еще одну функцию f3 () : X {T, F }, которая будет истинна только тогда, когда кончается на a. Для функции F3 = (f, f1, f2, f3 ), действующей в пространство Z+ ({T, F })3 получаем F3 () = (0, F, F, F ), Полученное равенство показывает, что F3 индуктивное расширение f, однако оно достаточно сложно и заведомо не является минимальным, так как f1, f2 и f3 не являются независимыми. У тройки величин (f1, f2, f3 ) имеется всего четыре допустимых состояния, которые можно представить одним числом:

n() = Сейчас мы докажем, что функция F : X Z+ {0, 1, 2, 3}, опредеM ленная соотношением F () = (f (), n()) является минимальным индуктивным расширением f.

Для доказательства индуктивности достаточно предъявить преобразование G : Z+ {0, 1, 2, 3} X Z+ {0, 1, 2, 3}:

Для доказательства сюръективности функции F предъявим прообраз произвольного элемента (f, n) Z+ {0, 1, 2, 3}. Им может служить, наM пример, цепочка, начинающаяся с f вхождений образца abcd, за которым следует еще n первых символов этого образца. Для того чтобы проверить второе условие критерия минимальности, необходимо убедиться в том, Если f1 = f2, то в качестве можно взять пустую цепочку. В противном случае без ограничения общности можно считать, что n 1 < n2.

Цепочка b заканчивается на n2 первых символа образца abcd, поэтому если в качестве взять 4 n2 последних символа этого образца, то доказательство минимальности F.

Текст программы.

import java.io.*;

public class ABCDSeq { public static void main(String[] args) { DataInputStream in = new DataInputStream(System.in);

§3. Индуктивные функции на пространстве последовательностей } catch(Exception e) { В данной программе используется метод "readByte", который позволяет вводить символы. При этом символ ’\n’ также оказывается введенным после того, как пользователь нажимает клавишу Enter на клавиатуре. Этот символ необходимо игнорировать, что и реализуется в программе оператором "if (x==’\n’) continue".

Не использовавшиеся нами ранее операторы "import java.io.*" и "DataInputStream in = new DataInputStream(System.in)" необходимы для вызова метода "readByte". В остальном программа полностью соответствует проведенному перед ее построением исследованию.

5. Задачи для самостоятельного решения. При решении задач, приведенных ниже, необходимо выяснить, является ли индуктивной заданная функция f. В случае ее индуктивности следует предъявить отображение G, иначе нужно построить индуктивное расширение F исходной функции и предъявить G для него. В последнем случае нужно также указать отображение и исследовать построенное расширение на минимальность (минимальность не является обязательным условием). Завершить решение следует написанием программы, реализующей однопроходный алгоритм, с указанием соответствия между программными переменными и обозначениями, использованными в теоретической части решения. Необходимо объяснить, как в программе реализуется вычисление f или F на пустой (или ее заменяющей) цепочке, как именно реализовано перевычисление функции при удлинении цепочки и как находится (F ()) в случае использования индуктивного расширения.

Задача 3.5. Напишите программу, определяющую количество минимальных элементов в последовательности неположительных целых чисел.

Указание. В данном случае для доопределения индуктивного расширения на пустой цепочке нет необходимости использовать величины Integer.MIN_VALUE или Integer.MAX_VALUE.

Задача 3.6. Напишите программу, определяющую значение в целой точке t многочлена, заданного последовательностью его целых коэффициентов (в порядке возрастания степеней).

Задача 3.7. Напишите программу, определяющую значение в целой точке t производной многочлена, заданного последовательностью его целых коэффициентов (в порядке убывания степеней).