авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 7 |

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

-- [ Страница 4 ] --

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

int a = 0;

while ( n = (a+1)*(a+1) ) a += 1;

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

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

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

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

0 a 1) (Q wp(S0, I)) = (n 0 wp("a=0;

", a n)) = (n 0 (0 0 0 n)) = (n 0 n 0) = T.

0 a2 n) = (a 1 (a + 1) 2) wp(S, I) = wp("a+=1;

", a n), поэтому (I e wp(S, I)) = (!I!e (a 1 (a + 1) n)).

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

3) (I!e R) = (!I e R) = (a 0 a2 n (a + 1)2 n (a 2 2 2 n) (!(a 0 a 0a n (a + 1) n)) = ((a 0 a n (a + 1) n (a + 1)2 n)) = T.

4) (I e h 0) = (!I!eh 0) = (!I (a+1)2 nn(a+1)2 + 0) = (!I (a + 1)2 n (a + 1)2 n) = (!I ((a + 1)2 n!((a + 1) n))) = (!I T ) = T.

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 + h1) = (n (a + 2)2 + 1 n (a + 1)2 + 1) = ((a + 1)2 (a + 2)2 ) = T, в предположении, что истинны 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. Проектирование цикла при помощи инварианта Решение. Выпишем формально заданные нам пред- и постусловия:

Q = (0 m x b[0..m 1]), R = ((0 i m) (j 0 jix= b[j]) (x = b[i])).

Так как добиться истинности третьего конъюнктивного члена одним или несколькими простыми присваиваниями трудно, устраним именно его. Тогда получим I = ((0 i m) (j 0 j i x = b[j])). В качестве условия продолжения цикла можно взять отрицание удаленного члена (e = (x = b[i])), а инвариант легко сделать истинным, выполняя команду "i=0;

", поэтому программа должна иметь вид "i=0;

while(x!=b[i])S;

" с неизвестным нам пока S.

В качестве ограничивающей функции можно попробовать взять h = m i, a для того, чтобы она уменьшалась, достаточно увеличивать i на каждой итерации цикла. Понятно, что увеличивая i более, чем на еди ницу, можно пропустить первое вхождение x в массив, поэтому одной из команд, входящих в S, должна быть команда "i=i+1;

". Так как выполне ние данной команды при условии истинности e сохраняет инвариант, то эта команда является единственной в теле цикла. Программа построена.

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

public class SearchL { static int b[], x;

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

b = new int[m];

for (int k=0;

km;

k++) b[k] = Xterm.inputInt("b["+k+"] - ");

x = Xterm.inputInt("x - ");

int i=0;

while (x != b[i]) i += 1;

Xterm.println("i = " + i);

} } Докажем правильность этой программы.

1) wp(S0, I) = wp("i=0;

", (0 i m) (j 0 j i x = b[j])) = ( m), что следует из Q.

2) wp(S, I) = wp("i+=1;

", (0 i m) (j 0 j i x = b[j])) = ( i + 1 m) (j 0 j i + 1 x = b[j]), поэтому (I e wp(S, I)) = (((( i m) (j 0 j i x = b[j])) (x = b[i])) ((0 i + 1 m) (j j i + 1 x = b[j]))). Данная импликация является тавтологией, ибо если в подмассиве b[0..i] элемент x не встретился, то из условия задачи следует, что элемент с индексом i + 1 в массиве b заведомо имеется (т.е., i + 1 m).

126 Глава II. Построение программ 3) (I!e R) = (!(I!e) R) = (!(I!e) (I!e)) = T.

4) (I e h 0) = (!I!eh 0) = ((x = b[i])(i 0i m!(j j i x = b[j]) m i)) = ((x = b[i] i 0!(j 0 j i x = b[j]))) (i m i m) = ((x = b[i] i 0!(j 0 j i x = b[j]))) T = T.

5) wp("h1=h;

S;

", h h1) = wp("h1=m-i;

", wp("i+=1;

", mi h1)) = wp("h1=m-i;

", m i 1 h1) = (m i 1 m i) = T.

Следовательно, (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 b[j].

R= s= j= Решение. В постусловие входит константа n, которую мы можем за менить новой переменной i, меняющейся в диапазоне от 0 до n включи тельно. Таким образом, метод замены константы переменной приводит i нас к инварианту I =. Понятно, что в каче 0 s= n i b[j] j= стве ограничивающей функции следует взять h = n i.

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

s=0;

while(in)S;

" с неизвестным нам пока телом цикла S.

Для того, чтобы цикл завершился, необходимо уменьшать h, что вполне естественно делать, увеличивая i на единицу на каждой итерации цикла. Используя инвариант, находим, что вторым необходимым действи ем является добавление к s значения b[i]:

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

public class SumArr { static int b[];

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

b = new int[n];

for (int k=0;

kn;

k++) b[k] = Xterm.inputInt("b["+k+"] - ");

int i=0, s=0;

§2. Проектирование цикла при помощи инварианта while (i n) { s += b[i];

i += 1;

} Xterm.println("s = " + s);

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

i 1) Так как wp("i=0;

s=0;

", 0 s= = ( i n b[j] n j= n), то (Q wp(S0, I)) = (n n) = T.

T ) = (0 i 2) wp(S, I) = wp "s+=b[i];

i+=1;

", 0 s= = i n b[j] j= i wp "s+=b[i];

", 0 i+1 s= =0 i+ n b[j] n j= i i.

s + b[i] = = n1 s= b[j] i b[j] j=0 j= Теперь вычислим (I e = (i 0) (i wp(S, I)) i1 i.

n)! s = (i n1 s= b[j] n) i b[j] j=0 j= Данный предикат заведомо истинен, если истинен один из первых че тырех его дизъюнктивных членов. В противном случае имеем 0 i n и I = T, поэтому истинен пятый его дизъюнктивный член, следовательно предикат является тавтологией.

i1 n 3) (I!e) = 0 s= (i n) = s= i n b[j] b[j] j=0 j= (i = n) = (R (i = n)).

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

4) (I e h 0) = (!I!eh 0) = (!I (i nn i)) = (!I T ) = T.

5) wp("h1=h;

S;

", h h1) = wp("h1=n-i;

", wp("s+=b[i];

i+=1;

", n i h1)) = wp("h1=n-i;

", n i 1 h1) = (n i 1 n i) = T.

Следовательно, (I e wp("h1=h;

S;

", h h1)) = (I e T ) = (!I!e T ) = T.

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

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

а Q = (n ZM n 0), R = (a ZM a 0 a2 n (a + 1)2 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 { int a, b, n;

n = Xterm.inputInt("n - ");

a = 0;

b = n+1;

while (a+1 != b) { int c = (a+b)/2;

if (c*c = n) a = c;

else b = c;

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

} } Докажите самостоятельно ее правильность и оцените эффективность.

§2. Проектирование цикла при помощи инварианта 5. Расширение области значения переменной. Данный метод в зна чительной мере подобен разобранному в предыдущей секции если необ ходимая переменная уже содержится в постусловии, то ее можно исполь зовать для построения инварианта, просто разрешив ей меняться в более широких пределах.

В качестве примера разберем классическую задачу Жулик на посо бии. В оригинальном варианте рассматриваются три потенциально бес конечных упорядоченных по алфавиту списка фамилий сотрудники исследовательского центра IBM, студенты Колумбийского университета и безработные Нью-Йорка. Требуется найти первую из фамилий, встре чающуюся во всех трех списках (в предположении, что она есть).

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

Решение. Пусть имеющиеся массивы это a, b и c. Переменные, содержащие значения индексов для каждого из этих массивов, обозначим через i, j и k соответственно, а индексы искомого числа в каждом из них iv, jv и kv.

Если не включать в предусловие информацию о том, что массивы яв ляются упорядоченными (не забывая об этом, конечно), то пред- и посту словия искомой программы буду иметь вид Q = T, и R = ((i = iv) (j = jv) (k = kv)).

Расширение области значений переменных i, j и k естественный способ построения инварианта в данном случае: I = ((0 i iv) ( j jv)(0 k kv)). В качестве ограничивающей функции можно взять h = ivi+jvj +kvk, выбор начальных присваиваний S0 проблем тоже не вызывает ясно, что операторы "i=0;

j=0;

k=0;

" сделают инвариант истинным.

В качестве действий, которые будут приближать цикл к завершению можно использовать операторы "i++;

", "j++;

" и "k++;

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

Вычислим wp("i++;

", I) = (i + 1 iv). Это означает, что увеличение индекса i в цикле нужно делать, когда i + 1 iv. К сожалению, записать подобное условие в программе невозможно, так как переменной iv в ней просто может не быть!

Легко заметить, однако, что выполнение условия i + 1 iv при ис тинном инварианте I означает, что число a[i] меньше искомого в за даче, а это может быть только при условии истинности дизъюнкции 130 Глава II. Построение программ a[i] b[j] a[i] c[k]. Аналогично заключаем, что если истинна дизъ юнкция b[j] a[i] b[j] c[k], то можно увеличивать значение индекса j, а при истинности предиката c[k] a[i] c[k] b[j] индекса k.

Это уже позволяет написать программу, но если внимательно исследо вать доказательство ее правильности, то можно обнаружить возможность для ее упрощения, что и реализовано ниже.

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

public class Arr3 { public static void main(String[] args){ int a[] = { 1, 2, 4, 8,16,32,64,128};

int b[] = {10,12,14,16,18,20,22, 24};

int c[] = { 9,12,13,16,17,20,21, 24};

int i = 0, j = 0, k = 0;

while (true) { if (a[i] b[j]) { i++;

continue;

} if (b[j] c[k]) { j++;

continue;

} if (c[k] a[i]) { k++;

continue;

} Xterm.println("Минимальное общее число=" + a[i]);

return;

} } } Обязательно проверьте все пять условий правильности этой итоговой программы.

6. Задачи для самостоятельного решения. При решении задач необ ходимо построить и доказать правильность построенной программы вида "S0;

while(e)S;

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

Задача 2.6. Напишите программу, печатающую n-ое число Фибонач чи (f0 = 0, f1 = 1, fk = fk1 + fk2 для k 1). При написании программы используйте Q = (n ZM n 0), R = (a = fn ), I = (1 i na = fi b = fi1 ), h = n i. Число n в программе изменять нельзя.

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

Величины 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. Вот более точная формулировка пред- и постусловия:

0 a2 n (a + 1)2 n).

(Q = n ZM n 0), R = (a ZM a При написании программы величину 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, в которую может 132 Глава II. Построение программ быть вставлено это число без нарушения упорядоченности массива. Точ ные пред- и постусловия требуемой программы, времення сложность ко а торой не должна превосходить (log n), таковы: Q = (x ZM n ZM n 0 (j 0 j n 1 : b[j] b[j + 1])), R = ((i = 1 x b[0]) (0 i n 1 b[i] x b[i + 1]) (i = n b[n 1] x)).

При написании программы величины x, n и элементы массива b изменять не разрешается, для построения инварианта используйте метод замены константы переменной.

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

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

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

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

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

Функция f : X Y называется индуктивной, если f ( x) можно вычислить, зная f () и x, т.е. если G : Y X Y такое, что X x X f ( x) = G(f (), x).

Доказательство индуктивности функции обычно проводят конструк тивно, предъявляя требуемую функцию 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 и b x.

Доказательство. Необходимость сформулированного в критерии условия немедленно следует из определения индуктивности. Если f ин дуктивна, то a, b X x Xf (a x) = G(f (a), x) = G(f (b), x) = f (b x).

Для доказательства достаточности построим требуемое отображение G : Y X Y такое, что X x X f ( x) = G(f (), x). Зададим это отображение формулой f ( x), если существует X такая, что f () = y, G(y, x) = иначе.

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

Так как X x X f ( x) = G(f (), x) для построенного отображения G, то теорема полностью доказана.

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

Схема вычисления индуктивной функции, приведенная на страни це 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.

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

134 Глава II. Построение программ 2. Индуктивные расширения.

Определение 3.2. Функция F : X Y называется индуктивным расширением функции f : X Y, если 1) F индуктивна, 2) : Y Y такое, что X f () = (F ()).

Рассмотрим функцию f : R R среднее арифметическое элементов последовательности, которая не является индуктивной. Тогда функция F : R R N, определенная по формуле F () = ((s(), n())), где = n a1 a2... an, s() = ai, а n = ||, является индуктивным расширением i= исходной функции 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 такое, что 1) F (X ) = Y сюръективно);

(F 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.

Так как F1 F2 (ибо F2 минимально), то p12 : Y1 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 тождественное e отображение. Рассматривая произвольный элемент 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 ;

2) a, b X x X a b a x b x;

3) a, b X a b f (a) = f (b).

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

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

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

136 Глава II. Построение программ Второй этап. Построим пространство 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.

Определим проекцию p : Y Y формулой p(y) = [], где один из прообразов элемента 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 ) = Y ) (a, b X F (a) = F (b) a b)).

§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, определенная по формуле n F () = ai, n, где = a1 a2... an, n = || и (s, n) = s/n, яв i= ляется минимальным индуктивным расширением для f : R R сред- нее арифметическое элементов последовательности. Для доказатель ства сюръективности функции F предъявим прообраз произвольного эле мента (s, n) R N. Им будет цепочка из n элементов, первый из ко торых равен s, а остальные нулевые. Для того чтобы проверить вто рое условие критерия минимальности, необходимо убедиться в том, что a, b X F (a) = F (b) X f (a ) = f (b ). Пусть F (a) = (s1, n1 ), 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 = s2 /n2, s1 /(n1 + 1) = s2 /(n2 + 1) получим s1 = s2, n1 = n2, что противоречит предположению. Это завер шает доказательство минимальности F.

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

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

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

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

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

Решение. В данной задаче X = ZM, Y = Z+, f : X Y. Взяв M a = 1, b = 2, x = 2, находим f (a) = f (b) = 1, но f (a x) = 1 = 2 = f (b 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, если x max(), f (), f ( x) = f () + 1, если x = max(), если x max().

1, Мы видим, что в качестве f1 следует взять функцию max, вычисля ющую максимальное значение элементов цепочки. Тогда для F = (f, f 1 ) получаем если x f1 (), (f (), f1()) F ( x) = (f () + 1, f1 ()) если x = f1 (), если x f1 ().

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

(1, x) Отображение : Z+ ZM Z+ тривиально: (y1, y2 ) = y1.

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

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

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

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

try { while (true) { int x = Xterm.inputInt("x - ");

if (x == y2) { y1 += 1;

} else if(x y2) { y1 = 1;

y2 = x;

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

} } } 140 Глава II. Построение программ Любая ошибка при вводе рассматривается здесь, как завер шение последовательности чисел. Имена переменных, имеющих ся в программе, совпадают с использованными при построении алгоритма, вычисление 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 : X Y, где X = ZM, а Y = Z+. Если x0 = 0, M a =, b = 1, то f (a) = f (b) = 0, но f (a x0 ) = 1 = 2 = f (b x0 ), следовательно f не является индуктивной.

Построим ее индуктивное расширение F. Заметим, что f () = 0, если f () = 0 x = x0, f (), f ( x) = || + 1, если f () = 0 x = x0.

Следовательно, в качестве F () можно взять пару (f (), ||), где функция F : (ZM ) Z+ Z+. Эта функция уже индуктивна, так как M M F () = (0, 0), а преобразование G : Z+ Z+ ZM Z+ Z+ имеет вид M M M M если y1 = 0 x = x0, (y1, y2 + 1), G((y1, y2 ), x) = (y2 + 1, y2 + 1), если y1 = 0 x = x0.

Заметим, что все значения функции f, отличные от нуля, являются стационарными, в то время как функция F не имеет стационарных зна чений. Ясно, что отображение : Z+ Z+ Z+ имеет вид (y1, y2 ) = y1.

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

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

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

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

int y1 = 0, y2 = 0;

try { while (true) { int x = Xterm.inputInt("x - ");

y2 += 1;

§3. Индуктивные функции на пространстве последовательностей if ( (y1 == 0) && (x == x0) ) y1 = y2;

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

} } } Имена программных переменных совпадают с использованными при построении алгоритма, вычисление 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 - ");

int y1 = 0, y2 = 0;

try { while (y1 == 0) { int x = Xterm.inputInt("x - ");

y2 += 1;

if (x == x0) y1 = y2;

} } catch(Exception e){ System.exit(0);

} Xterm.println("\nn = " + y1);

} } По достижению конца вводимой последовательности эта програм ма не выполняет никаких специальных действий (оператор ";

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

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

142 Глава II. Построение программ Задача 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 ( x) = = | x| S() + x f ()|| + x. Следовательно, в качестве F () можно взять = || + 1 || + пару (f (), ||). Для F : (RM ) RM Z+, где F () = (f (), ||), 1 M преобразование G : RM Z+ RM RM Z+ задается формулой M M y1 y2 + x, y2 + 1.

G((y1, y2 ), x) = y2 + Проектируемая программа будет проще, если мы сможем продол жить 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 тривиально:

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

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

public class AverSeq{ public static void main(String[] args) { double y1 = 0., y2 = 0.;

try { while (true) { double x = Xterm.inputDouble("x - ");

y1 = (y1*y2 + x) / (y2 + 1.);

y2 += 1;

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

} } } Рассмотрим задачу несколько другого типа.

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

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

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

f () + 1, если x = d и кончается на abc, f ( x) = f (), иначе.

Введем дополнительную функцию f1 () : X {T, F }, которая будет истинна только тогда, когда кончается на abc, и рассмотрим функцию F1 = (f, f1 ).Для нее имеем F1 () = (0, F ), (f () + 1, F ), если x = d и f1 () = T, F1 ( x) = (f (), T ), если x = c и кончается на ab, (f (), F ), иначе.

Необходимо ввести еще одну дополнительную функцию f2 () : X {T, F }, которая будет истинна только тогда, когда кончается на ab. Те рассмотреть F2 = (f, f1, f2 ). Для нее имеем F2 () = (0, F, F ), перь можно (f () + 1, F, F ), если x = d и f1 () = T, (f (), T, F ), если x = c и f2 () = T, F2 ( x) = (f (), F, T ), если x = b и кончается на a, (f (), F, F ), иначе.

Так как нам опять не удалось выразить F2 ( x) только через F2 () и x, придется рассмотреть еще одну функцию f3 () : X {T, F }, кото рая будет истинна только тогда, когда кончается на a. Для функции F3 = (f, f1, f2, f3 ), действующей в пространство Z+ ({T, F })3 получаем M F3 () = (0, F, F, F ), (f () + 1, F, F, F ), если x = d и f1 () = T, (f (), T, F, F ), если x = c и f2 () = T, F3 ( x) = (f (), F, T, F ), если x = b и f3 () = T, (f (), F, F, T ), если x = a, (f (), F, F, F ), иначе.

Полученное равенство показывает, что F3 индуктивное расширение f, однако оно достаточно сложно и заведомо не является минимальным, так как f1, f2 и f3 не являются независимыми. У тройки величин (f1, f2, f3 ) имеется всего четыре допустимых состояния, которые можно представить 144 Глава II. Построение программ одним числом:

3, если кончается на abc, 2, если кончается на ab, n() = 1, если кончается на a, 0, иначе.

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

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

M M (f + 1, 0), если x = d и n = 3, (f, 3), если x = c и n = 2, G((f, n), x) = (f, 2), если x = b и n = 1, (f, 1), если x = a, (f, 0), иначе.

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

Пусть F (a) = (f1, n1 ), F (b) = (f2, n2 ) и либо f1 = f2, либо n1 = n2.

Если f1 = f2, то в качестве можно взять пустую цепочку. В про тивном случае без ограничения общности можно считать, что n 1 n2.

Цепочка b заканчивается на n2 первых символа образца abcd, поэтому если в качестве взять 4 n2 последних символа этого образца, то f (a ) = f (a) = f1 f2 + 1 = f (b) + 1 = f (b ), что и завершает доказательство минимальности F.

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

import java.io.*;

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

int f = 0, n = 0;

try { while (true) { char x = (char)in.readByte();

if (x==’\n’) continue;

if (x==’d’ && n==3) { §3. Индуктивные функции на пространстве последовательностей f += 1;

n = 0;

} else if (x==’c’ && n==2) { n = 3;

} else if (x==’b’ && n==1) { n = 2;

} else if (x==’a’) { n = 1;

} else{ n = 0;

} } } catch(Exception e) { Xterm.println("f = " + f);

} } } В данной программе используется метод "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 ()) в случае использования индуктивного расширения.

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

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

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

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

Указание. Продифференцировав по x равенство Pn (x) = x·Pn1 (x)+ an и подставив затем x = t, получите соотношения P0 (t) = 0 и Pn (t) = t · Pn1 (t) + Pn1 (t), которые помогут построить индуктивное расширение исходной функции.

Задача 3.8. Напишите программу, определяющую правильность формулы над алфавитом из четырех символов X = {(, ), t, +}. Формула считается правильной, если она может быть получена с помощью следу ющей НФБН: e t | (e + e).

Указание. Рассмотрите следующее индуктивное расширение F = (f1, f2, f3 ) функции f, где f1 : X {T, F }, f2 : X ZM, f3 : X X, определены следующим образом:

f1 () = может быть продолжена до правильной формулы, f2 () = разность числа левых и правых скобок в, f3 () = последний элемент.

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

§ 4. Все задачи главы Полным решением задач, приведенных ниже, не может считаться только текст правильно написанной программы. Во всех случаях необ ходимо изложение теоретической части решения и описание соответствия между переменными программы и обозначениями, использованными при теоретическом исследовании.

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

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

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

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

Задача 4.3. Напишите рекурсивную программу, печатающую значе ние производной многочлена степени 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 )) для вычисления которой и пишется программа.

2. Проектирование цикла при помощи инвариантa. При решении задач из этого раздела необходимо построить и доказать правильность построенной программы вида "S0;

while(e)S;

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

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

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

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

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

Q = (n ZM n 0), R = (a ZM a 0 a2 n (a + 1)2 n). При написании программы величину n изменять нельзя.

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

Задача 4.8. Напишите программу, находящую сумму s элементов заданного целочисленного массива b[0..n 1], элементы которого и ве личину n изменять нельзя. Точные пред- и постусловия: Q = (n 0), n b[j].

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

а Q = (n ZM n 0), R = (a ZM a 0 a2 n (a + 1)2 n). При написании программы величину n изменять нельзя.

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

Задача 4.11. Напишите программу, печатающую n-ое число Фибо наччи (f0 = 0, f1 = 1, fk = fk1 + fk2 для k 1). При написании программы используйте Q = (n ZM n 0), R = (a = fn ), n a = fi b = fi1 ), h = n i. Число n в программе I = (1 i изменять нельзя.

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

Величины x и y в программе изменять не разрешается.

Задача 4.13. Напишите программу, находящую наибольший общий делитель 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.

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

0 a2 n (a + 1)2 n).

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

Задача 4.15. Напишите программу, определяющую первое вхождение заданного целого числа 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.

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

При написании программы величины x, n и элементы массива b изменять не разрешается, для построения инварианта используйте метод замены константы переменной.

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

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

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

Задача 4.19. Напишите программу, находящую сумму s элементов заданного целочисленного массива b[0..n 1], элементы которого и ве личину n изменять нельзя. Точные пред- и постусловия: Q = (n 0), n R= s= b[j]. Инвариант постройте методом замены константы 0 в j= постусловии R новой переменной i.

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

а Q = (n ZM n 0), R = (a ZM a 0 a2 n (a + 1)2 n). При написании программы величину n изменять нельзя, а инвариант следует построить методом замены константы a на переменную b в конъюнктив ном члене a2 n постусловия R.

Задача 4.21. Напишите программу, находящую наименьшее значение x ZM в заданном массиве целых чисел b[0..n 1], где n 0. Значения элементов массива b и число n в программе изменять нельзя, Q = (n ZM n 0), R = ((j 0 b[j]) (k 0 k n x = b[k])), jnx инвариант постройте методом замены константы n на переменную i.

1 самой Задача 4.22. Напишите программу, находящую длину p длинной площадки в упорядоченном по неубыванию массиве b[0..n 1] целых чисел. Площадкой мы называем последовательность нескольких равных значений. Значения элементов массива b и число n 0 в програм ме изменять нельзя, Q = (n ZM n 0(j 0 j n1 b[j] b[j +1])), §4. Все задачи главы R = (((k 0 k n p b[k] = b[k + p 1]) (j 0 j n p + 1 b[j] = b[j + p]))), инвариант постройте методом замены константы n на перемен ную i.

Задача 4.23. Напишите программу, находящую число m 1 пло щадок в упорядоченном по неубыванию массиве b[0..n 1] целых чисел.

Площадкой мы называем последовательность нескольких равных значе ний. Значения элементов массива b и число n 0 в программе изменять нельзя.

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

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

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

while(e)S;

S1;

".

Задача 4.25. Напишите программу, находящую наибольший общий делитель 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.

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

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

gcd(x%y, y), если x y, gcd(x, y) = gcd(x, y%x), иначе.

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

Задача 4.28. Напишите программу, возводящую целое число в це лую неотрицательную степень. Точные пред- и постусловия требуемой программы таковы: 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).

Задача 4.29. Напишите программу, находящую наибольший общий делитель 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 :

(x/2, y/2, 2z), если оба числа x и y четны, если x четно, а y нечетно, (x/2, y, z), T (x, y, z) = (x, y/2, z), если x нeчетно, а y четно, если x и y нечетны и x y, (x y, y, z), если x и y нечетны и x y.

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

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

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

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

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

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


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

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

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

Задача 4.36. Напишите программу, определяющую дисперсию не пу стой последовательности действительных чисел. Дисперсией d последо n (xi m)2, где m = вательности x1, x2,..., xn называется величина n i= среднее арифметическое элементов последова (x1 + x2 +... + xn )/n тельности. n n 1 (x2 2mxi + Указание. Так как d = (xi m) = n i=1 i n i= n n n n n 1 x2 x m)= m xi m (xi m) = m xi = i i n n i=1 i=1 i=1 i=1 i= 154 Глава II. Построение программ n n n n 1 x2 2, то вводя обозначения s0 = xi, xi 1 = n, s1 = i n n i=1 i=1 i=1 i= n x2, получим d = s2 /s0 (s1 /s0 )2. Легко проверить, что функция s2 = i i= F = (s2, s1, s0 ) является индуктивной.

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

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

Указание. Продифференцировав по x равенство Pn (x) = x·Pn1 (x)+ an и подставив затем x = t, получите соотношения P0 (t) = 0 и Pn (t) = t · Pn1 (t) + Pn1 (t), которые помогут построить индуктивное расширение исходной функции.

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

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

Задача 4.41. Напишите программу, определяющую правильность формулы над алфавитом из четырех символов X = {(, ), t, +}. Формула считается правильной, если она может быть получена с помощью следу ющей НФБН: e t | (e + e).

Указание. Рассмотрите следующее индуктивное расширение F = (f1, f2, f3 ) функции f, где f1 : X {T, F }, f2 : X ZM, f3 : X X, определены следующим образом:

f1 () = может быть продолжена до правильной формулы, f2 () = разность числа левых и правых скобок в, f3 () = последний элемент.

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

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

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

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

Указание. Рассмотрите эту функцию f, как функцию на простран стве последовательностей над алфавитом {0, 1}. В качестве последова тельности нужно взять инвертированное представление числа b в дво ичной системе счисления. Данная последовательность получается есте ственным образом последняя цифра числа b есть "b&1", предпоследняя получается по той же формуле после сдвига вправо ("b=1;

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

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

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

Глава III Применение ООП к разработке программных проектов Несмотря на то, что язык Java является объектно-ориентированным, до сих пор при разработке программ мы по существу пользовались па радигмой директивного программирования целью было создание кода, воздействующего должным образом на данные. Этот подход хорош при решении небольших задач, но порождает множество трудноразрешимых проблем при попытке создания больших программных систем.

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

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

§ 1. Основы объектно-ориентированного программирования В этом параграфе мы продолжим знакомство с базисными концепция ми объектно-ориентированного программирования, начатое еще в первой главе книги. Сначала будут обсуждены общие для различных языков про граммирования понятия ООП, а затем их реализация в языке Java.

Следует знать, что курс объектно-ориентированного программирова ния читается студентам-старшекурсникам в течение целого семестра, и поэтому материал, изложенный ниже, представляет собой лишь самое на чальное введение в мир ООП. Значительно более полное изложение мно гих вопросов, связанных с объектно-ориентированными дизайном, про ектированием и программированием, содержится в книге [2], а в тре тьей главе книги [13] можно найти очень ясное описание всех объектно ориентированных аспектов языка Java.

158 Глава III. Применение ООП к разработке программных проектов 1. Основные концепции ООП. Объектно-ориентированное програм мирование или ООП (object-oriented programming) методология про граммирования, основанная на представлении программы в виде совокуп ности объектов, каждый из которых является реализацией определенного типа, использующая механизм пересылки сообщений и классы, организо ванные в иерархию наследования.

Центральный элемент ООП абстракция. Данные с помощью аб стракции преобразуются в объекты, а последовательность обработки этих данных превращается в набор сообщений, передаваемых между этими объектами. Каждый из объектов имеет свое собственное уникальное пове дение. С объектами можно обращаться как с конкретными сущностями, которые реагируют на сообщения, приказывающие им выполнить какие то действия.

ООП характеризуется следующими принципами (по Алану Кею):

• все является объектом;

• вычисления осуществляются путем взаимодействия (обмена дан ными) между объектами, при котором один объект требует, чтобы другой объект выполнил некоторое действие;

объекты взаимодей ствуют, посылая и получая сообщения;

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

• каждый объект имеет независимую память, которая состоит из других объектов;

• каждый объект является представителем класса, который выра жает общие свойства объектов данного типа;

• в классе задается функциональность (поведение объекта);

тем са мым все объекты, которые являются экземплярами одного клас са, могут выполнять одни и те же действия;

• классы организованы в единую древовидную структуру с общим корнем, называемую иерархией наследования;

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

Определение 1.1. Абстрагирование (abstraction) метод решения задачи, при котором объекты разного рода объединяются общим поня тием (концепцией), а затем сгруппированные сущности рассматриваются как элементы единой категории.

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

§1. Основы объектно-ориентированного программирования Определение 1.2. Инкапсуляция (encapsulation) техника, при ко торой несущественная с точки зрения интерфейса объекта информация прячется внутри него.

Определение 1.3. Наследование (inheritance) свойство объектов, посредством которого экземпляры класса получают доступ к данным и методам классов-предков без их повторного определения.

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

Определение 1.4. Полиморфизм (polymorphism) свойство, позво ляющее использовать один и тот же интерфейс для различных действий;

полиморфной переменной, например, может соответствовать несколько различных методов.

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

Определение 1.5. Класс (class) множество объектов, связанных общностью структуры и поведения;

абстрактное описание данных и по ведения (методов) для совокупности похожих объектов, представители которой называются экземплярами класса.

Определение 1.6. Объект (object) конкретная реализация класса, обладающая характеристиками состояния, поведения и индивидуально сти, синоним экземпляра.

Как это уже отмечалось в самом начале курса, Java лишь один из объектно-ориентированных языков. Другим активно используемым про фессиональными программистами языком ООП, с который мы познако мимся в следующем семестре, является C++. В дальнейшем нам предсто ит знакомство с такими представителями этого семейства, как Smalltalk, Delphi Pascal и CLOS.

Следует иметь в виду, что в разных объектно-ориентированных язы ках для обозначения одних и тех же концепций ООП используются слегка отличающиеся друг от друга термины (см. стр. 186).

2. Классы и объекты в языке Java. Для знакомства с базовым для объекно-ориентированного программирования понятием класса, рассмот рим класс R2Point, задающий точку на плоскости.

Пример программы.

160 Глава III. Применение ООП к разработке программных проектов //Класс, описывающий точку (Point) на плоскости (R2).

class R2Point { // Переменные экземпляра, задающие координаты точки.

private double x, y;

// Конструктор с параметрами.

public R2Point(double x, double y) { this.x = x;

this.y = y;

} // Метод экземпляра - расстояние до начала координат.

public double dist0() { return Math.sqrt(x*x + y*y);

} } Для того, чтобы создать экземпляр этого класса, в программе следует предварительно объявить переменную типа R2Point, а затем воспользо ваться оператором new. Объявление переменной можно совмещать с со зданием нового объекта, что демонстрируется в следующей программе, находящей расстояние от точки до начала координат.

R2Point p = new R2Point(1.,2.);

double d = p.dist0();

Этот пример объясняет, почему такой стиль записи называют объектно-ориентированным: при вызове метода в центре внимания нахо дится объект p, а не метод dist0. Этот метод не нуждается в аргументе объект, над которым производится данное действие, уже указан в дан ной конструкции. Именно по этой причине внутри метода dist0 можно работать с величинами x и y, принадлежащими конкретному экземпля ру объекта. Имена x и y в теле метода dist0 являются сокращениями от this.x и this.y соответственно, где ключевое слово this является указателем на тот экземпляр класса, с которым должен работать метод.

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

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

Поэтому конструктор объекта типа R2Point, который вызывается с помо щью метода new, должен записать в переменные конкретного экземпляра §1. Основы объектно-ориентированного программирования его координаты. В том случае, если в качестве имен аргументов конструк тора выбраны x и y (а это вполне естественный выбор), для обеспечения доступа к переменным экземпляра необходимо использование ключевого слова this. В объявлении конструктора не разрешается указывать воз вращаемый тип (хотя неявно всегда возвращается объект this), а в его теле нельзя использовать оператор return.

Если в некоторой задаче необходимо создавать новые объекты типа R2Point, вводя их координаты с клавиатуры, то может возникнуть жела ние реализовать это непосредственно в конструкторе.

Пример программы.

//Класс, описывающий точку (Point) на плоскости (R2).

class R2Point{ // Переменные экземпляра, задающие координаты точки.

private double x, y;

// Конструктор с параметрами.

public R2Point(double x, double y) { this.x = x;

this.y = y;

} // Еще один конструктор, позволяющий вводить // координаты вновь создаваемой точки с клавиатуры.

public R2Point() throws Exception { x = Xterm.inputDouble("x - ");

y = Xterm.inputDouble("y - ");

} // Метод класса - расстояние до начала координат.

public static double dist0(R2Point a) { return Math.sqrt(a.x*a.x + a.y*a.y);

} // Метод экземпляра - расстояние до начала координат.

public double dist0() { return Math.sqrt(x*x + y*y);

} } Такой класс выглядит на первый взгляд весьма странно в нем раз ные методы имеют одинаковые имена. Компилятор, однако, может раз личить их. Признак, по которому это происходит количество и типы аргументов у различных методов. Так, если оператор new для объекта R2Point имеет два аргумента, то вызывается первый из конструкторов, а если аргументов нет второй.

Вторым интересным моментом в этом примере является иллюстрация использования метода класса. Первый из двух методов dist0 описан с 162 Глава III. Применение ООП к разработке программных проектов ключевым словом static, что и делает его методом класса. Такой ме тод не может быть вызван от конкретного объекта с помощью оператора точка, ему не передается указатель this на экземпляр, а само это клю чевое слово не может быть использовано в его теле. Приведенная ниже программа находит расстояние от точки p до начала координат двумя различными эквивалентными методами.

R2Point p = new R2Point(1.,2.);

double d1 = p.dist0();

double d2 = R2Point.dist0(p);

Могут существовать и переменные класса это такие переменные, ко торые всегда имеются ровно в одном экземпляре, независимо от того как много имеется объектов данного класса. Для их описания также приме няется ключевое слово static.

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

Пример программы.

//Класс, описывающий точку (Point) на плоскости (R2).

class R2Point { private double x, y;

public R2Point(double x, double y) { this.x = x;

this.y = y;

} public R2Point() throws Exception { x = Xterm.inputDouble("x - ");

y = Xterm.inputDouble("y - ");

} public static double dist(R2Point a, R2Point b) { return Math.sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

} public static double area(R2Point a, R2Point b, R2Point c) { return 0.5*((a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x));

} public static boolean equal(R2Point a, R2Point b) { return a.x==b.x && a.y==b.y;

} public static boolean isTriangle(R2Point a, R2Point b, R2Point c) { return area(a, b, c) != 0.0;

} public boolean inside(R2Point a, R2Point b) { §1. Основы объектно-ориентированного программирования return (a.x = x && x = b.x || a.x = x && x = b.x) && (a.y = y && y = b.y || a.y = y && y = b.y);

} public boolean light(R2Point a, R2Point b) { double s = area(a, b, this);

return s 0.0 || ( s == 0.0 && ! inside(a, b));

} } Рассмотрим задачу на реализацию класса с заданными свойствами.

Задача 1.1. Реализуйте класс R2Vector, позволяющий выполнять над векторами на плоскости следующие операции: сложение, вычитание, умножение на число и вычисление скалярного произведения.

Ее решение, приведенное ниже, в комментариях не нуждается.

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

class R2Vector { private double x, y;

public R2Vector(double x, double y) { this.x = x;

this.y = y;

} public R2Vector() throws Exception { x = Xterm.inputDouble("x - ");

y = Xterm.inputDouble("y - ");

} public static R2Vector plus(R2Vector a, R2Vector b) { return new R2Vector(a.x+b.x, a.y+b.y);

} public static R2Vector minus(R2Vector a, R2Vector b) { return new R2Vector(a.x-b.x, a.y-b.y);

} public static R2Vector mult(R2Vector a, double k) { return new R2Vector(k*a.x, k*a.y);

} public static double product(R2Vector a, R2Vector b) { return a.x*b.x + a.y*b.y;

} } Одним из достоинств объектно-ориентированного подхода является возможность использования уже существующих типов для порождения новых с автоматическим наследованием уже имеющихся свойств. Язык 164 Глава III. Применение ООП к разработке программных проектов Java реализует эту возможность с помощью двух механизмов расши рения или наследования классов (ключевое слово extends) и реализации интерфейсов (ключевое слово implements).

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

Пример расширения класса.

class Stack { private static final int DEFSIZE = 16;

private char[] array;

private int head;

public Stack() { array = new char[DEFSIZE];

head = 0;

} public final void push(char c) { array[head++] = c;

} public final char pop() { return array[--head];

} } public class Compf extends Stack { private void processSymbol(char c) { switch (c) { case ’(’:

push(c);

break;

case ’)’:

pop();

break;

case ’+’: case ’-’: case ’*’: case ’/’:

push(c);

break;

default:

break;

} } public Compf() { super();

} public final void compile(String str) { for(int i = 0;

i str.length();

i++) processSymbol(str.charAt(i));

} §1. Основы объектно-ориентированного программирования } Класс Stack (стек символов) в данном случае используется в каче стве базового для нового класса Compf (стековый компилятор формул), называемого в этом случае дочерним или выведенным. Все те методы, ко торые были реализованы в базовом классе (или суперклассе) Stack могут быть использованы и для объектов типа Compf, что и делается в методе processSymbol. Принято говорить, что между классами Stack и Compf возникает отношение наследования.

В языке Java каждый существующий класс неявно наследует класс Object, что превращает последний в суперкласс любого класса. Сам же класс Object является единственным классом, не имеющим суперкласса.

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



Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 7 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.