Одномерные массивы
Пример 1. Даны натуральное число n и элементы одномерного массива a1,a2,...,an. Поменять местами первый отрицательный и последний элементы массива.
#include <stdio.h>
void main()
{
const n=5;
float a[n+1], r;
int i;
for (i=1;i<=n;i++)
{ printf("a[%i]=",i); scanf("%f",&a[i]); }
i=0;
do i=i+1;
while (a[i]>=0&&i<n);
if (a[i]>=0) printf("Отрицательного элемента нет!");
else
{
r=a[i]; a[i]=a[n]; a[n]=r;
for (i=1;i<=n;i++) printf("a[%i]=%f\n",i,a[i]);
}
}
Пример 2. Бинарный поиск. Пусть элементы массива x1,x2,...,xn упорядочены по возрастанию (xi<xi+1). Найти номер элемента равного p.
#include <stdio.h>
void main()
{
const n=5;
int x[n+1], i, a, b, mid, p;
for (i=1;i<=n;i++)
{ printf("x%i=",i); scanf("%i",&x[i]); }
printf("p="); scanf("%i",&p);
a=1; b=n;
while (a<=b)
{ mid=(a+b)/2;
if (x[mid]==p) break;
if (x[mid]<p) a=mid+1; else b=mid-1;
}
if (x[mid]==p) printf("i=%i\n",mid); else printf("Not found\n");
}
Задания для решения на компьютере
A. В целочисленной последовательности из n чисел a0,a1,...,an-1 есть нулевые элементы. Создать массив из номеров нулевых элементов. Существование нулевых элементов гарантируется.
B. Дан одномерный массив целых чисел a1,a2,...,an. Найти min(a1,a3,...,a2k+1) + max(a2,a4,...,a2k), т.е. сумму минимального элемента элементов стоящих на нечетных местах и максимального элемента элементов стоящих на четных местах.
C. Дана последовательность n действительных чисел a0,a1,...,an-1. Выяснить, будет ли она возрастающей последовательностью. Ответ “Yes” или “No”.
D. Дана последовательность целых n чисел a1,a2,...,an. Определить количество инверсий.
Определение. Говорят, что два числа образуют в перестановке инверсию, если большее число стоит перед меньшей.
E. Даны натуральные числа n, M и целые числа a1,a2,...,an. Все элементы массива разные. Удалить из массива ближайший элемент к заданному числу M. Если их несколько, удалить последний.
Указание. Для того, чтобы решить данную задачу, необходимо:
· найти номер соответствующего элемента – k;
· сдвинуть все элементы, начиная с (k+1)-го, на один элемент влево;
· уменьшить n на единицу.
F. Сортировка выбором. Дана последовательность действительных чисел a1,a2,...,an. Требуется переставить элементы так, чтобы они были расположены по убыванию. Для этого в массиве, начиная с первого, выбирается наибольший элемент и ставится на первое место, а первый — на место наибольшего. Затем, начиная со второго, эта процедура повторяется. Написать алгоритм сортировки выбором.
G. Бинарный поиск. Для значений xi, в результате эксперимента, получены значения функции yi=y(xi), i=1,...,n. Значения xi упорядочены по возрастанию и не содержит одинаковых элементов. Найти элемент xk равный заданному числу p (x1≤p≤xn) и напечатать соответствующее значение yk. Если такого элемента нет, то найти интервал (xi,xi+1) в котором он лежит и интервал возможного значения y. Данные вещественного типа.
Примеры
| Входные данные | Выходные данные |
| 2.24 4.5 7 9 20 123.1 124 102.12 100 201 | 102.12 |
| 2.24 4.5 7 9 20 123.1 124.2 102.2 100.5 201.12 | 2.24 4.5 123.1 124.2 |
Задания для самостоятельной работы
Задания для самостоятельной работы
1.1. Дана последовательность из n натуральных чисел a1, a2,..., an. Создать массив из четных чисел этой последовательности. Если таких чисел нет, то вывести сообщение “NO”.
1.2. Вычислите площадь произвольного выпуклого n – угольника, заданного координатами своих вершин (xi, yi), i=1,2,…,n, в порядке обхода по часовой стрелке, разбив многоугольник на треугольники. Никакие три соседние вершины не лежат на одной прямой.
2.1. Даны n различных действительных числа a1, a2,..., an. Поменять местами наибольший и наименьший элементы. Напечатать полученный результат.
2.2. Даны координаты n точек (xi, yi) с целыми значениями, i=1,2,…,n (4≤n, | xi |,| yi |≤100). Найти координаты вершин одного из квадратов, из заданного множества точек. Существование гарантируется.
3.1. Дана последовательность из n действительных чисел a1, a2,..., an и число M. Заменить все ее члены, большие данного числа M, этим числом. Напечатать количество замен k и полученный результат.
3.2. Даны координаты точек на числовой оси x0, x1,..., xn-1. Указать наименьшую длину числовой оси, содержащую все эти числа.
4.1. Дан массив действительных чисел, размерность которого N. Найти количество нулевых элементов, сумму положительных элементов и произведение отрицательных элементов. Гарантируется существование всех указанных элементов.
4.2. Даны координаты n точек (xi, yi), i=1,2,…,n (n≥2). Найти номера самых удаленных друг от друга точек и наименее удаленных друг от друга точек. Если их несколько напечатать любую из них.
5.1. Даны целые числа a1, a2,..., an (n≤1000). Вывести на печать только те числа, для которых выполняется ai < i. Если таких чисел нет, напечатать 1001.
5.2. Даны координаты n точек (xi, yi), i=1,2,…,n (n≥1, xi + yi≠0). Определить кольцо с центром в начале координат, которое содержит все точки. Напечатать радиусы внутренней и наружной окружностей найденного кольца.
6.1. Даны натуральные числа a1, a2,..., an. Указать те, у которых остаток от деления на M равен L. Если таких чисел нет, напечатать -1.
6.2. Даны координаты n точек (xi, yi), i=1,2,…,n (n≥3). Определить номера вершин треугольника, для которого разность числа точек вне его и внутри является минимальной.
7.1. Задан одномерный массив из 2×n вещественных чисел. Обменять значениями a1 и a2, a3 и a4 и т. д. Результат вывести на экран.
7.2. Вычислите периметр произвольного выпуклого n – угольника, заданного координатами своих вершин (xi, yi), i=1,2,…,n, в порядке обхода по часовой стрелке. Найти периметр многоугольника.
8.1. При поступлении в вуз абитуриенты, получившие «двойку» на первом экзамене, ко второму не допускаются. В массиве A[n] записаны оценки экзаменующихся, полученные на первом экзамене. Подсчитать, сколько человек не допущено ко второму экзамену.
8.2. Пригодность детали оценивается по размеру B, который должен соответствовать интервалу (A - ε, A + ε). Определить, имеются ли в партии из N деталей бракованные. Если да, то подсчитать их количество, иначе выдать отрицательный ответ.
9.1. Дан целочисленный массив с количеством элементов n. Напечатать те его элементы, индексы которых являются степенями двойки (1, 2, 4, 8, 16,...).
9.2. Задан выпуклый n – угольник координатами своих вершин (xi, yi), i=1,2,…,n, в порядке обхода по часовой стрелке. Вычислите номера двух вершин наиболее удаленных друг от друга.
10.1. Дана последовательность целых положительных чисел. Найти произведение только тех чисел, которые меньше заданного числа М. Если таких нет, то выдать “ 0 ”.
10.2. Даны координаты n точек (xi, yi), i=1,2,…,n (n≥1). Указать номера тех точек, которые принадлежат окружности с центром в точке (x, y) и радиусом R.
11.1. Последовательность a1, a2,..., an состоит из нулей и единиц. Поставить в начало этой последовательности нули, а затем единицы.
11.2. Даны координаты n точек (xi, yi), i=1,2,…,n (n≥1). Указать номера тех точек, которые принадлежат прямоугольнику с координатами левого верхнего узла (a, b) и правого нижнего угла (c, d).
12.1. У вас есть доллары. Вы хотите обменять их на рубли. Есть информация о стоимости купли-продажи в банках города. В городе N банков. Составьте программу, определяющую, какой банк выбрать, чтобы выгодно обменять доллары на рубли. Напечатать номер банка совпадающего с порядком ввода. Если их несколько, напечатать любой из них.
12.2. Даны координаты n точек на плоскости: (x1, y1),...,(xn, yn) (n ≥ 2). Найти номер точки, расстояние которого до точки (x, y) наибольшее. Если их несколько, напечатать наибольший номер.
13.1. Дана последовательность из n натуральных чисел a1, a2,..., an. После чисел равных 0 вставить число равное M.
13.2. Даны координаты n точек (xi, yi), i=1,2,…,n (n≥3). Определить номера точек, которые могут являться вершинами равнобедренного треугольника.
14.1. В последовательности действительных чисел a1, a2,..., an есть только положительные и отрицательные элементы. Вычислить произведение отрицательных элементов P1 и произведение положительных элементов P2. Что больше? Напечатать “ P1” или “ P2” или “ P1 = P2 ” в зависимости от результата.
14.2. На плоскости n точек заданы своими координатами (xi, yi), i=1,2,…,n и дана окружность радиуса R с центром в начале координат. Указать множество (номера) всех треугольников с вершинами в заданных точках и содержащихся внутри окружности.
15.1. Даны целые положительные целые числа a1, a2,..., an. Найти среди них те, которые являются квадратами некоторого числа m.
15.2. На плоскости n точек заданы своими координатами (xi, yi), i=1,2,…,n. Определите номера точек наиболее близко расположенных к одному из осей координат.
16.1. Дана последовательность действительных чисел a1, a2,..., an. Вставить действительное число b в нее так, чтобы последовательность осталась неубывающей.
16.2. На плоскости n точек заданы своими координатами (xi, yi), i=1,2,…,n. Определите номера точек сумма расстояний от которых до осей координат наименьшее.
17.1. Дана последовательность целых чисел a1, a2,..., an. Образовать новую последовательность, выбросив из исходной последовательности те члены, которые равны min(a1, a2,..., an).
17.2. На плоскости n точек заданы своими координатами (xi, yi), i=1,2,…,n. Найти треугольник с максимальной площадью с вершинами в заданных точках. Напечатать площадь и номера вершин. Если их несколько, то напечатать любой из них.
18.1. В массиве целых чисел с количеством элементов n найти наиболее часто встречающееся число. Если таких чисел несколько, то определить наименьшее из них.
18.2. На плоскости n точек заданы своими координатами (xi, yi), i=1,2,…,n. Найти четырехугольник с максимальной площадью с вершинами в заданных точках. Напечатать площадь и номера вершин. Если их несколько, то напечатать любой из них.
19.1. В массиве A[0..n] найти наибольшее число одинаковых подряд стоящих элементов.
19.2. Прямая на плоскости может быть задана уравнением a x + b y + c = 0, где a и b одновременно не равные нулю. Пусть даны коэффициенты нескольких прямых ai, bi, ci, i=1,...,n. Определите, имеются ли среди этих прямых совпадающие или параллельные. Ответ “ YES ” или “ NO ”.
20.1. В массиве A[0..n] найти наиболее длинную цепочку, состоящую из одних нулей.
20.2. Произвольный выпуклый многоугольник задан координатами своих вершин (xi, yi), i=1,2,…,n. Найдите самую короткую диагональ данного многоугольника (номера вершин). Если их несколько, то напечатать любой из них.
21.1. Даны действительные числа a1, a2,..., an. Среди них есть только положительные и отрицательные. Заменить нулями те числа, величина которых по модулю больше максимального числа (| ai |>max(a1, a2,..., an)).
21.2. Пусть даны окружности с центром в точке (xi, yj) и радиусом ri. Найдите окружность содержащий все заданные окружности. Напечатать три числа x, y и r – центр и радиус найденной окружности.
22.1. Даны целые числа a1, a 2,..., an. Наименьший член этой последовательности заменить целой частью среднего арифметического всех членов, остальные члены оставить без изменения. Если в последовательности несколько наименьших членов, то заменить последний по порядку.
22.2. Пусть даны вещественные числа a1, a2,..., a2n (a2i-1 ≤ a2i+1, i=1,2,…,n-1). Эти точки определяют n интервалов числовой оси (a1, a2), (a3, a4),...,(a2n-1, a2n). Является ли интервалом объединение этих интервалов? Если да, то указать концы объединенного интервала. В противном случае напечатать “ -1 ”.
23.1. Даны целые числа a1, a2,..., an и b1, b2,..., bn. Преобразовать последовательность b1, b2,..., bn по правилу: если ai < 0, то bi увеличить в 10 раз, иначе bi заменить нулем (i = 1, 2,..., n).
23.2. Пусть даны вещественные числа a1, a2,..., a2n. Эти точки определяют n интервалов числовой оси (a1, a2),(a3, a4),...,(a2n-1, a2n). Имеются ли точки числовой оси, принадлежащие по крайней мере двум каким-нибудь из данных интервалов? Если да, то вывести любую из этих точек. В противном случае напечатать “ -1 ”.
24.1. Даны действительные числа a1, a2,..., an. Требуется умножить все члены последовательности a1, a2,..., an, на квадрат ее наименьшего члена, если ak > 0, и на квадрат ее наибольшего члена, если ak < 0 (1 ≤ k ≤ n).
24.2. Пусть числовая прямая разбита на произвольные отрезки точками x1, x2,..., xn. Выясните, какому из отрезков принадлежит данная точка x. Напечатать концы отрезка.
25.1. Дана последовательность из n различных целых чисел. Найти сумму ее членов, расположенных между максимальным и минимальным значениями (в сумму включить и оба этих числа).
25.2. Прямая на плоскости может быть задана уравнением a x+ b y+ c =0, где a и b одновременно не равные нулю. Пусть даны коэффициенты нескольких прямых ai, bi, ci (i=1,...,n) и a x+ b y+ c =0. Определите, имеются ли среди прямых ai x+ bi y+ ci =0 параллельная a x+ b y+ c =0. Если есть напечатайте номер одной из прямой, а если нет – “ -1 ”.
26.1. Дан массив, состоящий из n натуральных чисел. Образовать новый массив, элементами которого будут элементы исходного, оканчивающиеся на цифру k.
26.2. На плоскости заданы n точек своими координатами (xi, yi), i=1,2,…,n. Найдите номера двух точек лежащих в I-й и IV-й четвертях и наиболее близко расположенные друг к другу.
27.1. Дана последовательность из n натуральных чисел a1, a2,..., an. После чисел кратных 7 вставить число равное p.
27.2. Произвольный выпуклый многоугольник задан координатами своих вершин (xi, yi), i=1,2,…,n. Найдите номер вершины наиболее близкую начале координат.
28.1. У прилавка магазина выстроилась очередь из n покупателей. Время обслуживания i-того покупателя равно ti (i =1,....,n). Определить время Ci пребывания i-го покупателя в очереди.
28.2. Произвольный выпуклый многоугольник задан координатами своих вершин (xi, yi), i=1,2,…,n. Найдите номер вершины наиболее близкую заданной точке (x, y).
29.1. Дан целочисленный массив с количеством элементов n. Напечатать те его элементы, первая цифра которых равна 1.
29.2. На плоскости заданы n точек своими координатами (xi, yi), i=1,2,…,n. Найдите в IV четверти точку (x, y) наиболее близкую начале координат.
30.1. Дана последовательность целых положительных чисел. Найти номер числа ближайшего к заданному числу М.
30.2. Каждый солнечный день улитка, сидящая на дереве, поднимается вверх на 2 см, а каждый пасмурный день опускается вниз на 1 см. В начале наблюдения улитка находилась в A см от земли на B – метровом дереве. Имеется 30 – элементный массив, содержащий сведения о том, был ли соответствующий день наблюдения пасмурным или солнечным. Написать программу, определяющую местоположение улитки к концу 30 -го дня наблюдения.