Семакин И.Г., Шестаков А.П. Основы программирования
Подождите немного. Документ загружается.
31.
Сформировать массив простых чисел не больших заданного
натурального числа N.
32.
Сформировать массив простых множителей заданного числа.
В
1.
Дан одномерный массив А\Щ. Найти
тах(а
2
, а
4
, ..., а
2к
)
+
ттЦ, а
у
...,
а
2к+1
).
2.
Дана последовательность действительных чисел а
х
,
а
2
,...,
а„.
Указать те ее элементы, которые принадлежат отрезку [с, d].
3.
Дана последовательность целых положительных чисел. Найти
произведение только тех из них, которые больше заданного числа
М. Если таких чисел нет, то выдать сообщение об этом.
4.
Последовательность а
ь
а
2
, ..., а
п
состоит из нулей и единиц.
Поставить в начало этой последовательности нули, а затем единицы.
5.
Даны действительные числа а
ь
а
2
, ...,
а„.
Среди них есть по-
ложительные и отрицательные. Заменить нулями те числа, вели-
чина которых по модулю больше максимального числа
(|а,| > max
{а,,
а
ъ
..., а„}).
6. Даны действительные числа а
и
а
ъ
...,
а„.
Найти
тах(а,+а
2
„, а
2
+
а
1п
_
и
..., a
n
+
a„
+i
).
7.
В последовательности действительных чисел а
и
а
2
,...,
а„есть
только положительные и отрицательные элементы. Вычислить
произведение отрицательных элементов Р
х
и произведение поло-
жительных элементов Р
2
. Сравнить модуль Р
2
с модулем Р
ь
ука-
зать,
какое из произведений по модулю больше.
8.
Дан массив действительных
чисел.
Среди них есть
равные.
Найти
его первый максимальный элемент и заменить его нулем.
9. Дана последовательность действительных чисел а
х
<а
2
<...<а
п
Вставить в нее действительное число b так, чтобы последователь-
ность осталась неубывающей.
10.
Даны целые положительные числа а
ь
а
2
,...,
а„.
Найти среди
них те, которые являются квадратами некоторого числа т.
11.
Дана последовательность целых чисел а,, а
2
, ...,
а„.
Образо-
вать новую последовательность, выбросив из исходной те члены,
которые равны min(a
1
, a
2
, ..., а„).
12.
У прилавка магазина выстроилась очередь из п покупателей.
Время обслуживания /-го покупателя равно /,• (/ = 1, ..., п). Опре-
делить время
Cj
пребывания /-го покупателя в очереди.
13.
«Суперзамок». Секретный замок для сейфа состоит из 10
расположенных в рад ячеек, в которые надо вставить игральные
кубики. Но дверь открывается только в том случае, когда в любых
340
трех соседних ячейках сумма точек на передних гранях кубиков
равна 10. (Игральный кубик имеет на каждой грани от
1
до 6 то-
чек.) Напишите программу, которая разгадывает код замка при
условии, что два кубика уже вставлены в ячейки.
14.
В массиве целых чисел с количеством элементов п найти
наиболее часто встречающееся число. Если таких чисел несколь-
ко,
то определить наименьшее из них.
15.
Каждый солнечный день улитка, сидящая на дереве, под-
нимается вверх на 2 см, а каждый пасмурный день опускается
вниз на 1 см. В начале наблюдения улитка находилась в А см от
земли на 5-метровом дереве. Имеется 30-элементный массив,
содержащий сведения о том, был ли соответствующий день на-
блюдения пасмурным или солнечным. Написать программу, оп-
ределяющую местоположение улитки к концу 30-го дня наблю-
дения.
16.
Дан целочисленный массив с количеством элементов
п.
Сжать
массив, выбросив из него каждый второй элемент.
Примечание.
Дополнительный массив не использовать.
17.
Задан массив, содержащий несколько нулевых элементов.
Сжать его, выбросив эти элементы.
18.
Задан массив с количеством элементов N. Сформировать два
массива: в первый включить элементы исходного массива с чет-
ными номерами, а во второй — с нечетными.
19.
Дана последовательность целых чисел а
х
,
а
2
,...,
а
п
. Указать
пары чисел а„ aj, таких, что
я,-
+ Еа
}
= т.
20.
Дана последовательность целых чисел а
и
а
2
, ..., а„. Наи-
меньший член этой последовательности заменить целой частью
среднего арифметического всех членов, остальные члены оста-
вить без изменения. Если в последовательности несколько наи-
меньших членов, то заменить последний по порядку.
21.
Даны две последовательности целых чисел а
и
а
2
,...,
а„
и Ь
и
Ь
2
,
...,
Ь„.
Преобразовать последовательность Ь
и
Ъ
ъ
...,
Ь„
по сле-
дующему правилу: если а,- < 0, то
Ь-,
увеличить в 10 раз, в против-
ном случае
Ь,-
заменить нулем (/ = 1, 2, ..., п).
22.
Дана последовательность действительных чисел а
х
,
а
2
,...,
а
п
.
Требуется домножить все члены последовательности а
х
,
а
2
,...,
а
п
на квадрат ее наименьшего члена, если а
к
> 0, и на квадрат ее
наибольшего члена, если а
к
< 0 (1 < к
<
п).
23.
Даны координаты п точек на плоскости: (Х
и
Y
x
),...,
(Х„,
Y„)
(п
<
30). Найти номера пары точек, расстояние между которыми
наибольшее (считать, что такая пара единственная).
24.
Дана последовательность п различных целых чисел. Найти
сумму ее членов, расположенных между максимальным и мини-
мальным значениями (в сумму включить и оба этих числа).
25.
Японская радиокомпания провела опрос
./V
радиослушате-
лей по вопросу: «Какое животное вы связываете с Японией и
341
японцами?». Составить программу получения к наиболее часто
встречающихся ответов и их долей (в процентах).
26.
Дан массив, состоящий из п натуральных чисел. Образовать
новый массив, элементами которого будут элементы исходного,
оканчивающиеся на цифру к.
27.
Дан массив целых чисел. Найти в этом массиве минималь-
ный элемент от и максимальный элемент М. Получить в порядке
возрастания все целые числа из интервала (от; Л/), которые не
входят в данный массив.
28.
Даны действительное число х и массив А
[я].
В массиве найти
два члена, среднее арифметическое которых ближе всего к х.
29.
Даны две последовательности а
ъ
а
2
, •••, а„ и Ь^ Ь
2
, ..., Ь
т
(от < л). В каждой из них члены различны. Верно ли, что все члены
второй последовательности входят в первую последовательность?
30.
Напишите программу, входными данными которой являет-
ся возраст п человек. Программа подсчитывает количество людей,
возраст которых находится в интервале 10 лет, а именно:
0 — 9 лет;
10—19 лет;
20
— 29
лет и т.д.
Напечатать результаты расчетов в удобочитаемой форме.
31.
Дан массив Х[Щ целых чисел. Не используя других масси-
вов,
переставить его элементы в обратном порядке.
32.
Коэффициенты многочлена хранятся в массиве A[N] (N
—
натуральное число, степень многочлена). Вычислить значение этого
многочлена в точке х
(т.
е.
a[N\-x
N
+ ... + а[1]-х+ я[0]). Вычислить
значение его производной в той же точке.
33.
В массивах
А[К\
и B[L] хранятся коэффициенты двух мно-
гочленов степеней К и L. Поместить в массив С[М] коэффици-
енты их произведения. (Числа К, L, М— натуральные, М= K+L;
элемент массива с индексом / содержит коэффициент при х в
степени /.)
34.
Вывести информацию о наибольшем, наименьшем и наи-
менее удаленном от среднего арифметического членах последова-
тельности вещественных чисел.
35.
Задан массив А. Определить значение к, при котором сумма
И[1]+Л[2] + ...+Л[£] ~(A[k+l]
+
...+A[N])\ минимальна (т.е. мини-
мален модуль разности сумм элементов в правой и левой части,
на которые массив делится этим к).
С
1.
В одномерном массиве все отрицательные элементы перемес-
тить в начало массива, а остальные
—
в конец с сохранением поряд-
ка следования. Дополнительный массив заводить не разрешается.
342
2.
В одномерном массиве с четным количеством элементов (2N)
находятся координаты
./V
точек плоскости. Они располагаются в
следующем порядке: х
ь
у
и
х
2
, у
2
, х
3
, у
3
и т.д.
Определить минимальный радиус окружности с центром в на-
чале координат, которая содержит все точки.
3.
В одномерном массиве с четным количеством элементов (2N)
находятся координаты N точек плоскости. Они располагаются в
следующем порядке: х
и
у
и
х
2
, у
2
, х
3
, у
3
и т.д.
Определить кольцо с центром в начале координат, которое
содержит все точки.
4.
В одномерном массиве с четным количеством элементов (2N)
находятся координаты N точек плоскости. Они располагаются в
следующем порядке: х
ь
у
и
х
2
, у
2
, х
3
, у
3
и т.д. (x
h
у, — целые).
Определить номера точек, которые могут являться вершинами
квадрата.
5.
В одномерном массиве с четным количеством элементов (2N)
находятся координаты N точек плоскости. Они располагаются в
следующем порядке: х
ь
у
ь
х
2
, у
2
, х
3
, у
3
и т.д.
Определить номера точек, которые могут являться вершинами
равнобедренного треугольника.
6. Задан целочисленный массив размерности N. Есть ли среди
элементов массива простые числа? Если да, то вывести номера
этих элементов.
7.
Дана последовательность целых чисел. Найти количество
различных чисел в этой последовательности.
8. Дан массив из п четырехзначных натуральных чисел. Вывести
на экран только те, у которых сумма первых двух цифр равна
сумме двух последних.
9. Даны две последовательности целых чисел а
и
а
2
, ..., а„ и
b\, b
2
, ...,
Ь„.
Все члены последовательностей
—
различные числа.
Найти, сколько членов первой последовательности совпадает с
членами второй последовательности.
10.
Дан целочисленный массив
А[п],
среди элементов есть оди-
наковые. Создать массив из различных элементов А[п].
11.
На плоскости п точек заданы своими координатами, и так-
же дана окружность радиуса R с центром в начале координат. Ука-
зать множество всех треугольников с вершинами в заданных точ-
ках, пересекающихся с окружностью; множество всех треуголь-
ников, содержащихся внутри окружности.
12.
В одномерном массиве с четным количеством элементов (2N)
находятся координаты Лоточек плоскости. Они располагаются в
следующем порядке: х
и
у
ь
х
2
, у
2
, х
3
, у
3
и т.д. Найти номера наи-
более и наименее удаленных друг от друга точек.
13.
В одномерном массиве с четным количеством элементов (27V)
находятся координаты N точек плоскости. Они располагаются в
следующем порядке: х
ь
у
и
х
ъ
у
2
, х
г
, у
г
и т.д.
343
Определить три точки, являющиеся вершинами треугольника, для
которого разность точек вне его и внутри является минимальной.
14.
Некоторое число содержится в каждом из трех целочислен-
ных неубывающих массивов х[1]
<
... <х[р], у[1]< ... <y[q],
г[1]
<
... <
z[r].
Найти одно из таких чисел. Число действий должно
быть порядка p
+ q +
r.
15.
Выяснить, есть ли одинаковые числа в каждом из трех цело-
численных неубывающих массивов х[\]
<
...
<
х[р], у[\]
<
...
<
у[д],
г[1] < ... < z[r]. Найти одно из таких чисел или сообщить о его от-
сутствии.
16.
Дана целочисленная таблица
А[п].
Найти наименьшее число
А'элементов, которые можно выкинуть из данной последователь-
ности, так чтобы осталась возрастающая подпоследовательность.
17.
Разделить массив на две части, поместив в первую элемен-
ты,
большие среднего арифметического их суммы, а во вторую
—
меньшие (части не сортировать).
Сортировка массивов
1.
Заданы два одномерных массива с различным количеством
элементов и натуральное число к. Объединить их в один массив,
включив второй массив между к-м и (к+1)-м элементами перво-
го,
при этом не используя дополнительный массив.
2.
Даны две последовательности а
х
<
а
2
<
...
< а„
и
Ь
х
<
Ь
2
<
...
<
Ъ
т
.
Образовать из них новую последовательность чисел так, чтобы
она тоже была неубывающей. Примечание. Дополнительный мас-
сив не использовать.
3.
Сортировка выбором. Дана последовательность чисел
а
и
а
2
, ..., а
п
. Требуется переставить элементы так, чтобы они
были расположены по убыванию. Для этого в массиве, начиная с
первого, выбирается наибольший элемент и ставится на первое
место, а первый — на место наибольшего. Затем, начиная со
второго, эта процедура повторяется. Написать алгоритм сорти-
ровки выбором.
4.
Сортировка обменами. Дана последовательность чисел
а
и
а
2
, •••,Й'„. Требуется переставить числа в порядке возрастания.
Для этого сравниваются два соседних числа
а,-
и о
/+1
. Если щ
>
a
i+u
то делается перестановка. Так продолжается до тех пор, пока все
элементы не станут расположены в порядке возрастания. Соста-
вить алгоритм сортировки, подсчитывая при этом количества пе-
рестановок.
5.
Сортировка вставками. Дана последовательность чисел
а
и
а
2
, ...,
а„.
Требуется переставить числа в порядке возрастания.
Делается это следующим образом. Пусть а
и
а
ъ
...,
д,-
—
упорядо-
ченная последовательность,
т.
е.
а
х
<
а
2
<
...
<
я,. Берется следующее
число a,+
i
и вставляется в последовательность так, чтобы новая
344
последовательность была тоже возрастающей. Процесс произво-
дится до тех пор, пока все элементы от / +1 до п не будут пере-
браны. Примечание. Место помещения очередного элемента в от-
сортированную часть производить с помощью двоичного поиска.
Двоичный поиск оформить в виде отдельной функции.
6. Сортировка Шелла. Дан массив п действительных чисел. Тре-
буется упорядочить его по возрастанию. Делается это следующим
образом: сравниваются два соседних элемента я,- и а
/+1
. Если
а-,
< а
1+и
то продвигаются на один элемент вперед. Если д,- > а
ж
,
то производится перестановка и сдвигаются на один элемент на-
зад.
Составить алгоритм этой сортировки.
7.
Пусть даны две неубывающие последовательности действи-
тельных чисел а\
<
а
2
< ...
<
а
п
и
Ь
х
<
Ь
2
< ...
<
Ь
т
.
Требуется указать
те места, на которые нужно вставлять элементы последовательно-
сти b
u
b
2
, ..., Ь
т
в первую последовательность так, чтобы новая
последовательность оставалась возрастающей.
8. Даны дроби —, —,..., in- (p
h
о,
—
натуральные). Соста-
вить программу, которая приводит эти дроби к общему знамена-
телю и упорядочивает их в порядке возрастания.
9. Алгоритм фон Неймана. Упорядочить массив а
х
, а
2
, ...,
а„
по
неубыванию с помощью алгоритма сортировки слияниями:
1) каждая пара соседних элементов сливается в одну группу из
двух элементов (последняя группа может состоять из одного эле-
мента);
2) каждая пара соседних двухэлементных групп сливается в одну
четырехэлементную группу и т.д.
При каждом слиянии новая укрупненная группа упорядочи-
вается.
10.
Сортировка подсчетом. Выходной массив заполняется зна-
чениями
—
1.
Затем для каждого элемента определяется его ме-
сто в выходном массиве путем подсчета количества элементов
строго меньших данного. Естественно, что все одинаковые эле-
менты попадают на одну позицию, за которой следует ряд зна-
чений
—
1.
После этого оставшиеся в выходном массиве пози-
ции со значением —1 заполняются копией предыдущего зна-
чения.
11.
«Хитрая» сортировка. Из массива путем однократного про-
смотра выбирается последовательность элементов, расположен-
ных в порядке возрастания, переносится в выходной массив и
заменяется во входном на
—1.
Затем оставшиеся элементы вклю-
чаются в полученную упорядоченную последовательность мето-
дом «погружения», когда очередной элемент путем ряда обменов
«погружается» до требуемой позиции в уже упорядоченную часть
массива.
345
6.8. Задачи по теме «Двумерные массивы»
6.8.1.
Задачи на формирование массивов
В задачах 1—12 сформировать квадратную матрицу порядка и
по заданному образцу:
1.
П 2 3
п я-
1
я-2
1 2 3
л л-1 я- 2
я п-
1
я-2
(я — четное).
1
л
(0
0
0
0
я
0
0
0
л-1
0
0 •
0 •
0 •
0 •
0 •
•ООП
•020
•300
•000
•000
л 0 0
0 л-1 0
0 0 я-2
0
0
0
0
0
0
••• 0 0 0^
•••0
0 0
-000
-020
- 0 0 1
у
(
4.
V
1-2 0 0
0 2-3 0
О 0 3-4
О
О
О
О
О (я-1)л
О О
О
'
О
О
О
л(л
+1)
5.
(\ 1 1 •
10 0-
10 0-
10 0-
111-
V
• 1 1 П
•001
•001
•001
• 111
)
6.
1 1
2
2
3
3
л-1 л-1 О
л О О
... 1
- 2
••• 3
... о
- 0
1
2
0
0
0
п
0
0
0
0
)
7.
а
0
0
0
1
1
1
0
1
1
1 •
1 •
1 •
1 •
1 •
• 1
• 1
• 1
• 1
• 1
1
1
0
1
1
п
0
0
0
1
(\
1
1
1
1
0
1
1
1
0
0
0
1
0
0
•• 0
•• 0
•• 1
•• 0
•• 0
0
1
1
1
0
V)
1
1
1
1
346
9.
л О О
и-1 л О
и-2 л-1 и
3 4
2 3
О 0 0^
0 0 0
0 0 0
и-1 л 0
л-2 и-1 и
10.
1 2 3
2 3 4
3 4 5
и-1 и 0
и 0 0
л-2 л-1 и^
л-1 и 0
и 0 0
12.
( 1
2
3
0 0
0 0
3
2
1
л-1 и-2 и-3
л и-1 и-2
V
11.
П 0 0
0 2 0
0 0 3
0 2 0
v
l 0 0
0 0 и^
0 и-1 0
л-2 0 0
0 л-1 0
0
0 и
и-2 л-1 и
л-2 и-2 и-1
л-4 и-3 и-2
13.
Построить квадратную матрицу порядка 2л:
1 1 ..
1 1 ..
1 1 ..
3 3..
3 3..
3 3 ..
.12 2
.12 2
1 2 2
. 34 4
. 34 4
. 34 4
... 2
... 2
2 2
... 4
... 4
... 4
347
14.
Дано действительное число
х.
Получить квадратную матрицу
порядка п + 1:
1 х х"
х О О
х
2
О О
X""
1
О О
х" х"-
1
х"-
2
х"'
2
х""
1
х"
Л
О
О
О
О
,л-2
О 0 х
х
2
х 1
15.
Даны действительные числа а
ъ
а
2
,...,
а„.
Получить квадрат-
ную матрицу порядка п:
а, а
1
а,
а-, а-, а
л
а-, а
л
а,
h-i а„ а
х
а„ а, а,
а„-2 а„-1 а„
а
п
-\ а
п
-г «I
а„ а, а
2
а
п-4
а
п-Ъ
а
п-1
а
п-Ъ
а
п-2
а
п-\
16.
Получить матрицу:
1
0
0
0
2
1
0
0
3 .
2 .
1 .
0 .
. 9
. 8
. 7
. 0
10
1
9
8
1
У
17.
Получить матрицу:
(\
0
0
I
1
0 .
1 .
1 .
0 .
. 0
. 1
. 1
. 0
п
0
0
1
J
348
18.
Составить программу, которая заполняет квадратную мат-
рицу порядка и натуральными числами 1, 2, 3, ..., л
2
, записывая
их в нее «по спирали».
Например, для п = 5 получаем следующую матрицу:
м
16
15
14
13
2
17
24
23
12
3
18
25
22
11
4
19
20
21
10
5^
6
7
8
9
19.
Дана действительная квадратная матрица порядка 2л. Полу-
чить новую матрицу, переставляя ее блоки размера их
л
по часо-
вой стрелке, начиная с блока в левом верхнем углу.
20.
Дана действительная квадратная матрица порядка 2л. Полу-
чить новую матрицу, переставляя ее блоки размера лхл крест-
накрест.
21.
Дан линейный массив х
и
х
2
, ..., х„_
1;
х
п
. Получить действи-
тельную квадратную матрицу порядка п:
Х
п-1
"J
22.
Дан линейный массив х
{
,
х
2
,...,
х„_
ь
х
п
. Получить действи-
тельную квадратную матрицу порядка п:
1 1
xl
Л.
j Л]
1 1
Х
п-\
„я-1 „и-1
л
п-\
л
п
23.
Получить квадратную матрицу порядка п:
1
п + 1
2л+ 1
-1)л
+
1
2
п +
2
2л+
2
(л-1)л
+
2
.
. л-1 л
.
2л
-
1
2л
.
Зл
-
1
Зл
. л
2
-1 л
2
349