Типовые алгоритмы Ч2. Аа нн
 Скачать 1.6 Mb.
|
А А . . Н Н . . Г Г У У Щ Щ И И Н Н , , Т Т . . И И . . Л Л А А З З А А Р Р Е Е В В А А , , И И . . В В . . М М А А Р Р Т Т Ы Ы Н Н О О В В А А , , О О . . А А . . П П А А Л Л Е Е Х Х О О В В А А , , И И . . К К . . Р Р А А К К О О В В А А А А Л Л Г Г О О Р Р И И Т Т М М Ы Ы О О Б Б Р Р А А Б Б О О Т Т К К И И М М А А С С С С И И В В О О В В И И В В С С П П О О М М О О Г Г А А Т Т Е Е Л Л Ь Ь Н Н Ы Ы Е Е А А Л Л Г Г О О Р Р И И Т Т М М Ы Ы Министерство образования и науки Российской Федерации Балтийский государственный технический университет «Военмех» Кафедра систем управления и компьютерных технологий А.Н. ГУЩИН, Т.И. ЛАЗАРЕВА, И.В. МАРТЫНОВА, О.А. ПАЛЕХОВА, И.К. РАКОВА АЛГОРИТМЫ ОБРАБОТКИ МАССИВОВ И ВСПОМОГАТЕЛЬНЫЕ АЛГОРИТМЫ Учебное пособие Под редакцией ИК. Раковой Санкт-Петербург 2016 УДК 004.421(075.8) А УДК 004.421(075.8) Рецензенты канд. пед. наук, доц. каф. информатики и информационных технологий ТГПУ им. Л.Н. Толстого (г. Тула) Ю.М. Мартынюк; канд. техн. наук, доц. каф. И БГТУ А.А. Сорокин Утверждено редакционно-издательским советом университета ISBN 978-5-85546-984-4 Авторы, 2016 БГТУ, 2016 Алгоритмы обработки массивов и вспомогательные алгоритмы учебное пособие / АН. Гущин и др под. ред. ИК. Раковой Балт. гос. техн. унт. – СПб., 2016. – 210 с. ISBN 978-5-85546-984-4 Пособие включает теоретический материал и большое количество подробно разобранных примеров составления алгоритмов и программ для обработки одномерных и двумерных массивов, а также для решения более сложных вычислительных задач с помощью вспомогательных алгоритмов. Для каждой задачи приводится подробное описание алгоритма и программная реализация на пяти алгоритмических языках Си (ISO C90), Паскаль (Free Pascal х, Фортран (Compaq Visual Fortran), Питон (Python ха также в системе Матлаб (MATLAB х. Предназначено для студентов всех специальностей, изучающих программирование на языках высокого уровня (Си, Паскаль, Фортран, Питон, Матлаб или других) в рамках дисциплин Основы программирования, Автоматизация инженерных расчетов, Информатика и других. А ОСНОВНЫЕ АЛГОРИТМЫ ОБРАБОТКИ МАССИВОВ Одномерные массивы Основное предназначение современных компьютеров – обработка больших объемов данных, при размещении которых в памяти возникает проблема очень сложно дать каждой ячейке собственное имя и при этом не запутаться. Был найден простой выход имя дается сразу группе ячеек, в которой каждая ячейка имеет свой номер. Именованный набор однотипных элементов, доступ к каждому из которых осуществляется по общему имени набора и номеру элемента в наборе, называется массивом. Количество элементов в таком наборе определяет размер массива. Уникальный номер элемента массива называется индексом. Индексы элементов массива являются целыми числами, следующими друг за другом в порядке возрастания. При программной реализации алгоритма первый элемент массива в зависимости от языка программирования может иметь разный индекс. Различают три основных разновидности массивов с отсчетом от нуля (zero-based), с отсчетом от единицы (one-based) и с отсчетом от специфического значения, заданного программистом (n-based). В языке Fortran (по умолчанию) и языке системы Matlab индексация элементов массива начинается с единицы, как это принято в математике. Отсчет от нуля характерен для массивов в языках C/C++, Java, Python, Visual Basic, открытых массивов в языке Pascal. В языках Fortran и Pascal также широко используется произвольное задание начального индекса. Очень важно не путать порядковый номер элемента в массиве сего индексом. Если в словесном описании алгоритма для указания конкретного элемента массива используется порядковое числительное (первый, второй, десятый, двадцать четвертый, то нужно понимать, что это именно порядковый номер элемента, а не индекс, и делать поправку на точку отсчета. Например, если индексация начинается с нуля, то первый элемент будет иметь индекс 0, второй – 1, двадцать четвертый – 23. Если индексация начнется сто первый элемент это элемент с индексом -5, второй – с индексом -4, а двадцать четвертый – с индексом 18. И только если индексация начинается с единицы, индекс элемента и его порядковый номер будут совпадать. Для обращения к элементу массива нужно указать имя массива и индекс элемента в скобках (квадратных или круглых в зависимости от языка программирования. Индекс может быть задан константой, переменной или выражением, значением которого будет целое число. С любым элементом массива можно выполнять все действия, применимые к переменной того же типа. В некоторых языках программирования есть средства для обработки массивов как единых объектов, но универсальным методом работы является выполнение действий над отдельными элементами массива последовательно. Легко заметить, что если для массивов, содержащих небольшое количество элементов, для обработки каждого элемента можно написать отдельный оператор, то для массивов с большим количеством элементов это сложно количество таких операторов будет равно количеству элементов массива. Поэтому для работы с массивами используют циклические алгоритмы. В цикле по определенным правилам изменяется значение переменной, используемой для обозначения индекса элемента. Обязательно нужно следить затем, чтобы не выйти заграницы массива, так как ошибки в индексации могут привести к непредсказуемым последствиям. Если обработке должны подвергнуться все элементы массива например, при задании начальных значений элементов, вводе или выводе массива на экран, поиске максимального элемента и т.п.), то количество повторов в цикле будет равно количеству элементов массива. В большинстве случаев последовательный перебор элементов массива выполняется от первого элемента к последнему, несколько реже – от последнего к первому. Если обработке должна подвергнуться только часть массива (например, до первого положительного элемента, то вычислить число повторов не всегда возможно, но оно все равно не может превзойти количество элементов массива. Когда для решения задачи должны использоваться только отдельные элементы массива, удовлетворяющие некоторым условиям, при составлении алгоритма обязательно нужно учитывать, что таких элементов в массиве может не оказаться. В этом случае должен быть предусмотрен как минимум вывод сообщения о невозможности получить требуемый результат из-за некорректных исходных данных. Память под массив может выделяться разными способами. Если количество элементов в массиве известно, то создается переменная типа массив из такого-то количества таких-то элементов. При этом число элементов предпочтительно задать именованной константой. Если в программе понадобится изменить размер массива, достаточно будет изменить только одно число – значение этой константы. Когда количество элементов в массиве заранее неизвестно, есть выбор. Можно создать массив из большого количества элементов, а использовать потом столько, сколько нужно. Естественно, для такого метода нужно иметь представление о максимально возможном количестве элементов массива, которое может понадобиться. Недостатком такого подхода является нерациональное использование памяти. Второй вариант предполагает динамическое выделение памяти в процессе работы программы уже после того, как станет известным требуемое число элементов массива. У такого метода несколько преимуществ. Во-первых, можно выделить память именно такого размера, какого нужно. Во-вторых, можно использовать всю свободную оперативную память, следовательно, размер массива может быть значительно больше, чем при статическом выделении памяти. В-третьих, таким способом можно создавать динамические массивы, те. массивы, количество элементов в которых может изменяться вовремя работы программы. К сожалению, не все языки программирования содержат средства для динамического выделения памяти. Обращение к элементам массивов осуществляется одинаково вне зависимости оттого, как именно выделялась память под массив. Задача 1. Нахождение среднего арифметического элементов массива Условие задачи Дан массив из 20 вещественных элементов. Найти среднее арифметическое элементов этого массива. Из математики известно, что среднее арифметическое чисел представляет собой отношение суммы всех чисел к их количеству. Обозначим величину среднего арифметического как sred, сумму всех элементов – как s. Тогда формула вычисления среднего арифметического будет выглядеть так 20 sråd s . Поскольку количество элементов задано по условию задачи, то остается вычислить значение суммы s. В данной задаче исходные данные представлены массивом x из 20 элементов, поэтому слагаемым будет элемент массива x[i], где i индекс элемента массива, изменяющий свое значение от 1 до 20. В языках высокого уровня, как правило, все действия с массивами выполняются поэлементно с использованием циклов. Поэтому для ввода массива будем использовать цикл с известным числом повторений. Как ив задачах № 10 13 пособия [1], для получения суммы каких либо слагаемых используется следующий прием. Сначала сумму полагают равной нулю s=0. Далее к ней последовательно прибавляют по одному слагаемому s=s+x[i] и результат сложения заносят каждый разв туже самую переменную. Количество повторений такого суммирования соответствует количеству слагаемых в искомой сумме. Поэтому для вычисления суммы можно использовать цикл с известным числом повторений, которое равно числу слагаемых 20. Структурированная запись алгоритма 1 1. Повторять для i от 1 до 20 следующие действия 1.1. Ввод элемента массива x[i]. 2. s=0. 3. Повторять для i от 1 до 20: 3.1. s = s+x[i]. 4. Вычислить sred=s/20. 5. Вывести сообщение Среднее арифметическое =” и значение переменной sred. Схема алгоритма 1 Поскольку в условии задачи количество элементов в массиве точно указано (оно равно 20), то при реализации алгоритма в программах описан массив из 20 элементов и для общности и удобства восприятия использована именованная константа N=20 для обозначения количества элементов. Программа на языке Си #include #define N 20 int main (void) { int i=0; double x[N], s=0, sred; Введите элементы массива for (i; i 1 Программа на языке Паскаль Program Pr_1; Const N=20; Var x: array[1..N] of real; i: integer; s, sred: real; begin writeln (’ Введите элементы массива for i:=1 to N do readln(x[i]); s:=0; for i:=1 to N do s:=s+x[i]; sred:=s/N; writeln (’ Cреднее арифметическое =’, sred:7:5); end. Программа на языке Фортран Program Pr_1 implicit none integer, parameter:: N=20 real x(N), s, sred integer i print *,’ Введите элементы массива x’ read *,x s=0 do i =1, n s=s+x(i) enddo sred = s/N print *,’ sred =’, sred end Программа на языке Python # В качестве массива используется # стандартный тип list (список) N = 20 x = [] # Создаем пустой список for i in range(N): # i = 0, ... , N-1 -- всего N Введите значение x[{0}]=".format(i+1)) x.append(float(input())) s = 0 for i in range(N): # i = 0, ... , N-1 -- всего N s = s + x[i] # Первый элемент имеет индекс 0, последний -- N-1 9 sred = s / 20 print(" Среднее арифметическое = ", sred) Программа в системе Matlab N=20; Введи 20 элементов массива for i=1:N disp(sprintf('x(%g)=',i)) x(i)= input(' '); end s=0; for i=1:N s=s+x(i); end sred=s/N; среднее арифм.=%f',sred)) С использованием векторных функций n=20; for i=1:n x(i)=input(' x(i)='); end sred = mean(x); среднее disp(sred); Задача 2. Нахождение среднего арифметического элементов, удовлетворяющих условию Условие задачи. Дан целочисленный массив из N элементов, N ≤ 20. Найти среднее арифметическое четных положительных элементов этого массива. Выделение среди набора целых чисел четных положительных, как и расчет среднего арифметического для них, были рассмотрены соответственно в задачах 17 и 18 пособия [1]. Ключевым отличием данной задачи является предопределенность количества чисел, участвующих в расчетах, а также их предварительное размещение в массиве структуре данных, позволяющей обращаться к своим элементам по индексу (как правило, последовательному номеру элемента. Предположим, что элементы массива имеют последовательные индексы от 1 до N. Тогда задача сводится к последовательному обращению по индексу к каждому из элементов, проверке соответствия элемента критерию четный положительный ив случае соответствия – его прибавлению к сумме всех таких элементов и увеличению на единицу переменной-счетчика количества четных положительных элементов массива. После анализа всех элементов массива, если счетчик четных положительных элементов имеет положительное значение вместо исходного нулевого, то вычисляется их среднее арифметическое и выводится пользователю, иначе выводится сообщение Четных положительных элементов в массиве нет. Для краткости зададим следующие обозначения переменных N – число элементов в массиве, 1 ≤ N ≤ 20 (массив с нулевым или отрицательным числом элементов выглядит странно Massiv – сам массив Massiv[1], Massiv[2], …, Massiv[i], …, Massiv[N] – элементы массива с соответствующими индексами, 1 ≤ i ≤ N; i – индекс текущего рассматриваемого элемента массива (отдельная переменная Counter – счетчик количества четных положительных чисел Sr – искомое среднее арифметическое четных положительных чисел, этаже переменная первоначально будет использоваться для накопления суммы четных положительных чисел. Для обработки всех элементов массива используем алгоритмическую конструкцию цикл с предопределенным числом повторений, тело которого будет повторяться N раз. В нем перед каждым выполнением тела цикла (перед каждой итерацией) переменной i будут последовательно присваиваться значения от 1 до N. То есть, в переменной i будет храниться порядковый номер выполняемой итерации ион же будет номером анализируемого на этой итерации элемента массива. Как уже рассматривалось в предыдущем примере, ввод массива при известном числе элементов осуществляется для каждого элемента отдельно, в цикле, с помощью алгоритмической конструкции цикл с предопределенным числом повторений. В данном примере и во всех последующих не будем подробно рассматривать ввод массива, вопи- сании алгоритма ив структурной схеме будем считать его атомарным (единым) действием ввода, тогда алгоритм с использованием ранее введенных обозначений и сокращений будет иметь следующий вид: Структурированная запись алгоритма 2 1. Повторять 1.1. Ввести значение N. Завершить повторение, если 1 ≤ N ≤ 20. 2. Ввести массив из N элементов в переменную Massiv. 3. Sr = 0. 4. Counter = 0. 5. Повторить для i от 1 до N: 5.1. Если Massiv[i] > 0, то 11 5.1.1. Если Massiv[i] mod 2 = 0, то 5.1.1.1. Sr = Sr + Massiv[i] 5.1.1.2.Counter=Counter +1. 6. Если Counter > 0, то Sr = Sr / Counter, вывести значение переменной, иначе вывести сообщение Четных положительных элементов в массиве нет, среднее арифметическое вычислить невозможно. Схема алгоритма 1 12 1 Программа на языке Си #include #include #define NMAX 20 int main(int argc, char *argv[]) { int Massiv[NMAX], N, i, Counter; double Sr; do{ Введите число элементов (1<=N<=20) "); scanf("%d",&N); } while(N < 1 || N > 20); for(i=0;i } Sr=0; Counter=0; for(i=0;i Sr = Sr + Massiv[i]; Counter++; } } if (Counter > 0){ Sr = Sr / Counter; Среднее арифметическое = %6.3lf\n",Sr); } else Четных положительных эл-тов нет \n"); system("pause"); return 0; } Программа на языке Паскаль Program Pr_2; Var Massiv : array [1..20] of integer; n, i, Counter: integer; Sr : real; begin repeat writeln (Введите число элементов массива readln (n); until (n>=1) and (n<=20); 14 writeln (Введите значения элементов for i:=1 to n do begin write ('Massiv[’, i, ’]=’); read (Massiv[i];) end; Sr:=0; Counter:=0; for i:=1 to n do if Massiv[i]>0 then if Massiv[i] mod 2=0 then begin Sr := Sr + Massiv[i]; Counter := Counter+1; end; if Counter > 0 then begin Sr = Sr / Counter; Среднее арифметическое = ',Sr:6:3); end else Четных положительных эл-тов нет '); end. Программа на языке Фортран Program Pr_2 Implicit none integer, parameter:: nmax=20 integer Massiv(nmax), n/0/, Sr, i, Counter do while (n<1.or.n>20) print *,’ Введите число элементов массива read *, n end print *,’ Введите элементы массива x’ read *, (Massiv(i),i=1,n) Sr=0 Counter=0 do i =1, n if (Massiv(i) > 0) then if (mod(Massiv(i),2) == 0) then Sr = Sr + Massiv(i); Counter = Counter + 1; endif endif enddo if (Counter > 0) then Sr = Sr / Counter print *,’ sred =’, sred else 15 print *, 'Четных положительных элементов ' print *, 'в массиве нет' endif end Программа на языке Python N = 0 while not 1 <= N <= 20: Введите число элементов (1<=N<=20) ") N=int(input()) Massiv = [] # Создаем пустой список for i in range(N): # i = 0, ... , N-1 -- всего N Введите й элемент массива ". format(i+1)) Massiv.append(float(input())) Sr = 0 Counter = 0 for i in range(N): # i = 0, ... , N-1 -- всего N if Massiv [i] > 0: if Massiv [i] % 2 == 0: Sr = Sr + Massiv [i] Counter = Counter + 1 if Counter > 0: Sr = Sr / Counter print("Sr = ") print(Sr) else: Четных положительных эл-тов в массиве нет, среднее арифметическое вычислить невозможно) # Вывод двух строк одним оператором – # тройные кавычки сохраняют внутри # строки все переводы строк, пробелы и т.п. Программа в системе Матлаб n=0; while (1 <= n && n <= 20) Введите число элементов (1<=n<=20)') n= input(' '); end Введите элементы массива) for i=1:n x(i)=input(' x(i)='); end Sr = 0; Counter = 0; for i=1:n if x(i) > 0 if mod(x(i),2) == 0 16 Sr = Sr + x(i); Counter = Counter + 1; end end end if Counter > 0 Sr = Sr / Counter; Среднее disp(Sr); else disp(' Четных положительных элементов нет) end С использованием векторных функций n=0; while (1 <= n && n <= 20) Введите число элементов (1<=n<=20)') n= input(' '); end Введите элементы массива) for i=1:n x(i)=input(' x(i)='); end Sr = mean(x(x>0 & mod(x,2)==0)); Среднее disp(Sr); Задача 3. Проверка наличия определенных элементов в массиве Условие задачи. Дан целочисленный массив из N элементов, N 20. Проверить, имеются ли в нём трёхзначные числа. Трехзначными числами являются положительные целые числа в диапазоне от 100 дои отрицательные целые в диапазоне от -999 до -100. Можно проверять вхождение значения в один из двух диапазонов или взять значение по модулю и тогда проверять только принадлежность его диапазону [100; 999]. Исходными данными для этой задачи являются количество элементов массива N и их значения, результатом – сообщения Да или Нет в зависимости от выполнения условий задачи. Назовем массив А, а признак выполнения условия – flag. Начальное состояние переменной flag устанавливается соответствующим значению нет. В цикле осуществляется последовательная проверка элементов массива. Если очередной элемент является трехзначным числом, значение переменной flag должно измениться и стать соответствующим дав этом случае цикл можно прервать. Окончательный ответ можно дать только по завершении просмотра элементов в зависимости от значения переменной Структурированная запись алгоритма 3 1. Ввести N. 2. Если N>20, то ограничим его максимально возможным N=20. 3. Повторять N разв цикле i=1,N: 3.1. Ввести значение элемента A[i] 4. Задать начальное значение flag = нет. 5. Повторять N разв цикле i=1,N: 5.1. Если 100≤A[i]≤999 или -999≤A[i]≤-100, то flag = да и цикл можно прервать. 6. Если flag = да, то вывести сообщение В массиве есть трехзначные числа, иначе вывести сообщение Трехзначных чисел в массиве нет». |