Программирование. Задачи на массивы

к содержанию задачника

Заполнение массива

1. Заполнить массив нулями, кроме первого и последнего элементов, которые должны быть равны единице.
2. Заполнить массив нулями и единицами, при этом данные значения чередуются, начиная с нуля.
3. Заполнить массив последовательными нечетными числами, начиная с единицы.
4. Сформировать массив из элементов арифметической прогрессии с заданным первым элементом \(x\) и разностью \(d\).
5. Сформировать возрастающий массив из четных чисел.
6. Сформировать убывающий массив из чисел, которые делятся на 3.
7. Создать массив из \(n\) первых чисел Фибоначчи.
8. Заполнить массив заданной длины различными простыми числами. Натуральное число, большее единицы, называется простым, если оно делится только на себя и на единицу.
9. Создать массив, каждый элемент которого равен квадрату своего номера.
10. Создать массив, на четных местах в котором стоят единицы, а на нечетных местах – числа, равные остатку от деления своего номера на 5.
11. Создать массив, состоящий из троек подряд идущих одинаковых элементов.
12. Создать массив, который одинаково читается как слева направо, так и справа налево.
13. Сформировать массив из случайных чисел, в которых ровно две единицы, стоящие на случайных позициях.
14. Заполните массив случайным образом нулями и единицами так, чтобы количество единиц было больше количества нулей.
15. Сформировать массив из случайных целых чисел от 0 до 9 , в котором единиц от 3 до 5 и двоек больше троек.
16. Создайте массив, в котором количество отрицательных чисел равно количеству положительных и положительные числа расположены на случайных местах в массиве.
17. Заполните массив случайным образом нулями, единицами и двойками так, чтобы первая двойка в массиве встречалась раньше первой единицы, количество единиц было в точности равно суммарному количеству нулей и двоек.
18. Придумайте правило генерации массива заданной длины. Определите, сгенерирован ли данный массив вашим правилом или нет.

Анализ элементов массива

19. Определить, содержит ли массив данное число \(x\)
20. Найти количество четных чисел в массиве.
21. Найти количество чисел в массиве, которые делятся на 3, но не делятся на 7.
22. Определите, каких чисел в массиве больше: которые делятся на первый элемент массива или которые делятся на последний элемент массива.
23. Найдите сумму и произведение элементов массива.
24. Найдите сумму четных чисел массива.
25. Найдите сумму нечетных чисел массива, которые не превосходят 11.
26. Найдите сумму чисел массива, которые расположены до первого четного числа массива. Если четных чисел в массиве нет, то найти сумму всех чисел за исключением крайних.
27. Найдите сумму чисел массива, которые стоят на четных местах.
28. Найдите сумму чисел массива, которые стоят на нечетных местах и при этом превосходят сумму крайних элементов массива.
29. Дан массив x из n элементов. Найдите \(x_1-x_2+x_3-\ldots-x_{n-1}+x_n\).
30. Дан массив x из n элементов. Найдите \(x_1x_n+x_2x_{n-1}+\ldots+x_nx_1\).
31. Дан массив x из n элементов. Найдите \(x_n(x_n+x_{n-1})(x_n+x_{n-1}+x_{n-2})\ldots (x_n+\ldots+x_1)\).
32. Найти наибольший элемент массива.
33. Найдите сумму наибольшего и наименьшего элементов массива.
34. Найдите количество элементов массива, которые отличны от наибольшего элемента не более чем на 10%.
35. Найдите наименьший четный элемент массива.
36. Среди элементов с нечетными номерами найдите наибольший элемент массива, который делится на 3.
37. Дан массив и число \(p\). Найдите два различных числа в массиве, сумма которых наиболее близка к \(p\).
38. Дан массив. Найдите два соседних элемента, сумма которых минимальна.
39. Дан массив. Найдите три последовательных элемента в массиве, сумма которых максимальна.
40. В данном массиве найдите количество чисел, соседи у которых отличаются более чем в 2 раза.
41. Найдите количество чисел, каждое из которых равно сумме квадратов своих соседей и при этом не является наибольшим в массиве.
42. Проверьте, содержит ли данный массив из \(n\) чисел, все числа от \(1\) до \(n\).
43. Проверьте, образует ли элементы массива в данном порядке арифметическую или геометрическую прогрессии.
44. Проверьте, является ли данный массив возрастающим или убывающим.
45. Найдите количество различных элементов данного массива.
46. Определите количество перемен знаков элементов массива.
47. В данном массиве найти максимальное количество одинаковых элементов.
48. Найти наиболее часто встречающийся элемент в массиве целых чисел.
49. В одномерном массиве, состоящем из n вещественных элементов, вычислите номер минимального элемента массива и сумму элементов массива, расположенных между первым и вторым отрицательными элементами.
50. Напишите программу, которая вводит с клавиатуры непустой массив целых чисел, и выводит число локальных максимумов (элемент является локальным максимумом, если он не имеет соседей, больших, чем он сам).
51. В данном массиве найдите два наименьших элемента.
52. Определите, есть ли в массиве повторяющиеся элементы.
53. В данном массиве найдите наибольшую серию подряд идущих элементов, расположенных по возрастанию.
54. В массиве найдите количество серий из четверок подряд идущих попарно различных элементов.
55. Определите, можно ли вычеркнуть из данного массива одно число так, чтобы оставшиеся числа оказались упорядоченными по возрастанию.

Преобразование массива

56. В массиве заменить все числа, большие данного числа, на среднее арифметическое всех чисел массива.
57. Дан массив. Заменить все числа, меньшие последнего элемента массива, на первый элемент.
58. Поменять местами наибольший и наименьший элементы массива.
59. Найти наибольший четный элемент массива и поменять его местами с наименьшим нечетным элементом. Если одного из таких элементов нет, то всем элементам массива присвоить значение, равное нулю.
60. Заменить каждый элемент массива с четным номером на соседний слева элемент.
61. Удалить в массиве первый и последний элементы.
62. Удалить в массиве все числа, которые повторяются более двух раз.
63. Найти в массиве все серии подряд идущих одинаковых элементов и удалить из них все элементы кроме одного.
64. Удалить в массиве все наибольшие элементы.
65. Переставить элементы массива в обратном порядке.
66. Дан массив \(a\) из \(n\) элементов. Сформировать новый массив \(b\) такого же размера так, что элемент \(b_k\) равен сумме элементов первых элементов массива\(a\) до номера \(k\) включительно.
67. В данном массиве найти все нулевые элементы и заменить их вместе с соседними элементами на 3.
68. Преобразовать массив таким образом, чтобы сначала располагались все элементы, модуль которых не превышает единицу, а потом – все остальные.
69. Даны два массива. Сформировать третий массив, состоящий из тех элементов, которые: а) присутствуют в обоих массивах; б) присутствуют только в одном из массивов.
70. Дан массив. Осуществите циклический сдвиг массив на k единиц вправо, если первый наименьший элемент массива расположен раньше последнего наибольшего элемента массива, и влево, если иначе.
71. Даны два массива. Определите, существуют ли в первом массиве такие два элемента, что их сумма равна сумме каких-либо трех элементов второго массива.
72. Дана упорядоченная последовательность \(a_n\) чисел от 1 до N. Из копии данной последовательности \(b_n\) удалили одно число, а оставшиеся перемешали. Найти удаленное число.
73. Дан массив, в котором количество отрицательных элементов равно количеству положительным. Поменяйте местами первый отрицательный и первый положительный, второй отрицательный и второй положительный и так далее.
74. Удалите в целочисленном массиве все положительные числа, которые являются палиндромами.
75. Дан массив. Сформировать новый массив, в котором идут сначала отрицательные элементы, затем нули, затем положительные.
76. Даны два массива. Определите все серии подряд идущих элементов из первого массива (серия может состоять и из одного элемента), каждая из которых совпадает с какой-нибудь серией подряд идущих элементов второго массива.
77. Дан массив из n элементов. Переставьте его элементы случайным образом.
78. В данном массиве каждый элемент равен 0, 1  или 2. Переставить элементы массива так, чтобы сначала располагались все нули, затем все единицы и, наконец, все двойки. Дополнительный массив не использовать.
79. Даны два упорядоченных по возрастанию массива. Образовать из этих двух массивов единый упорядоченный по возрастанию массив.
80. Осуществить поиск данного числа в упорядоченном по возрастанию массиве методом бинарного поиска.
81. Дан массив натуральных чисел. Найти наименьшее натуральное число, не представимое суммой никаких элементов массива. Сумма может состоять и из одного слагаемого, но каждый элемент массива может входить в нее только один раз.
82. В данном массиве найти серию подряд идущих элементов наибольшей длины, в которой первое число равно последнему, второе – предпоследнему и так далее.
83. Выполните сортировку массива следующими тремя способами: сортировкой выбором, сортировкой вставками, сортировкой обменом.
84. Дано натуральное число \(n\) от 9 до \(10^7\). Необходимо найти минимальное число \(k\) такое, что произведение цифр этого числа равно \(n\). Например, для \(n=20\) ответ равен \(45\).
85. Даны координаты центров окружностей и их радиусы. Определите количество пар окружностей, которые пересекаются.
86. Даны два множества точек на плоскости. Выбрать три различные точки первого множества так, чтобы круг, ограниченный окружностью, проходящей через эти три точки, содержал все точки второго множества и имел минимальную площадь.
87. Даны два множества точек на плоскости. Выбрать четыре различные точки первого множества так, чтобы квадрат с вершинами в этих точках накрывал все точки второго множества и имел минимальную площадь.
88. На прямой задано n числовых интервалов. Определите, образует ли объединение этих интервалов один интервал.
89. Из данных n точек на плоскости определите те три, которые образуют треугольник наибольшей площади.
90. На данных n точек на плоскости найдите все тройки точек, которые образуют равносторонние треугольники.
91. Дано 3n точек на плоскости, причем никакие три из них не лежат на одной прямой. Построить множество n треугольников с вершинами в этих точках так, что­бы никакие два треугольника не пересекались и не содержали друг друга.
92. На плоскости задано множество из \(n\) точек и прямая \(ax+by+c=0\). Найдите максимальное расстояние между точками, лежащими по разные стороны от прямой.
93. Найти три треугольника с вершинами в заданном множестве точек на плоскости так, чтобы второй треугольник лежал строго внутри первого, а третий внутри второго.
94. Определите, образует ли последовательность из n точек на плоскости выпуклый многоугольник.
95. Дано n точек в трехмерном пространстве. Определите, лежат ли эти точки на одной плоскости.
96. Дано n точек на плоскости. Найдите круг минимального радиуса с центром в одной из точек, внутри которого и на границе находилось бы ровно m точек.
97. На плоскости дано \(n\) точек. Определите коэффициенты прямой \(y=kx+b\), проходящей через первую точку и наибольшее число остальных точек.
98. На плоскости дано \(n\) точек. Определите коэффициенты прямой \(y=kx+b\), проходящей через первую и одну из оставшихся точек так, чтобы все n точек лежали по одну сторону от этой прямой, и, быть может, на самой прямой.
99. По заданной последовательности целых чисел \(a_1,a_2,…,a_n\) построить последовательность \(b_n\) такую, что \(b_i\) – это количество элементов, превосходящих \(a_i\), в начальном отрезке последовательности\(a\) длиной \(i-1\).
100. Определить в заданной последовательности целых чисел количество чисел Фибоначчи.
101. Найти наименьшее общее кратное всех чисел, содержащихся в заданной последовательности натуральных чисел.
102. Пользователь вводит два натуральных числа, каждое из которых может состоять более чем из десяти цифр. Найдите сумма, разность и произведение данных чисел.
103. Определить количество повторений каждой из цифр \(0, 1, 2,…,9\) в числе \(n\)!, где \(n\) – натуральное число, \(n >100\).
104.  Получить все перестановки чисел \(1, 2, …, n\). Например, при \(n=3\) это 1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2, 3 2 1.
105. Дан массив a размера n. Сформировать новый массив b того же размера по следующему правилу: элемент b_k равен среднему арифметическому элементов массива a с номерами от k до n.
106. Дан целочисленный массив размера n. Увеличить все четные числа, содержащиеся в массиве, на исходное значение первого четного числа. Если четные числа в массиве отсутствуют, то оставить массив без изменений.
107. Дан массив размера n. Заменить каждый элемент массива на среднее арифметическое этого элемента и его соседей.
108. Дан массив размера n. После каждого отрицательного элемента массива вставить элемент с нулевым значением.
109. Дано  n точек (точки заданы своими координатами x, y). Среди всех точек этого множества, лежащих во второй четверти, найти точку, наиболее удаленную от начала координат. Если таких точек нет, то вывести точку с нулевыми координатами.
110. Даны n обыкновенных дробей (массив числителей и массив знаменателей). Выполнить их сложение и умножение.
111. Два многочлена заданы массивами своих коэффициентов. Найдите их сумму и произведение.
112. Два многочлена заданы массивами своих коэффициентов. Найдите частное и остаток от деления одного многочлена на второй.
113. Дан массив коэффициентов многочлена. Найдите производную \(k\)-порядка этого многочлена.
114. По кругу расположены \(n\) человек. Ведущий считает по кругу, начиная с первого, и исключает из круга каждого \(m\)-го человека. Найдите номер человека, который останется последним в круге.
115. По кругу стоят \(n\) человек. Ведущий посчитал \(m\) человек по кругу, начиная с первого. При этом каждый из тех, кто участвовал в этом счете, получил по одной монете, остальные получили по две монеты. Далее человек, на котором остановился счет,  отдает все свои монеты следующему по счету человеку, а сам выбывает из круга. Процесс продолжается с места остановки аналогичным образом до последнего человека в круге. Определите номер этого человека и количество монет, которые оказались у него в конце игры.
116. В массиве в порядке убывания заданы достоинства купюр валютной системы некоторой страны. Реализуйте выдачу заданной суммы s минимальным количеством купюр.
117. Из элементов массива a, состоящего из 2n элементов, получить массивы b и c следующим образом: выбрать в массиве a два наиболее близких по значению элемента, меньший из них поместить в массив b, а больший – в массив c. Исключить из рассмотрения в массиве a эти элементы и продолжить выбор из оставшихся элементов.
118. На большинстве Московских олимпиад каждый участник заполняет персональную карточку участника на которой указан 4(5)-значный номер карточки. Ясно, что не все числа из этого диапазона используются. Придумайте способы кодирования карточек, удовлетворяющие следующим требованиям:
     1) При минимальном диапазоне возможных значений номеров в него должно умещаться максимальное число карточек, то есть не следует кодировать номера карточек десятизначными последовательностями.
     2)Система кодирования должна уметь исправлять одну (две, …) ошибки в написании номера карточек (то есть если школьник ошибется в одной (двух, …) цифрах при переписывании номера карточек, то эта ошибка может быть исправлена, например, после ввода информации в компьютер).
     3)Система кодирования должна быть максимально простой, например, номера карточек должны образовывать арифметическую прогрессию. Также желательно сделать максимально простым и алгоритм исправления ошибок в номере карточки.
     Можете придумать и свои критерии к системе кодирования номеров карточек.
119. В  данном массиве наименьший элемент поместить на первое место, наименьший из оставшихся – на последнее место, следующий – предпоследнее и так далее – до середины массива.
120. Даны два многочлена \(P(x)\) и \(Q(x)\). Определить коэффициенты многочлена \(P(Q(x))\).
121. Удалить в заданном массиве элементы так, чтобы оставшиеся образовывали возрастающую последовательность наибольшей длины.
122. В массиве h хранятся значения высот некоторого профиля местности (ее вертикального сечения) с постоянным шагом горизонтали. Найдите области (номера точек измерения высот), невидимые для наблюдателя, находящегося в точке h_i.
123. Даны результаты ежедневных измерений количества выпавших осадков. За какую из недель, считая с начала периода измерений, выпало наибольшее количество осадков?
124. Задан массив, состоящий из n неотрицательных чисел. Найдите в нем индекс элемента, для которого сумма элементов, стоящих до него, наименее отличается от суммы элементов, стоящих после него.
125. Данный массив разбить случайным образом на m фрагментов. Границы фрагментов сохранить в новый массив.
126. Реализовать алгоритм перестановки элементов массива a так, чтобы ни один из элементов не остался на своем месте и имел бы одинаковые вероятности занять любое из остальных мест.
127. Имитировать перетасовку колоды карт. Каждая перетасовка состоит из трех этапов: разбиение колоды на две подколоды, выбор в каждой подколоде части, перемешивание выбранных частей, объединение всех карт в одну колоду.
128. Даны n точек на плоскости – точки графика  некоторой функции. Найти многочлен, график которого проходит через данные точки.
129. В игре следующие правила. В ряд лежат 25 монет. За ход разрешается брать одну или две рядом лежащие монеты. Проигрывает тот, кому нечего брать. Реализовать возможность игры пользователя с компьютером.
130. Построить множество, которое состоит из дружных чисел на интервале от 1 до 255. Дружными числами называется такая пара натуральных чисел М и N, для которых сумма всех делителей числа М (кроме самого М) равняется числу N, а сумма всех делителей числа N (кроме самого числа N) равняется числу М.
131. Игра начинается с числа 0. За ход можно прибавлять к имеющемуся числу любое число от 1 до 10. Выигрывает получивший число 100. Реализовать возможность игры пользователя с компьютером.
132. В игре следующие правила. Имеется две кучи конфет: в первой – 40, во второй – 45. За ход нужно одну кучу съесть, а другую разделить на две (не обязательно равные). Проигрывает тот, кто не может сделать ход. Реализовать возможность игры пользователя с компьютером.
133. На плоскости заданы n точек своими декартовыми координатами. Найти минимальный периметр многоугольника, содержащего все эти точки. Гарантируется, что искомый многоугольник имеет ненулевую площадь.
134. Вывести все представления натурального числа n суммой натуральных чисел. Перестановка слагаемых нового способа представления не дает.
135. Заданы вес e пустой копилки и вес v копилки с монетами. В копилке могут находиться монеты n видов; известны ценность p_i, каждого вида монет и вес w_i одной монеты. Найти минимальную и максимальную суммы денег, которые могут находиться в копилке.
136. Даны \(n\) целых чисел. Расставить между ними знаки «+» и «-» так, чтобы значение получившегося выражения было равно заданному целому \(s\).
137. Даны координаты \(n\) точек на плоскости. Данные точки последовательно соединяем. Предложите способ определения коэффициента от 0 до 1, по которому можно сказать, насколько сильно данная прямая похожа на прямую. Если коэффициент равен 1, то это строго прямая (с точностью используемых типов данных).
138. Многоугольник на плоскости задан целочисленными координатами своих n вершин в декартовой системе координат. Требуется найти число точек с целочисленными координатами, лежащих внутри многоугольника (не на границе). Стороны многоугольника друг с другом не соприкасаются (за исключением соседних — в вершинах) и не пересекаются.
139. Герой компьютерной игры, обладающий силой в 25 баллов, находится в круглом зале, из которого ведут 10 закрытых дверей. За каждой дверью героя ждет либо магический артефакт, дарующий силу от 10 до 80 баллов, либо монстр, имеющий силу от 5 до 100 баллов, с которым герою нужно сразиться. Битву выигрывает персонаж, обладающий наибольшей силой; если силы равны, побеждает герой.
     1. Организовать ввод информации о том, что находится за дверями, либо заполнить ее, используя генератор случайных чисел.
     2. Вывести эту самую информацию на экран в понятном табличном виде.
     3. Посчитать, за сколькими дверями героя ждет смерть. Рекурсивно.
     4. Вывести номера дверей в том порядке, в котором следует их открывать герою, чтобы остаться в живых, если такое возможно.