АЛГОРИТМЫ И ПРОГРАММИРОВАНИЕ
массив элемент массива индекс элемента значение элемента описание элемента заполнение массива вывод массива обработка массива последовательный поиск сортировка
Одномерный массив 6 3 4 -2 0 1 9 -5 7 9 8 7 6 5 4 3 2 1 Значение элемента массива Индекс элемента массива МАССИВ Массив - это набор элементов одного типа, которым присвоено общее имя. Каждый элемент массива имеет свой номер ( индекс ). Решение разнообразных задач, связанных с обработкой массивов, базируется на решении типовых задач: суммирование элементов массива; поиск элемента с заданными свойствами; сортировка массива.
10 50 1 3 50 14 21 50 10 21 Здесь: трём равен 4-й элемент десяти равны 1-й и 9-й элементы нет элемента, равного 12
ОПИСАНИЕ МАССИВА var < имя_массива >: array [< мин_знач_индекса >.. < макс_знач_индекса >] of < тип_элементов >; var A : array [1..10] of integer ; const B : array [1..5] of integer = (4, 2, 3, 5, 7); Тип элементов массива Имя массива Конечное значение индекса Начальное значение индекса Значение 1-го элемента массива Массив B с постоянными значениями описан в разделе описания констант.
СПОСОБЫ ЗАПОЛНЕНИЯ МАССИВА 1 способ. Ввод каждого значения с клавиатуры: for i:=1 to 10 do read (A[i ]); 2 способ. С помощью оператора присваивания - по формуле: for i:=1 to 10 do A[i ]:=i; 3 способ. С помощью оператора присваивания - случайными числами: for i:=1 to 10 do A[i ]:= random (100);
ВЫВОД МАССИВА 1 способ. Элементы массива можно вывести в строку, разделив их пробелом: for i:=1 to 10 do write (A[i ], ' '); 2 способ. Вывод с комментариями: for i:=1 to 10 do writeln ( 'A[', i, ']=', A[i ]); 45 21 56 43 83 56 69 34 28 15 А [1 ]=4 А [2 ]=1 А [3 ]=6 А [4 ]=3 А [5 ]=8 А [6 ]=5 А [7 ]=9 А [8 ]=4 А [9 ]=8 А [10 ]=7
var i : integer; A: array [1..10] of integer begin for i := 1 to 10 do A[ i ] :=random(100); for i := 1 to 10 do writeln ('A [', i, ']=', A[ i ]) end. Блок описания переменных Основная программа Заполнение массива Вывод массива Программа, выполняющая: заполнение целочисленного массива A, состоящего из 10 элементов, случайными числами, значения которых изменяются в диапазоне от 0 до 99; вывод массива А на экран.
ВЫЧИСЛЕНИЕ СУММЫ ЭЛЕМЕНТОВ МАССИВА Суммирование элементов массива осуществляется за счёт поочерёдного добавления слагаемых : Определяется ячейка памяти (переменная s ), в которой будет последовательно накапливаться результат суммирования Переменной s присваивается начальное значение 0 - число, не влияющее на результат сложения N раз текущее значение переменной s складывается со значением текущего элемента массива A[ i ] ; полученный результат присваивается переменной s.
Процесс поочерёдного добавления слагаемых в сумму:
const N = 20; var i, s: integer; A: array [1..N] of integer; begin for i := 1 to N do begin A[ i ] := random(100) + 50; writeln('A[',i,']=', A[i]) end ; s := 0; for i := 1 to N do s := s + A[ i ]; writeln ('s=', s) end ПРОГРАММА НА ЯЗЫКЕ ПАСКАЛЬ Блок описания констант Блок описания переменных Основная программа Заполнение и вывод массива Вычисление суммы элементов массива Вывод результата
ВЫЧИСЛЕНИЕ СУММЫ ЭЛЕМЕНТОВ МАССИВА Значение i Операция присваивания Текущее значение s s := 0 0 i = 1 s := s + A[1] 100 i = 2 s := s + A[2] 220 i = 3 s := s + A[3] 350 i = 4 s := s + A[4] 430 i = 5 s := s + A[5] 500 A = (100, 120, 130, 80, 70 )
Типовые задачи поиска в массиве Нахождение наибольшего (наименьшего) элемента массива Нахождение элемента массива, значение которого равно заданному значению Нахождение количества (суммы) элементов массива, удовлетворяющих заданному условию
При организации поиска наибольшего элемента массива правильнее искать его индекс. ! Нахождение значения наибольшего элемента в стопке карточек с записанными числами : 1. Взять верхнюю карточку, записать на доске (запомнить) число как наибольшее. 2. Взять следующую карточку, сравнить числа. Если на карточке число больше, то стереть старую запись и записать это число. 3. Повторить действия, описанные в пункте 2 для всех оставшихся карточек.
const N = 10; var i, imax : integer; A : array[1..10] of integer ; b egin for i:=1 to N do begin A[ i ] := random(100); writeln ( ' A[ ', i, ' ]= ', A[ i ]) end; imax := 1; for i := 2 to N do if A[ i ] > A[ imax ] then imax := i ; writeln ( ' Наибольший элемент ', A[ imax ]) end. Блок описания данных Основная программа Заполнение и вывод массива Поиск индекса наибольшего элемента массива Вывод результатов НАХОЖДЕНИЕ НАИБОЛЬШЕГО ЭЛЕМЕНТА МАССИВА
const N = 5; var i, imax : integer; A : array[1..10] of integer ; b egin for i:=1 to N do readln (A[ i ]); imax := 1; for i := 2 to N do if A[ i ] > A[ imax ] then imax := i ; writeln ( ' Наибольший элемент ', A[ imax ]) end. А = (100, 120, 130, 80, 70) imax i A[ i ] > A[ imax ] 1 2 120 > 100 ( Да) 2 3 130 > 120 (Да) 3 4 80 > 130 (Нет) 3 5 70 > 130 ( Нет ) Наибольший элемент: 130
Результат нахождения элемента массива, значение которого равно заданному значению : k — индекс элемента массива такой, что A[k] = x, где х — заданное число; сообщение о том, что искомого элемента в массиве не обнаружено.
const N = 10; var i, k, x: integer; A: array[1..N] of integer; begin for i:=1 to N do r е adln A[ i ]; writeln ( ' x= ' ); readln (x ); k := 0; for i :=1 to N do if A[ i ] = x then k := i ; if k = 0 then writeln ( ' Нет ' ) else writeln ( ' k= ', k) end. А = (100, 80, 120, 130, 80, 70 ), x = 80 Какое значение индекса – 2 или 5 - будет получено в результате выполнения программы? 5 – индекс последнего элемента, равного 80
const N = 10; var i, k, x: integer; A: array[1..N] of integer; begin for i:=1 to N do r е adln A[ i ]; writeln ('x='); readln (x); i := 0; repeat i := i + 1; until (A[ i ] = x) or ( i = N); if A[ i ] = x then write( i ) else write(' Нет ') end. А = (100, 80, 120, 130, 80, 70 ), x = 80 Какое значение индекса – 2 или 5 - будет получено в результате выполнения программы? 2 – индекс первого элемента, равного 80
Подсчёт количества элементов массива, удовлетворяющих некоторому условию : вводится переменная, значение которой увеличивается на единицу каждый раз, когда найден нужный элемент var k, i: integer; А : array[1..10] of integer; begin for i:=1 to 10 do А [ i ]:=random(100); for i:=1 to 10 do write (a[ i ], ' ' ); k:=0; for i:=1 to 10 do if a[ i ]>50 then k:=k+1; write ('k=', k) end. 10 6 0 2 1 5 3 5 8 14 2 8 50 10 5 1
Количество каких элементов массива подсчитывается с помощью следующего фрагмента программы? k := 0; for i := 1 to N do if A[ i ] mod 2 = 0 then k := k + 1; writeln ('k=', k) 10 6 0 2 1 5 3 5 8 14 2 8 50 10 5 1
Суммирование значений элементов массива, удовлетворяющих некоторому условию : вводится переменная, к значению которой прибавляется значение найденного элемента массива var s, i: integer; А : array[1..10] of integer; begin for i:=1 to 10 do А [ i ]:=random(100); for i:=1 to 10 do write ( А [ i ], ' ' ); s:=0; for i:=1 to 10 do if (a[ i ]>10) and (a[ i ]<30) then s:=s+a[i]; write ( ' s =', s) end. 10 50 1 3 50 14 21 50 10 21
Какому условию удовлетворяют элементы массива, значения Которых суммируются с помощью следующего фрагмента программы? s := 0; for i := 1 to N do i f (A[ i ] mod 2 = 0) and (A[ i ] mod 10 = 4) then s := s + A[ i ]; writeln ('s=', s) 10 6 0 2 1 5 4 5 8 14 2 8 50 10 5 1
Порядок, при котором в массиве первый элемент имеет самое большое значение, а значение каждого следующего элемента не больше значения предыдущего элемента, называют невозрастающим. СОРТИРОВКА МАССИВА Сортировка ( упорядочение ) массива – это понимают перераспределение его элементов в некотором определённом порядке. Порядок, при котором в массиве первый элемент имеет самое маленькое значение, а значение каждого следующего элемента не меньше значения предыдущего элемента, называют неубывающим.
СОРТИРОВКА ВЫБОРОМ Сортировка элементов массива по невозрастанию выбором осуществляется следующим образом: 1. В массиве выбирается максимальный элемент 2. Максимальный и первый элемент меняются местами, после чего первый элемент считается отсортированным 3. В неотсортированной части массива снова выбирается максимальный элемент; он и первый неотсортированных элемент массива меняются местами Действия пункта 3 повторяются с неотсортированными элементами массива, пока не останется один неотсортированный элемент (минимальный)
СОРТИРОВКА ВЫБОРОМ Индекс 1 2 3 4 5 6 7 8 Значение 0 1 9 2 4 3 6 5 Шаги 1 2 3 4 5 6 7 Итог: 1 6 9 0 0 2 5 0 4 3 3 2 2 1 1 0 1 2 4 3 6 5 9 1 4 5 2 6 9 0 2 4 3 5 9 6 2 4 3 1 9 6 5 3 1 0 9 6 5 4 1 9 6 5 4 3 0 0 9 6 5 4 3 2
for i := 1 to N do begin imax := 1; for j := i + 1 to N do if A[j] > A[ imax ] then imax := j; x := A[ i ]; A[ i ] := A[ imax ]; A[ imax ] := x end ; СОРТИРОВКА ВЫБОРОМ
Если требуется обработать некоторое множество однотипных целочисленных данных, то в зависимости от решаемой задачи можно пойти одним из двух путей: сохранить все элементы множества в памяти компьютера как массив и организовать обработку массива; завести одну переменную, в которую последовательно считывать каждый отдельный элемент множества и сразу же производить его обработку.
Камера наблюдения, установленная в населённом пункте, регистрирует в автоматическом режиме скорость проезжающих мимо неё автомобилей. Программа, которую вам необходимо составить, получает на вход значения скорости проехавших N ≤ 1000 автомобилей. Программа должна анализировать скорость каждого автомобиля и анализировать получаемую информацию.
Надо выяснить: 1 ) количество автомобилей, проехавших со скоростью, превышающей 60 км/ч 2) максимальную скорость проехавших автомобилей 3) количество автомобилей, проехавших с максимальной скоростью 4) среднюю скорость проехавших автомобилей 5) количество автомобилей, проехавших со скоростью, ниже средней
Линейный односвязный список — последовательность линейно связанных элементов, для которых разрешены операции добавления элемента в произвольное место списка и удаление любого элемента. В линейном списке для каждого элемента, кроме первого, есть предыдущий элемент; для каждого элемента, кроме последнего, есть следующий элемент.
Для работы с большим количеством однотипных данных используются массивы. Массив — это набор элементов одного типа, которым присвоено общее имя. Каждый элемент массива имеет свой номер (индекс). Перед использованием в программе массив должен быть описан. Общий вид описания одномерного массива: var < имя_массива >: array [< нач_знач_индекса >.. < кон_знач_индекса >] of < тип_элементов >; Заполнять массив можно разными способами: вводя значение каждого элемента с клавиатуры, присваивая элементам некоторые значения в программе. При заполнении массива и его выводе на экран используется цикл с параметром. При решении разнообразных задач, связанных с обработкой массивов, используются такие типовые алгоритмы, как суммирование элементов массива, поиск элемента с заданными свойствами, сортировка массива. Для вычисления суммы элементов массива используется переменная, в которой накапливается сумма. Начальное значение этой переменной равно нулю. При подсчёте элементов, удовлетворяющих условию, используется переменная, которая увеличивается на 1 каждый раз, когда найден новый подходящий элемент. Начальное значение этой переменной равно нулю.
Может ли массив одновременно содержать целые и вещественные значения? ВОПРОСЫ И ЗАДАНИЯ
Для чего необходимо описание массива? ВОПРОСЫ И ЗАДАНИЯ
Что вы можете сказать о массиве, сформированном следующим образом? а ) for i :=1 to 10 do А [ i ]:= random (101)-50; б ) for i :=1 to 20 do А [ i ]:= i ; в ) for i :=1 to 5 do А [ i ]:= 2* i -1; ВОПРОСЫ И ЗАДАНИЯ
Объявлен набор в школьную баскетбольную команду. Известен рост каждого из n учеников, желающих попасть в эту команду. Подсчитайте количество претендентов, имеющих шанс попасть в команду, если рост игрока команды должен быть не менее 170 см. Считайте рост претендента в команду случайным числом из диапазона от 150 до 200 см, а число претендентов n = 50. ВОПРОСЫ И ЗАДАНИЯ
Напишите программу, которая вычисляет среднюю за неделю температуру воздуха. Исходные данные вводятся с клавиатуры. ВОПРОСЫ И ЗАДАНИЯ Пример входных данных Пример выходных данных Введите температуру Понедельник >> 12 Вторник >> 1 0 Среда >> 1 6 Четверг >> 1 8 Пятница >> 1 7 Суббота >> 1 6 Воскресенье >> 1 4 Средняя температура за неделю: 14,71
Дан массив из десяти целых чисел. Определите, сколько элементов этого массива имеют максимальное значение. ВОПРОСЫ И ЗАДАНИЯ
В классе 20 учеников писали диктант по русскому языку. Напишите программу, подсчитывающую количество двоек, троек, четвёрок и пятёрок, полученных за диктант. ВОПРОСЫ И ЗАДАНИЯ
В целочисленных массивах A и B содержатся длины катетов десяти прямоугольных треугольников: A [ i ] - длина первого катета, B [ i ]—длина второго катета i - го треугольника. Найдите треугольник с наибольшей площадью. Выведите его номер, длины катетов и площадь. Предусмотрите случай, когда таких треугольников несколько. ВОПРОСЫ И ЗАДАНИЯ
Занесите информацию о десяти европейских странах в массивы NAME (название страны), K (численность населения), S (площадь страны). Выведите названия стран в порядке возрастания плотности их населения.
Массив — это набор элементов одного типа, которым присвоено общее имя. Каждый элемент массива имеет свой номер ( индекс ). var < имя_массива >: array [< мин_знач_индекса >.. < макс_знач_индекса >] of тип_элементов ; Ввод с клавиатуры Присваивание значений Заполнение массива Суммирование элементов Поиск элементов массива с заданными свойствами Сортировка элементов массива Задачи по обработке массива
