Научно-образовательный материал «Задачи на составление алгоритмов»

Некоммерческая организация «Ассоциация московских вузов»

Государственное образовательное учреждение

высшего профессионального образования

Московский государственный индустриальный университет

ГОУ ВПО МГИУ

Научно-образовательный материал

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

Состав научно-образовательного коллектива:

, к. т.н.

, ведущий инженер

Москва 2010 г.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ЗАДАЧА 7.19. Напишите программу, вводящую действительные коэф­фициенты a, b и с квадратного уравнения ах2-\-Ъх-\-с — 0 с положительным дискриминантом, находящую оба корня этого уравнения.

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

ЗАДАЧА 7.21. Напишите программу, которая вводит действительные координаты (х, у) и (а, Ь) двух точек на плоскости, и печатает расстояние от точки М[х7 у) до единичной окружности с центром в точке С (а, Ь).

ЗАДАЧА 7.22. Напишите программу, которая вводит действительные координаты (х, у) и (а, Ь) двух точек на плоскости, и печатает расстояние от точки М(ж, у) до прямой О А, где О — начало координат, а А(а: Ь) — отличная от О точка.

ЗАДАЧА 7.23. Напишите программу, вводящую три целых числа а, Ь и с, печатающую мощность множества решений уравнения ах2 + Ъх + с = 0.

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

ЗАДАЧА 7.24. Докажите, что выражение ((а Л Ъ) = (Ь V а)) является предикатом.

ЗАДАЧА 7.25. Докажите, что выражение а V а — не предикат.

ЗАДАЧА 7.26. Докажите, что выражение ((ei Л (е2 V е3)) — ((ei Л е2) V (ei Л ез))) является предикатом.

ЗАДАЧА 7.27. Докажите, что выражение ((е1Л(е2Лез)) — ((е1Ле2)Лез)) является предикатом.

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

ЗАДАЧА 7.29. Докажите, что выражение ((а => 6)) — не предикат.

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

ЗАДАЧА 7.31. Вычислите значения предикатов Рх = {х = 0 Л х/(у — 2и Р2 = (х = 0 && х/(у - 2) = 0) в состоянии s = {{х, 7), (у, 2)}.

ЗАДАЧА 7.32. Вычислите значения предиката Р = (Зг 0 ^ г ^ 9 (г2 ^ 0)) Л (Vj j2 ^ к) в состоянии s = {(&, 0)}.

ЗАДАЧА 7.33. Вычислите значения предиката Р = (\(х > у =^> 6) Л (6 =>■ х > y))Wl(x > у =>■ 6) в состоянии s = {(ж, 3), (?/, 2), (6, F)}.

ЗАДАЧА 7.34. Вычислите значения предиката Р = (Ь =>■ (х > у)) Л {{Ъ ^(х> у))\\(\(х > у) =ИЬ)) в состоянии s = {(х, 2), (у, 3), (6, Г)}.

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

ЗАДАЧА 7.36. Запишите предикат, утверждающий, что если г < j, а т > п, то и = v.

ЗАДАЧА 7.37. Запишите предикат, утверждающий, что самое большее одно из следующих утверждений истинно: а < 6, Ь < с.

ЗАДАЧА 7.38. Запишите предикат, утверждающий, что ни одно из сле­дующих утверждений не является истинным: а<Ъ, Ъ<сжх = у.

ЗАДАЧА 7.39. Запишите предикат, утверждающий, что следующие утверждения не являются истинными одновременно: а<Ь, Ь<сжх = у.

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

ЗАДАЧА 7.41. Запишите предикат, утверждающий, что для массива Ь[0..п — 1] длины п > 0 все элементы вырезки 6[j..fc] являются нулевыми.

ЗАДАЧА 7.42. Запишите предикат, утверждающий, что для массива Ь[0..п — 1] длины п > 0 ни один из элементов вырезки 6[j..fc] не нулевой.

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

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

ЗАДАЧА 7.45. Запишите предикат, утверждающий, что для массива Ь[0..п — 1] длины п > 0 некоторые нули массива находятся в вырезке

b\j..k].

ЗАДАЧА 7.46. Запишите предикат, утверждающий, что для массива Ь[0..п — 1] длины п > 0 справедливо высказывание: неверно, что все нули массива находятся в вырезке 6[j..fc].

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

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

п — 1] длины п > 0 справедливо высказывание: если в вырезке b[j..k] есть два нуля, то j = 1.

ЗАДАЧА 7.50. Запишите предикат, утверждающий, что для массива Ь[0..п — 1] длины п > 0 справедливо высказывание: элементы в вырезке 6[j..fc] расположены в возрастающем порядке.

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

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

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

ЗАДАЧА 7.54. Запишите предикат, который утверждает, что функция /: {1,2,3,4,5} —>• {1,2,3,4,5} является инъективной и отрицание этого факта. Упростите получившиеся предикаты, если это возможно.

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

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

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

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

ЗАДАЧА 7.59. Основываясь на определении 6.4, докажите закон мо­нотонности (Q =3- R) =>• (wp(S, Q) =^ wp(S, R)).

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

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

ЗАДАЧА 7.62. Вычислите и упростите wp("i=i+l; j=j-l;",z • j — 0).

ЗАДАЧА 7.63. Вычислите и упростите wp(,,x=x+y) ", ж < 2г/).

ЗАДАЧА 7.64. Вычислите и упростите w;p(Mx=(x+y)*(x-y) ; ",ж + у2 ф 0).

ЗАДАЧА 7.65. Вычислите и упростите w;]9("i=i+l; j=j+l; ", г = j).

ЗАДАЧА 7.66. Вычислите и упростите wp("x=a/h;"7x2 ^ 0).

ЗАДАЧА 7.67. Вычислите и упростите iup("i=l; s=b[0];M, l ^ i <

п Л в = Ь[0] + ... + 6[г-1]).

ЗАДАЧА 7.68. Вычислите и упростите w;p("a=0; п=1;",а2<п Л (а + 1)2>п).

ЗАДАЧА 7.69. Вычислите и упростите w;p("s=s+b[i] ; i=i+l;",0 <

г < n Л в = 6[0] + ... + Ь[г - 1]).

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

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

ЗАДАЧА 7.72. Найдите такое значение выражения ж, включающее дру­гие переменные, для которого спецификация {Q} S {R} становится тав­тологией: {Т} "а=а+1; Ь=х;" {Ь — а + 1}.

ЗАДАЧА 7.73. Найдите такое значение выражения ж, включающее дру­гие переменные, для которого спецификация {Q} S {R} становится тав­тологией: {Г} "Ь=х; а=а+1; " {Ъ = а + 1}.

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

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

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

— случайно выберите из банки два зерна и

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

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

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

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

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

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

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

ЗАДАЧА 7.79. Предъявите действительное (типа double) число х та­кое, что х + 1 = ж, а {х • 2)/2 ф х. Воспользуйтесь тем, что класс Java. lang.Double определяет константу MAX_VALUE.

ЗАДАЧА 7.80. Предъявите такие действительные (типа double) числа а, Ъ и с такие, что а + (Ь + с) ф {а + Ъ) + с.

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

ЗАДАЧА 7.82. Предъявите действительное (типа double) число х та­кое, что (х/2) • 2 ф х. Воспользуйтесь тем, что класс Java.lang.Double определяет константу MIN_VALUE.

ЗАДАЧА 7.83. Определите (приближенно) MAC HEPS (машинное эпсилон) для типов double и float. Машинным эпсилоном называет­ся наибольшее число х данного типа, удовлетворяющее соотношению 1 + ж = 1.

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

ЗАДАЧА 7.85. Напишите программу, вводящую действительные коэф­фициенты а, 6 и с квадратного уравнения ах2 + Ьх + с — 0 с положитель­ным дискриминантом, находящую оба корня этого уравнения достаточно точно во всех случаях.

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

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

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

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

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

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

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

УКАЗАНИЕ. Воспользуйтесь тем, что факториал очень быстро ра­стущая функция, а множество Ъм — ограничено, и поэтому любая про­грамма, работающая с величинами типа int, способна вычислить факто­риал только очень небольших чисел.

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

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

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

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

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

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

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

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

ЗАДАЧА 7.99. Напишите рекурсивную программу, печатающую бино­минальный коэффициент С% для целых п и к, где 0 ^ к ^ п. Для нео­трицательных п и к имеют место следующие соотношения: С® — С™ = 1,

°п+1 — °п + игг-

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

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

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

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

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

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

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

ЗАДАЧА 7.107. Напишите программу, печатающую первые к пар про­стых чисел. Два числа а и Ь образуют пару простых чисел, если они оба простые и Ъ — а + 2.

ЗАДАЧА 7.108. Напишите программу, находящую сумму

111 1

0! + il+2!+'" + Ы' сложность которой была бы линейной.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

УКАЗАНИЕ. Воспользуйтесь теоремой Безу, согласно которой числи­тель р любого рационального корня многочлена х = — является делителем

свободного члена, а знаменатель q — делителем старшего коэффициента.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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