Массивы в Pascal
Переменные стандартного типа можно изобразить отдельными маленькими ячейками. То же самое относится и к переменным перечисляемого и интервального типов:
В данных ячейках могут содержаться любые значения из диапазона, определяемого их типами. Например, в ячейке month может быть любое одно значение от 1 до 12, а в ячейке x любое натуральное число в диапазоне примерно от -32000 до 32000.
Помимо этого, имеется также возможность объявлять переменные, которые являются массивами таких маленьких ячеек.
Ячейки массива можно назвать элементами; в квадратных скобках стоят индексы. Базовый тип массива – это тип элементов, из которых составлен массив (в каждом массиве все компоненты одного типа).
Элементы можно обрабатывать так же, как переменные базового типа:
Однако такое использование элементов массива в качестве обычных переменных не дает никакой выгоды. Массивы ценны тем, что индексы могут быть переменными или выражениями, обеспечивая доступ к последовательным элементам.
Во фрагменте кода ниже записывается false во все элементы массива tbl и 0 во все элементы массива nums :
Одномерные массивы
Предположим, что программа работает с большим количеством однотипных данных. Скажем около ста разных целых чисел нужно обработать, выполнив над ними те или иные вычисления. Как вы себе представляете 100 переменных в программе? И для каждой переменной нужно написать одно и тоже выражение вычисления значения? Это очень неэффективно.
Есть более простое решение. Это использование такой структуры (типа) данных как массив. Массив представляет собой последовательность ячеек памяти, в которых хранятся однотипные данные. При этом существует всего одно имя переменной связанной с массивом, а обращение к конкретной ячейке происходит по ее индексу (номеру) в массиве.
Нужно четко понимать, что индекс ячейки массива не является ее содержимым. Содержимым являются хранимые в ячейках данные, а индексы только указывают на них. Действия в программе над массивом осуществляются путем использования имени переменной, связанной с областью данных, отведенной под массив.
Итак, массив – это именованная группа однотипных данных, хранящихся в последовательных ячейках памяти. Каждая ячейка содержит элемент массива. Элементы нумеруются по порядку, но необязательно начиная с единицы (хотя в языке программирования Pascal чаще всего именно с нее). Порядковый номер элемента массива называется индексом этого элемента.
Помним, все элементы определенного массива имеют один и тот же тип . У разных массивов типы данных могут различаться. Например, один массив может состоять из чисел типа integer , а другой – из чисел типа real .
Индексы элементов массива обычно целые числа, однако могут быть и символами, а также описываться другими порядковыми типами. Т.е. для индекса можно использовать тип, в котором определена дискретная последовательность значений, и все эти значения можно пересчитать по порядку. Индексировать можно как константами и переменными, так и выражениями, результат вычисления которых дает значение перечислимого типа.
Если индекс массива может приобретать все допустимые значения определенного перечислимого типа, то при описании массива возможно задание имени типа вместо границ изменения индекса. При этом границами индекса будут первое и последнее значения в описании типа индекса. Границы изменения индексов могут задаваться с помощью ранее объявленных констант. Рекомендуется предварительно объявлять тип массива в разделе описания типов.
Массив можно создать несколькими способами.
Обращение к определенному элементу массива осуществляется путем указания имени переменной массива и в квадратных скобках индекса элемента.
Простой массив является одномерным . Он представляет собой линейную структуру.
В примере выделяется область памяти под массив из 11 символов. Их индексы от 1 до 11. В процессе выполнения программы пользователь вводит 11 любых символов (например, ‘q’, ’w’, ’e’, ’2’, ’t’, ’9’, ’u’, ’I’, ’I’, ’o’, ’p’), которые записываются в ячейки массива. Текущее значение переменной i в цикле for используется в качестве индекса массива. Второй цикл for отвечает за вывод элементов массива на экран.
Функция sizeof , примененная к имени массива или имени массивного типа, возвращает количество байтов, отводимое под массив.
Введение в программирование на языке Python. 8 Модуль. Теория. Списки
Обращаем Ваше внимание, что в соответствии с Федеральным законом N 273-ФЗ «Об образовании в Российской Федерации» в организациях, осуществляющих образовательную деятельность, организовывается обучение и воспитание обучающихся с ОВЗ как совместно с другими обучающимися, так и в отдельных классах или группах.
8 Модуль. Списки.
Cписки (в большинстве же языков программирования используется другой термин – «массив») — это такая структура данных, которая позволяет хранить в себе несколько однотипных значений, таких как числа или строки. Например, если мы хотим проверить число на простоту, а потом построить его разложение на простые множители, нам удобно создать список простых чисел. Тогда мы сможем проверять делимость числа на все ранее построенные элементы списка.
Список в Python представляет собой последовательность элементов, пронумерованных от 0 , как символы в строке. Тогда список, состоящий из n элементов, будет заканчиваться элементом с индексом n −1
Список можно задать перечислением элементов списка в квадратных скобках, например, список из первых 6 6 простых чисел можно задать так:
p = [ 2 , 3 , 5 , 7 , 11 , 13 ]
В списке p — 6 элементов, а именно:
p [ 0 ] == 2 , p [ 1 ] == 3 , p [ 2 ] == 5 , p [ 3 ] == 7 , p [ 4 ] == 11 , p [ 5 ] == 13 .
Также как и символы строки, элементы списка в Python можно индексировать отрицательными числами с конца, например, p [- 1 ] == 13 . Длину списка, то есть количество элементов в нём, можно узнать при помощи функции len () , например, len ( p ) == 6 .
Если мы попробуем обраться к элементу списка по некорректному индексу, например, обратимся к элементу p [ 6 ] , то произойдёт ошибка IndexError: list index out of range.
Пусть теперь мы хотим перебрать все элементы списка, при этом выводя их на экран, а потом возводя в квадрат. Организуем цикл следующим образом:
for i in range ( len ( p )) :
print ( p [ i ])
p [ i ] = p [ i ] ** 2
Таким образом, при использовании списков можно присваивать элементам новые значения, в отличие от работы со строками.
Пусть нам необходимо хранить базу данных учащихся некоторой школы, содержащую данные об учащихся и их оценках для ведения электронного дневника. Заведем списки для хранения имен учащихся names и для хранения их оценок scores , причём элементы с одинаковыми индексами будут соответствовать один и тем же ученикам. Выведем данные, пронумеровав записи, с помощью следующей программы:
names = [ ‘Иванов’ , ‘Петров’ , ‘Королев’ ]
scores = [ 5 , 4 , 5 ]
for i in range ( len ( scores )) :
print ( i+ 1 , ‘.’ , sep = » , end = ‘ ‘ )
print ( names [ i ] , scores [ i ])
На выходе получим:
Операции со списками
Для списков целиком определены следующие операции: конкатенация списков (добавление одного списка в конец другого) и повторение списков (умножение списка на число). Например:
В результате приведенных выше операций список c будет равен [ 1 , 2 , 3 , 4 , 5 ] , а список d будет состоять из 30 элементов, из элементов 1 , 2 , 3 , повторенных 10 раз.
Создание списков
Операция повторения списка позволяет конструировать большие списки. Например, списки с 1000 элементов, заполненных нулями.
Рассмотрим другой способ создания списков — при помощи метода append , позволяющего помещать элементы в конец списка. Прежде всего можно создать пустой список (не содержащий элементов, имеющий длину 0 ), в конец списка можно последовательно добавлять элементы.
for i in range ( 1000 ) :
Ноль можно заменить любым другим выражением.
for i in range ( 1000 ) :
В полученном списке будет 1000 элементов — от 0 до 999 .
Список одинаковых чисел
Вам дано число N и число X . Выведите число X ровно N раз в формате [ X , X , X , . , X ] . Используйте функцию print () для вывода списка.
Входные данные:
В двух строках входных данных заданы натуральные числа N ( N ≤ 1000 ) и X ( X ≤ 10 9 ) .
Выходные данные:
Выведите ответ на задачу.
Список квадратов
Дано число N . Выведите N квадратов чисел от 1 до N (включительно) в формате [ 1 , 4 , 9 , 16 , … , N** 2 ] . Используйте функцию print () для вывода списка.
Входные данные:
В одной строчке дано натуральное число N ≤ 200 .
Выходные данные:
Список квадратов в указанном формате.
Метод split
Элементы списка, разделённые пробелами, могут при вводе находиться в одной строке. В этом случае строку можно считать функцией input () . После этого можно использовать метод строки split , возвращающий список строк, разрезав исходную строку на части по пробелам.
Если при запуске этой программы ввести строку ‘2 3 5 7 11’ , то список a будет равен [ ‘2’ , ‘3’ , ‘5’ , ‘7’ , ’11’ ] . Обратите внимание, что список будет состоять из строк, а не из чисел! Если хочется получить список именно из чисел, то можно элементы списка по одному преобразовать в числа:
В результате получим список, состоящий из чисел: [ 2 , 3 , 5 , 7 , 11 ]
Используя функции языка map () и list () то же самое можно сделать в одну строку:
Здесь манипулятор map () применяет функцию int () сразу ко всем элементам, полученным после разделения строки, и организует из них список list . Если нужно считать список действительных чисел, то в данной записи необходимо заменить int () на float () .
Подобным способом можно считать и несколько отдельных переменных из одной строки. В этом случае распаковка по переменным считанных данных произойдет автоматически:
Метод join
Научимся выводить элементы списка в одной строке через пробел при помощи однострочной команды. Для этого используется метод join . У этого метода один параметр — список строк. В результате получается строка, которая является соединением элементов списка (которые были переданы в качестве параметра). При этом между элементами списка вставляется разделитель, равный той строке, к которой применяется метод. Например , программа
«red green blue» , «red***green***blue» и «redgreenblue» .
Следующая программа выведет считанные слова в столбец по одному в каждой строке. Здесь символ \n обзначает переход на новую строчку:
Если же список состоит из чисел, то придется использовать функцию map () . То есть вывести элементы списка чисел, разделяя их пробелами, можно, предварительно преобразовав их в строки следующим образом:
Чётные элементы
Выведите все чётные элементы списка.
Входные данные
Вводится список чисел. Все числа списка находятся на одной строке и не превосходят по модулю 1000 .
Выходные данные
Выведите ответ на задачу.
Чётные индексы
Выведите все элементы списка с чётными индексами (то есть A [ 0 ], A [ 2 ], A [ 4 ]. ).
Программа должна быть эффективной и не выполнять лишних действий!
Входные данные
Вводится список чисел. Все числа списка находятся на одной строке и не превосходят по модулю 1000 .
Выходные данные
Выведите ответ на задачу.
Задача
Необходимо найти индекс первого вхождения некоторого элемента key в заданный массив, а если такого элемента в массиве нет, то напечатать сообщение ‘нет’ .
1-й способ решения
2- й способ решения
3- й способ решения
4- й способ решения
Больше своих соседей
Дан список чисел. Определите, сколько в этом списке элементов, которые больше двух своих соседей, и выведите количество таких элементов.
Входные данные
Вводится список целых чисел. Все числа списка вводятся на одной строке, разделённые пробелом, и не превосходят по модулю 2 31 .
Выходные данные
Выведите ответ на задачу.
Соседи одного знака
Дан список чисел. Если в нем есть два соседних элемента одного знака, выведите эти числа. Если соседних элементов одного знака нет — не выводите ничего. Если таких пар соседей несколько — выведите первую пару.
Входные данные
Вводится список чисел. Все числа списка находятся на одной строке и не превосходят по модулю 1000 .
Выходные данные
Выведите ответ на задачу.
Наименьший положительный
Выведите значение наименьшего из всех положительных элементов в списке. Известно, что в списке есть хотя бы один положительный элемент.
Входные данные
Вводится список чисел. Все числа списка находятся на одной строке и не превосходят 1000 .
Выходные данные
Выведите ответ на задачу.
Количество различных элементов
Дан список, упорядоченный по неубыванию элементов в нём. Определите, сколько в нём различных элементов.
Входные данные
Вводится список чисел. Все числа списка находятся на одной строке, и гарантируется, что каждое следующее число не меньше предыдущего.
Выходные данные
Выведите ответ на задачу.
Ближайшее число
Напишите программу, которая находит в массиве элемент, самый близкий по величине к данному числу.
Входные данные
В первой строке содержится список чисел — элементы массива (целые числа, не превосходящие 1000 по абсолютному значению).
Во второй строке вводится одно целое число x , не превосходящее 1000 по абсолютному значению.
Выходные данные
Вывести значение элемента массива, ближайшего к x . Если таких чисел несколько, выведите любое из них.
Шеренга
Петя перешёл в другую школу. На уроке физкультуры ему понадобилось определить своё место в строю. Помогите ему это сделать.
Входные данные
Программа получает на вход невозрастающую последовательность натуральных чисел, означающих рост каждого человека в строю. После этого вводится число X — рост Пети. Все числа во входных данных натуральные и не превышают 200 по значению.
Выходные данные
Выведите номер, под которым Петя должен встать в строй. Если в строю есть люди с одинаковым ростом, таким же, как у Пети, то он должен встать после них.
Циклический сдвиг вправо
Циклически сдвиньте элементы списка вправо ( A [ 0 ] переходит на место A [ 1 ] , A [ 1 ] — на место A [ 2 ],…, A[2],…, последний элемент переходит на место A [ 0 ] ).
Используйте минимально возможное количество операций присваивания. Не используйте кортежные присваивания.
Входные данные
Вводится список чисел. Все числа списка находятся на одной строке.
Выходные данные
Выведите ответ на задачу.
Два ближайших числа
Дан список целых чисел, содержащий как минимум два элемента. Найдите в нём два ближайших элемента (то есть два элемента с минимальной абсолютной разностью). Изменять список при этом нельзя.
Входные данные
В единственной строке входных данных задан список целых чисел, не превосходящих по модулю 231 .
Выходные данные
Программа должна вывести два числа: индексы двух элементов списка, абсолютная величина разности которых минимальна.
Медиана
В списке нечётное число элементов, при этом все элементы различны. Найдите медиану списка: элемент, который стоял бы ровно посередине списка, если список отсортировать.
При решении этой задачи нельзя модифицировать данный список (в том числе и сортировать его), использовать вспомогательные списки.
Программа должна вывести единственное число — значение медианного элемента в списке.
Входные данные
Первая строка содержит размер массива N . Во второй строке через пробел задаются N чисел – элементы массива. Гарантируется, что N ≤ 1000 и N – нечётное число.
§ 12. Поиск элементов с заданными свойствами
Рассмотрим, как осуществляется поиск данных, хранящихся в массиве.
Среди разновидностей простейших задач поиска, встречающихся на практике, можно выделить следующие типы:
1. Найти хотя бы один элемент, равный заданному элементу x . В результате получают i — индекс (номер) элемента массива, такой что a[i] = x .
2. Найти все элементы, равные заданному x . В результате получают количество таких элементов и (или) их индексы.
Иногда поиск организуется не по совпадению с элементом x , а по выполнению некоторых условий. Примером может служить поиск элементов, удовлетворяющих условию: x1 ≤ a[i] ≤ x2 , где x1 и x2 заданы.
Если нет никакой дополнительной информации о разыскиваемых данных, то самый простой подход — последовательный просмотр элементов массива.
Человек постоянно сталкивается с задачами поиска требуемой информации. В современном мире информацию ищут с использованием сети Интернет. Также примером поиска информации может служить работа со справочниками или библиотечной картотекой, которые могут быть электронными.
Для того чтобы этот поиск был результативным и быстрым, разрабатывают эффективные алгоритмы поиска. Важную роль в процессе поиска информации играет способ хранения данных. Одной из самых простых структур для этого является массив.
Алгоритмы поиска можно разделить на алгоритмы, использующие неупорядоченные наборы данных, и на алгоритмы, работающие с предварительно упорядоченным набором данных.
Примером поиска в неупорядоченном наборе данных может служить поиск тетради конкретного учащегося в стопке тетрадей, сданных учащимися на проверку. Чтобы найти нужную тетрадь, возможно, придется пересмотреть все. Поиск в словаре — поиск в упорядоченном наборе данных, т. к. все слова расположены в алфавитном порядке.
12.2. Поиск одного элемента, удовлетворяющего условию поиска
Пример 12.1. Одномерный массив a состоит из n случайных натуральных чисел (все числа меньше 100). Определить, есть ли в нем хотя бы один элемент, равный x (значение x вводится).
Этапы выполнения задания
I. Исходные данные: массив a, количество чисел n, искомое число x.
II. Результат: вывод сообщения «элемент найден» или «элемент не найден».
III. Алгоритм решения задачи.
1. Ввод количества элементов и генерация элементов массива случайным образом.
2. Логическая переменная p имеет значение «истина», если элемент в массиве найден, и «ложь» — в противном случае. До просмотра элементов массива p = false .
3. В цикле будем просматривать все числа в массиве и сравнивать их с числом x .
4. Поиск заканчивается при выполнении одного из двух следующих условий:
4.1. Элемент найден (p = true) , т. е. в массиве есть такой элемент a[i], что a[i] = x .
4.2. Весь массив просмотрен, и совпадения не обнаружено (p = false) .
5. Вывод результата.
IV. Описание переменных: n, x – int, p – bool, a – vector <int> .
Часто требуется не только определить, есть ли в массиве искомый элемент, но и установить, на каком месте он находится.
Будем хранить индекс найденного элемента в переменной k , которой до начала просмотра присвоили значение –1 (пример 12.2). После выполнения данного алгоритма по значению переменной k можно определить, есть ли в массиве искомый элемент, и, если есть, то где он стоит. Если в массиве несколько таких элементов, то в переменной k будет храниться номер последнего из них. Если такого элемента нет, то значение переменной k не изменится ( k останется равным — 1).
На практике операцию поиска приходится выполнять достаточно часто, и скорость работы программы находится в прямой зависимости от используемого алгоритма поиска.
В рассмотренных выше алгоритмах требуется просмотреть весь массив даже в том случае, если искомый элемент находится на первом месте.
Для сокращения времени поиска можно останавливаться сразу после того, как элемент найден. В этом случае весь массив придется просмотреть только тогда, когда искомый элемент последний или его нет.
Если используется цикл for с условием просмотра всех элементов, то при нахождении элемента нужно прервать выполнение цикла (пример 12.3).
Можно воспользоваться циклом while . Цикл заканчивает работу, когда будет найден искомый элемент либо когда k == n , т. е. элемента, совпадающего с x , нет в массиве (пример 12.4).
using namespace std ;
srand ( time ( NULL ));
vector < int > a ( n );
for ( int i = 0 ; i < n ; i ++)<
a [ i ] = rand () % 100 + 1 ;
bool p = false ;
/// линейный поиск элемента
for ( int i = 0 ; i < n ; i ++)<
if ( a [ i ] == x )
cout << «ne naiden» ;
Пример 12.2. Фрагмент программы:
/// линейный поиск элемента
for ( int i = 0 ; i < n ; i ++)<
if ( a [ i ] == x )
cout << «ne naiden» ;
cout << «naiden na meste » << k ;
Пример 12.3. Фрагмент программы:
/// линейный поиск элемента
for ( int i = 0 ; i < n ; i ++)<
if ( a [ i ] == x )<
cout << «ne naiden» ;
cout << «naiden na meste » << k ;
Пример 12.4. Фрагмент программы:
///линейный поиск элемента
while ( k < n && a [ k ] != x )
cout << «ne naiden» ;
cout << «naiden na meste » << k ;
Пример 12.5. Программа:
using namespace std ;
srand ( time ( NULL ));
vector < int > a ( n + 1 );
for ( int i = 0 ; i < n ; i ++)<
a [ i ] = rand () % 100 ;
///линейный поиск с барьером
while ( a [ k ] != x )
cout << «ne naiden» ;
cout << «naiden na meste » << k ;
В примере 12.5 приведена программа решения задачи из примера 12.1, в которой реализован алгоритм поиска с барьером.
12.3. Нахождение всех элементов, удовлетворяющих условию поиска
Если требуется определить количество элементов, удовлетворяющих какому-либо условию, то для этого определяют отдельную переменную, значение которой увеличивают на 1 каждый раз, когда найден нужный элемент. Такую переменную называют счетчиком. До начала просмотра элементов массива счетчику нужно задать начальное значение или, другими словами, инициализировать значение переменной. В случае подсчета количества элементов, удовлетворяющих условию, счетчик инициализируется нулем. Для решения задачи нужно просматривать весь массив.
Пример 12.6. Задан одномерный массив из n чисел. Определить количества элементов, кратных x в этом массиве.
Этапы выполнения задания
I. Исходные данные: массив a , количество чисел n , искомое число x .
II. Результат: количество элементов, удовлетворяющих условию — k .
III. Алгоритм решения задачи.Описание переменных: n, x, k – int, a – vector <int> .
1. Зададим числа случайно на [0; 100).
2. Инициализация счетчика.
3. В цикле будем просматривать все числа в массиве и сравнивать с нулем их остатки от деления на число x . Если остаток равен нулю, то счетчик увеличиваем на 1.
IV. Вывод результата.
Если необходимо не только посчитать, сколько элементов удовлетворяют условию, но и сохранить индексы таких элементов, то для этого можно воспользоваться дополнительным массивом. Создадим новый массив b . Как только будет найден необходимый элемент, его индекс будет заноситься в массив b . Количество элементов в массиве b заранее не известно. Поэтому опишем массив b как вектор без размера:
vector <int> b;
using namespace std ;
srand ( time ( NULL ));
vector < int > a ( n );
for ( int i = 0 ; i < n ; i ++)<
a [ i ] = rand () % 100 ;
for ( int i = 0 ; i < n ; i ++)<
if ( a [ i ] % x == 0 )
cout << » elementov» << endl ;
VII. Анализ результатов. В первом случае кратными двум будут числа 34, 18, 82, 30, 24. Во втором случае — в массиве нет чисел, кратных 13.
using namespace std ;
srand ( time ( NULL ));
vector < int > a ( n );
for ( int i = 0 ; i < n ; i ++)<
a [ i ] = rand () % 100 ;
vector < int > b ;
for ( int i = 0 ; i < n ; i ++)
if ( a [ i ] % x == 0 )
b . push_back ( i );
int k = b . size ();
cout << » elementov» << endl ;
cout << «ih pozicii:» << endl ;
for ( int i = 0 ; i < k ; i ++)
12.4. Решение задач с использованием алгоритма линейного поиска
Пример 12.8. На складе хранятся пустые ящики для упаковки товара. Известно, что вместимость одного пакета с конфетами x кг. Какова суммарная масса пакетов с конфетами, которые можно упаковать в такие ящики, заполнив ящик целиком?
Этапы выполнения задания
I. Исходные данные: массив а , количество чисел n , число x .
II. Результат: количество ящиков — k , суммарная масса — s .
III. Алгоритм решения задачи.
1. Ввод исходных данных.
2. Инициализация счетчика и значения суммы:
k = 0 ; s = 0 ;
3. Просматривая массив, проверим, является ли текущий элемент числом, кратным x (в этом случае ящик будет заполнен целиком). Если кратен, то увеличим счетчик k на 1, а переменную s — на значение найденного элемента массива.
4. Вывод результата.
IV. Описание переменных: n, x, k — int, a – vector <int> .
Пример 12.9. Имеется список мальчиков 10 В класса и результаты их бега на 100 м. Для сдачи норматива необходимо пробежать дистанцию не более чем за 16 с. Вывести фамилии учащихся, которые не выполнили норматив по бегу. Сколько таких учащихся в классе? Исходные данные хранятся в текстовом файле input.txt. Результат вывести в текстовый файл output.txt.
Этапы выполнения задания
Исходные данные: массивы fam (фамилии учащихся) и r (результаты бега в секундах), количество учащихся n.
II. Результат: фамилии тех учащихся, которые не выполнили норматив по бегу.
III. Алгоритм решения задачи.
1. Ввод исходных данных.
2. Инициализация счетчика: k = 0 ;
3. Будем просматривать массив с результатами и проверять, является ли текущий элемент числом, большим 16 (норматив не сдан). Если такое значение найдено, то выведем элемент массива fam с соответствующим номером и увеличим значение счетчика на 1.
4. Вывод значения счетчика.
IV. Описание переменных:
n, k – int, r – vector <double>,
fam – vector <string>.
Пример 12.10. В двух линейных массивах x и y , заданных случайным образом, хранятся координаты точек плоскости ( –200 ≤ x[i], y[i] ≤ 200 ). Определить, каких точек больше — лежащих внутри или снаружи области, ограниченной окружностью радиуса r, с центром в начале координат (будем считать, что точки, лежащие на окружности, лежат внутри области).
Этапы выполнения задания
I. Исходные данные: x, y — массивы чисел, r — радиус окружности, n — количество точек.
II. Результат — одно из сообщений: «внутри точек больше», «снаружи точек больше» или «точек поровну».
III. Алгоритм решения задачи.
1. Ввод исходных данных.
2. Инициализация счетчиков: k1 = 0 ; k2 = 0 ;
3. Будем просматривать все точки и для каждой проверять принадлежность области. Если x 2 + y 2 ≤ R 2 , то точка лежит внутри области, тогда увеличим значение счетчика k1 на 1, если нет, то увеличим на 1 значение счетчика k2 .
4. Сравним значения k1 и k2 и выведем результат.
IV. Описание переменных: n, k1, k2 — int, x, y – vector <int> .
Пример 12.11. Задан одномерный массив из n целых чисел. Определить количества элементов, которые являются числами Смита. Вывести те элементы, которые являются числами Смита. (Число Смита — такое составное число, сумма цифр которого равна сумме цифр всех его простых сомножителей.) Например, числом Смита является 202 = 2 × 101, поскольку 2 + 0 + 2 = 4 и 2 + 1 + 0 + 1 = 4.
Этапы выполнения задания
I. Исходные данные: а — массив чисел, n — количество чисел в массиве.
II. Результат: числа Смита и их количество в массиве.
III. Алгоритм решения задачи.
1. Ввод исходных данных.
2. Инициализация счетчика: k = 0 ;
3. Будем просматривать каждый элемент массива и определять, является ли он числом Смита. Для проверки создадим функцию check, которая будет получать в качестве параметра элемент массива, а также возвращать значение true , если число является числом Смита, и false в противном случае.
3.1. Найдем сумму цифр числа.
3.2. Будем разлагать число на простые множители и для каждого множителя находить сумму цифр.
3.3. Для разложения числа на простые множители будем делить его сначала на 2 (пока делится), затем на 3. На 4 число уже делиться не будет, будем делить на 5 и т. д. Закончится разложение тогда, когда после всех делений число станет равным 1.
4. Также нам понадобится функция sum, которая для числа будет возвращать его сумму цифр.
IV. Описание переменных:
n, k – int, a – vector <int> .
Пример 12.12. Задан одномерный массив из n строк. Данные в массиве читаются из текстового файла input.txt. Каждая строка является предложением из слов, разделенных пробелами. Найти и вывести в текстовый файл output.txt те предложения, в которых нечетное количество слов. Сколько предложений вывели?
Этапы выполнения задания
I. Исходные данные: а — массив строк, n — количество строк в массиве.
II. Результат: искомые строки и их количество.
III. Алгоритм решения задачи.
1. Ввод исходных данных.
2. Инициализация счетчика: k = 0 ;
3. Будем просматривать каждую строку и определять, сколько в ней слов. Для проверки создадим функцию check, которая будет получать в качестве параметра элемент массива и возвращать количество слов в строке. Если количество слов является нечетным числом, то выведем строку и увеличим значение счетчика.
3.1. Перед каждым словом предложения, кроме первого, стоит пробел. Слово начинается с символа, который пробелом не является.
3.2. Добавим пробел перед первым словом, тогда количество слов будет определяться количеством сочетаний пар символов: пробел и не пробел.
using namespace std ;
vector < int > a ( n );
for ( int i = 0 ; i < n ; i ++)
cout << » масса конфет » ;
int s = 0 , k = 0 ;
for ( int i = 0 ; i < n ; i ++)
if ( a [ i ] % x == 0 )<
cout << » упаковали » << k ;
cout << » ящиков, масса » ;
VII. Анализ результатов. Ящики, удовлетворяющие условию задачи, имеют массу 15, 25, 10, 20, 45.
using namespace std ;
ifstream fin ( «input.txt» );
ofstream fout ( «output.txt» );
vector < string > fam ( n );
vector < double > r ( n );
for ( int i = 0 ; i < n ; i ++)
for ( int i = 0 ; i < n ; i ++)
if ( r [ i ] > 16 )<
fout << fam [ i ] << endl ;
fout << «не сдали норматив » ;
VII. Анализ результатов. Результат Сидорова 21, а Королева 16.1, что превышает норматив.
Пример 12.10.
using namespace std ;
srand ( time ( NULL ));
vector < int > x ( n ), y ( n );
for ( int i = 0 ; i < n ; i ++)<
x [ i ] = rand () % 401 — 200 ;
y [ i ] = rand () % 401 — 200 ;
int k1 = 0 , k2 = 0 ;
for ( int i = 0 ; i < n ; i ++)
if ( x [ i ] * x [ i ] + y [ i ] * y [ i ]
<= r * r )
if ( k1 > k2 )
if ( k1 < k2 )
VII. Анализ результатов. По сообщениям, которые выдает программа, сложно судить о ее правильности. Для проверки можно вывести значения координат каждой точки в файл и при проверке ставить дополнительные пометки. Например, «+», если точка внутри, и «-», если снаружи.
Пример 12.11.
using namespace std ;
int sum ( int x )
while ( x > 0 )<
bool check ( int x )
int s1 = sum ( x );
//разложение на простые множители
while ( x != 1 )<
while ( x % d == 0 )<
return ( s1 == s2 );
vector < int > a ( n );
for ( int i = 0 ; i < n ; i ++)
for ( int i = 0 ; i < n ; i ++)
if ( check ( a [ i ]))<
cout << » chisel Smita» << endl ;
Пример 12.12.
using namespace std ;
using namespace std :: __cxx11 ;
int check ( string x )
int len = x . length ();
for ( int i = 0 ; i < len — 1 ; i ++)
if ( x [ i ] == ‘ ‘ && x [ i + 1 ] != ‘ ‘ )
ifstream fin ( «input.txt» );
ofstream fout ( «output.txt» );
vector < string > a ( n );
for ( int i = 0 ; i < n ; i ++)
getline ( fin , a [ i ]);
for ( int i = 0 ; i < n ; i ++)
if ( check ( a [ i ]) % 2 )<
fout << » строк (– а , –u)» << endl ;
Вопросы к параграфу
1. Что называют последовательным поиском?
2. Как определить, что в массиве был найден элемент с определенными свойствами?
3. Для чего используют переменные-счетчики?
4. Что такое инициализация переменной?
Упражнения
1. Рост учащихся класса представлен в виде массива. Напишите программу, которая определит количество учащихся, рост которых больше среднего роста по классу.
2. Заданы фамилии и рост учащихся 10-го класса. Напишите программу, которая выведет фамилии учащихся, рост которых меньше среднего роста по классу.
3. Известны данные о площади n стран (в млн кв. км) и численности населения (в млн). Напишите программу, которая выведет номера тех стран, плотность населения в которых больше x .
4. Для упражнения 3 добавьте возможность вводить и выводить названия стран из текстового файла.
5. Напишите программу, которая определит, есть ли в линейном массиве хотя бы один элемент, который удовлетворяет указанному ниже свойству. Если да, то выведите его номер.
1. Является положительным числом.
2. Является четным числом.
3. Является нечетным, кратным 7 числом.
4. При делении на 7 дает в остатке 1, 2 или 3.
6 . Написать программу, которая посчитает количество элементов массива, удовлетворяющих свойствам, описанным в упражнении 5.
7. Напишите программу, которая найдет в линейном массиве и выведет все простые числа с нечетной суммой цифр. Указать, сколько чисел вывели.
8. В примере 7.15 рассматривалась рекурсивная функция для разложения числа на простые множители. Измените функцию check в примере 12.11 на рекурсивную по аналогии с функцией из примера 7.15.
9. Написать программу, которая посчитает количество пар соседних (номера таких элементов отличаются на 1) элементов массива, удовлетворяющих указанному ниже свойству:
1. Оба числа в паре являются положительными.
2. Числа в паре имеют разные знаки.
3. Ни одно число из пары не равно нулю.
4. Числа имеют одинаковую четность (или оба четные, или оба нечетные).
10. Напишите программу, которая найдет в линейном массиве и выведет все числа Армстронга. Числом Армстронга называется такое число, которое равно сумме своих цифр, возведенных в степень, равную количеству его цифр. Например, числом Армстронга является число 371 = 3 3 + 7 3 + 1 3 = 27 + 343 + 1. Указать, сколько чисел вывели.