Все задачи курса

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 7.12.Напишите программу, вводящую два целых числа a и b, печатающую их, затем обменивающую значения этих переменных (так, чтобы новое значение 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$$ квадратного уравнения $$a x^2 + b x + 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$$, печатающую мощность множества решений уравнения $$ax^2+bx+c=0$$.

Задачи на предикаты

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

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

Задача 7.26. Докажите, что выражение $$((e_1\land (e_2\lor e_3)) = ((e_1\land e_2)\lor (e_1\land e_3)))$$ является предикатом.

Задача 7.27. Докажите, что выражение $$((e_1\land (e_2\land e_3)) = ((e_1\land e_2)\land e_3))$$ является предикатом.

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

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

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

Задача 7.31. Вычислите значения предикатов $$P_1 = (x=0\ \land\ x/(y-2)=0)$$ и $$P_2 = (x=0 \ \lands \ x/(y-2)=0)$$ в состоянии $$s = \{(x, 7), (y, 2)\}$$.

Задача 7.32. Вычислите значения предиката $$P = (\exists i \ 0 \leqslant i \leqslant 9 \ (i^2 \leqslant 0)) \land (\forall j \ j^2 \geqslant k)$$ в состоянии $$s = \{(k, 0)\}$$.

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

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

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

Задача 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\geqslant y$$, то $$y<z$$ не может выполняться; однако если $$v=w$$, то $$x<y$$.

Задача 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\colon \{1, 2, 3, 4, 5\} \rightarrow \{1, 2, 3, 4, 5\}$$ является сюръективной и отрицание этого факта. Упростите получившиеся предикаты, если это возможно.

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 7.67. Вычислите и упростите $$wp("i=1; s=b[0];", 1 \leqslant i < n \ \land \ s = b[0]+\ldots+b[i-1] )$$.

Задача 7.68. Вычислите и упростите $$wp("a=0; n=1;", a^2 < n \ \land \ (a + 1)^2 \geqslant n)$$.

Задача 7.69. Вычислите и упростите $$wp("s=s+b[i]; i=i+1;", 0<i<n\ \land\ s=b[0]+\ldots+b[i-1])$$.

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

Задача 7.71. Вычислите и упростите следующее слабейшее предусловие $$wp("if (a > b) a=a-b; else b=b-a;",a>0 \ \land \ 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$$ сводится к проведению пунктирной линии, обладающей теми же свойствами. Проводить линию по уже нарисованной противником нельзя.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Указание Воспользуйтесь тем, что факториал — очень быстро растущая функция, а множество $$\mathbb{Z}_M$$ — ограничено, и поэтому любая программа, работающая с величинами типа int, способна вычислить факториал только очень небольших чисел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 7.108. Напишите программу, находящую сумму$$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\ldots+\frac{1}{n!},$$ сложность которой была бы линейной.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 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.

Все задачи лекций 8-10

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

Задачи на рекурсию

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

Задача 11.1. Напишите рекурсивную программу, перемножающую два целых числа, одно из которых неотрицательно, без использования операции умножения. Точные пред- и постусловия требуемой программы, временная сложность которой не должна превосходить $$\Theta(\log b)$$, таковы: $$Q=(a\in \mathbb{Z}_M \land b\in \mathbb{Z}_M \land b \geqslant 0)$$, $$R=(z=ab)$$. Числа $$a$$ и $$b$$ в программе изменять нельзя.

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

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

Указание Пусть $$P_n(x)=a_0x^n+a_1x^{n-1}+\ldots+a_{n-1}x+a_n$$. Продифференцируем по $$x$$ равенство $$P_n(x) = x \cdot P_{n-1}(x) + a_n$$ и подставим затем $$x=x_0$$. Мы получим следующие соотношения:

$$P'_0(x_0) = 0$$,

$$P'_n(x_0) = x_0 \cdot P'_{n-1}(x_0) + P_{n-1}(x_0)$$.

Воспользовавшись ими и формулами

$$P_0(x_0) = a_0$$,

$$P_n(x_0) = x_0 \cdot P_{n-1}(x_0) + a_n$$,

легко определить рекурсивную функцию неотрицательного целого аргумента $$g\colon \mathbb{Z}_M \rightarrow \mathbb{Z}_M \times \mathbb{Z}_M$$, $$g(n) = (P'_n(x_0), P_n(x_0))$$ для вычисления которой и пишется программа.

Проектирование цикла при помощи инвариантa

При решении задач из этого раздела необходимо построить и доказать правильность построенной программы вида "S0;while(e)S;", а при отсутствии в условии задачи явно заданных инварианта цикла и ограничивающей функции объяснить предварительно, каким образом они были получены.

Задача 11.4. Напишите программу, перемножающую два целых числа, одно из которых неотрицательно, без использования операции умножения. Точные пред- и постусловия требуемой программы, временная сложность которой не должна превосходить $$\Theta(\log b)$$, таковы: $$Q=(a\in \mathbb{Z}_M \land b\in \mathbb{Z}_M \land b \geqslant 0)$$, $$R=(z=ab)$$. При написании программы величины $$a$$ и $$b$$ изменять не разрешается, следует использовать инвариант $$I = (y \geqslant 0 \land z + xy = ab)$$ и ограничивающую функция $$h = y$$.

Задача 11.5. Напишите программу, возводящую целое число в целую неотрицательную степень. Точные пред- и постусловия требуемой программы таковы: $$Q=(a\in \mathbb{Z}_M \land b\in \mathbb{Z}_M \land a > 0 \land b \geqslant 0)$$, $$R=(z=a^b)$$. При написании программы величины $$a$$ и $$b$$ изменять не разрешается, следует использовать инвариант $$I = (y \geqslant 0 \land z \cdot x^y = a^b)$$ и ограничивающую функцию $$h = y$$.

Задача 11.6. Напишите программу, находящую приближенное значение квадратного корня $$a \in \mathbb{Z}_M^+$$ из заданного неотрицательного целого числа $$n$$. Вот более точная формулировка пред- и постусловия: $$Q=(n\in \mathbb{Z}_M \land n \geqslant 0)$$, $$R= (a \in \mathbb{Z}_M \land a \geqslant 0 \land a^2\leqslant n \land (a + 1)^2 > n)$$. При написании программы величину $$n$$ изменять нельзя.

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

Задача 11.8. Напишите программу, находящую сумму $$s$$ элементов заданного целочисленного массива $$b[0..n-1]$$, элементы которого и величину $$n$$ изменять нельзя. Точные пред- и постусловия: $$Q = (n>0)$$,$$\displaystyle R=\left(s = \sum_{j=0}^{n-1} b[j]\right).$$

Задача 11.9. Напишите программу, находящую приближенное значение квадратного корня $$a \in \mathbb{Z}_M^+$$ из заданного неотрицательного целого числа $$n$$. Точные пред- и постусловия требуемой программы, временная сложность которой не должна превосходить $$\Theta(\log n)$$, таковы: $$Q=(n\in \mathbb{Z}_M \land n \geqslant 0)$$, $$R= (a \in \mathbb{Z}_M \land a \geqslant 0 \land a^2\leqslant n \land (a + 1)^2 > n)$$. При написании программы величину $$n$$ изменять нельзя.

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

Задача 11.11. Напишите программу, печатающую $$n$$ -ое число Фибоначчи ( $$f_0=0$$, $$f_1=1$$, $$f_k=f_{k-1}+f_{k-2} \ \mbox{для $k>1$}$$ ). При написании программы используйте $$Q=(n\in \mathbb{Z}_M \land n>0)$$, $$R=(a=f_n)$$, $$I=(1 \leqslant i \leqslant n \land a = f_i \land b = f_{i-1})$$, $$h=n-i$$. Число $$n$$ в программе изменять нельзя.

Задача 11.12. Напишите программу, находящую частное $$q$$ и остаток $$r$$ от деления $$x$$ на $$y$$, не использующую операций умножения и деления. При написании программы положите $$Q=(x\in \mathbb{Z}_M \land y\in \mathbb{Z}_M \land x\geqslant 0 \land y>0)$$, $$R=(0 \leqslant r < y \land q y + r = x)$$, $$I=(0 \leqslant r \land 0 < y \land q y + r = x)$$, $$h=r-y+1$$. Величины $$x$$ и $$y$$ в программе изменять не разрешается.

Задача 11.13. Напишите программу, находящую наибольший общий делитель $$gcd(X,Y)$$ двух целых положительных чисел $$X$$ и $$Y$$, не использующую операций умножения и деления и не изменяющую величин $$X$$ и $$Y$$. При написании программы положите $$Q=(X\in \mathbb{Z}_M \land Y\in \mathbb{Z}_M \land X>0 \land Y>0)$$, $$R=(x=y=gcd(X,Y))$$, $$I=(0<x \land 0<y \land gcd(x,y)=gcd(X,Y))$$, $$h=x+y-2\cdot 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$$.

Задача 11.14. Напишите программу, находящую приближенное значение квадратного корня $$a \in \mathbb{Z}_M^+$$ из заданного неотрицательного целого числа $$n$$. Вот более точная формулировка пред- и постусловия: $$(Q=n\in \mathbb{Z}_M \land n \geqslant 0)$$, $$R= (a \in \mathbb{Z}_M \land a \geqslant 0 \land a^2\leqslant n \land (a + 1)^2 > n)$$. При написании программы величину $$n$$ изменять нельзя. Для построения инварианта удалите из постусловия конъюнктивный член $$a^2\leqslant n$$. Оцените временную сложность получившейся программы и сравните ее со сложностью программы, построенной в задаче 9.1.

Задача 11.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 \land n>0)$$, $$R=((0\leqslant i <m \land 0 \leqslant j < n \land x = b[i][j])\lor (i=m \land x \notin b[0..m-1][0..n-1]))$$.

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

Задача 11.16. Напишите программу (бинарный или двоичный поиск), определяющую для упорядоченного по неубыванию массива $$b[0..n-1]$$ целых чисел и заданного целого числа $$x$$ позицию $$i$$, в которую может быть вставлено это число без нарушения упорядоченности массива. Точные пред- и постусловия требуемой программы, временная сложность которой не должна превосходить $$\Theta(\log n)$$, таковы: $$Q=(x\in \mathbb{Z}_M \land n\in \mathbb{Z}_M \land n >0 \land (\forall j\ 0 \leqslant j < n-1\colon b[j] \leqslant b[j+1]))$$, $$R=( (i=-1\land x < b[0])\lor (0\leqslant i < n-1\land b[i] \leqslant x < b[i+1])\lor (i=n\land b[n-1] \leqslant x) )$$. При написании программы величины $$x$$, $$n$$ и элементы массива $$b$$ изменять не разрешается, для построения инварианта используйте метод замены константы переменной.

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

Задача 11.18. Напишите программу, находящую наибольшее целое число, являющееся степенью двойки, не превосходящее заданного натурального числа $$n\in\mathbb{Z}_M$$, изменять которое в программе нельзя.

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

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

Задача 11.20. Напишите программу, находящую приближенное значение квадратного корня $$a \in \mathbb{Z}_M^+$$ из заданного неотрицательного целого числа $$n$$. Точные пред- и постусловия требуемой программы, временная сложность которой не должна превосходить $$\Theta(\log n)$$, таковы: $$Q=(n\in \mathbb{Z}_M \land n \geqslant 0)$$, $$R= (a \in \mathbb{Z}_M \land a \geqslant 0 \land a^2\leqslant n \land (a + 1)^2 > n)$$. При написании программы величину $$n$$ изменять нельзя, а инвариант следует построить методом замены константы $$a$$ на переменную $$b$$ в конъюнктивном члене $$a^2\leqslant n$$ постусловия $$R$$.

Задача 11.21. Напишите программу, находящую наименьшее значение $$x \in \mathbb{Z}_M$$ в заданном массиве целых чисел $$b[0..n-1]$$, где $$n>0$$. Значения элементов массива $$b$$ и число $$n$$ в программе изменять нельзя, $$Q=(n\in \mathbb{Z}_M \land n>0)$$, $$R=( (\forall j\ 0\leqslant j <n\ x \leqslant b[j])\land (\exists k\ 0\leqslant k <n\ x = b[k]))$$, инвариант постройте методом замены константы $$n$$ на переменную $$i$$.

Задача 11.22. Напишите программу, находящую длину $$p \geqslant 1$$ самой длинной площадки в упорядоченном по неубыванию массиве $$b[0..n-1]$$ целых чисел. Площадкой мы называем последовательность нескольких равных значений. Значения элементов массива $$b$$ и число $$n>0$$ в программе изменять нельзя, $$Q=(n\in \mathbb{Z}_M \land n>0\land (\forall j\ 0 \leqslant j < n-1\ b[j] \leqslant b[j+1]))$$, $$R=( ((\exists k\ 0\leqslant k \leqslant n-p\ b[k]=b[k+p-1])\land (\forall j\ 0\leqslant j \leqslant n-p+1\ b[j] \ne b[j+p])))$$, инвариант постройте методом замены константы $$n$$ на переменную $$i$$.

Задача 11.23. Напишите программу, находящую число $$m \geqslant 1$$ площадок в упорядоченном по неубыванию массиве $$b[0..n-1]$$ целых чисел. Площадкой мы называем последовательность нескольких равных значений. Значения элементов массива $$b$$ и число $$n>0$$ в программе изменять нельзя.

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

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

Схема вычисления инвариантной функции

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

Задача 11.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$$.

Задача 11.26. Напишите программу, перемножающую два целых числа, одно из которых неотрицательно, без использования операции умножения. Точные пред- и постусловия требуемой программы, временная сложность которой не должна превосходить $$\Theta(\log b)$$, таковы: $$Q=(a\in \mathbb{Z}_M \land b\in \mathbb{Z}_M \land b \geqslant 0)$$, $$R1=(z=ab)$$. При написании программы величины $$a$$ и $$b$$ изменять не разрешается. Воспользуйтесь тем, что функция $$F\colon \mathbb{Z}_M\times\mathbb{Z}_M\times\mathbb{Z}_M \rightarrow \mathbb{Z}_M$$, $$F(x,y,z) = z+xy$$ является инвариантной относительно преобразования $$T\colon \mathbb{Z}_M\times\mathbb{Z}_M\times\mathbb{Z}_M \rightarrow \mathbb{Z}_M\times\mathbb{Z}_M\times\mathbb{Z}_M$$, задаваемого формулой $$$$T(x,y,z)=\begin{cases} (2x,y/2,z), \text{если $y$ — четно},\\ (x,y-1,z+x), \text{иначе}. \end{cases} $$$$

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

$$gcd(x,y)=\begin{cases} gcd(x\%y,y), \text{если $x\geqslant y$},\\ gcd(x,y\%x), \text{иначе}. \end{cases}$$

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

Задача 11.28. Напишите программу, возводящую целое число в целую неотрицательную степень. Точные пред- и постусловия требуемой программы таковы: $$Q=(a\in \mathbb{Z}_M \land b\in \mathbb{Z}_M \land a > 0 \land b \geqslant 0)$$, $$R1=(z=a^b)$$. При написании программы величины $$a$$ и $$b$$ изменять не разрешается. Воспользуйтесь тем, что функция $$F\colon \mathbb{Z}_M\times\mathbb{Z}_M\times\mathbb{Z}_M \rightarrow \mathbb{Z}_M$$, $$F(x,y,z) = zx^y$$ является инвариантной относительно преобразования $$T\colon \mathbb{Z}_M\times\mathbb{Z}_M\times\mathbb{Z}_M \rightarrow \mathbb{Z}_M\times\mathbb{Z}_M\times\mathbb{Z}_M$$, задаваемого формулой $$T(x,y,z)=(x,y-1,xz)$$.

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

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

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

$$T(x,y,z)=\begin{cases} (x/2,y/2,2z), \text{если оба числа $x$ и $y$ — четны},\\ (x/2,y,z), \text{если $x$ — четно, а $y$ — нечетно},\\ (x,y/2,z), \text{если $x$ — нeчетно, а $y$ — четно},\\ (x-y,y,z), \text{если $x$ и $y$ — нечетны и $x\geqslant y$},\\ (x,y-x,z), \text{если $x$ и $y$ — нечетны и $x < y$}. \end{cases}$$

Не забудьте доказать $$T$$ -инвариантность функции $$F$$.

Задачи на индуктивные функции

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

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

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

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

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

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

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

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

Задача 11.36. Напишите программу, определяющую дисперсию не пустой последовательности действительных чисел. Дисперсией $$d$$ последовательности $$x_1, x_2, \ldots, x_n$$ называется величина $$\displaystyle \frac{1}{n}\sum_{i=1}^n(x_i-m)^2$$, где $$m=(x_1+x_2+\ldots+x_n)/n$$ — среднее арифметическое элементов последовательности.

Указание

Так как

$$\begin{align*} \displaystyle d = \frac{1}{n}\sum_{i=1}^n(x_i-m)^2= \frac{1}{n}\sum_{i=1}^n(x_i^2-2mx_i +m^2)=\\ \frac{1}{n}\left(\sum_{i=1}^n x_i^2 -m \sum_{i=1}^n x_i - m \sum_{i=1}^n (x_i-m)\right)=\\ \frac{1}{n}\left(\sum_{i=1}^n x_i^2 -m \sum_{i=1}^n x_i\right)= \frac{1}{n}\sum_{i=1}^n x_i^2 -\frac{1}{n^2}\left(\sum_{i=1}^n x_i\right)^2, \end{align*} $$

то вводя обозначения $$\displaystyle s_0= \sum_{i=1}^n 1 = n$$, $$\displaystyle s_1= \sum_{i=1}^n x_i$$, $$\displaystyle s_2= \sum_{i=1}^n x_i^2$$, получим $$\displaystyle d=s_2/s_0 - (s_1/s_0)^2$$. Легко проверить, что функция $$F = (s_2, s_1, s_0)$$ является индуктивной.

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

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

Указание Продифференцировав по $$x$$ равенство $$P_n(x) = x \cdot P_{n-1}(x) + a_n$$ и подставив затем $$x=t$$, получите соотношения $$P'_0(t) = 0$$ и $$P'_n(t) = t \cdot P'_{n-1}(t) + P_{n-1}(t)$$, которые помогут построить индуктивное расширение исходной функции.

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

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

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

Указание Рассмотрите следующее индуктивное расширение $$F=(f_1, f_2, f_3)$$ функции $$f$$, где $$f_1\colon X^* \rightarrow \{T,F\}$$, $$f_2\colon X^* \rightarrow \mathbb{Z}_M$$, $$f_3\colon X^* \rightarrow X$$, определены следующим образом:

$$f_1(\omega) = \omega$$ может быть продолжена до правильной формулы,

$$$f_2(\omega)$$ = разность числа левых и правых скобок в $$\omega$$,

$$$f_3(\omega) =$$ последний элемент $$\omega$$.

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

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

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

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

Указание Рассмотрите эту функцию $$f$$, как функцию на пространстве последовательностей над алфавитом $$\{0,1\}$$. В качестве последовательности $$\omega$$ нужно взять инвертированное представление числа $$b$$ в двоичной системе счисления. Данная последовательность получается естественным образом — последняя цифра числа $$b$$ есть "b1", предпоследняя получается по той же формуле после сдвига вправо ( "b>>>=1;" ) и так далее. Индуктивное расширение $$F$$ исходной функции $$f$$ легко находится, что и позволяет написать требуемую программу.

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

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

Дополнительные задачи

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

Задача 16.2. Напишите программу, печатающую площадь поверхности и объем двух $$n$$ -мерных стандартных параллелепипедов. Стандартным параллелепипедом называется множество $$\Pi = \{(x_1, x_2, \ldots, x_n) \in \mathbb{R} \colon \forall i \in 1..n \ a_i \leqslant x_i \leqslant b_i\}$$.

Задача 16.3. Создайте аплет, изображающий график функции $$f(x)$$ на заданном отрезке. Формулу, задающую функцию $$f(x)$$, следует предварительно откомпилировать с помощью одного из методов, изложенных в проекте "Компилятор формул".

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 16.33. Напишите программу, вводящую последовательность наборов $$(x_1, y_1, x_2, y_2)$$ — координат концов отрезков, и определяющую, образует ли этот набор отрезков многоугольник.

Задача 16.34. Напишите программу, вводящую последовательность наборов $$(x_1, y_1, x_2, y_2)$$ — координат концов отрезков, и определяющую, образует ли этот набор отрезков ломаную линию (не обязательно со звеньями, следующими в порядке ввода).

Задача 16.35. Напишите программу, вводящую последовательность наборов $$(x_1, y_1, x_2, y_2)$$ — координат концов отрезков, и определяющую, образует ли этот набор отрезков множество многоугольников.

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

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

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

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

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

Задача 16.41. Напишите программу, вводящую последовательность наборов $$(x, y, z, r)$$, которая рассматривает их в качестве координат центров сфер и их радиусов и определяет, вложены ли они друг в друга, как матрешки (не обязательно в порядке их ввода).

Задача 16.42. Создайте аплет, вводящий натуральное число $$n\geqslant 3$$, находящий и изображающий какую-либо траекторию обхода конем шахматной доски размера $$n \times n$$.

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

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