Файл: Алгоритмизация как обязательный этап разработки программы.pdf

- размерность, равная количеству измерений массива;

- значения верхней и нижней границы для каждого индекса;

- размер массива - количество компонентов. [4]

Типовые приемы алгоритмизации

Часто в информационных и вычислительных задачах используются алгоритмы, связанные с обработкой массивов различных типов данных. К ним относятся:

• алгоритмы накопления (счетчик, вычисление суммы и произведения элементов массива);
• поиск максимума (минимума);
• сортировка.

Вычисление суммы и произведения

При вычислении используется прием накопления. Вычисление суммы сводится к ее накоплению в переменной в цикле, в котором вычисляются соответствующие слагаемые. При этом вновь вычисленное слагаемое прибавляется к сумме предыдущих слагаемых, т.е. в цикле последовательно вычисляются все промежуточные суммы. Поэтому формула, предназначенная для накопления суммы, имеет вид

S = S + у,

где у - очередное слагаемое;

S - промежуточная сумма.

После первого выполнения цикла первая промежуточная сумма должна быть равна значению первого слагаемого. Следовательно, начальное значение S должно быть равно нулю.

Вычисление произведения выполняется аналогично, используется также прием накопления. Вычисление произведения сводится к его накоплению в цикле в переменной, при этом в цикле вычисляются последовательно все промежуточные произведения. Формула для вычисления произведения имеет вид

P = P⋅у,

где у - очередной сомножитель;

Р - промежуточное произведение.

Начальное значение Р, которое задается перед циклом, должно быть равно единице (если нет условия, для каких сомножителей вычисляется произведение). Среди членов произведения не должно быть нулевых значений.

Рассмотрим вычисление суммы и произведения на примере.

Задача. Задан массив по имени А, состоящий из 20 элементов А_i; i = 1, ..., 20. Составить алгоритм вычисления суммы и произведения элементов этого массива.

Решение. В соответствии со смыслом описываемых величин выбираем имя переменных: для суммы - S, произведения - P.

Алгоритм вычисления будет состоять из следующих шагов.

1. Ввод массива A_i; i = 1, ..., 20.

2. Задание начальных значений переменных S и P.

S = 0, P = 1.

3. Цикл. Задаются параметры цикла: начальное значение параметра цикла 1, конечное значение 20, шаг 1.

4. Вычисление текущих значений S и P.

S = S + A_i;

P = P × A_i.

5. Проверка окончания цикла. Если параметр цикла меньше конечного значения, то увеличиваем переменную цикла на 1 и переходим к шагу 4. Если переменная цикла больше конечного значения, то переходим к шагу 6.

6. Печать вычисленных значений S и P.

7. Конец.

Вычисление количества элементов

При вычислении количества элементов, как и при вычислении суммы и произведения, используется прием накопления. Переменная, описывающая количество, должна иметь целый тип. Если не задано дополнительных условий, то правило изменения количества таково:

К = К + 1.

Начальное значение К = 0.

Задача. Задан массив А, состоящий из 20 элементов, A_i; i = 1, ..., 20. Составить алгоритм вычисления суммы и количества положительных элементов массива.

Решение. Т.к. в этом примере вычисляется сумма и количество только положительных элементов, то внутри цикла необходимо добавить проверку очередного элемента на знак.

1. Ввод массива A_i; i = 1, ..., 20.

2. Задание начальных значений переменных

S = 0,

К = 0.

3. Цикл. Задаются начальное и конечное значение переменной цикла и шаг цикла.

4. Проверка очередного элемента A_i на знак. Если условие A_i > 0 выполняется, то переход к шагу 5, если нет - к шагу 6.

5. Накопление суммы

S = S + X,

и увеличение счетчика К на 1,

К = К + 1.

6. Проверка окончания цикла.

7. Печать значений S и К.

8. Конец.

Нахождение максимального и минимального элементов в заданной последовательности

Задача. Задан массив A_i; j = 1, ..., 30. Найти максимальный элемент этого массива.

Решение. Поиск максимального элемента массива выполняется в цикле путём последовательного сравнения значения текущего элемента массива с максимальным элементом из всех предыдущих. И, если значение текущего элемента больше максимального из предыдущих, то максимуму присваивается значение текущего элемента. В j-м цикле для выбора максимального элемента используется следующая формула:

После окончания цикла значение А_max будет максимальным из всёх рассмотренных значений А.

Для применения указанного способа необходимо перед началом цикла задать начальное значение А_max некоторое начальное значение. Например, это может быть значение первого элемента массива. Поиск в цикле начинается со второго элемента. При первом выполнении цикла (j = 2) А_max будет сравниваться с А₂. И если А₂ будет больше А_max, то меняем значение А_max, присваивая переменной А_max значение А₂. И продолжаем сравнение, теперь уже со следующим элементом.

Можно взять в качестве начального значения заведомо маленькое число. Тогда после выполнения первого цикла (j = 1) А_max будет равен А₁. Данный приём используется в циклах с простыми переменными.

Алгоритм вычисления будет состоять из следующих пунктов.

1. Ввод исходного массива А; j = 1, ..., 30.

2. Задание начального значения А_max = А₁.

3. Цикл. Задаются параметры цикла: начальное значение переменной цикла 2, конечное значение 30, шаг цикла 1.

4. Сравнение очередного j-го элемента А_j и А_max. Проверяется условие А_j > А_max? Если условие выполняется, переход к шагу 5, если нет, то - к шагу 6.

5. Присвоение А_max = А_j.

6. Конец цикла.

7. Печать максимального элемента массива А_max.

8. Конец.

Если надо найти минимальный элемент массива, то для выбора минимального элемента используется формула

и алгоритм выбора аналогичен рассмотренному выше.

В качестве начальных значений А_min может быть взято значение первого элемента массива, и поиск в цикле начнётся со второго элемента. Или заведомо большое число, которое больше любого элемента в исходном массиве, и поиск в цикле начнётся с первого элемента.

Задача. Для массива А, заданного в предыдущей задаче, найти минимальный элемент А_min и его порядковый номер j_min.

Решение. Особенностью задачи является то, что нужно найти не только минимальный элемент, но и его порядковый номер. Для решения данной задачи в алгоритм предыдущего примера нужно внести следующие изменения.

2. Задание начального значения А_min = А₁, j_min = 1.

4. Сравнение очередного элемента А_j и А_min. Если А_j меньше А_min, то переход к шагу 5, если больше - к шагу 6.

5. Присвоение А_min = А_j, j_min = j.

6. Конец цикла.

7. Печать номера минимального элемента j_min и значения минимального элемента А_min.

Так как цикл начнется со второго элемента массива, то первый элемент А₁ может оказаться минимальным. Поэтому в п. 2 задаётся начальное значение не только А_min = А₁, но и j_min = 1.

Структуры с вложенными циклами

Алгоритмы решения многих задач требуют нескольких циклов. Это:

• упорядочение массивов;
• обработка массивов;
• расчет таблицы значений функций, заданной степенным рядом.

В этих случаях важно правильно определить структуру алгоритма, прежде всего количество и взаимное расположение циклов. При этом необходимо определить, в каком цикле (внешнем или внутреннем) будет использоваться тот или иной приём алгоритмизации.

Например, вычисление суммы всех элементов матрицы. Здесь начальное значение суммы элементов нужно задать перед внешним циклом, а накапливать её во внутреннем цикле.

Если необходимо вычислить сумму элементов каждой строки матрицы, то начальное значение суммы нужно задать перед внутренним циклом, в котором перебираются и суммируются элементы одной строки матрицы. При этом внешним обязательно должен быть цикл, изменяющий номер строки, а внутренним - изменяющий номер столбца.

Задача. Задана матрица Х(N×М). Определить количество положительных элементов в каждой строке матрицы.

Решение. Матрица Х имеет размер N×М, т.е. в ней N строк и М столбцов. Вводить и печатать матрицу будем в общепринятом виде - по строкам. Вывод матрицы на печать необходим для получения результата в удобном для чтения виде.

Алгоритм.

1. Ввод матрицы Х(N, М), где i = 1, ..., N; j = 1, ..., М.

2. Печать исходной матрицы Х(N, М), где i = 1, N; j = 1, М.

3. Внешний цикл по строкам. Переменная цикла i изменяется от 1 до N, шаг 1.

4. Задание начального значения количества положительных элементов для каждой строки матрицы К = 0.

5. Внутренний цикл по столбцам. Параметр цикла j изменяется о 1 до М, шаг 1.

6. Проверка очередного элемента Х_ij на знак. Если Х_ij больше или равно нулю, то переход к шагу 7, иначе - к шагу 8.

7. Увеличение счетчика количества положительных элементов К на 1,

К = К + 1.

8. Конец внутреннего цикла.

9. Печать номера строки i и количества положительных элементов К.

10. Конец внешнего цикла.

11. Конец.

Заключение

В данной работе была сделана попытка систематизировать информацию по алгоритмизации: рассмотрены приемы и методы построения алгоритмов, изложены практически все основные алгоритмические конструкции, приведены примеры.

Разработка программ - это сложный процесс, она требует и знания систем программирования, владения технологией и сознательного использования парадигм программирования.

Важную роль при разработке программ занимает этап алгоритмизации - разработки алгоритма. Алгоритмизация - это раздел информатики, изучающий методы и приемы построений алгоритма, а также их свойства. Она является основным, базовым компонентом компьютерной грамотности в современном компьютерном мире.